問題の説明
N Queens Problem は「8 クイーン」の拡張バージョンで、N 行 N 列の盤面に N 個のクイーンを互いの利き筋が重ならないように配置する問題です。クイーンは将棋の飛車と角をあわせた駒で、縦横斜めに任意に動くことができます。下図に 8 クイーンの解答例を示します。
図 : 8 クイーンの解答例
まず最初に「8 クイーン」を解いてみましょう。そのあとで N Queens Problem に挑戦することにします。使用するプログラミング言語は Python3 (PyPy3) です。
●8 クイーンの解法
8 クイーンを解くには、すべての置き方を試してみるしか方法はありません。最初のクイーンは、盤上の好きなところへ置くことができるので、64 通りの置き方があります。次のクイーンは 63 通り、その次は 62 通りあります。したがって、置き方の総数は 64 * 63 * ... * 57 = 178,462,987,637,760 通りもあります。
ところが、解答例を見ればわかるように、同じ行と列に 2 つ以上のクイーンを置くことはできません。上図の解答例をリストを使って表すと下図のようになります。
0 1 2 3 4 5 6 7 <-- 列の位置
---------------------------
[0, 6, 4, 7, 1, 3, 5, 2] <-- 要素が行の位置を表す
図 : リストでの行と列の表現方法
列をリストの位置に、行番号を要素に対応させれば、各要素には 0 から 7 までの数字が重複しないで入ることになります。すなわち、0 から 7 までの順列の総数である 8! = 40320 通りの置き方を調べればよいことになります。パズルを解く場合は、そのパズル固有の性質をうまく使って、生成するパターンの総数を減らすように工夫することが大切です。
順列を生成するプログラムは簡単です。拙作のページ 新・お気楽 Python プログラミング入門 第 3 回 再帰定義と高階関数 : 順列の生成 で説明しました。ですが、同じプログラムを作るのは面白くないので、ここでは別な方法を紹介しましょう。次のリストを見てください。
リスト : 順列の生成
def permutations(f, n, xs, m = 0):
if m == n:
f(xs[:m])
else:
for i in range(m, len(xs)):
xs[i], xs[m] = xs[m], xs[i]
permutations(f, n, xs, m + 1)
xs[i], xs[m] = xs[m], xs[i]
関数 permutations() は高階関数です。引数 f に関数を渡します。n が選択する要素の個数、xs が要素を格納したリスト (一次元配列)、m が選択した要素の個数を表します。プログラムのポイントは、xs の前半 xs[:m] に選んだ要素を格納し、後半 xs[m:] に未選択の要素を集めるところです。
m が n と等しい場合、順列がひとつ完成しました。順列は xs[:m] に格納されているので、それを関数 f に渡します。そうでなければ、m 番目の要素を選びます。未選択の要素は xs[m:] に格納されています。for ループの変数 i が選択する要素の添字です。xs[i] と xs[m] を交換すれば、選んだ要素 xs[i] を前半に、選ばなかった要素 xs[m] を後半に集めることができます。あとは、permutations() を再帰呼び出しして、戻ってきたら再度 xs[i] と xs[m] を交換して元に戻します。
簡単な実行例を示します。
>>> permutations(print, 2, [1,2,3]) [1, 2] [1, 3] [2, 1] [2, 3] [3, 2] [3, 1] >>> permutations(print, 3, [1,2,3]) [1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 2, 1] [3, 1, 2] >>> permutations(print, 3, [1,2,3,4]) [1, 2, 3] [1, 2, 4] [1, 3, 2] [1, 3, 4] [1, 4, 3] [1, 4, 2] [2, 1, 3] [2, 1, 4] [2, 3, 1] [2, 3, 4] [2, 4, 3] [2, 4, 1] [3, 2, 1] [3, 2, 4] [3, 1, 2] [3, 1, 4] [3, 4, 1] [3, 4, 2] [4, 2, 3] [4, 2, 1] [4, 3, 2] [4, 3, 1] [4, 1, 3] [4, 1, 2]
あとは、生成した順列が 8 クイーンの条件を満たしているかチェックすればいいわけです。ポイントは斜めの利き筋のチェックです。次の図を見てください。
図 : 斜めの利き筋のチェック
斜めの利き筋は、行と列の位置を足す、または行から列を引くと一定の値になる、ということを利用すれば簡単にチェックできます。プログラムは次のようになります。
リスト : 斜め利き筋のチェック
def is_safe(b):
for x in range(1, len(b)):
if conflict(b, b[x], x): return False
return True
関数 is_safe() の引数 b が盤面を表すリストです。is_safe() は x 列のクイーンが 0 から x - 1 列までのクイーンと衝突していないか、関数 conflict() を呼び出してチェックします。
最初は 1 列目のクイーンが 0 列のクイーンと衝突していないかチェックし、次に 2 列目のクイーンと 0, 1 列のクイーンをチェックします。このように、順番にクイーンをチェックしていき、最後に 7 列目のクイーンと 0 - 6 列のクイーンをチェックします。クイーン同士が衝突していたら False を返し、そうでなければ True を返します。
次は関数 conflict() を作りましょう。次のリストを見てください。
リスト : 衝突のチェック
def conflict(b, y, x):
for x1 in range(x):
y1 = b[x1]
if x1 - y1 == x - y or x1 + y1 == x + y:
return True
return False
関数 conflict() の引数 y がチェックするクイーンの行、x が列を表します。for ループで 0 列から x - 1 列のクイーンを取り出します。変数 x1 に列を、変数 y1 に行をセットします。あとはクイーン (x, y) と (x1, y1) の斜めの利き筋をチェックし、同じであれば衝突しているので True を返します。0 から x - 1 列のクイーンと衝突していなければ、最後に False を返します。
ここまで作ればあとは簡単です。8 クイーンを解くプログラムは次のようになります。
リスト : 8 クイーンの解法 (単純版)
def solver0(size):
def check(b):
if is_safe(b): print(b)
permutations(check, size, list(range(size)))
関数 solver0() の引数 size は盤面の大きさを表します。permutations() で順列を生成し、局所関数 check() で生成した盤面 b が 8 クイーンの条件を満たしているかチェックします。そうであれば、print() で盤面 b を出力します。
それでは実際に試してみましょう。
>>> solver0(4)
[1, 3, 0, 2]
[2, 0, 3, 1]
>>> solver0(5)
[0, 2, 4, 1, 3]
[0, 3, 1, 4, 2]
[1, 3, 0, 2, 4]
[1, 4, 2, 0, 3]
[2, 0, 3, 1, 4]
[2, 4, 1, 3, 0]
[3, 1, 4, 2, 0]
[3, 0, 2, 4, 1]
[4, 1, 3, 0, 2]
[4, 2, 0, 3, 1]
>>> solver0(6)
[1, 3, 5, 0, 2, 4]
[2, 5, 1, 4, 0, 3]
[3, 0, 4, 1, 5, 2]
[4, 2, 0, 5, 3, 1]
>>> solver0(8)
[0, 4, 7, 5, 2, 6, 1, 3]
[0, 5, 7, 2, 6, 3, 1, 4]
[0, 6, 3, 5, 7, 1, 4, 2]
・・・省略・・・
[7, 1, 4, 2, 0, 6, 3, 5]
[7, 2, 0, 5, 1, 4, 6, 3]
[7, 3, 0, 2, 5, 1, 6, 4]
solver0(8) を実行すると 92 通りの解が出力されます。
●プログラムの問題点
ところで、クイーンの個数を増やすと、プログラムの実行時間は極端に遅くなります。
リスト : N Queens Problem
def test0():
def check(b):
nonlocal cnt
if is_safe(b): cnt += 1
for n in range(8, 11):
cnt = 0
s = time.time()
permutations(check, n, list(range(n)))
e = time.time()
print(n, cnt, e - s)
局所関数 check() は解を表示するのではなく、解の個数をカウントするように修正します。実行結果は次のようになりました。
表 : 実行結果 (時間 : 秒)
個数 : 8 : 9 : 10 : 11
-----+------+------+------+-------
解 : 92 : 352 : 724 : 2680
時間 : 0.03 : 0.23 : 1.67 : 18.46
実行環境 : PyPy3 (ver 7.3.1), Ubunts 20.04 (WSL), Intel Core i5-6200U 2.30GHz
クイーンの個数をひとつ増やしただけでも、実行時間はとても遅くなります。実はこのプログラム、とても非効率なことをやっているのです。
●無駄を省く
実行速度が遅い理由は、失敗することがわかっている順列も生成してしまうからです。たとえば、最初 (1, 1) の位置にクイーンを置くと、次のクイーンは (2, 2) の位置に置くことはできませんね。したがって、[1, 2, X, X, X, X, X, X,] という配置はすべて失敗するのですが、順列を生成してからチェックする方法では、このような無駄を省くことができません。
そこで、クイーンの配置を決めるたびに衝突のチェックを行うことにします。これをプログラムすると次のようになります。
リスト : N Queens Problem (高速化その１)
def nqueens(f, n, xs, m = 0):
if m == n:
f(xs)
else:
for i in range(m, len(xs)):
if conflict(xs, xs[i], m): continue
xs[i], xs[m] = xs[m], xs[i]
nqueens(f, n, xs, m + 1)
xs[i], xs[m] = xs[m], xs[i]
def test(func):
def check(b):
nonlocal cnt
cnt += 1
for n in range(8, 15):
cnt = 0
s = time.time()
func(check, n, list(range(n)))
e = time.time()
print(n, cnt, e - s)
関数 nqueens() は permutations() に conflict() の処理を付け加えただけです。これで無駄な順列の生成を省くことができます。
実行結果を示します。
表 : 実行結果 (時間 : 秒)
個数 : 8 : 9 : 10 : 11 : 12 : 13 : 14
-----+------+------+------+-------+-------+-------+--------
解 : 92 : 352 : 724 : 2680 : 14200 : 73712 : 365596
(0) : 0.03 : 0.23 : 1.67 : 18.46 : ----- : ----- : ------
(1) : ---- : ---- : 0.02 : 0.08 : 0.36 : 2,03 : 12.20
実行環境 : PyPy3, Ubunts 18.04 (WSL), Intel Core i5-6200U 2.30GHz
実行時間は速くなりましたが、クイーンの個数が 14 を超えると実行時間が極端に遅くなります。これは、斜めの利き筋をチェックする関数 conflict() の処理に時間がかかるからです。そこで、藤原博文さん の ８クイーン＠勉強会のページ を参考にプログラムを改良してみましょう。
●プログラムの高速化
斜めの利き筋は、行と列の位置を足す、または行から列を引くと一定の値になることを利用してチェックしています。斜めの利き筋を配列 (リスト) にセットしておけば、もっと簡単にチェックすることができます。右斜め上の利き筋を rs, 左斜め上の利き筋を ls で表すことにすると、(x, y) にクイーンを置いた場合は次のようにセットします。
rs[x + y] = true ls[x - y + n - 1] = true
n は盤面の大きさ (クイーンの個数) です。バックトラックするときはリセットすることをお忘れなく。プログラムは次のようになります。
リスト : N Queens Problem (高速化その２)
def nqueens1(f, n, xs, ls, rs, m = 0):
if m == n:
f(xs)
else:
for i in range(m, len(xs)):
if rs[m + xs[i]] or ls[m - xs[i] + n - 1]: continue
rs[m + xs[i]] = True
ls[m - xs[i] + n - 1] = True
xs[i], xs[m] = xs[m], xs[i]
nqueens1(f, n, xs, ls, rs, m + 1)
xs[i], xs[m] = xs[m], xs[i]
rs[m + xs[i]] = False
ls[m - xs[i] + n - 1] = False
def solver1(f, n, xs):
nqueens1(f, n, xs, [False] * (2 * n), [False] * (2 * n))
プログラムは、とくに難しいところはないので、説明は割愛します。詳細はリストをお読みくださいませ。
実行結果を示します。
表 : 実行結果 (時間 : 秒)
個数 : 10 : 11 : 12 : 13 : 14
-----+------+-------+-------+-------+--------
解 : 724 : 2680 : 14200 : 73712 : 365596
(0) : 1.67 : 18.46 : ----- : ----- : ------
(1) : 0.02 : 0.08 : 0.36 : 2.03 : 12.20
(2) : 0.01 : 0.04 : 0.15 : 0.87 : 5.10
実行環境 : PyPy3, Ubunts 18.04 (WSL), Intel Core i5-6200U 2.30GHz
N = 14 で約 2.5 倍の高速化に成功しました。でも、まだまだ遅いですね。
●ビット演算による高速化
次はビット演算を使って高速化する方法を紹介します。オリジナルは Jeff Somers さんのプログラムですが、高橋謙一郎さん が再帰を使って書き直したプログラムを Ｎクイーン問題（解の個数を求める） で発表されています。今回は高橋さんのプログラムを参考にさせていただきました。高橋さんに感謝します。
プログラムのポイントは、斜めの利き筋のチェックをビット演算で行うことです。次図を見てください。
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
*-------------
図 : 斜めの利き筋のチェック
クイーンの位置をビットオンで表すことします。上図のように 0 列目の 4 番目にクイーンを置いた場合、クイーンの位置は第 4 ビットをオンにした値 0x10 となります。
次に、斜めの利き筋を考えます。上図の場合、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 (高速化その３)
def nqueens2(f, n, xs, left = 0, right = 0, m = 0):
if m == n:
f(xs)
else:
for i in range(m, len(xs)):
bit = 1 << xs[i]
if (left | right) & bit != 0: continue
xs[i], xs[m] = xs[m], xs[i]
nqueens2(f, n, xs, (left | bit) << 1, (right | bit) >> 1, m + 1)
xs[i], xs[m] = xs[m], xs[i]
関数 nqueens2() の引数 right が右斜め上の利き筋、left が左斜め上の利き筋を表します。そして、xs から斜めの利き筋にあたらないクイーンの位置 (bit) を選びます。nqueens2() を再帰呼び出しするときは、right と left にクイーンの位置をセットして、それを 1 ビットシフトします。right と left は局所変数なので、元の値に戻す処理は必要ありません。あとは、とくに難しいところはないでしょう。詳細はプログラムリストをお読みください。
実行結果を示します。
表 : 実行結果 (時間 : 秒) 個数 : 10 : 11 : 12 : 13 : 14 -----+------+-------+-------+-------+-------- 解 : 724 : 2680 : 14200 : 73712 : 365596 (0) : 1.67 : 18.46 : ----- : ----- : ------ (1) : 0.02 : 0.08 : 0.36 : 2.03 : 12.20 (2) : 0.01 : 0.04 : 0.15 : 0.87 : 5.10 (3) : ---- : 0.03 : 0.14 : 0.72 : 4.22 実行環境 : PyPy3, Ubunts 18.04 (WSL), Intel Core i5-6200U 2.30GHz
実行速度は速くなりましたが、それほど大きな効果はないようです。Python のようなスクリプト言語ではなく、ネイティブコードにコンパイルするプログラミング言語では、もっと大きな効果がありました。興味のある方は以下に示す拙作のページをお読みください。
●プログラムリスト
#
# nqueens.py : N Queens Prolblem
#
# Copyright (C) 2022 Makoto Hiroi
#
import time
# 順列の生成
# xs に格納されている要素を n を選ぶ
def permutations(f, n, xs, m = 0):
if m == n:
f(xs[:m])
else:
for i in range(m, len(xs)):
xs[i], xs[m] = xs[m], xs[i]
permutations(f, n, xs, m + 1)
xs[i], xs[m] = xs[m], xs[i]
# 斜めの利き筋
def conflict(b, y, x):
for x1 in range(x):
y1 = b[x1]
if x1 - y1 == x - y or x1 + y1 == x + y:
return True
return False
# クイーンは安全か
def is_safe(b):
for x in range(1, len(b)):
if conflict(b, b[x], x): return False
return True
# 単純な生成検定法
def solver0(size):
def check(b):
if is_safe(b): print(b)
permutations(check, size, list(range(size)))
def test0():
def check(b):
nonlocal cnt
if is_safe(b): cnt += 1
for n in range(8, 12):
cnt = 0
s = time.time()
permutations(check, n, list(range(n)))
e = time.time()
print(n, cnt, e - s)
# 無駄な順列生成を省く
def nqueens(f, n, xs, m = 0):
if m == n:
f(xs)
else:
for i in range(m, len(xs)):
if conflict(xs, xs[i], m): continue
xs[i], xs[m] = xs[m], xs[i]
nqueens(f, n, xs, m + 1)
xs[i], xs[m] = xs[m], xs[i]
# 高速化
def nqueens1(f, n, xs, ls, rs, m = 0):
if m == n:
f(xs)
else:
for i in range(m, len(xs)):
if rs[m + xs[i]] or ls[m - xs[i] + n - 1]: continue
rs[m + xs[i]] = True
ls[m - xs[i] + n - 1] = True
xs[i], xs[m] = xs[m], xs[i]
nqueens1(f, n, xs, ls, rs, m + 1)
xs[i], xs[m] = xs[m], xs[i]
rs[m + xs[i]] = False
ls[m - xs[i] + n - 1] = False
def solver1(f, n, xs):
nqueens1(f, n, xs, [False] * (2 * n), [False] * (2 * n))
# ビット操作による高速化
def nqueens2(f, n, xs, left = 0, right = 0, m = 0):
if m == n:
f(xs)
else:
for i in range(m, len(xs)):
bit = 1 << xs[i]
if (left | right) & bit != 0: continue
xs[i], xs[m] = xs[m], xs[i]
nqueens2(f, n, xs, (left | bit) << 1, (right | bit) >> 1, m + 1)
xs[i], xs[m] = xs[m], xs[i]
# 時間計測
def test(func):
def check(b):
nonlocal cnt
cnt += 1
for n in range(8, 15):
cnt = 0
s = time.time()
func(check, n, list(range(n)))
e = time.time()
print(n, cnt, e - s)
改訂 2022 年 11 月 19 日