N-Queens問題をscalaでやってみた
N-Queens問題とは
チェスボード上に、クイーンを互いにチェックされないように置いていきます。クイーンは縦、横、斜めに相手がいる時にチェックできます。
したがって、８×８のチェスボード上では、各列に１つずつ、最大８つのクイーンを置くことができそうです。
これをｎ×ｎのチェスボードに拡張して、ｎ個のクイーンの配置を考えます。
listとfor-comprehensionを使って解いてみる
まず、１個目からk-1個目までのクイーンが配置されていると仮定します。各行についても列と同様に、一つずつクイーンが置かれるので、１行目からk-1行目まで順番にクイーンが置かれているとします。これは、１からｋ−１のクイーンが置かれている列番号のリストと、そのリストを一つの要素とした、並べ方の組み合わせのリスト、すなわちリストのリストで表されます。
ここに、k番目のクイーンを、チェックされないように置くことを考えます。１からｎまでの列番号に対して、それがチェックされない位置なら、列番号リストのk番目に加えます。これをすべての組み合わせに対して総当たりで行います。ここに、for-comprehensionの強さが出るわけですね。
def queens(n: Int): List[List[Int]] = {
def placeQueens(k: Int): List[List[Int]] =
if (k == 0) List(List())
else for { queen <- placeQueens(k - 1)
column <- List.range(1, n + 1)
if isSafe(column, queen, 1) } yield column :: queen
placeQueens(n)
}
※ここまでのコードは http://www.scala-lang.org/docu/files/ScalaByExample.pdf
の第１０章 For-Comprehensionsに載っています。この続き、isSafeを作るのが課題として提示されています。
チェックされない安全地帯を求める
さて、※に書いたように、ここからisSafeを表現するのが課題です。isSafeは、引数のカラムが、列番号リストに対して安全かどうかをBooleanで返します。３番目の引数deltaは、行番号ｋと対象のクイーンの行番号(1からk-1)の差で、初期値を１としています。ｋ−(k-1)。
縦方向の条件から、ｋ番目の列番号は、i番目(0<i<k)の列番号と違わなくてはなりません。また、斜め方向の条件を考えると、i番目の列番号±deltaは安全ではありません。
以上より、isSafeは次のように書けます。
def isSafe(col: Int, queen: List[Int], delta: Int): Boolean = { queen match{
case Nil => true
case head :: tail =>
if (col == head || col == head - delta || col == head + delta ) { false
}else { isSafe(col, tail, delta + 1) }
}
}
結果の表示
これで、N-Queens問題の解がList[List]の形で求められるようになりました。
しかし、リスト形式だとわかりにくいので、チェスボードを描画してみます。
描画は以下の関数で行います。
def describe(row: Int, col: Int): String = col match{
case `row` => describe(row, col - 1) + "_q_|"
case 0 => "|"
case _ => describe(row, col - 1) + "___|"
}
queens関数で求められた解を受け取りつつ、描画してみると、クイーンの配置が平面図でわかります。
def schema(n: Int) = {
val solution = queens(n)
var count = 1
for (eachboad <- solution) {
for (line <- List.range(1, n + 1)) print(" ___")
print("\n")
for (eachrow <- eachboad) {
println(describe(eachrow, n))
}
println(eachboad + "\n--------No." + count + "----------\n")
count += 1
}
}
８×８のチェスボードで計算したところ、92通りの配置方法があることがわかりました。
意外と多いですね。
16×16でやってみると、さすがに計算に時間がかかってなかなか結果が帰ってこなかったので中断しました。
計算効率を上げる方法があれば教えていただきたいです。
全文
object Queen {
def schema(n: Int) = {
val solution = queens(n)
var count = 1
for (eachboad <- solution) {
for (line <- List.range(1, n + 1)) print(" ___")
print("\n")
for (eachrow <- eachboad) {
println(describe(eachrow, n))
}
println(eachboad + "\n--------No." + count + "----------\n")
count += 1
}
}
def queens(n: Int): List[List[Int]] = {
def placeQueens(k: Int): List[List[Int]] =
if (k == 0) List(List())
else for { queen <- placeQueens(k - 1)
column <- List.range(1, n + 1)
if isSafe(column, queen, 1) } yield column :: queen
placeQueens(n)
}
def isSafe(col: Int, queen: List[Int], delta: Int): Boolean = { queen match{
case Nil => true
case head :: tail =>
if (col == head || col == head - delta || col == head + delta ) { false
}else { isSafe(col, tail, delta + 1) }
}
}
def describe(row: Int, col: Int): String = col match{
case `row` => describe(row, col - 1) + "_q_|"
case 0 => "|"
case _ => describe(row, col - 1) + "___|"
}
}