【C言語】エイトクイーン問題(Nクイーン問題)のバックラック法での解き方

エイトクイーン問題の解説ページアイキャッチ

このページにはプロモーションが含まれています

このページでは有名なパズルであるエイトクイーン問題(Nクイーン問題)を解くC言語プログラムの紹介を行なっていきます。

まずはエイトクイーン問題(Nクイーン問題)について解説を行い、続いてエイトクイーン問題(Nクイーン問題)を普通に総当たりでチェックを行って問題を解くプログラムを紹介します。

続いて度々「アルゴリズムとデータ構造」の参考書でも登場するバックトラック法を用いて解くプログラムの紹介を行っていきます。

パズル?

面白そうじゃん!

エイトクイーン問題はまさにパズルを解く感じで楽しくプログラミングできる良い問題だよ!

このページでは解法の1例のプログラムを載せてるけど、是非自分でもプログラミングしてみてね

エイトクイーン問題

まずはエイトクイーン問題およびその派生の問題である N クイーン問題について解説していきます。

エイトクイーン問題とは

エイトクイーン問題とは、チェスのクイーンを用いたパズルです。

クイーンってどんな駒?

クイーンは縦横斜めの方向に好きなだけ移動(他の駒にぶつからない限り)することのできる駒だよ

将棋の飛車と角を足し合わせた感じだね

クイーンの説明図

エイトクイーン問題は「8×8マスのチェス盤上に、他のクイーンの移動先にぶつからないように8つのクイーンを配置する問題」です。

例えば、下図のように1つクイーンを置いた状態では、このクイーンの移動先にぶつからないように2つ目のクイーン(オレンジ枠のクイーン)を配置します。

エイトクイーン問題の解き方1

さらに、2つのクイーンが置かれた状態では、この2つのクイーンの移動先にぶつからないように3つ目のクイーン(緑枠のクイーン)を配置します。

エイトクイーン問題の解き方2

このような感じで、他のクイーンの移動先にぶつからないように8つのクイーンを配置した結果が、エイトクイーン問題の1つの解となります。

下図はエイトクイーン問題の解の1例です。

エイトクイーン問題の解の例

ちなみにエイトクイーン問題での解の総パターンは92個あるよ

そんなに?!

全パターンを見つけ出すのはかなり大変だね…

人が自力で解こうとするとかなり時間はかかるね…

でもバックトラック法を用いてプログラミングすれば、ほぼ一瞬で見つけ出せるよ!

スポンサーリンク

N クイーン問題とは

エイトクイーン問題が「8×8マスのチェス盤上に、他のクイーンの移動先にぶつからないように、8つのクイーンを配置する問題」であるのに対し、N クイーン問題は「N × N マスのチェス盤上に、他のクイーンの移動先にぶつからないように、N つのクイーンを配置する問題」になります。

N を増やすほど解のパターン数が増える(例外もある)ので、問題を解くための時間や難易度が上がります。

エイトクイーン問題を総当たりで解くプログラム

次は、ここまで解説してきたエイトクイーン問題を解くプログラムを見ていきましょう。

プログラム

下記はクイーンの配置全パターンに対して、他のクイーンの移動先にぶつからないかを確認することで解の全パターンを求めるプログラムになります。

エイトクイーン問題(総当たり)
#include <stdio.h>
#include <time.h>

/* チェスの盤の縦横サイズ */
#define N 8

/* クイーンがあることを示す定数 */
#define QUEEN 1

/* クイーンがないことを示す定数 */
#define EMPTY 0

#define OK 1
#define NG 0

void printQueen(int);
int check(int, int, int, int, int);
int checkQueen(int);
void nQueen(int, int, int);
void initQueen(int);

/* チェスの盤 */
int board[N][N];

/* 見つけた解の数 */
int resolve = 0;

/**
 * チェス盤の表示
 * n:1方向のマスの数
 */
