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

この問題を解くための最も素朴な方法が、8 つのクイーンを全ての組み合わせについて配置し、上記のコンディションを満たすかをチェックする方法です。つまり、8 × 8 = 64 のマスから、8 個選ぶ組み合わせなので、
無論、この天文学的な数の組み合わせを全て調べることは現実的ではありません。まず、2つ以上のクイーンが同じ行には配置できないので、1行に1つのクイーンしか配置できないことを考えれば、
と大幅に組み合わせ数を少なくすることができます。さらに、2つ以上のクイーンが同じ列に配置できないことを考えれば、1 行目は 8 つの候補、2 行目は 7 つの候補、3 行目は 6 つの候補、、、8 行目は 1 つの候補、となるので、
と導くことは容易です。
しかし、上記の組み合わせを全て調べるよりも、以下のようにバックトラッキングアルゴリズムを適用すれば、さらに効率的に 8 クイーン問題を解くことができます。
1 行目の任意のコマに、クイーンを配置する | |
1行目に配置したクイーンによって襲撃されない2行目のコマに、クイーンを配置する | |
... | |
全てのクイーンが他のどのクイーンも襲撃しないように、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; }
| コメント(0) | トラックバック(0) | ↑ページトップ |