本記事は、ソフトバンクパブリッシングから発行されている「」を参考にPythonでアルゴリズムとデータ構造について学習していきます。
今回は、前回で学んだ8クイーン（Eight Queens Puzzle）からすべての解を求める方法について学んでいきます。
8クイーン問題とは
8クイーン（Eight Queens Puzzle：エイト・クイーン）とは、チェス盤と駒のクイーンを使ったパズルのことを言います。
クイーンは、将棋でいう飛車と角を合わせた動きが可能で、以下のように移動することができます。
そして、どのように8つのクイーンを互いに利いていない場所に配置していくかを考えるのが、今回の8クイーン問題になります。
1848年にMax Bezzelが発表し、数学者のC.F.Gauss（有名なガウスです）などもこの問題に挑戦しましたが、数学的な解法は見つかっておらず、一つ一つ盤上の駒と駒の関係を確かめながら解いていくしかないようです。
Pythonで8クイーンを作成
それでは、Pythonで8クイーン問題のすべての解を求めるスクリプトを作成します。
# 8queens_all.py
from copy import deepcopy
SUCCESS = 1
FAIL = 0
FREE = 1
NOT_FREE = 0
N = 8
class Queens:
def __init__(self):
self.pos = [-1 for _ in range(N)]
self.col = [FREE for _ in range(N)]
self.up = [FREE for _ in range(2*N-1)]
self.down = [FREE for _ in range(2*N-1)]
self.count = 0
self.answer = {}
def print_queens(self, pos):
for i in range(N):
for j in range(N):
if pos[i] == j:
print("Q ", end="")
else:
print(". ", end="")
print()
print("---------------")
def put_queen(self, a):
for b in range(N):
if self.col[b] == FREE and self.up[a+b] == FREE and \
self.down[a-b+(N-1)] == FREE:
self.pos[a] = b
self.col[b] = NOT_FREE
self.up[a+b] = NOT_FREE
self.down[a-b+(N-1)] = NOT_FREE
if a + 1 >= N:
self.count += 1
pos = deepcopy(self.pos)
self.answer[self.count] = pos
else:
self.put_queen(a+1)
self.pos[a] = -1
self.col[b] = FREE
self.up[a+b] = FREE
self.down[a-b+(N-1)] = FREE
def run(self):
self.put_queen(0)
if self.count:
print("Found {} solutions.".format(self.count))
else:
print("Sorry, but there is no solution.")
if __name__ == '__main__':
q = Queens()
q.run()
for k in q.answer.keys():
q.print_queens(q.answer[k])
動作確認
それでは上記で作成したスクリプトを実行してみます。
> python 8queens_all.py Found 92 solutions. Q . . . . . . . . . . . Q . . . . . . . . . . Q . . . . . Q . . . . Q . . . . . . . . . . . Q . . Q . . . . . . . . . Q . . . . --------------- Q . . . . . . . . . . . . Q . . . . . . . . . Q . . Q . . . . . . . . . . . Q . . . . Q . . . . . Q . . . . . . . . . . Q . . . --------------- ... --------------- . . . . . . . Q . . . Q . . . . Q . . . . . . . . . Q . . . . . . . . . . Q . . . Q . . . . . . . . . . . . Q . . . . . Q . . . ---------------
8クイーンでは12種類の基本解があり、そのうち11種類は8つの変形があり、残りの1種類は4つの変形があるため、合計で の解が存在します。
また、 のチェス盤に
個のクイーンを配置するものをnクイーンと言います。
参考書籍
定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)