void printQueen(int n)
{
    int i, j;

    printf("%d個目の解\n", resolve);

    /* 全マスを表示 */
    for (j = 0; j < n; j++)
    {
        for (i = 0; i < n; i++)
        {
            if (board[j][i] == QUEEN)
            {
                /* (i, j)マスにクイーンがある場合 */
                printf("Q");
            }
            else
            {
                /* (i, j)マスにクイーンが無い場合 */
                printf("*");
            }
        }
        printf("\n");
    }
    printf("\n\n");
}

/**
 * 指定された方向に他のクイーンが無いかどうかを判断
 * n:1方向のマスの数
 * i:クイーンの位置の列番号
 * j:クイーンの位置の行番号
 * di:列番号の増加量
 * dj:行番号の増加量
 */
int check(int n, int i, int j, int di, int dj)
{
    int k;
    int ii, jj;

    for (k = 1; k < n; k++)
    {
        /* (di, dj)方向にkマスを進める */
        ii = i + di * k;
        jj = j + dj * k;
        if (ii >= n || ii < 0 || jj >= n || jj < 0)
        {
            /* 盤外までチェックしたらその方向にクイーンはない */
            break;
        }

        if (board[j + dj * k][i + di * k] == QUEEN)
        {
            /* マス上にクイーンがあればNGを返却 */
            return NG;
        }
    }

    /* その方向にクイーンが無いのでOKを返却 */
    return OK;
}

/**
 * Nクイーン問題を満たしているかどうかを判断
 * n:1方向のマスの数
 */
int checkQueen(int n)
{
    int i, j;

    /* クイーンがあるマスを探索 */
    for (j = 0; j < n; j++)
    {
        for (i = 0; i < n; i++)
        {
            if (board[j][i] == QUEEN)
            {
                /* クイーンのあるマスから縦横斜め方向にクイーンがあるかどうかをチェック */

                /* 左方向をチェック */
                if (!check(n, i, j, -1, 0))
                {
                    return NG;
                }
                /* 右方向をチェック */
                if (!check(n, i, j, 1, 0))
                {
                    return NG;
                }
                /* 下方向をチェック */
                if (!check(n, i, j, 0, -1))
                {
                    return NG;
                }
                /* 上方向をチェック */
                if (!check(n, i, j, 0, 1))
                {
                    return NG;
                }
                /* 左下方向をチェック */
                if (!check(n, i, j, -1, -1))
                {
                    return NG;
                }
                /* 左上方向をチェック */
                if (!check(n, i, j, -1, 1))
                {
                    return NG;
                }
                /* 右下方向をチェック */
                if (!check(n, i, j, 1, -1))
                {
                    return NG;
                }
                /* 右上方向をチェック */
                if (!check(n, i, j, 1, 1))
                {
                    return NG;
                }
            }
        }
    }

    return OK;
}

/**
 * クイーンの設置
 * n:1方向のマスの数
 * q:配置済みのクイーンの数
 * k:配置開始
 */
void nQueen(int n, int q, int k)
{
    int i, j;
    int l;

    if (q == n)
    {
        /* n個クイーン設置ずみの場合 */

        if (checkQueen(n))
        {
            /* Nクイーン問題を満たしている場合 */

            /* 解の数をインクリメント */
            resolve++;

            /* チェス盤を表示 */
            printQueen(n);
        }
        return;
    }

    /* 配置位置の開始点から順にクイーンを配置していく */
    for (l = k; l < n * n; l++)
    {
        /* 配置位置より行番号と列番号を算出 */
        j = l / n;
        i = l % n;

        /* (i, j)マスにクイーンを置く */
        board[j][i] = QUEEN;

        /* 次のクイーンを置く */
        nQueen(n, q + 1, l + 1);
        
        /* (i, j)マスからクイーンを取り除く */
        board[j][i] = EMPTY;
    }
}

/**
 * チェス盤の初期化
 * n:1方向のマスの数
 */
void initQueen(int n)
{
    int i, j;
    for (j = 0; j < n; j++)
    {
        for (i = 0; i < n; i++)
        {
            /* マスを空にする */
            board[j][i] = EMPTY;
        }
    }
}

