ail3 parallel programming

n女王問題(n-queens problem)

n女王問題

n-queen問題と呼ばれる。n × n に拡張したチェスのボード上で、n個のチェスの女王駒が互いに当たりの関係にならないような配置を求める。(女王は将棋の飛車と角を合わせた方向に移動できる)
以下の図で Q の位置に女王駒を置いた場合，空白のマス目の部分は当たりではないが， |, -, /, \ の記号でしめしたマス目は縦，横，斜め(左下方向, 右下方向)について当たりになっていて，他の女王駒を置くことが許されない．

+---+---+---+---+---+---+
| \ |   | | |   | / |   |
+---+---+---+---+---+---+
|   | \ | | | / |   |   |
+---+---+---+---+---+---+
| - | - | Q | - | - | - |
+---+---+---+---+---+---+
|   | / | | | \ |   |   |
+---+---+---+---+---+---+
| / |   | | |   | \ |   |
+---+---+---+---+---+---+
|   |   | | |   |   | \ |
+---+---+---+---+---+---+

例えば n = 4 の場合，解は以下の2つである．

+---+---+---+---+   +---+---+---+---+
|   | Q |   |   |   |   |   | Q |   |
+---+---+---+---+   +---+---+---+---+
|   |   |   | Q |   | Q |   |   |   |
+---+---+---+---+   +---+---+---+---+
| Q |   |   |   |   |   |   |   | Q |
+---+---+---+---+   +---+---+---+---+
|   |   | Q |   |   |   | Q |   |   |
+---+---+---+---+   +---+---+---+---+

全解探索

すべての解(の個数がいくつか)を求める。
例えば，n=4 については解の個数は2である．

n	解の個数
1	1
2	0
3	0
4	2
5	10
6	4
7	40

対称解の除去

解の個数をカウントする際に、対称性から本質的に同等な解は二重にカウントしないようにする。

例えば，n=4 の2つの解は，左右反転で互いに写りあうので， 1つだけカウントするようにする．
対称解の間で順序を付けて最小解(最大解)のみカウントすればよい．
解Aと解Bの間の順序のつけ方としては，大雑把にいえば
1. (A の1行目にある女王の桁番号) > (B の1行目にある女王の桁番号) => A > B
2. (A の1行目にある女王の桁番号) < (B の1行目にある女王の桁番号) => A < B
3. 1. の条件も 2. の条件も満たさないなら
  (A の2行目にある女王の桁番号) > (B の2行目にある女王の桁番号) => A > B
4. 1. の条件も 2. の条件も満たさないなら
  (A の2行目にある女王の桁番号) < (B の2行目にある女王の桁番号) => A < B
5. 1.～4. のいずれの条件も満たさないなら，
  (A の3行目にある女王の桁番号) > (B の3行目にある女王の桁番号) => A > B
6. 1.～4. のいずれの条件も満たさないなら，
  (A の3行目にある女王の桁番号) < (B の3行目にある女王の桁番号) => A < B
7. ....
とすればよい．
例えば，カウント前の解が1つ得られたとき，その回転，反転などで他に最大7通りの対称解が考えられる．そのどれよりも小さい(大きい)ならカウントするという方法が考えられる．

n	解の個数	対称解を除いた個数
1	1	1
2	0	0
3	0	0
4	2	1
5	10	2
6	4	1
7	40	6

バックトラック探索木

木の根(ルートノード)は空の解。
(例えば，n女王問題の場合は、まだ駒を置いていない初期部分解)
子ノードは親ノードの部分解を一段階拡張した部分解。
(例えば，n女王問題の場合は、次の行の当たりのない場所に駒を追加した部分解)
木の葉ノードは、条件を満たす解(の候補)もしくはそれ以上拡張できない部分解。

深さ優先探索

すべての部分解の上を渡り歩く(traverse)
木の生成と traverse を同時に行えばよい．
すべての部分解を同時にデータとして保持する必要はない．未拡張の部分解のみ保持すれば十分である．
深さ優先探索では，複数の部分解を拡張できるとき，いま拡張で得られたばかりの部分解を優先して拡張する．
再帰呼出しを使えば，以下のようにできる
```
traverse(部分解 a) {
  if(aは解) return;
  forall (拡張方向 i) {
    if( a を i方向に拡張可能 ) {
       部分解 b = aをi方向に一段階拡張した部分解;
       traverse(b);
    }
  }
}
```
例えば，部分解を変数n (問題サイズ), 変数k (これまで置いた駒数), 配列a (サイズkの配列で，これまでの各駒を置いた位置) に保持することにすると:
```
int 
nqueens(int n, int k, int *a)
{
  if (n == k)
    return 1;
  else
    {
      int s = 0;
      int i;
      for (i = 0; i < n; i++) {
	if (extend_ok(i, n, k, a)){
	  /* allocate an array for a partial solution  */
	  int *b = alloca((k + 1) * sizeof(int));
	  memcpy(b, a, k * sizeof(int));
	  b[k] = i;	  
	  s += nqueens(n, k + 1, b);
	}
      }
      return s;
    }
}
```
のようにすれば，部分解(n, k, *a) (n個のうちk個を置いた部分解で，これまでのk個の位置は配列aに保持)から，部分解 (n, k+1, *b) (k+1個目をiの位置に置くように拡張) へと拡張できる． (C言語では引数で配列を渡そうとしてもコピーされないので，明示的にコピーしている)

並列プログラミング, 先頭ページへ

Masahiro Yasugi