n女王問題

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

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

全解探索

対称解の除去

• 例えば，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女王問題の場合は、まだ駒を置いていない初期部分解)
• 子ノードは親ノードの部分解を一段階拡張した部分解。
  (例えば，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言語では引数で配列を渡そうとしてもコピーされないので， 明示的にコピーしている)