int main(void)
{
    clock_t start, end;

    /* チェス盤の初期化 */
    initQueen(N);

    start = clock();

    /* Nクイーン問題を解く */
    nQueen(N, 0, 0);

    end = clock();

    /* 処理時間を表示 */
    printf("time = %f[s]", (double)(end - start) / CLOCKS_PER_SEC);
}

マス数8×8のチェス盤上の8つの箇所にクイーンを配置する組み合わせは「4426165368」パターンになります。

上記プログラムではこの「4426165368」パターンのクイーンの置き方全てに対して、エイトクイーン問題を満たしているかどうか(他のクイーンの移動先にぶつかっていないかどうか)を確認しています。

私の PC でエイトクイーン問題の全ての解(92パターン)を求めるのに要した処理時間は下記のように、約9分程度かかりまました。

time = 553.428553[s]

スポンサーリンク

スポンサーリンク

プログラムの解説

簡単にプログラムの解説も行なっておきます。

チェス盤のマス数・クイーンの数

チェス盤のマス数と配置するクイーンの数は下記で定数 N として定義しています。

マス数とクイーンの数の定義
/* チェスの盤の縦横サイズ */
#define N 8

この N を変更すれば、ナインクイーン問題やテンクイーン問題を解くこともできます。つまり、このプログラムは実は N クイーン問題を解くプログラムになります。

チェス盤の管理

チェス盤上のどこにクイーンが配置されたかは二次元配列 board により管理しています。

二次元配列 board の1つ目の添字はチェス盤の各マスの行番号(0 〜 N – 1)を表し、2つ目の添字はチェス盤の各マスの列番号 (0 〜 N – 1)を表しています。

クイーン配置位置の管理

さらに、二次元配列 board に格納される値はクイーンが配置されているかどうかの情報となります。クイーンがそのマスに配置されている場合は QUEEN を、配置されていない場合は EMTPY を格納することでチェス盤上のクイーンの位置を管理します。

例えばチェス盤に上図のようにクイーンが配置されている場合、board[2][0]board[6][2]board[5][7]QUEEN が格納され、他には EMPTY が格納されることになります。

二次元配列 board の全ての要素にはプログラム開始時に initQueen 関数により EMPTY を格納しています。

エイトクイーン問題を満たしているかどうかの確認

checkQueen 関数は二次元配列 board で表されるチェス盤上の各クイーンが他のクイーンの移動先にぶつかっていないかどうかを判断する関数です。

ぶつかっていない場合は OK を、ぶつかっている場合は NG を返却します。

checkQueen 関数は、まず各マスにクイーンが配置されているかどうかを確認し(board[j][i]QUEEN が格納されているかどうか)、クイーンが配置されているマスを見つけた際にはそのマスの下記8方向に他のクイーンが存在するかどうかを判断します。

  • 左下
  • 左上
  • 右下
  • 右上

各方向にクイーンが存在するかどうかの判断には check 関数を用いてます。

check 関数は引数 ij で指定されたマスの位置から、引数 didj で指定される方向にマスを1つずつ移動させながらクイーンが存在するかどうかを判断する関数です。

上記の8方向に対してクイーンの存在の判断を行うためには引数 didj にそれぞれ下記を指定します。

  • 左:di = -1dj = 0
  • 右:di = 1dj = 0
  • 下:di = 0dj = -1
  • 上:di = 0dj = 1
  • 左下:di = -1dj = -1
  • 左上:di = -1dj = 1
  • 右下:di = 1dj = -1
  • 右上:di = 1dj = 1

例えば di = 1dj = -1 とした場合は下図のように行番号と列番号がそれぞれ + 1、 -1 しながらクイーンが存在するかどうかの判断を行います。

ある方向にクイーンがあるかどうかを判断する様子

クイーンの配置

クイーンの配置は nQueen 関数により実施しています。

クイーンを配置する関数
void nQueen(int, int, int);

nQueen 関数の各引数は下記のようになります。

  • n(第1引数):マスの数(=最終的に配置するクイーンの数)
  • q(第2引数):既に配置したクイーンの数
  • k(第3引数):クイーンの配置位置の開始点

