10.1 N クィーン問題 (The N-Queens Problem)

for 内包表記は組み合わせパズルを解くのに特に役立ちます。そのようなパズルの一つの例が８クイーン問題 : 標準的なチェス盤に、８個のクイーンをお互いにチェックしない (クイーンは他の駒が同じ行、列、斜めにある時にチェックできます) ように置け、です。この問題の解法を考えますが、一般化してチェス盤を任意の大きさにします。したがって問題は、n個のクイーンを n x n の大きさのチェス盤に置け、となります。

問題を解くには、クイーンは各行に置かなくてはならないことに注意しましょう。ですから、クイーンを各行に置き、その度に新しく置いたクイーンが、すでに置かれた他のクイーンからチェックされないことを確認します。探索の過程において、行 k のどの場所にクイーンを置いても、それが行 1 から行 k-1 までのどれかのクイーンによってチェックされるかもしれません。そのような場合にはその部分の探索を止め、列 1 から列 k-1 のクイーンの異なる配置で探索を続けます。

以上から、再帰的なアルゴリズムが示唆されます。サイズ n x n の盤に k-1 個のクイーンを置いた解がすでにあるとしましょう。そのような解は、長さ k-1 の列番号のリスト (1 から n の範囲の値) として表現できます。この部分解リストをスタックのように扱います。リストの最初は k-1 行のクイーンの列番号、二番目は k-2 行のクイーンの列番号です。スタックの底は、盤の最初の行のクイーンの列番号です。すべての解はリストのリストとして表現され、各要素が個々の解です。

さて、k 番目のクイーンを置くために、前の解にクイーンを一つ追加し、可能なすべての拡張を作ります。これは長さ k の次の解のリストとなります。このプロセスをチェス盤のサイズ n に達するまで繰り返します。このアルゴリズムは次の関数 placeQueens に表されます。

def queens(n: Int): List[List[Int]] = { def placeQueens(k: Int): List[List[Int]] = if (k == 0) List(List()) else for { queens <- placeQueens(k - 1) column <- List.range(1, n + 1) if isSafe(column, queens, 1) } yield column :: queens placeQueens(n) }

演習 10.1.1 次の関数を書きなさい。

def isSafe(col: Int, queens: List[Int], delta: Int): Boolean

この関数は与えられた列 col に置くクイーンが、すでに置かれているクイーンに対して安全か否かを判定します。ここで delta は、クイーンを置く行と、リスト中の最初のクイーンの行との差です。