「8 クイーン」はコンピュータに解かせるパズルの中でも特に有名な問題です。このパズルは 8 行 8 列のチェス盤の升目に、8 個のクイーンを互いの利き筋が重ならないように配置する問題です。クイーンは将棋の飛車と角をあわせた駒で、縦横斜めに任意に動くことができます。解答の一例を下図に示します。
列
1 2 3 4 5 6 7 8
*-----------------*
1 | Q . . . . . . . |
2 | . . . . Q . . . |
3 | . . . . . . . Q |
行 4 | . . . . . Q . . |
5 | . . Q . . . . . |
6 | . . . . . . Q . |
7 | . Q . . . . . . |
8 | . . . Q . . . . |
*-----------------*
図 : 8 クイーンの解答例
N Queens Problem は「8 クイーン」の拡張バージョンで、N 行 N 列の盤面に N 個のクイーンを互いの利き筋が重ならないように配置する問題です。まず最初に「8 クイーン」を解いてみて、そのあと N Queens Problem に挑戦することにしましょう。
8 クイーンを解くには、すべての置き方を試してみるしか方法はありません。最初のクイーンは、盤上の好きなところへ置くことができるので、64 通りの置き方があります。次のクイーンは 63 通り、その次は 62 通りあるので、置き方の総数は 64 から 57 までの整数を掛け算した 178462987637760 通りもあります。
ところが、解答例を見ればわかるように、同じ行と列に 2 つ以上のクイーンを置くことはできません。上図の解答例をリストを使って表すと、 次のようになります。
1 2 3 4 5 6 7 8 <--- 列の位置
---------------------------
[1, 7, 5, 8, 2, 4, 6, 3] <--- 要素が行の位置を表す
図 : リストでの行と列の表現方法
列をリストの位置に、行番号を要素に対応させれば、各要素には 1 から 8 までの数字が重複しないで入ることになります。すなわち、1 から 8 までの順列の総数である 8! = 40320 通りの置き方を調べるだけでよいのです。パズルを解く場合、そのパズル固有の性質をうまく使って、調べなければならない場合の数を減らすように工夫することが大切です。あとは、その順列が 8 クイーンの条件を満たしているかチェックすればいいわけです。
それでは、プログラムを作りましょう。次のリストを見てください。
リスト : 8 クイーンの解法
object nqueens {
// 衝突しているか
def attack(x: Int, ys: List[Int]): Boolean = {
var n = 1
for (y <- ys) {
if (x == y + n || x == y - n) return true
n += 1
}
false
}
// 安全か？
def safe(xs: List[Int]): Boolean =
xs match {
case Nil => true
case y::ys => if (attack(y, ys)) false else safe(ys)
}
def queen0(xs: List[Int]): Int = {
val it = xs.permutations
var c = 0
while (it.hasNext) {
val xs = it.next()
if (safe(xs)){
c += 1
println(xs)
}
}
c
}
}
関数 queen0 でメソッド permutations を呼び出して、引数のリスト xs の順列を生成します。permutations はイテレータを返すことに注意してください。あとは、while ループで順列を取り出して、それが 8 クイーンの条件を満たしているかチェックします。関数 safe はリストの先頭の要素から順番に衝突のチェックを行います。端にあるクイーンから順番に調べるとすると、斜めの利き筋は次のように表すことができます。
1 2 3 --> 調べる方向
*-------------
| . . . . . .
| . . . -3. . 5 - 3 = 2
| . . -2. . . 5 - 2 = 3
| . -1. . . . 5 - 1 = 4
| Q . . . . . Q の位置は 5
| . +1. . . . 5 + 1 = 6
| . . +2. . . 5 + 2 = 7
| . . . +3. . 5 + 2 = 8
*-------------
図 : 衝突の検出
図を見てもらえばおわかりのように、Q が行 5 にある場合、ひとつ隣の列は 4 と 6 が利き筋に当たります。2 つ隣の列の場合は 3 と 7 が利き筋に当たります。このように単純な足し算と引き算で、利き筋を計算することができます。この処理を関数 attack で行います。
attack はリストの先頭から斜めの利き筋に当たるか調べます。引数 x がクイーンの位置、ys が残りのクイーンを格納したリストです。変数 n が差分を表します。for ループで ys からクイーン y を取り出し、y + n または y - n が x と等しいかチェックします。等しい場合は衝突しているので true を返します。そうでなければ、次のクイーンを調べます。このとき、差分 n を +1 することをお忘れなく。すべてのクイーンを調べたら false を返します。
これでプログラムは完成です。それでは実行してみましょう。
scala> :load nqueens.scala 1 warning found // defined object nqueens ... 略 ... scala> nqueens.queen0(List(1,2,3,4,5,6,7,8)) List(1, 5, 8, 6, 3, 7, 2, 4) List(1, 6, 8, 3, 7, 4, 2, 5) List(1, 7, 4, 6, 8, 2, 5, 3) ・・・省略・・・ List(8, 2, 5, 3, 1, 7, 4, 6) List(8, 3, 1, 6, 2, 5, 7, 4) List(8, 4, 1, 3, 6, 2, 7, 5) val res0: Int = 92
8 クイーンの場合、回転解や鏡像解を含めると全部で 92 通りあります。
ところで、クイーンの個数を増やすと、プログラムの実行時間は極端に遅くなります。クイーンの個数を増やすのは簡単です。次のリストを見てください。
リスト : N Queens Problem
def test0(): Unit = {
for (i <- 8 to 11) {
val s = System.currentTimeMillis
println(queen0(Range(1, i + 1).toList))
println((System.currentTimeMillis - s) + "msec")
}
}
Range で 1 から i までの数列を生成し、それを toList でリストに変換して queen0 に渡します。queen0 は解を表示するのではなく、解の個数をカウントするように修正します。実行結果は次のようになりました。
表 : 実行結果 (時間 : 秒)
個数 : 8 : 9 : 10 : 11
-----+-----+------+------+------
解 : 92 : 352 : 724 : 2680
時間 :0.14 : 0.23 : 0.81 : 10.8
実行環境 : Ubunts 22.04 (WSL2), Intel Core i5-6200U 2.30GHz
クイーンの個数をひとつ増やしただけでも、実行時間はとても遅くなります。実はこのプログラム、とても非効率なことをやっているのです。
実行速度が遅い理由は、失敗することがわかっている順列も生成してしまうからです。たとえば、最初 (1, 1) の位置にクイーンを置くと、次のクイーンは (2, 2) の位置に置くことはできませんね。したがって、[1, 2, X, X, X, X, X, X,] という配置はすべて失敗するのですが、順列を発生させてからチェックする方法では、このような無駄を省くことができません。
そこで、クイーンの配置を決めるたびに衝突のチェックを行うことにします。これをプログラムすると次のようになります。
リスト : N Queens Problem (改良版)
def queen1(f: List[Int] => Unit, xs: List[Int], a: List[Int]): Unit =
if (xs == Nil)
f(a)
else
for (x <- xs if (!attack(x, a))) {
queen1(f, xs.filterNot(_ == x), x::a)
}
def test1(): Unit = {
for (i <- 8 to 13) {
val s = System.currentTimeMillis
var c = 0
queen1(_ => c += 1, Range(1, i + 1).toList, Nil)
println(c)
println((System.currentTimeMillis - s) + "msec")
}
}
関数 queen1 は高階関数として定義します。解をひとつ見つけたら引数 f の関数を呼び出します。queen1 でクイーンを選択するとき、関数 attack を呼び出して選択したクイーンが衝突しないかチェックします。関数 test1 では、queen1 に渡す匿名関数で解の個数をカウントします。とても簡単ですね。
実行結果を示します。
表 : 実行結果 (時間 : 秒)
個数 : 8 : 9 : 10 : 11 : 12 : 13
-----+------+------+------+------+-------+-------
解 : 92 : 352 : 724 : 2680 : 14200 : 73712
(0) : 0.14 : 0.23 : 0.81 : 10.8 : ----- : -----
(1) : ---- : ---- : 0.06 : 0.08 : 0.21 : 1.06
実行時間は速くなりましたが、クイーンの個数が 13 を超えると実行時間が極端に遅くなります。これは、斜めの利き筋をチェックする関数 attack に時間がかかるからです。そこで、藤原博文さんの「８クイーン＠勉強会のページ」を参考にプログラムを改良してみましょう。
斜めの利き筋のチェックは、簡単な方法で高速化できます。次の図を見てください。
右斜め上の利き筋 左斜め上の利き筋
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
*-----------------* *-----------------*
|／／／／／／／／ | 8 -1 |＼＼＼＼＼＼＼＼ |
|／／／／／／／／ | 9 -2 |＼＼＼＼＼＼＼＼ |
|／／／／／／／／ | 10 -3 |＼＼＼＼＼＼＼＼ |
|／／／／／／／／ | 11 -4 |＼＼＼＼＼＼＼＼ |
|／／／／／／／／ | 12 -5 |＼＼＼＼＼＼＼＼ |
|／／／／／／／／ | 13 -6 |＼＼＼＼＼＼＼＼ |
|／／／／／／／／ | 14 -7 |＼＼＼＼＼＼＼＼ |
|／／／／／／／／ | |＼＼＼＼＼＼＼＼ |
*-----------------* *-----------------*
x + y = constant x - y = constant
図：斜めの利き筋のチェック
斜めの利き筋は、行と列の位置を足す、または行から列を引くと一定の値になることを利用してチェックしています。attack は確定済みのクイーンと衝突していないかひとつずつチェックしていますが、斜めの利き筋を配列にセットしておけば、もっと簡単にチェックすることができます。
右斜め上の利き筋を配列 rUsed, 左斜め上の利き筋を配列 lUsed で表すことにすると、(x, y) にクイーンを置いた場合は次のようにセットします。
rs(x + y) = true ls(x - y + n - 1) = true
n は盤面の大きさ (クイーンの個数) です。バックトラックするときはリセットすることをお忘れなく。プログラムは次のようになります。
リスト : N Queens Problem (2)
val MaxSize = 16
val board = new Array[Int](MaxSize)
val nUsed = new Array[Boolean](MaxSize)
val rUsed = new Array[Boolean](MaxSize * 2)
val lUsed = new Array[Boolean](MaxSize * 2)
var size = 0
var cnt = 0
def queen2(n: Int): Unit = {
if (n == size)
cnt += 1
else {
for (m <- 0 until size) {
if (!nUsed(m) && !rUsed(m + n) && !lUsed(m - n + size - 1)) {
board(n) = m
rUsed(m + n) = true
lUsed(m - n + size - 1) = true
nUsed(m) = true
queen2(n + 1)
rUsed(m + n) = false
lUsed(m - n + size - 1) = false
nUsed(m) = false
}
}
}
}
def test2(): Unit = {
for (i <- 10 to 14) {
val s = System.currentTimeMillis
size = i
cnt = 0
queen2(0)
println(cnt)
println((System.currentTimeMillis - s) + "msec")
}
}
プログラムは配列を使って書き直しています。配列 nUsed は未使用の数字を false で、使用した数字を true で表します。あとは、とくに難しいところはないと思います。説明は割愛しますので、詳細はリストをお読みくださいませ。
実行結果を示します。
表 : 実行結果 (時間 : 秒)
個数 : 10 : 11 : 12 : 13 : 14
-----+------+------+-------+-------+--------
解 : 724 : 2680 : 14200 : 73712 : 365596
(0) : 0.81 : 10.8 : ----- : ----- : ------
(1) : 0.06 : 0.08 : 0.21 : 1.06 : ------
(2) : 0.07 : 0.07 : 0.01 : 0.53 : 3.20
改良の効果は十分に出ていますね。
最後に、ビット演算を使って高速化する方法を紹介します。オリジナルは Jeff Somers さんのプログラムですが、高橋謙一郎さんが再帰を使って書き直したプログラムを「Ｎクイーン問題（解の個数を求める）」で発表されています。今回は高橋さんのプログラムを参考にさせていただきました。高橋さんに感謝します。
プログラムのポイントは二つあります。一つはクイーンの選択処理をビット演算で行うこと、もう一つは斜めの利き筋のチェックをビット演算で行うことです。
クイーンの位置をビットオンで表すことします。つまり、i 行目のクイーンは i ビットを 1 にした値になります。この場合、未選択のクイーンは整数値で表すことができます。8 クイーンの場合、まだ一つもクイーンを選択していない状態は 255 になります。残っているクイーンを表す値を n とすると、次の処理でクイーンを順番に取り出していくことができます。
リスト : クイーンの選択処理
var m = n
while (m > 0) {
q := m & (-m)
...
m &= m - 1
}
while ループの最後で m &= m - 1 とすれば、右端の 1 を 0 にクリアすることができます。そして、ループの中で q := m & (- m) とすれば、右端の 1 を取り出すことができます。n から取り出した q を削除するのも簡単で、排他的論理和 n ^ q を計算するだけです。
次は斜めの利き筋のチェックを説明します。下図を見てください。
0 1 2 3 4
*-------------
| . . . . . .
| . . . -3. . 0x02
| . . -2. . . 0x04
| . -1. . . . 0x08 (1 bit 右シフト)
| Q . . . . . 0x10 (Q の位置は 4)
| . +1. . . . 0x20 (1 bit 左シフト)
| . . +2. . . 0x40
| . . . +3. . 0x80
*-------------
図 : 斜めの利き筋のチェック
上図の場合、1 列目の右斜め上の利き筋は 3 番目 (0x08)、2 列目の右斜め上の利き筋は 2 番目 (0x04) になります。この値は 0 列目のクイーンの位置 0x10 を 1 ビットずつ右シフトすれば求めることができます。また、左斜め上の利き筋の場合、1 列目では 5 番目 (0x20) で 2 列目では 6 番目 (0x40) になるので、今度は 1 ビットずつ左シフトすれば求めることができます。
つまり、右斜め上の利き筋を right、左斜め上の利き筋を left で表すことにすると、right と left にクイーンの位置をセットしたら、隣の列を調べるときに right と left を 1 ビットシフトするだけで、斜めの利き筋を求めることができるわけです。
プログラムは次のようになります。
リスト : N Queens Problem (3)
def queen3(n: Int, right: Int, left: Int): Unit = {
if (n == 0)
cnt += 1
else {
var m = n
while (m > 0) {
val q = m & (-m)
if ((q & (right | left)) == 0) {
queen3(n ^ q, (right | q) >> 1, (left | q) << 1)
}
m &= m - 1
}
}
}
def test3(): Unit = {
for (i <- 10 to 15) {
val s = System.currentTimeMillis
cnt = 0
queen3((1 << i) - 1, 0, 0)
println(cnt)
println((System.currentTimeMillis - s) + "msec")
}
}
関数 queen3 の引数 n が未選択のクイーン、引数 right が右斜め上の利き筋、left が左斜め上の利き筋を表します。(rigth | left) のビットオンの位置が斜めの利き筋にあたります。そして、n から斜めの利き筋にあたらないクイーンを選びます。
queen を再帰呼び出しするときは、right と left にクイーンの位置をセットして、それを 1 ビットシフトします。right と left は局所変数なので、元の値に戻す処理は必要ありません。あとは、とくに難しいところはないでしょう。詳細はプログラムリストをお読みください。
実行結果を示します。
表 : 実行結果 (時間 : 秒)
個数 : 11 : 12 : 13 : 14 : 15
-----+------+-------+-------+--------+---------
解 : 2680 : 14200 : 73712 : 365596 : 2279184
(1) : 0.08 : 0.21 : 1.06 : ------ : ------
(2) : 0.07 : 0.01 : 0.53 : 3.20 : ------
(3) : ---- : 0.03 : 0.19 : 0.58 : 3.42
ビット演算の効果はきわめて大きいですね。ここまで速くなるとは M.Hiroi も大変驚きました。
//
// nqueens.scala : N Queens Problems
//
// Copyright (C) 2014-2024 Makoto Hiroi
//
object nqueens {
// 衝突のチェック
def attack(x: Int, ys: List[Int]): Boolean = {
var n = 1
for (y <- ys) {
if (x == y + n || x == y - n) return true
n += 1
}
false
}
// 安全か？
def safe(xs: List[Int]): Boolean =
xs match {
case Nil => true
case y::ys => if (attack(y, ys)) false else safe(ys)
}
// 解法 (0)
def queen0(xs: List[Int]): Int = {
val it = xs.permutations
var c = 0
while (it.hasNext) {
val xs = it.next()
if (safe(xs)) {
c += 1
println(xs)
}
}
c
}
def test0(): Unit = {
for (i <- 8 to 11) {
val s = System.currentTimeMillis
println(queen0(Range(1, i + 1).toList))
println(s"${System.currentTimeMillis - s} msec")
}
}
// 解法 (1)
def queen1(f: List[Int] => Unit, xs: List[Int], a: List[Int]): Unit =
if (xs == Nil)
f(a)
else
for (x <- xs if (!attack(x, a))) {
queen1(f, xs.filterNot(_ == x), x::a)
}
def test1(): Unit = {
for (i <- 8 to 13) {
val s = System.currentTimeMillis
var c = 0
queen1(_ => c += 1, Range(1, i + 1).toList, Nil)
println(c)
println(s"${System.currentTimeMillis - s} msec")
}
}
// 解法 (2)
val MaxSize = 16
val board = new Array[Int](MaxSize)
val nUsed = new Array[Boolean](MaxSize)
val rUsed = new Array[Boolean](MaxSize * 2)
val lUsed = new Array[Boolean](MaxSize * 2)
var size = 0
var cnt = 0
def queen2(n: Int): Unit = {
if (n == size)
cnt += 1
else {
for (m <- 0 until size) {
if (!nUsed(m) && !rUsed(m + n) && !lUsed(m - n + size - 1)) {
board(n) = m
rUsed(m + n) = true
lUsed(m - n + size - 1) = true
nUsed(m) = true
queen2(n + 1)
rUsed(m + n) = false
lUsed(m - n + size - 1) = false
nUsed(m) = false
}
}
}
}
def test2(): Unit = {
for (i <- 10 to 14) {
val s = System.currentTimeMillis
size = i
cnt = 0
queen2(0)
println(cnt)
println(s"${System.currentTimeMillis - s} msec")
}
}
// 解法 (3)
def queen3(n: Int, right: Int, left: Int): Unit = {
if (n == 0)
cnt += 1
else {
var m = n
while (m > 0) {
val q = m & (-m)
if ((q & (right | left)) == 0) {
queen3(n ^ q, (right | q) >> 1, (left | q) << 1)
}
m &= m - 1
}
}
}
def test3(): Unit = {
for (i <- 10 to 15) {
val s = System.currentTimeMillis
cnt = 0
queen3((1 << i) - 1, 0, 0)
println(cnt)
println(s"${System.currentTimeMillis - s} msec")
}
}
}