1度の nQueen 関数の呼び出しで配置するクイーンの数は1つです。さらに、nQueen 関数の中で nQueen 関数を再帰呼び出しすることでどんどんクイーンを配置していきます(配置については後述します)。

この配置済みのクイーン数を表すのが第2引数の q です。

nQueen 関数の中で1つクイーンを配置してから nQueen 関数を第2引数に q+1 を指定して再帰呼び出しすることで配置済みクイーンの数を管理します。

配置済みクイーン数の増加
/* 次のクイーンを置く */
nQueen(n, q + 1, l + 1);

この配置済みのクイーン数 q が最終的に配置するクイーンの数 n と一致した際には、checkQueen 関数で、その時点のチェス盤のクイーンがエイトクイーン問題を満たしているかどうかを判断します。

全てクイーンを配置した際の処理
if (q == n)
{
    /* n個クイーン設置ずみの場合 */

    if (checkQueen(n))
    {
        /* Nクイーン問題を満たしている場合 */

        /* 解の数をインクリメント */
        resolve++;

        /* チェス盤を表示 */
        printQueen(n);
    }
    return;
}

満たしている場合はそのチェス盤を printQueen で表示しています。

次は、肝心の nQueen 関数でのクイーンの配置について解説していきます。

nQueen 関数ではチェス盤の各マス目を下図の青字のように1次元の数字の並びとして考えてクイーンの配置を行ないます。この数字が第3引数に登場する「配置位置」となります。

配置位置の説明図

nQueen 関数では、この配置位置を小さい方から大きい方に移動させながらクイーンを配置していきます。つまり、下記のようなループの中でクイーンの配置を行います(k は第3引数で与えられる配置位置の開始点)。

クイーン配置するループ
for (l = k; l < n * n; l++)

そしてループの中で二次元配列 boardQUEEN を格納し、

クイーンの配置
/* 配置位置より行番号と列番号を算出 */
j = l / n;
i = l % n;

/* (i, j)マスにクイーンを置く */
board[j][i] = QUEEN;

さらに下記により nQueen 関数を再帰呼び出しすることで次のクイーンの配置を行います。

次のクイーンの配置
/* 次のクイーンを置く */
nQueen(n, q + 1, l + 1);

ポイントは再帰呼び出し時に指定する nQueen 関数の第3引数です。この第3引数には直前にクイーンを配置した配置位置に +1 した数字を指定します。

これは、既にチェック済みのクイーンの配置パターンを重複してチェックしないためです。

逆に配置位置開始点を考慮せずに配置を行なっていくと、同じパターンを重複してチェックすることになるため、解となるパターンの数が多くなってしまう・処理時間が余計に必要になるので注意してください。

nQueen 関数の再帰呼び出しが完了した場合、その階層までに配置したクイーンを含む配置パターン全てのチェックが完了したことになります。

ですので、一旦置いたクイーンを取り除き、次の配置位置にクイーンを置いて同様の処理を繰り返していきます。

クイーンの取り除き
/* (i, j)マスからクイーンを取り除く */
board[j][i] = EMPTY;

これらの処理を全パターンチェックし終わるまでループ&再帰処理を繰り返しています。

バックトラック法

続いてバックトラック法について解説していきます。このアルゴリズムを用いることで、エイトクイーン等の問題を解く時にチェックすべきパターン数を極端に削減することができます。

バックトラック法とは

バックトラック法は Wikipedia において下記のような方法で解を導き出す手法と解説されています。

探索の際、ある組み合わせが解でなかったなら、探索木をたどって戻り別の組み合わせを試す。その組み合わせを試しても解でなかった場合、さらに探索木を戻り、新たな組み合わせを試す。

引用元:バックトラッキング(Wikipedia)

これだけ見ると「?」と思うかもしれませんが、バックトラック法は非常に直感的に理解しやすいアルゴリズムです。

なぜなら、バックトラック法はエイトクイーン問題などを解く際に人間が直感的に行う思考と似ているからです。他にも迷路を解く時にもバックトラック法を自然に利用しています。

