プログラミング実習II (2026) [XB]

8-Queen 問題

8-Queen とは「8×8 のチェッカーボードに 8 つのクイーンをお互いに取られないように配置せよ」という問題 (パズル) である. 一般には n×n のチェッカーボードを用いる「n-Queen」パズルに拡張できる.

入力: 自然数 n
出力: n×n の 2 次元マス目配列上に n 個の「Queen」を配置せよ. ただし, マス目の縦, 横, 斜めいずれの線上にも 2 つの Queen があってはならない.

例えば, n=4 の場合には次のような配置が答えとなる.

+---+---+---+---+ 
|   |   | q |   | 
+---+---+---+---+ 
| q |   |   |   | 
+---+---+---+---+ 
|   |   |   | q | 
+---+---+---+---+ 
|   | q |   |   | 
+---+---+---+---+

(課題 B_1)

n=4 の場合の解をすべて列挙するプログラムを作成せよ.

盤面のクイーンの配置の表現法は色々考えられるが, 例えば, サイズ 4 の 1 次元の整数配列を用いて, 各列のクイーンが何行目にあるかを記憶する方法が考えられる.

          0   1   2   3
         列  列  列  列
        +---+---+---+---+ 
    0行 |   |   | q |   | 
        +---+---+---+---+ 
    1行 | q |   |   |   | 
        +---+---+---+---+ 
    2行 |   |   |   | q | 
        +---+---+---+---+ 
    3行 |   | q |   |   | 
        +---+---+---+---+ 

  x[] = { 1 , 3 , 0 , 2 }

クイーンの配置は, 下記のような 4 重のループによって探索することができる.

x[0] = 0, 1, 2, 3 について {
  x[1] = 0, 1, 2, 3 について {
    もし x[1] の配置に問題がなければ {
      x[2] = 0, 1, 2, 3 について {
        もし x[2] の配置に問題がなければ {
          x[3] = 0, 1, 2, 3 について {
            もし x[3] の配置に問題がなければ {
              解が求まったので, クイーンの配置を出力
            }
          }
        }
      }
    }
  }
}

(課題 B_2)

入力された n に対して n-queen 問題を解くプログラムを作成せよ. 最初の 1 つのみ解を表示し, 後は全ての解の個数を数えて表示するようにせよ. n = 8, 9, 10, ... と n を増やし, 5分程度の計算時間でどの程度大きな n まで解けるか試してみよ.

基本的には n が固定の場合と同じだが, 「n 重のループ」は n が決まらないとプログラミングできない. これは, 関数の再帰呼び出しにより解決できる.

void place_queens(int *x, int n, int k) を, n-queen 問題の「k ～ n-1 列クイーンの配置を求める」関数と定義する.

n-queen 問題を解くためには, place_queens(x, n, 0) を呼び出せば, 0～n-1 列のクイーンの配列が探索される.

さて, place_queens(x, n, k) は, 次のような仕事をする.

1) k 列目のクイーンの配置 (x[k]) を求める.
2) place_queens(x, n, k+1) を呼び出して, 残りの列 (k+1～n 列) のクイーンの配置を求める.

終了条件は k==n である. すなわち, place_queens(x, n, k) が呼び出されたときに k==n であれば, この時点で 1～n 列までの配置が求まっているので, 解を出力して探索を終了すればよい. 終了条件を忘れると, 「無限再帰呼び出し」に陥るので注意.

place_queens のおおよその構造は次のようになる.

void place_queens(int *x, int n, int k)
{
    もし k==n なら解を出力して終了. 
    x[k] = 0, 1, 2, …, n-1 について {
        もし x[k] の配置に問題がなければ {
            place_queens(x, n, k+1);
        }
    }
}

参考

対称性等を考慮せずに全解を求めた場合, 次のようになる.

     n     解の個数
   ----------------
     1          1
     2          0
     3          0
     4          2
     5         10
     6          4
     7         40
     8         92
     9        352
    10        724
    11      2,680
    12     14,200
    13     73,712
    14    365,596
    15  2,279,184
   ----------------

対称性を考慮すれば探索空間を小さくすることができる. 例えば, 0 行目のクイーンの配置の探索を, 0～7 ではなく 0～3 とすれば, 盤面上で上下対称なクイーンの配置を除外することができる. 他にも色々な対称性を考慮する方法が考えられる.

無駄な配置の探索を避けることにより, 計算を高速化することができる. また, データの表現法によってアルゴリズムや計算の効率が大きく変わってくるので, データの表現法を考えることは非常に重要で本質的である. さらに効率的なデータ構造もあり得るので, 基本が理解できたら他のデータ構造も考えてみるとよい.