N Queens Problem は「8 クイーン」の拡張バージョンで、N 行 N 列の盤面に N 個のクイーンを互いの利き筋が重ならないように配置する問題です。クイーンは将棋の飛車と角をあわせた駒で、縦横斜めに任意に動くことができます。8 クイーンの解答例を示しましょう。
┌─┬─┬─┬─┬─┬─┬─┬─┐
│Ｑ│ │ │ │ │ │ │ │
├─┼─┼─┼─┼─┼─┼─┼─┤
│ │ │ │ │Ｑ│ │ │ │
├─┼─┼─┼─┼─┼─┼─┼─┤
│ │ │ │ │ │ │ │Ｑ│
├─┼─┼─┼─┼─┼─┼─┼─┤
│ │ │ │ │ │Ｑ│ │ │
├─┼─┼─┼─┼─┼─┼─┼─┤
│ │ │Ｑ│ │ │ │ │ │
├─┼─┼─┼─┼─┼─┼─┼─┤
│ │ │ │ │ │ │Ｑ│ │
├─┼─┼─┼─┼─┼─┼─┼─┤
│ │Ｑ│ │ │ │ │ │ │
├─┼─┼─┼─┼─┼─┼─┼─┤
│ │ │ │Ｑ│ │ │ │ │
└─┴─┴─┴─┴─┴─┴─┴─┘
図：8 クイーンの解答例
高橋謙一郎さん の プログラミングパズル雑談コーナー に N Queens Problem の話題がありました。それに触発されて、M.Hiroi も N Queens Problem に挑戦してみました。なお、このドキュメントは拙作のページ Memorandum で取り上げた N Queens Problem をまとめたものです。内容は重複していますが、ご了承くださいませ。
8 クイーンは拙作の Ｃ言語講座 第 6 回 で取り上げたことがあります。このプログラムを N Queens Problem に対応させると、次のようになります。
リスト：N Queens Problem の解法（その１）
#include <stdio.h>
#include <time.h>
#define MAXSIZE 16
#define TRUE 1
#define FALSE 0
#define FREE 0
#define USE 1
int position[MAXSIZE];
int usedata[MAXSIZE];
int size;
int count;
/* 斜めの利き筋をチェックする */
int conflict( int i, int n )
{
int j;
for( j = 0; j < n; j++ ){
if( ((position[j] - j ) == (i - n)) ||
((position[j] + j ) == (i + n)) ){
return FALSE;
}
}
return TRUE;
}
/* 解法 */
void queen( int n )
{
int i;
if( n == size ){
count++;
} else {
for( i = 0; i < size; i++ ){
if( usedata[i] == FREE && conflict( i, n ) ){
position[n] = i; /* データセット */
usedata[i] = USE;
queen( n + 1 ); /* 再帰する */
usedata[i] = FREE;
}
}
}
}
int main()
{
int i, start;
for( size = 10; size <= 14; size++ ){
/* データの初期化 */
for( i = 0; i < size; i++ ){
usedata[i] = FREE;
}
count = 0;
start = clock();
queen( 0 );
printf("%d --> %d, 時間 %d\n", size, count, clock() - start );
}
return 0;
}
このプログラムでは、対称解のチェックは行わずに解の個数だけを求めています。また、一番左端の列 (0 列) のクイーンの位置を、0 から size / 2 までに限定するともっと速くなりますが、今回は単純に深さ優先探索で求めています。
このプログラムは、クイーンの個数が増えると実行時間が極端に遅くなります。これは、斜めの利き筋をチェックする関数 conflict と、異なる数字（クイーンの位置）を選ぶために行う配列 usedata のチェック処理に時間がかかるからです。そこで、藤原博文さん の ８クイーン＠勉強会のページ を参考にプログラムを改良してみましょう。
まず、usedata のチェックですが、配列 board に数字をひとつずつ入れておいて、選んだ数字と未使用の数字を交換していくことで改良することができます。n 列目のクイーンを選ぶ場合、確定済みのクイーンは board の 0 から n - 1 までに格納されていて、残りの n から size - 1 までが未使用のクイーンになります。これで未使用のクイーンを簡単に選ぶことができます。
次は斜めの利き筋のチェックです。実は、これも簡単な方法で高速化できます。次の図を見てください。
右斜め上の利き筋 左斜め上の利き筋
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
*-----------------* *-----------------*
|／／／／／／／／ | 8 -1 |＼＼＼＼＼＼＼＼ |
|／／／／／／／／ | 9 -2 |＼＼＼＼＼＼＼＼ |
|／／／／／／／／ | 10 -3 |＼＼＼＼＼＼＼＼ |
|／／／／／／／／ | 11 -4 |＼＼＼＼＼＼＼＼ |
|／／／／／／／／ | 12 -5 |＼＼＼＼＼＼＼＼ |
|／／／／／／／／ | 13 -6 |＼＼＼＼＼＼＼＼ |
|／／／／／／／／ | 14 -7 |＼＼＼＼＼＼＼＼ |
|／／／／／／／／ | |＼＼＼＼＼＼＼＼ |
*-----------------* *-----------------*
x + y = constant x - y = constant
図：斜めの利き筋のチェック
斜めの利き筋は、行と列の位置を足す、または行から列を引くと一定の値になることを利用してチェックしています。conflict は確定済みのクイーンと衝突していないかひとつずつチェックしていますが、斜めの利き筋を配列にセットしておけば、もっと簡単にチェックすることができます。
右斜め上の利き筋を r_used, 左斜め上の利き筋を l_used で表すことにすると、(x, y) にクイーンを置いた場合は次のようにセットします。
r_used[x + y] = l_used[x - y + size - 1] = TRUE;
バックトラックするときはリセットすることをお忘れなく。プログラムは次のようになります。
リスト：N Queens Problem の解法（その２）
#include <stdio.h>
#include <time.h>
#define MAXSIZE 16
#define TRUE 1
#define FALSE 0
int board[MAXSIZE];
int r_used[MAXSIZE * 2 - 1];
int l_used[MAXSIZE * 2 - 1];
int size;
int count;
/* 解法 */
void queen( int n )
{
int i;
if( n == size ){
count++;
} else {
for( i = n; i < size; i++ ){
int m = board[i];
/* 斜めの利き筋をチェック */
if( r_used[m + n] || l_used[m - n + size - 1] ) continue;
r_used[m + n] = l_used[m - n + size - 1] = TRUE;
/* 未使用の数字（クイーン）と交換する */
board[i] = board[n];
board[n] = m;
/* 再帰する */
queen( n + 1 );
/* 元に戻す */
r_used[m + n] = l_used[m - n + size - 1] = FALSE;
board[n] = board[i];
board[i] = m;
}
}
}
int main()
{
int i, start;
for( size = 10; size <= 14; size++ ){
/* データの初期化 */
for( i = 0; i < size; i++ ){
board[i] = i;
}
for( i = 0; i < size * 2 - 1; i++ ){
r_used[i] = l_used[i] = FALSE;
}
count = 0;
start = clock();
queen( 0 );
printf("%d --> %d, 時間 %d\n", size, count, clock() - start );
}
return 0;
}
プログラムは、とくに難しいところはないので、説明は省略いたします。リストをお読みくださいませ。
それでは、実際に試してみましょう。プログラムは Borland C++ 5.5.1 for Win32 でコンパイルし、M.Hiroi のオンボロマシン (Windows95, Pentium 166 MHz) で実行しました。結果は次のようになりました。
| 11 | 12 | 13 | 14 | |
|---|---|---|---|---|
| 解(個数) | 2680 | 14200 | 73712 | 365596 |
| その１ | 0.5 | 2.3 | 11.4 | 72.7 |
| その２ | 0.1 | 0.8 | 3.1 | 16.9 |
改良の効果は十分に出ていますね。ちなみに、斜めの利き筋のチェックを次のように変更すると、ほんの少しですが速くなります。
if( r_used[m + n] | l_used[m - n + size - 1] ) continue;
r_used と l_used の OR を計算して、その結果が真であれば利き筋であると判断できます。結果は size = 14 で 16.0 秒になりました。だたし、使用されているコンパイラによっては、この程度のことは最適化されているかもしれません。今回の結果は M.Hiroi のコーディング、実行したマシン、コンパイラなどの環境に大きく依存しています。興味のある方は、ご自分の環境で試してみてください。
次は M.Hiroi が作成したプログラムを紹介します。基本的な考え方は、「列ごとにクイーンを置ける位置 (free position) を管理して、クイーンを置けない列が生じた時点で枝刈りを行う」というものです。この場合、free position はビットを使って管理した方が簡単です。ビットオンの位置にはクイーンを置けることにすると、値が 0 になった時点で、クイーンはその列に置けないことがわかります。
プログラムは次のようになります。
リスト：N Queens Problem の解法（その３）
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define TRUE 1
#define FALSE 0
#define MAX_SIZE 16
unsigned int biton[MAX_SIZE];
unsigned int bitoff[MAX_SIZE];
int board[MAX_SIZE];
int size;
int count;
/* n 列の m 番目にクイーンを置いた場合 */
int update_free_position( int n, int m,
unsigned int *free_position,
unsigned int *new_free_position )
{
int i, l, h;
/* n + 1 から size - 1 までの free_position を更新 */
for( i = n + 1, l = m - 1, h = m + 1; i < size; i++, l--, h++ ){
int position = free_position[i];
position &= bitoff[m];
if( l >= 0 ) position &= bitoff[l];
if( h < size ) position &= bitoff[h];
if( !position ) return FALSE; /* 置ける場所が無い */
new_free_position[i] = position;
}
return TRUE;
}
void queen( int n, unsigned int *free_position )
{
unsigned int new_free_position[MAX_SIZE];
int i, j;
if( n == size ){
count++;
} else {
for( i = n; i < size; i++ ){
/* n 列目の位置に board[i] を選ぶ */
j = board[i];
if( !(free_position[n] & biton[j]) ) continue;
if( !update_free_position( n, j, free_position, new_free_position ) ) continue;
board[i] = board[n];
board[n] = j;
queen( n + 1, new_free_position );
/* 元に戻す */
board[n] = board[i];
board[i] = j;
}
}
}
int main()
{
unsigned int free_position[MAX_SIZE];
int i, j, start;
/* 初期化 */
size = 11;
for( i = 0, j = 1; i < MAX_SIZE; i++, j *= 2 ){
biton[i] = j;
bitoff[i] = ~j;
}
for( size = 10; size <= 14; size++ ){
for( i = 0; i < size; i++ ){
board[i] = i;
free_position[i] = (1 << size) - 1;
}
start = clock();
count = 0;
queen( 0, free_position );
printf("Queen = %d, 総数 %d, 時間 %d\n", size, count, clock() - start );
printf("\n");
}
return 0;
}
クイーンの free position を管理する配列が free_position です。バックトラックするときに元の値に戻していては時間がかかるので、グローバル変数ではなく局所変数として定義します。
free_position を更新する関数が update_free_position です。n 列の m 番目にクイーンを置いた場合、n + 1 から size - 1 までの列の free_position を更新して、その値を new_free_position にセットします。クイーンを置いた位置 m と斜めの利き筋のビットをオフにして、その値が 0 になったならば FALSE を返します。
関数 queen では、クイーンを置くときに free_position を使ってチェックを行います。そして、update_free_position で free_position を更新します。もし、その結果が 0 ならば、クイーンを置くことができない列が生じたので、この時点で枝刈りを行います。
あとは、とくに難しいところはないでしょう。詳細はプログラムリストをお読みくださいませ。さっそく、M.Hiroi のオンボロマシン (Pentium 166 MHz) で実行したところ、結果は次のようになりました。
| 11 | 12 | 13 | 14 | |
|---|---|---|---|---|
| 解(個数) | 2680 | 14200 | 73712 | 365596 |
| その１ | 0.5 | 2.3 | 11.4 | 72.7 |
| その２ | 0.1 | 0.8 | 3.1 | 16.9 |
| その３ | 0.1 | 0.8 | 3.2 | 17.0 |
プログラム（その２）とほぼ同じ結果になりました。枝刈りの効果は十分に出ていますが、update_free_position の処理に時間がかかるため、プログラム（その２）を越えることはできませんでした。もっと簡単にチェックできる方法があればよかったのですが、残念ながら M.Hiroi には思いつきませんでした。何かよいアイデアがありましたら、ぜひ教えてくださいね。
今度はビット演算を使ってプログラム（その２）を高速化する方法を紹介します。オリジナルは Jeff Somers さんのプログラムですが、高橋謙一郎さん が再帰を使って書き直したプログラムを Ｎクイーン問題（解の個数を求める） で発表されています。今回は高橋さんのプログラムを参考にさせていただきました。高橋さんに感謝します。
プログラムのポイントは、斜めの利き筋のチェックをビット演算で行うことです。次図を見てください。
0 1 2 3 4
*-------------
| . . . . . .
| . . . -3. . 0x02
| . . -2. . . 0x04
| . -1. . . . 0x08 (1 bit 右シフト)
| Q . . . . . 0x10 (Q の位置は 4)
| . +1. . . . 0x20 (1 bit 左シフト)
| . . +2. . . 0x40
| . . . +3. . 0x80
*-------------
図：斜めの利き筋のチェック
クイーンの位置をビットオンで表すことします。上図のように 0 列目の 4 番目にクイーンを置いた場合、クイーンの位置は第 4 ビットをオンにした値 0x10 となります。
次に、斜めの利き筋を考えます。上図の場合、1 列目の右斜め上の利き筋は 3 番目 (0x08)、2 列目の右斜め上の利き筋は 2 番目 (0x04) になります。この値は 0 列目のクイーンの位置 0x10 を 1 ビットずつ右シフトすれば求めることができます。また、左斜め上の利き筋の場合、1 列目では 5 番目 (0x20) で 2 列目では 6 番目 (0x40) になるので、今度は 1 ビットずつ左シフトすれば求めることができます。
つまり、右斜め上の利き筋を right、左斜め上の利き筋を left で表すことにすると、right と left にクイーンの位置をセットしたら、隣の列を調べるときに right と left を 1 ビットシフトするだけで、斜めの利き筋を求めることができるわけです。
プログラムは次のようになります。
リスト：N Queens Problem の解法（その４）
#include <stdio.h>
#include <time.h>
#define MAXSIZE 16
#define TRUE 1
#define FALSE 0
int board[MAXSIZE];
int size;
int count;
void queen( int n, int right, int left )
{
if( n == size ){
count++;
} else {
int i, bit, used = right | left;
for( i = n; i < size; i++ ){
bit = board[i];
if( bit & used ) continue;
board[i] = board[n];
board[n] = bit;
queen( n + 1, (right | bit) >> 1, (left | bit) << 1 );
/* 元に戻す */
board[n] = board[i];
board[i] = bit;
}
}
}
int main()
{
int i, start;
/* 初期化 */
for( size = 10; size <= 14; size++ ){
for( i = 0; i < size; i++ ){
board[i] = 1 << i;
}
start = clock();
count = 0;
queen( 0, 0, 0 );
printf("%d --> %d, 時間 %d\n", size, count, clock() - start );
}
return 0;
}
配列 board は単純な数値ではなく、クイーンの位置をビットで表した値をセットします。関数 queen の引数 right が右斜め上の利き筋、left が左斜め上の利き筋を表します。rigth と left の OR を計算して used にセットすると、used のビットオンの位置が斜めの利き筋にあたります。
そして、board から斜めの利き筋にあたらないクイーンの位置 (bit) を選びます。ちなみに、高橋さんのプログラムではクイーンの選択処理もビット操作で行っていますが、このプログラムではわかりやすさを優先しました。興味のある方は、高橋さんのプログラムをお読みくださいませ。
queen を再帰呼び出しするときは、right と left にクイーンの位置をセットして、それを 1 ビットシフトします。right と left は局所変数なので、元の値に戻す処理は必要ありません。
あとは、とくに難しいところはないでしょう。詳細はプログラムリストをお読みください。さっそく、M.Hiroi のオンボロマシン (Pentium 166 MHz) で実行したところ、結果は次のようになりました。
| 11 | 12 | 13 | 14 | |
|---|---|---|---|---|
| 解(個数) | 2680 | 14200 | 73712 | 365596 |
| その１ | 0.5 | 2.3 | 11.4 | 72.7 |
| その２ | 0.1 | 0.8 | 3.1 | 16.9 |
| その４ | 0.1 | 0.5 | 2.1 | 10.5 |
いやー、とても速いので驚きました。こんな簡単な方法で、ここまで速くなるとは思ってもいませんでした。まさに Simple is best といったところでしょうか。脱帽するしかありません。
高橋謙一郎さん が公開された Ｎクイーン問題（解の個数を求める） では、ビット演算による高速化やユニーク解の判定方法が詳しく解説されていて、とても勉強になります。それから、クイーンの選択処理をビット演算で行うと、実行速度はもっと速くなります。興味のある方は、高橋さんのドキュメントをお読みくださいませ。