これを理解するために実際にエイトクイーン問題を自力で解いてみましょう!

じゃあ実際にエイトクイーン問題の解を導き出してみてくれる?

オーケー!

とりあえず問題なく配置できそうな場所にてきとうにクイーンを配置していって…

バックトラック法の解説1

あっ…
そこに置くと他のクイーンの移動先にぶつかっちゃうね…

バックトラック法の解説2

うーん、じゃあ一手戻してもう一度配置して直してみる!

バックトラック法の解説3

 

今度は上手くいったね!

どんなもんだい!!

素晴らしい!

そして、君はしっかりバックトラック法を実践してるね!

え?

まさにここで実践した解き方がバックトラック法です。

途中で他のクイーンの移動先にぶつかると分かった時、つまり「この組み合わせが解であり得ない」と分かった時に、一手戻して他の組み合わせを試しました。

おそらくほとんどの方がエイトクイーンを自力で解く場合にこの方法を用いると思います。

これこそがバックトラック法です。

つまり、「どんどん手を進めて組み合わせを作成していき、途中でその組み合わせが解になり得ないと分かった時に、手を戻して別の組み合わせを作成する」のがバックトラック法です。

スポンサーリンク

エイトクイーン問題におけるバックトラック法

エイトクイーン問題におけるバックトラック法をもう少し詳しく見ていきましょう。

例えばエイトクイーン問題を8×8マスに8つのクイーンを置くパターン全てに対してエイトクイーンの解になり得るかをチェックする場合、下図のようなクイーンの配置パターンもチェックする必要があります。

バックトラック法の解説4

でもこれって、8つクイーンを置かなくても2つクイーンを置いた時点で解になり得ないことが分かりますよね?

バックトラック法の解説4

つまり、この2つのクイーンを置いた状態のパターンをチェックするのは無駄です。

バックトラック法では、この解になり得ないことが分かった時点で、そのクイーンの配置の組み合わせを含むパターンのチェックを止めます。

バックトラック法の解説5

これにより、このクイーンの配置の組み合わせを含むパターンのチェックを省略することができます。

そして、直前においたクイーンを取り除き、別の場所に新たにクイーンを置き、その時点でエイトクイーン問題の解になり得るかどうかを判断します(半透明のクイーンを置いたとしても解になり得ない)。

バックトラック法の解説6

解になり得る場合のみ、そのクイーンの配置に対して新たなクイーンを追加で配置します。

バックトラック法の解説7

こんな感じで、ある時点でのクイーンの配置の組み合わせが解になり得るかどうかを判断し、解になり得ない場合は一手戻して別の組み合わせを試していくことで、多くのパターンのチェックを省略することができます。

これがエイトクイーン問題におけるバックトラック法による解き方になります。

エイトクイーン問題をバックトラック法で解くプログラム

それではエイトクイーン問題をバックトラック法で解くプログラムを実際に紹介していきます。

プログラム

エイトクイーン問題をバックトラック法で解くプログラムは下記のようになります。

エイトクイーン問題(バックトラック法)
#include <stdio.h>
#include <time.h>

/* チェスの盤の縦横サイズ */
#define N 8

/* クイーンがあることを示す定数 */
#define QUEEN 1

/* クイーンがないことを示す定数 */
#define EMPTY 0

#define OK 1
#define NG 0

void printQueen(int);
int check(int, int, int, int, int);
int checkQueen(int);
void nQueen(int, int, int);
void initQueen(int);

/* チェスの盤 */
int board[N][N];

/* 見つけた解の数 */
int resolve = 0;

/**
 * チェス盤の表示
 * n:1方向のマスの数
 */
void printQueen(int n)
{
    int i, j;

    printf("%d個目の解\n", resolve);

    /* 全マスを表示 */
    for (j = 0; j < n; j++)
    {
        for (i = 0; i < n; i++)
        {
            if (board[j][i] == QUEEN)
            {
                /* (i, j)マスにクイーンがある場合 */
                printf("Q");
            }
            else
            {
                /* (i, j)マスにクイーンが無い場合 */
                printf("*");
            }
        }
        printf("\n");
    }
    printf("\n\n");
}

