ホームページへ戻るＮクイーン問題（解の個数を求める）「Ｎクイーン問題」は８クイーン問題を単に一般化したというだけでなく、どこまで大きな Ｎ まで解を求められるかという挑戦でもあります。その中でも「解の個数を求める」というアプローチについて、ソルバープログラムの高速化を考えてみます。
まず、Ｎクイーン問題の解の個数を求めるプログラムの中で特に注目したものは「ビット処理」によるもので、Jeff Somers さんの書いたプログラムです。
http://www.jsomers.com/nqueen_demo/nqueens.html ←リンク切れ
基本アルゴリズムはバックトラッキングですが、ビット操作を使ったシンプルな構造で高速性を実現させています。このプログラムは左右反転によるパターンの探索を省略して最後に結果を２倍するという工夫がなされていますが、ビット演算による高速性の秘密を明確にするために、この仕組みをいったん外し、さらにバックトラッキング探索を非再帰で書いているので、読み易くするために再帰で書き直してみたものがこれです。
#include <stdio.h>
int SIZE, MASK, COUNT;
void Backtrack(int y, int left, int down, int right)
{
int bitmap, bit;
if (y == SIZE) {
COUNT++; /* 配置が完了したので解の個数をカウントする */
} else {
bitmap = MASK & ~(left | down | right); /* 配置可能フィールド */
while (bitmap) {
bit = -bitmap & bitmap; /* 最も下位の１ビットを抽出 */
bitmap ^= bit;
Backtrack(y+1, (left | bit)<<1, down | bit, (right | bit)>>1);
}
}
}
int main(void)
{
SIZE = 10; /* N:ボードの大きさをここに設定する */
COUNT = 0; /* 解の個数:初期化 */
MASK = (1 << SIZE) - 1; /* N個のオールONビット */
Backtrack(0, 0, 0, 0);
printf("N=%d -> %d\n", SIZE, COUNT);
return 0;
}
Ｎ×ＮのチェスボードをＮ個のビットフィールドで表し、ひとつの行の状態をひとつのビットフィールドに対応させます。(クイーンが置いてある位置のビットをONにする) そして、バックトラッキングは0番目のビットフィールドから下に向かって順にいずれかのビット位置をひとつだけONにして進めていきます。 - - - - - Q - - 00000100 0番目のビットフィールド - - - Q - - - - 00010000 1番目のビットフィールド - - - - - - Q - 00000010 2番目のビットフィールド Q - - - - - - - 10000000 3番目のビットフィールド - - - - - - - Q 00000001 4番目のビットフィールド - Q - - - - - - 01000000 5番目のビットフィールド - - - - Q - - - 00001000 6番目のビットフィールド - - Q - - - - - 00100000 7番目のビットフィールド次に、効き筋をチェックするためにさらに３つのビットフィールドを用意します。左下に効き筋が進むもの、真下に効き筋が進むもの、右下に効き筋が進むものの３つです。その３つのビットフィールドをそれぞれ、left, down, right と呼ぶことにします。 n番目のビットフィールドからn+1番目のビットフィールドに探索を進めるときに、その３つのビットフィールドとn番目のビットフィールド(bit)とのOR演算をそれぞれ行い、leftは左にひとつシフトし、downはそのまま、rightは右にひとつシフトしてn+1番目のビットフィールド探索に渡してやります。 left ← (left | bit)<<1, down ← down | bit, right ← (right | bit)>>1n+1番目のビットフィールドの探索では、この３つのビットフィールドをOR演算したビットフィールドを作り、それがONになっている位置は効き筋に当たるので置くことができない位置ということになります。 次にその３つのビットフィールドをORしたビットフィールドをビット反転させます。つまり「配置可能なビットがONになったビットフィールド」に変換します。そしてこの配置可能なビットフィールドを bitmap と呼ぶとして、次の演算を行なってみます。 bit = -bitmap & bitmap;この演算式の意味を理解するには負の値がコンピュータにおける２進法ではどのように表現されているのかを知る必要があります。負の値を２進法で具体的に表わしてみると次のようになります。 00000011 3 00000010 2 00000001 1 00000000 0 11111111 -1 11111110 -2 11111101 -3正の値nを負の値-nにするときは、nをビット反転してから+1されています。そして、例えばn=22としてnと-nをAND演算すると下のようになります。nを２進法で表したときの一番下位のONビットがひとつだけ抽出される結果が得られるのです。極めて簡単な演算によって1ビット抽出を実現させていることが重要です。
00010110 22
AND 11101010 -22
------------------
00000010
さて、そこで下のようなwhile文を書けば、このループは bitmap のONビットの数の回数だけループすることになります。配置可能なパターンをひとつずつ全く無駄なループがなく生成されることになります。
while (bitmap) {
bit = -bitmap & bitmap;
bitmap ^= bit;
/* ここでは配置可能なパターンがひとつずつ生成される(bit) */
}
全探索によって得られたある１つの解が、回転・反転などによる本質的に変わることのない変換によって他の解と同型となるものが存在する場合、それを別の解とはしないとする解の数え方で得られる解を「ユニーク解」といいます。つまり、ユニーク解とは、全解の中から回転・反転などによる変換によって同型になるものどうしをグループ化することを意味しています。 従って、ユニーク解はその「個数のみ」に着目され、この解はユニーク解であり、この解はユニーク解ではないという定まった判定方法はありません。ユニーク解であるかどうかの判断はユニーク解の個数を数える目的の為だけに各個人が自由に定義することになります。もちろん、どのような定義をしたとしてもユニーク解の個数それ自体は変わりません。 さて、Ｎクイーン問題は正方形のボードで形成されるので回転・反転による変換パターンはぜんぶで８通りあります。だからといって「全解数＝ユニーク解数×８」と単純にはいきません。ひとつのグループの要素数が必ず８個あるとは限らないのです。Ｎ＝５の下の例では要素数が２個のものと８個のものがあります。Ｎ＝５の全解は１０個、ユニーク解は２個なのです。 グループ１: - - - Q - - Q - - - Q - - - - - - - - Q - - Q - - - - Q - - - - - - Q Q - - - - - Q - - - - - - Q - グループ２: - - - - Q Q - - - - - - Q - - - - Q - - - - - Q - - Q - - - Q - - - - - - - - Q - - Q - - - - Q - - Q - - - - - - - - Q - Q - - - - - - Q - - - - Q - - Q - - - Q - - - - - - - - Q - - - Q - - Q - - - - - - - Q Q - - - - - Q - - - - - - Q - - - - Q - - Q - - - - Q - - - - - - Q - - - Q - - - - Q - - - - - - Q Q - - - - - Q - - - - - - Q - - - - - Q Q - - - - Q - - - - - - - - Q - - Q - - - - Q - -それでは、ユニーク解を判定するための定義付けを行いますが、次のように定義することにします。 各行のクイーンが右から何番目にあるかを調べて、最上段の行から下の行へ順番に列挙します。そしてそれをＮ桁の数値として見た場合に最小値になるものをユニーク解として数えることにします。尚、このＮ桁の数を以後は「ユニーク判定値」と呼ぶことにします。 - - - - Q 0 - - Q - - 2 Q - - - - 4 ---> 0 2 4 1 3 (ユニーク判定値) - - - Q - 1 - Q - - - 3探索によって得られたある１つの解(オリジナル)がユニーク解であるかどうかを判定するには「８通りの変換を試み、その中でオリジナルのユニーク判定値が最小であるかを調べる」ことになります。しかし結論から先にいえば、ユニーク解とは成り得ないことが明確なパターンを探索中に切り捨てるある枝刈りを組み込むことにより、３通りの変換を試みるだけでユニーク解の判定が可能になります。
先ず最上段の行のクイーンの位置に着目します。その位置が左半分の領域にあればユニーク解には成り得ません。何故なら左右反転によって得られるパターンのユニーク判定値の方が確実に小さくなるからです。また、Ｎが奇数の場合に中央にあった場合はどうでしょう。これもユニーク解には成り得ません。何故なら仮に中央にあった場合、それがユニーク解であるためには少なくとも他の外側の３辺におけるクイーンの位置も中央になければならず、それは互いの効き筋にあたるので有り得ません。 最上段の行のクイーンの位置は中央を除く右側の領域に限定されます。(ただし、N ≧ 2)次にその中でも一番右端(右上の角)にクイーンがある場合を考えてみます。他の３つの角にクイーンを置くことはできないので、ユニーク解であるかどうかを判定するには、右上角から左下角を通る斜軸で反転させたパターンとの比較だけになります。突き詰めれば、上から２行目のクイーンの位置が右から何番目にあるかと、右から２列目のクイーンの位置が上から何番目にあるかを比較するだけで判定することができます。この２つの値が同じになることはないからです。
3 0
↓↓
- - - - Q ←0
- Q - - - ←3
- - - - - 上から２行目のクイーンの位置が右から４番目にある。
- - - Q - 右から２列目のクイーンの位置が上から４番目にある。
- - - - - しかし、互いの効き筋にあたるのでこれは有り得ない。
結局、再帰探索中において下図の X への配置を禁止する枝刈りを入れておけば、得られる解は総てユニーク解であることが保証されます。
- - - - X Q - Q - - X - - - . - X - - - - . X - - - - - A - - - - - - -次に右端以外にクイーンがある場合を考えてみます。オリジナルがユニーク解であるためには先ず下図の X への配置は禁止されます。よって、その枝刈りを先ず入れておきます。 X X - - - Q X X X - - - - - - X - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - X - - - - - - X X X - - - - X X次にクイーンの利き筋を辿っていくと、結局、オリジナルがユニーク解ではない可能性があるのは、下図の A,B,C の位置のどこかにクイーンがある場合に限られます。従って、90度回転、180度回転、270度回転の３通りの変換パターンだけを調べれはよいことになります。 X X x x x Q X X X - - - x x x X C - - x - x - x - - x - - x - - - x - - - x - - x - - - - x - A X - - - - x - X X X B - - x X X
これまでの考察はユニーク解の個数を求めるためのものでした。全解数を求めるにはユニーク解を求めるための枝刈りを取り除いて全探索する必要があります。したがって探索時間を犠牲にしてしまうことになります。そこで「ユニーク解の個数から全解数を導いてしまおう」という試みが考えられます。これは、左右反転によるパターンの探索を省略して最後に結果を２倍するというアイデアの拡張版といえるものです。そしてそれを実現させるには「あるユニーク解が属するグループの要素数はいくつあるのか」という考察が必要になってきます。 最初に、クイーンが右上角にあるユニーク解を考えます。斜軸で反転したパターンがオリジナルと同型になることは有り得ないことと(×２)、右上角のクイーンを他の３つの角に写像させることができるので(×４)、このユニーク解が属するグループの要素数は必ず８個(＝２×４)になります。 次に、クイーンが右上角以外にある場合は少し複雑になりますが、考察を簡潔にするために次の事柄を各自で確認して下さい。 (1)に該当するユニーク解が属するグループの要素数は、左右反転させたパターンを加えて２個しかありません。(2)に該当するユニーク解が属するグループの要素数は、180度回転させて同型になる場合は４個(左右反転×縦横回転)、そして180度回転させてもオリジナルと異なる場合は８個になります。(左右反転×縦横回転×上下反転) 以上のことから、ひとつひとつのユニーク解が上のどの種類に該当するのかを調べることにより全解数を計算で導き出すことができます。探索時間を短縮させてくれる枝刈りを外す必要がなくなったというわけです。
以上の考察を基にして書いたプログラムをここに置きます。 Download nqueens1.c 基本コード Download nqueens2.c 再帰 + OpenMP Download nqueens3.c 非再帰 + OpenMP版 (ver3.3 2023/03/07 高速版)
もっと高速なプログラムがここにあります. (deepgreenさん) 【プログラムの実行結果 / 非再帰+OpenMP版】 Version 3.3 (MAR/2023) 2023/03/13 <------ N-Queens Solutions -----> <---- time ----> N: Total Unique days hh:mm:ss.-- 2: 0 0 0.00 3: 0 0 0.00 4: 2 1 0.00 5: 10 2 0.00 6: 4 1 0.00 7: 40 6 0.00 8: 92 12 0.00 9: 352 46 0.00 10: 724 92 0.00 11: 2680 341 0.00 12: 14200 1787 0.00 13: 73712 9233 0.00 14: 365596 45752 0.01 15: 2279184 285053 0.04 16: 14772512 1846955 0.22 17: 95815104 11977939 1.33 18: 666090624 83263591 9.15 19: 4968057848 621012754 1:21.10 20: 39029188884 4878666808 12:41.56 21: 314666222712 39333324973 1:44:33.37 22: 2691008701644 336376244042 14:45:03.08 23: 24233937684440 3029242658210 5 10:37:12.97 CPU i7-10870H 2.21GHz 8-core 16-thread RAM 16.0GB 2933MHz Visual Studio Community 2022 ホームページへ戻る |
