N Queens Problem
「8 クイーン」はコンピュータに解かせるパズルの中でも特に有名な問題です。このパズルは 8 行 8 列のチェス盤の升目に、8 個のクイーンを互いの利き筋が重ならないように配置する問題です。クイーンは将棋の飛車と角をあわせた駒で、縦横斜めに任意に動くことができます。解答の一例を下図に示します。
図 : 8 クイーンの解答例
N Queens Problem は「8 クイーン」の拡張バージョンで、N 行 N 列の盤面に N 個のクイーンを互いの利き筋が重ならないように配置する問題です。まず最初に「8 クイーン」を解いてみて、そのあと N Queens Problem に挑戦することにしましょう。
●8 クイーンの解法
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 クイーンの解法 (nqueen0.go)
package main
import "fmt"
// 順列の生成
func permSub(f func([]int), n int, xs []int, used []bool) {
if len(xs) == n {
f(xs)
} else {
for i := 1; i <= n; i++ {
if used[i] { continue }
used[i] = true
permSub(f, n, append(xs, i), used)
used[i] = false
}
}
}
func permutation(f func([]int), n int) {
xs := make([]int, 0, n)
used := make([]bool, n + 1)
permSub(f, n, xs, used)
}
// 衝突の検出
func attack(x int, ys []int) bool {
n := 1
for _, y := range ys {
if x == y + n || x == y - n {
return true
}
n++
}
return false
}
// 安全か？
func safe(xs []int) bool {
for i := 0; i < len(xs) - 1; i++ {
if attack(xs[i], xs[i + 1:]){
return false
}
}
return true
}
func main() {
permutation(func(xs []int){if safe(xs) { fmt.Println(xs) }}, 8)
}
関数 permutation は 1 から n までの順列を生成します。main で permutation を呼び出し、匿名関数の中で生成された順列 xs が 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 を返します。
●実行結果
これでプログラムは完成です。それでは実行してみましょう。
C>go run nqueen0.go [1 5 8 6 3 7 2 4] [1 6 8 3 7 4 2 5] [1 7 4 6 8 2 5 3] ・・・省略・・・ [8 2 5 3 1 7 4 6] [8 3 1 6 2 5 7 4] [8 4 1 3 6 2 7 5]
8 クイーンの場合、回転解や鏡像解を含めると全部で 92 通りあります。
ところで、クイーンの個数を増やすと、プログラムの実行時間は極端に遅くなります。クイーンの個数を増やすのは簡単です。次のリストを見てください。
リスト : N Queens Problem
func main(){
for i := 8; i <= 12; i++ {
fmt.Println("-----", i, "-----")
s := time.Now()
c := 0
permutation(func(xs []int){if safe(xs) { c++ }}, i)
e := time.Now().Sub(s)
fmt.Println(c)
fmt.Println(e)
}
}
permutation の第 2 引数にクイーンの個数を指定するだけです。匿名関数は解を表示するのではなく、解の個数をカウントするように修正します。実行結果は次のようになりました。
表 : 実行結果 (時間 : 秒)
個数 : 8 : 9 : 10 : 11 : 12
-----+-----+------+------+------+-------
解 : 92 : 352 : 724 : 2680 : 14200
時間 : --- : 0.03 : 0.25 : 2.75 : 34.04
実行環境 : Go 言語 (ver 1.17.4), Ubunts 18.04 (WSL), Intel Core i5-6200U 2.30GHz
クイーンの個数をひとつ増やしただけでも、実行時間はとても遅くなります。実はこのプログラム、とても非効率なことをやっているのです。
●無駄を省く
実行速度が遅い理由は、失敗することがわかっている順列も生成してしまうからです。たとえば、最初 (1, 1) の位置にクイーンを置くと、次のクイーンは (2, 2) の位置に置くことはできませんね。したがって、[1, 2, X, X, X, X, X, X,] という配置はすべて失敗するのですが、順列を発生させてからチェックする方法では、このような無駄を省くことができません。
そこで、クイーンの配置を決めるたびに衝突のチェックを行うことにします。これをプログラムすると次のようになります。
リスト : N Queens Problem (改良版)
package main
import (
"fmt"
"time"
)
// 衝突のチェック
func attack(x int, ys []int) bool {
n := len(ys)
for _, y := range ys {
if x == y + n || x == y - n {
return true
}
n--
}
return false
}
// N Queens Problem
func queenSub(f func([]int), n int, xs []int, used []bool) {
if len(xs) == n {
f(xs)
} else {
for i := 1; i <= n; i++ {
if used[i] || attack(i, xs) { continue }
used[i] = true
queenSub(f, n, append(xs, i), used)
used[i] = false
}
}
}
func queen(f func([]int), n int) {
xs := make([]int, 0, n)
used := make([]bool, n + 1)
queenSub(f, n, xs, used)
}
func main(){
for i := 8; i <= 15; i++ {
fmt.Println("-----", i, "-----")
s := time.Now()
c := 0
queen(func(xs []int){ c++ }, i)
e := time.Now().Sub(s)
fmt.Println(c)
fmt.Println(e)
}
}
permutation と permSub の名前を queen と queenSub に変更します。queenSub でクイーンを選択するとき、関数 attack を呼び出して選択したクイーンが衝突しないかチェックします。クイーンはスライスの末尾に追加するので、関数 attack は差分 n をスライスの大きさに初期化して、スライスの先頭から順番にチェックし、n の値を -1 していくことに注意してください。
実行結果を示します
表 : 実行結果 (時間 : 秒)
個数 : 8 : 9 | 10 : 11 : 12 : 13 : 14 : 15
-----+-----+------+------+------+-------+-------+--------+---------
解 : 92 : 352 : 724 : 2680 : 14200 : 73712 : 365596 : 2279184
(0) : --- : 0.03 : 0.25 : 2.75 : 34.04 : ----- : ------ : -------
(1) : --- : ---- : ---- : 0.02 : 0.10 : 0.53 : 3.20 : 20.80
実行環境 : Go 言語 (ver 1.17.4), Ubunts 18.04 (WSL), Intel Core i5-6200U 2.30GHz
実行時間は速くなりましたが、クイーンの個数が 14 を超えると実行時間が極端に遅くなります。これは、斜めの利き筋をチェックする関数 attack と、異なる数字（クイーンの位置）を選ぶために行うスライス used のチェック処理に時間がかかるからです。そこで、藤原博文さん の ８クイーン＠勉強会のページ を参考にプログラムを改良してみましょう。
●プログラムの改良
まず、used のチェックですが、別のスライス zs に数字をひとつずつ入れておいて、選んだ数字と未使用の数字を交換していくことで改良することができます。n 列目のクイーンを選ぶ場合、確定済みのクイーンは zs の 0 から n - 1 までに格納されていて、残りが未使用のクイーンになります。これで未使用のクイーンを簡単に選ぶことができます。
次は斜めの利き筋のチェックです。実は、これも簡単な方法で高速化できます。次の図を見てください。
図 : 斜めの利き筋のチェック
斜めの利き筋は、行と列の位置を足す、または行から列を引くと一定の値になることを利用してチェックしています。attack は確定済みのクイーンと衝突していないかひとつずつチェックしていますが、斜めの利き筋を配列にセットしておけば、もっと簡単にチェックすることができます。
右斜め上の利き筋を rs, 左斜め上の利き筋を ls で表すことにすると、(x, y) にクイーンを置いた場合は次のようにセットします。
rs[x + y] = true ls[x - y + n - 1] = true
n は盤面の大きさ (クイーンの個数) です。バックトラックするときはリセットすることをお忘れなく。プログラムは次のようになります。
リスト：N Queens Problem (nqueen2.go)
package main
import (
"fmt"
"time"
)
func queenSub(f func([]int), n int, zs, xs []int, rs, ls []bool) {
if len(xs) == n {
f(xs)
} else {
k := len(xs)
for i := k; i < n; i++ {
m := zs[i]
if rs[m + k] || ls[m - k + n - 1] {
continue
}
rs[m + k] = true
ls[m - k + n - 1] = true
zs[i] = zs[k]
zs[k] = m
queenSub(f, n, zs, append(xs, m), rs, ls)
zs[k] = zs[i]
zs[i] = m
rs[m + k] = false
ls[m - k + n - 1] = false
}
}
}
func queen(f func([]int), n int) {
xs := make([]int, 0, n)
zs := make([]int, n)
rs := make([]bool, n * 2)
ls := make([]bool, n * 2)
for i := 0; i < n; i++ {
zs[i] = i + 1
}
queenSub(f, n, zs, xs, rs, ls)
}
func main(){
for i := 11; i <= 15; i++ {
fmt.Println("-----", i, "-----")
s := time.Now()
c := 0
queen(func(xs []int){ c++ }, i)
e := time.Now().Sub(s)
fmt.Println(c)
fmt.Println(e)
}
}
プログラムは、とくに難しいところはないので、説明は割愛します。詳細はリストをお読みくださいませ。
実行結果を示します。
表 : 実行結果 (時間 : 秒)
個数 : 11 : 12 : 13 : 14 : 15
-----+------+-------+-------+--------+---------
解 : 2680 : 14200 : 73712 : 365596 : 2279184
(0) : 2.75 : 34.04 : ----- : ------ : -------
(1) : 0.02 : 0.10 : 0.53 : 3.20 : 20.80
(2) : 0.01 : 0.04 : 0.21 : 1.25 : 8.23
実行環境 : Go 言語 (ver 1.17.4), Ubunts 18.04 (WSL), Intel Core i5-6200U 2.30GHz
約 2.5 倍の高速化に成功しました。でも、まだまだ遅いですね。
●ビット演算による高速化
次はビット演算を使って高速化する方法を紹介します。オリジナルは Jeff Somers さんのプログラムですが、高橋謙一郎さん が再帰を使って書き直したプログラムを Ｎクイーン問題（解の個数を求める） で発表されています。今回は高橋さんのプログラムを参考にさせていただきました。高橋さんに感謝します。
プログラムのポイントは二つあります。一つはクイーンの選択処理をビット演算で行うこと、もう一つは斜めの利き筋のチェックをビット演算で行うことです。Go 言語のビット演算はＣ言語とだいたい同じですが、このほかにも覚えておくと便利なビット操作があるので、それを先に紹介しておきましょう。
最も右側 (LSB) にあるビット 1 を 0 にクリアする、逆に最も右側にある 0 を 1 にセットすることは簡単にできます。
(1) 右側にある 1 をクリア => x & (- x) x : 1 1 1 1 x - 1 : 1 1 1 0 ---------------- AND : 1 1 1 0 x : 1 0 0 0 x - 1 : 0 1 1 1 ---------------- AND : 0 0 0 0 (2) 右側にある 0 を 1 にセット => x | (x + 1) x : 0 0 0 0 x + 1 : 0 0 0 1 ---------------- OR : 0 0 0 1 x : 0 1 1 1 x + 1 : 1 0 0 0 ---------------- OR : 1 1 1 1
上図 (1) を見てください。x から 1 を引くと、右側から連続している 0 は桁借りにより 1 になり、最初に出現する 1 が 0 になります。したがって、x & (x - 1) を計算すると、最も右側にある 1 を 0 にクリアすることができます。(2) の場合、x に 1 を足すと、右側から連続している 1 は桁上がりにより 0 になり、最初に出現する 0 が 1 になります。x | (x + 1) を計算すれば、最も右側にある 0 を 1 にセットすることができます。
また、最も右側にある 1 を取り出すことも簡単にできます。簡単な例として 4 ビットの整数値を考えてみます。負の整数を 2 の補数で表した場合、4 ビットで表される整数は -8 から 7 になります。次の図を見てください。
0 : 0000
1 : 0001 -1 : 1111 1 & (-1) => 0001
2 : 0010 -2 : 1110 2 & (-2) => 0010
3 : 0011 -3 : 1101 3 & (-3) => 0001
4 : 0100 -4 : 1100 4 & (-4) => 0100
5 : 0101 -5 : 1011 5 & (-5) => 0001
6 : 0110 -6 : 1010 6 & (-6) => 0010
7 : 0111 -7 : 1001 7 & (-7) => 0001
-8 : 1000
図 : 最も右側にある 1 を取り出す方法
2 の補数はビットを反転した値 (1 の補数) に 1 を加算することで求めることができます。したがって、x と -x の論理積 (x & (-x)) は、最も右側にある 1 だけが残り、あとのビットはすべて 0 になります。
これらの操作はクイーンの選択処理に使うことができます。クイーンの位置をビットオンで表すことします。つまり、i 行目のクイーンは i ビットを 1 にした値になります。この場合、未選択のクイーンは整数値で表すことができます。8 クイーンの場合、まだ一つもクイーンを選択していない状態は 255 になります。残っているクイーンを表す値を n とすると、次の処理でクイーンを順番に取り出していくことができます。
リスト : クイーンの選択処理
for m := n; m > 0; m &= m - 1 {
q := m & (-m)
...
}
for ループの更新処理で 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 (nqueen3.go)
package main
import (
"fmt"
"time"
)
func queen(f func([]int), n, right, left int, xs []int) {
if n == 0 {
f(xs)
} else {
for m := n; m > 0; m &= m - 1 {
q := m & (- m)
if q & (right | left) != 0 { continue }
queen(f, n ^ q, (right | q) >> 1, (left | q) << 1, append(xs, q))
}
}
}
func main(){
for i := uint(12); i <= 16; i++ {
fmt.Println("-----", i, "-----")
s := time.Now()
c := 0
xs := make([]int, 0, i)
queen(func(_ []int){ c++ }, (1 << i) - 1, 0, 0, xs)
e := time.Now().Sub(s)
fmt.Println(c)
fmt.Println(e)
}
}
関数 queen の引数 n が未選択のクイーン、引数 right が右斜め上の利き筋、left が左斜め上の利き筋を表します。(rigth | left) のビットオンの位置が斜めの利き筋にあたります。そして、n から斜めの利き筋にあたらないクイーンを選びます。
queen を再帰呼び出しするときは、right と left にクイーンの位置をセットして、それを 1 ビットシフトします。right と left は局所変数なので、元の値に戻す処理は必要ありません。あとは、とくに難しいところはないでしょう。詳細はプログラムリストをお読みください。
実行結果を示します。
表 : 実行結果 (時間 : 秒) 個数 : 12 : 13 : 14 : 15 : 16 -----+-------+-------+--------+---------+---------- 解 : 14200 : 73712 : 365596 : 2279184 : 14772512 (1) : 0.10 : 0.53 : 3.20 : 20.80 : -------- (2) : 0.04 : 0.21 : 1.25 : 8.23 : -------- (3) : 0.02 : 0.11 : 0.62 : 3.88 : 26.02 実行環境 : Go 言語 (ver 1.17.4), Ubunts 18.04 (WSL), Intel Core i5-6200U 2.30GHz
(1) と比べると 5 倍以上、(2) と比べても 2 倍以上の高速化に成功しました。ビット操作でここまで速くなるとは M.Hiroi も大変驚きました。
●並列処理による高速化
最後に、並列処理でどのくらい速くなるか試してみましょう。プログラムは次のようになります。
リスト : N Queens Problem (nqueen4.go)
package main
import (
"fmt"
"time"
"runtime"
)
func queen(f func([]int), n, right, left int, xs []int) {
if n == 0 {
f(xs)
} else {
for m := n; m > 0; m &= m - 1 {
q := m & (- m)
if q & (right | left) != 0 { continue }
queen(f, n ^ q, (right | q) >> 1, (left | q) << 1, append(xs, q))
}
}
}
func main(){
runtime.GOMAXPROCS(runtime.NumCPU())
for i := 12; i <= 16; i++ {
fmt.Println("-----", i, "-----")
ch := make(chan int, i)
s := time.Now()
for m := (1 << uint(i)) - 1; m > 0; m &= m - 1 {
go func(i uint, m int){
c := 0
m &= - m
xs := make([]int, 1, i)
xs[0] = m
queen(func(_ []int){ c++ }, ((1 << i) - 1) ^ m, m >> 1, m << 1, xs)
ch <- c
}(uint(i), m)
}
sum := 0
for j := i; j > 0; j-- {
sum += <- ch
}
e := time.Now().Sub(s)
fmt.Println(sum)
fmt.Println(e)
}
}
並列化の考え方は拙作のページ 並列プログラミング の「順列生成の並列化」と同じなので、説明は割愛します。興味のある方は「並列プログラミング」をお読みください。
実行結果を示します。
表 : 実行結果 (時間 : 秒) 個数 : 12 : 13 : 14 : 15 : 16 -----+-------+-------+--------+---------+---------- 解 : 14200 : 73712 : 365596 : 2279184 : 14772512 (1) : 0.10 : 0.53 : 3.20 : 20.80 : -------- (2) : 0.04 : 0.21 : 1.25 : 8.23 : -------- (3) : 0.02 : 0.11 : 0.62 : 3.88 : 26.02 (4) : 0.01 : 0.05 : 0.25 : 1.52 : 10.14 実行環境 : Go 言語 (ver 1.17.4), Ubunts 18.04 (WSL), Intel Core i5-6200U 2.30GHz 表 : 初版の実行結果 個数 : 12 : 13 : 14 : 15 : 16 -----+-------+-------+--------+---------+---------- 解 : 14200 : 73712 : 365596 : 2279184 : 14772512 (1) : 0.11 : 0.58 : 3.60 : 23.49 : -------- (2) : 0.06 : 0.30 : 1.82 : 11.59 : -------- (3) : 0.03 : 0.12 : 0.69 : 4.28 : 28.85 (4) : 0.01 : 0.03 : 0.17 : 0.87 : 5.59 実行環境 : Go 言語 ver 1.2, Windows 7, Core i7-2670QM 2.20GHz
2 倍ちょっとの高速化に成功しました。並列化の効果はとても大きいですね。並列処理はパズルの解法にも有効なことがわかります。
●参考URL
高橋謙一郎さん が公開された Ｎクイーン問題（解の個数を求める） では、ビット演算による高速化やユニーク解の判定方法が詳しく解説されていて、とても勉強になります。興味のある方は、高橋さんのドキュメントをお読みくださいませ。
改訂 2021 年 12 月 11 日