/**
 * 指定された方向に他のクイーンが無いかどうかを判断
 * n:1方向のマスの数
 * i:クイーンの位置の列番号
 * j:クイーンの位置の行番号
 * di:列番号の増加量
 * dj:行番号の増加量
 */
int check(int n, int i, int j, int di, int dj)
{
    int k;
    int ii, jj;

    for (k = 1; k < n; k++)
    {
        /* (di, dj)方向にkマスを進める */
        ii = i + di * k;
        jj = j + dj * k;
        if (ii >= n || ii < 0 || jj >= n || jj < 0)
        {
            /* 盤外までチェックしたらその方向にクイーンはない */
            break;
        }

        if (board[j + dj * k][i + di * k] == QUEEN)
        {
            /* マス上にクイーンがあればNGを返却 */
            return NG;
        }
    }

    /* その方向にクイーンが無いのでOKを返却 */
    return OK;
}

/**
 * Nクイーン問題を満たしているかどうかを判断
 * n:1方向のマスの数
 */
int checkQueen(int n)
{
    int i, j, k;
    int ret;

    /* クイーンがあるマスを探索 */
    for (j = 0; j < n; j++)
    {
        for (i = 0; i < n; i++)
        {
            if (board[j][i] == QUEEN)
            {
                /* クイーンのあるマスから縦横斜め方向にクイーンがあるかどうかをチェック */

                /* 左方向をチェック */
                if (!check(n, i, j, -1, 0))
                {
                    return NG;
                }
                /* 右方向をチェック */
                if (!check(n, i, j, 1, 0))
                {
                    return NG;
                }
                /* 下方向をチェック */
                if (!check(n, i, j, 0, -1))
                {
                    return NG;
                }
                /* 上方向をチェック */
                if (!check(n, i, j, 0, 1))
                {
                    return NG;
                }
                /* 左下方向をチェック */
                if (!check(n, i, j, -1, -1))
                {
                    return NG;
                }
                /* 左上方向をチェック */
                if (!check(n, i, j, -1, 1))
                {
                    return NG;
                }
                /* 右下方向をチェック */
                if (!check(n, i, j, 1, -1))
                {
                    return NG;
                }
                /* 右上方向をチェック */
                if (!check(n, i, j, 1, 1))
                {
                    return NG;
                }
            }
        }
    }

    return OK;
}

/**
 * クイーンの設置
 * n:1方向のマスの数
 * q:配置済みのクイーンの数
 * k:配置開始
 */
void nQueen(int n, int q, int k)
{
    int i, j;
    int l;

    if (q == n)
    {
        /* n個クイーン設置ずみの場合 */

        if (checkQueen(n))
        {
            /* Nクイーン問題を満たしている場合 */

            /* 解の数をインクリメント */
            resolve++;

            /* チェス盤を表示 */
            printQueen(n);
        }
        return;
    }

    /* 配置位置の開始点から順にクイーンを配置していく */
    for (l = k; l < n * n; l++)
    {
        /* 配置位置より行番号と列番号を算出 */
        j = l / n;
        i = l % n;

        /* (i, j)マスにクイーンを置く */
        board[j][i] = QUEEN;

        if (checkQueen(n))
        {
            /* クイーンを置いてもまだNクイーン問題を満たしている場合 */

            /* 次のクイーンを置く */
            nQueen(n, q + 1, l + 1);
        }
        /* (i, j)マスからクイーンを取り除く */
        board[j][i] = EMPTY;
    }
}

/**
 * チェス盤の初期化
 * n:1方向のマスの数
 */
void initQueen(int n)
{
    int i, j;
    for (j = 0; j < n; j++)
    {
        for (i = 0; i < n; i++)
        {
            /* マスを空にする */
            board[j][i] = EMPTY;
        }
    }
}

