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

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

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

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

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

パズル？

面白そうじゃん！

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

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

Contents

エイトクイーン問題
- エイトクイーン問題とは
- N クイーン問題とは
エイトクイーン問題を総当たりで解くプログラム
- プログラム
- プログラムの解説
バックトラック法
- バックトラック法とは
- エイトクイーン問題におけるバックトラック法
エイトクイーン問題をバックトラック法で解くプログラム
- プログラム
- プログラムの解説
まとめ

エイトクイーン問題

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

エイトクイーン問題とは

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

クイーンってどんな駒？

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

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

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

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

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

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

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

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

そんなに？！

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

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

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

N クイーン問題とは

エイトクイーン問題が「８×８マスのチェス盤上に、他のクイーンの移動先にぶつからないように、８つのクイーンを配置する問題」であるのに対し、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：１方向のマスの数
 */
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：１方向のマスの数
 * 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：１方向のマスの数
 */
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：１方向のマスの数
 * 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：１方向のマスの数
 */
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);
}

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

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

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

time = 553.428553[s]

プログラムの解説

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

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

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

マス数とクイーンの数の定義

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

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

チェス盤の管理

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

二次元配列 board の１つ目の添字はチェス盤の各マスの行番号（0 〜 N – 1）を表し、２つ目の添字はチェス盤の各マスの列番号（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 が格納されているかどうか）、クイーンが配置されているマスを見つけた際にはそのマスの下記８方向に他のクイーンが存在するかどうかを判断します。

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

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

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

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

左：di = -1、dj = 0
右：di = 1、dj = 0
下：di = 0、dj = -1
上：di = 0、dj = 1
左下：di = -1、dj = -1
左上：di = -1、dj = 1
右下：di = 1、dj = -1
右上：di = 1、dj = 1

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

クイーンの配置

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

クイーンを配置する関数

void nQueen(int, int, int);

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

n（第１引数）：マスの数（＝最終的に配置するクイーンの数）
q（第２引数）：既に配置したクイーンの数
k（第３引数）：クイーンの配置位置の開始点

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

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

nQueen 関数の中で１つクイーンを配置してから nQueen 関数を第２引数に 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 関数ではチェス盤の各マス目を下図の青字のように１次元の数字の並びとして考えてクイーンの配置を行ないます。この数字が第３引数に登場する「配置位置」となります。

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

クイーン配置するループ

for (l = k; l < n * n; l++)

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

クイーンの配置

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

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

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

次のクイーンの配置

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

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

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

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

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

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

クイーンの取り除き

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

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

バックトラック法

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

バックトラック法とは

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

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

引用元：バックトラッキング（Wikipedia）

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

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

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

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

オーケー！

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

あっ…

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

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

今度は上手くいったね！

どんなもんだい！！

素晴らしい！

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

え？

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

プログラム

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

エイトクイーン問題（バックトラック法）

#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：１方向のマスの数
 */
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：１方向のマスの数
 * 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：１方向のマスの数
 */
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：１方向のマスの数
 * 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：１方向のマスの数
 */
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;

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

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