8クイーン問題 Eight Queens Problem

8クイーン問題とは、8 × 8 のチェス版に、どのクイーンも他のクイーンを襲撃できないように、8 つのクイーンを配置する問題です。(※チェスでは、クイーンは以下のように襲撃することができます)

この問題を解くための最も素朴な方法が、8 つのクイーンを全ての組み合わせについて配置し、上記のコンディションを満たすかをチェックする方法です。つまり、8 × 8 = 64 のマスから、8 個選ぶ組み合わせなので、

₆₄C₈ = 4,426,165,368 通り

無論、この天文学的な数の組み合わせを全て調べることは現実的ではありません。まず、２つ以上のクイーンが同じ行には配置できないので、１行に１つのクイーンしか配置できないことを考えれば、

8⁸ = 16,777,216 通り

と大幅に組み合わせ数を少なくすることができます。さらに、２つ以上のクイーンが同じ列に配置できないことを考えれば、1 行目は 8 つの候補、2 行目は 7 つの候補、3 行目は 6 つの候補、、、8 行目は 1 つの候補、となるので、

8! = 40,320 通り

と導くことは容易です。

しかし、上記の組み合わせを全て調べるよりも、以下のようにバックトラッキングアルゴリズムを適用すれば、さらに効率的に 8 クイーン問題を解くことができます。

	1 行目の任意のコマに、クイーンを配置する
	１行目に配置したクイーンによって襲撃されない２行目のコマに、クイーンを配置する
	...
	全てのクイーンが他のどのクイーンも襲撃しないように、i 個のクイーンを最初の i 行に配置したとすれば、前の i 個のどのクイーンにも襲撃されない (i + 1) 行目のコマに、クイーンを配置する
	もしも、そのようなコマが (i + 1) 行目のコマに存在しなければ、i 行目に戻り i 行目に配置するクイーンのための他の襲撃されないコマを探し（もしそのようなコマがなければ、さらに (i - 1) 行目に戻る）、探索を続行します。

このアルゴリズムの実装では、コマ (i, j) が他のクイーンによって襲撃されているか否かを記録するために、以下の配列を用意します。

row[8]	row[x] が NOT_FREE ならば、row[x] は襲撃されている
col[8]	col[x] が NOT_FREE ならば、col[x] は襲撃されている
dpos[15]	dpos[x] が NOT_FREE ならば、dpos[x] は襲撃されている
dneg[15]	dnedg[x] が NOT_FREE ならば、dneg[x] は襲撃されている

つまり、row[i]、col[j]、dpos[i+j]、dneg[i-j+N-1] のいづれかが NOT_FREE であれば、コマ (i, j) が襲撃されていることになります。逆に考えれば、row[i]、col[j]、dpos[i+j]、dneg[i-j+n-1] すべてが FREE のとき、クイーンを配置することができます。各配列のインデック（i, j, i+j, i-j+N-1）の関係は下図を参照して下さい。

row: x = i	col: x = j

dpos: x = i + j	dneg: x = i - j + (N - 1)

// @author yutaka C++
// N queens problem: 全ての可能な配置と総数を出力
#include<iostream>
using namespace std;

#define N 8
#define FREE -1
#define NOT_FREE 1

int row[N], col[N], dpos[2*N-1], dneg[2*N-1];
int counter;

void initialize(){
    for ( int i = 0; i < N; i++ ){ row[i] = FREE, col[i] = FREE; }
    for ( int i = 0; i < 2*N - 1; i++ ) { dpos[i] = FREE; dneg[i] = FREE; }
}

void printBoard(){
    for ( int i = 0; i < N; i++ ){
        for ( int j = 0; j < N; j++ ){
            cout << (( row[i] == j ) ? "Q" : ".");
        }
        cout << endl;
    }
    cout << endl;
}

void recursive( int i ){
    if ( i == N ){ // SUCCESS
        counter++;
        printBoard(); return;
    }
    
    for ( int j = 0; j < N; j++ ){
        // if (i, j) is attacked by other queens, continue
        if ( col[j] == NOT_FREE || dpos[i+j] == NOT_FREE ||
        dneg[i-j+N-1] == NOT_FREE ) continue;
        // put a queen on (i, j)
        row[i] = j; col[j] = dpos[i+j] = dneg[i-j+N-1] = NOT_FREE;
        // try next row
        recursive( i + 1 );
        // remove the queen from (i, j)
        row[i] = col[j] = dpos[i+j] = dneg[i-j+N-1] = FREE;
    }
    
    // FAIL
}

main(){
    initialize();
    counter = 0;
    recursive( 0 );
    cout << counter << endl;
}