int main(void)
{
    clock_t start, end;

    /* チェス盤の初期化 */
    initQueen(N);

    start = clock();

    /* Nクイーン問題を解く */
    nQueen(N, 0, 0);

    end = clock();

    /* 処理時間を表示 */
    printf("time = %f[s]", (double)(end - start) / CLOCKS_PER_SEC);
}

処理時間は下記のようになりました。エイトクイーン問題を総当たりで解くプログラムで示したプログラムの処理時間と比較すると、その差は歴然だと思います。

time = 0.662611[s]

この処理時間の差の分、チェックしたパターン数が削減できていることになります。

こんな感じでアルゴリズムを少し工夫するだけで、処理時間を大幅に削減することができます。アルゴリズムって重要でしょ?

スポンサーリンク

スポンサーリンク

プログラムの解説

エイトクイーン問題を総当たりで解くプログラムで示したプログラムとの違いは nQueen 関数の下記部分になります。

バックトラック処理
/* (i, j)マスにクイーンを置く */
board[j][i] = QUEEN;

if (checkQueen(n))
{
    /* クイーンを置いてもまだNクイーン問題を満たしている場合 */

    /* 次のクイーンを置く */
    nQueen(n, q + 1, l + 1);
}
/* (i, j)マスからクイーンを取り除く */
board[j][i] = EMPTY;

クイーンを配置してみて、配置した時点でエイトクイーン問題の解になり得ないと分かった場合には、それ以上クイーンを配置するのを止め、一手戻して(置いたクイーンを取り除いて)、新たな場所にクイーンを配置するようにしています。

違いはこれだけです。これだけでプログラムの処理時間を大幅に削減できていることが確認できると思います。

まとめ

このページではエイトクイーン(N クイーン)問題およびその解き方およびそのプログラムについて解説しました。

プログラムとしては、クイーンの配置全パターンを総当たりで調べる方法でエイトクイーン問題を解くものと、続いてバックトラック法で解くプもの2つを紹介しています。

エイトクイーン問題はパズル感覚で楽しくプログラミングできる題材です。さらに、アルゴリズムを変更することにより処理時間を大幅に削減することができますので、アルゴリズムの重要性を実感することもできます。

今回示したプログラムはエイトクイーン問題を解くための1例になります。他にもエイトクイーン問題を解くプログラムには様々なものが考えられますので、是非ご自身でもプログラミングしてみてください!

エイトクイーン問題同様にチェス盤を利用したパズルである「ナイト巡回問題」の解説ページも下記に用意しておりますので、是非こちらも併せてお読みください。

ナイト巡回問題解説ページのアイキャッチ 【C言語】ナイト巡回問題(ナイトツアー)のバックラック法での解き方

同じカテゴリのページ一覧を表示

5 COMMENTS

Kちゃん

アルゴリズムの問題解説、勉強しているので参考になります。
ありがとうございます。
コード中にあるint ret;の変数は誤植かと思います。

daeu

Kちゃん

いつもコメントありがとうございます!
ご指摘の通り、確かに不要でした。
いつも指摘していただいて申し訳ない&本当にありがとうございます。

コンパイル時に警告出すようにしてみましたので、
今後は使用してない変数のないソースコードをアップできると思います!

また何かありましたらコメントいただけると幸いです。

Kちゃん

VSCodeの拡張機能「C/C++ Advanced Lint」を使うと、リアルタイムでいろいろと警告してもらえるのでおすすめです。
ただ、私は細かい設定ができないので持て余している感があります。
よかったらでよいのですが、デバッグの記事みたいにこちらの拡張機能も解説してもらえると嬉しいです。

daeu

Kちゃん

情報ありがとうございます!
拡張機能使うのはアリですね!まずは試してみます!

daeu

Kちゃん

「C/C++ Advanced Lint」使ってみました!
静的解析が自動的に動作してくれていい感じです。

設定項目はたくさんありますが、そこまで必要な設定はないと思います。
(既に導入済みかもしれませんが)CppCheck 入れておくと
メモリリークも発見してくてるのでオススメです!

現在コメントは受け付けておりません。