ホームページへ戻る　開発ノートメニューへ戻る

Ｎクイーン問題（解の個数を求める）


　「Ｎクイーン問題」は８クイーン問題を単に一般化したというだけでなく、どこまで大きな Ｎ まで解を求められるかという挑戦でもあります。その中でも「解の個数を求める」というアプローチについて、ソルバープログラムの高速化を考えてみます。

■ビット処理を用いた基本形

　まず、Ｎクイーン問題の解の個数を求めるプログラムの中で特に注目したものは「ビット処理」によるもので、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)>>1
　n+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 -
- - - - - -
- - - - - -
　次に右端以外にクイーンがある場合を考えてみます。オリジナルがユニーク解であるためには先ず下図の 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) 90度回転させてオリジナルと同型になる場合、さらに90度回転(オリジナルから180度回転)
　　　させても、さらに90度回転(オリジナルから270度回転)させてもオリジナルと同型になる。
　(2) 90度回転させてオリジナルと異なる場合は、270度回転させても必ずオリジナルとは異なる。
　　　ただし、180度回転させた場合はオリジナルと同型になることも有り得る。
　(1)に該当するユニーク解が属するグループの要素数は、左右反転させたパターンを加えて２個しかありません。(2)に該当するユニーク解が属するグループの要素数は、180度回転させて同型になる場合は４個(左右反転×縦横回転)、そして180度回転させてもオリジナルと異なる場合は８個になります。(左右反転×縦横回転×上下反転)

　以上のことから、ひとつひとつのユニーク解が上のどの種類に該当するのかを調べることにより全解数を計算で導き出すことができます。探索時間を短縮させてくれる枝刈りを外す必要がなくなったというわけです。

■ソースプログラムと実行結果

　以上の考察を基にして書いたプログラムをここに置きます。

　　　Download nqueens.c　　(ver3.1 2003)
　　　Download nqueens2.c　(ver3.2 2011)
　　　もっと高速なプログラムがここにあります.　(deepgreenさん)

　　　【プログラムの実行結果】 
Version 3.2 (2-core)
<------  N-Queens Solutions  -----> <---- time ---->
 N:           Total          Unique days hh:mm:ss.--
 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.02
14:          365596           45752             0.05
15:         2279184          285053             0.22
16:        14772512         1846955             1.47
17:        95815104        11977939             9.42
18:       666090624        83263591          1:11.21
19:      4968057848       621012754          8:32.54
20:     39029188884      4878666808       1:10:55.48
21:    314666222712     39333324973       9:24:40.50

AMD Athlon(tm) Dual Core Processor 5050e 2.60 GHz
Microsoft Visual C++ 2008 Express Edition with SP1
Windows SDK for Windows Server 2008 and .NET
ホームページへ戻る　開発ノートメニューへ戻る