1. 動機
64個のマスの中に8つの駒を配置するというシンプルなルールのパズルであり，総当たりで解くことが可能だと考えたこと．
2. 8Queenについて
チェス盤上に8つのクイーンを，どの駒も他の駒に取られないように配置するパズルである．クイーンは，盤上で上下・左右・斜め（右上，右下，左上，左下）の8方向に障害物がない限り任意の距離進むことができる．
3. チェス盤の座標表現方法
チェス盤の座標は，行（ランク）と列（ファイル）を用いて表す．ランクは下から1, 2, 3, ..., 8で，ファイルは左からa, b, c, ..., hである．
4. 実装
各クイーンの位置を把握する必要があるので，まず file と rank をインスタンス変数にもつ Queen クラスを定義します．
class Queen:
def __init__(self, file, rank):
self.file = file
self.rank = rank
クイーンの初期配置を「ファイルa, b, c, ..., hに置かれている各クイーンのランク（クイーンが配置されていないファイルでは0）」として8桁の整数で受け取り，その配置を反映します．0を指定されたファイルについては，1ランクにクイーンを配置します．
def get_initial_positions():
print(
'\nEnter the initial positions of the queens as an 8-digit number.'
'\nEach digit corresponds to a file from a to h in order, and indicates the queen’s rank (1–8, or 0 if no queen is placed).'
'\nFor instance, if queens are placed only on c4 and f2, enter \'00400200\'.'
)
while True:
try:
init_pos = [int(i) for i in input('\nINPUT> ')]
if len(init_pos) == 8 and all(0 <= i <= 8 for i in init_pos):
break
except ValueError:
pass
print('\n[ERROR] Invalid input. Please try again.')
# クイーンの置かれていないファイルとランクを取得する
# 例えば入力が「00400200」なら empty_files = [0, 1, 3, 4, 6, 7], empty_ranks = [0, 2, 4, 5, 6, 7]
empty_files = [i for i, rank in enumerate(init_pos) if rank == 0]
empty_ranks = [i for i in range(8) if i + 1 not in init_pos]
queens = [Queen(file, rank - 1 if rank != 0 else 0) for file, rank in enumerate(init_pos)]
return empty_files, empty_ranks, queens
例えば入力が「00400200」の場合，クイーンを（Q1, Q2, Q3, Q4, Q5, Q6, Q7, Q8）＝（a1, b1, c4, d1, e1, f2, g1, h1）に配置します．
次に，0を指定されたファイルに配置したクイーンを，利きの重複を判定（後述）しながら以下の要領で移動していきます．
（操作）
最も右にあるクイーンを，（＊）に従って移動する．
（＊）
クイーンのランクが7以下の場合，同一ファイル内で1つ上のランクに移動して操作を終了する．
クイーンのランクが8の場合，同一ファイル内の1ランクに移動する．
クイーンを1ランクに移動した場合，その1つ左にあるクイーンも（＊）に従って移動する（繰り上がり）．その結果生じた繰り上がりにも（＊）を適用し続け，繰り上がりが発生しなくなったら終了する．
クイーンは，その rank を変更することで移動できます．以下は，初めに書いたコードです．
# empty_files の要素数を n とする．0以上8 ^ (n - 1) - 1以下の各整数を n 桁の8進数として表し，各クイーンの `rank` に割り当てる
# 例えば empty_files = [0, 1, 3, 4, 6, 7] , i = 500 のとき， 500(10) = 000764(8) より
# [queens[j].rank for j in empty_files] = [0, 0, 0, 7, 6, 4] となる
for i in range(8 ** len(empty_files)):
for j, file in enumerate(reversed(empty_files)):
queens[file].rank = i // (8 ** j) % 8
しかし，クイーンのランクに重複がある配置を調べる必要はありません．そこで， empty_ranks 内の全要素を並べる順列をすべて挙げ，その一つ一つを各クイーンの rank に割り当てるようにして探索効率を高めます．先ほどの例では，Q1, Q2, Q4, Q5, Q7, Q8のランクを（Q1, Q2, Q4, Q5, Q7, Q8）＝（0, 0, 0, 0, 0, 0）から（0, 2, 4, 5, 6, 7），（0, 2, 4, 5, 7, 6），（0, 2, 4, 6, 5, 7），……，（7, 6, 5, 4, 0, 2），（7, 6, 5, 4, 2, 0）と変更していきます．順列を求める関数は標準ライブラリーの itertools に実装されており，これを利用すれば
from itertools import permutations
for pattern in permutations(empty_ranks):
for i in range(len(pattern)):
queens[i].rank = rank
と簡単に書けますが，ここでは自前で実装することにします．さて， $ n $ 個の要素からなるリストを受け取り，その全要素を並べる順列をすべて挙げる関数を作成したいわけですが，これは再帰処理で実現可能です．なぜなら，期待する出力は「要素を $ 1 $ つ選び，その後ろに残り $ n - 1 $ 個の要素を並べる」という操作をすべての要素について行うことで得られるからです．したがって， permutations 関数は以下のように書けます．
def permutations(empty_ranks):
if len(empty_ranks) == 1:
return [empty_ranks]
return [[empty_ranks[i]] + p for i in range(len(empty_ranks)) for p in permutations(empty_ranks[: i] + empty_ranks[i + 1: ])]
クイーンの攻撃判定は，各クイーンの以下の値を使用すれば可能です．
（1）縦： file
（2）横： rank
（3）斜め（左上─右下）： file + rank
（4）斜め（右上─左下）： file - rank
例えば，先ほどの初期配置においてQ3とQ6が互いに取られないことは，
(
queens[2].file != queens[5].file and
queens[2].rank != queens[5].rank and
queens[2].file + queens[2].rank != queens[5].file + queens[5].rank and
queens[2].file - queens[2].rank != queens[5].file - queens[5].rank
)
が True となることにより確認できます．
ある配置が解であるかどうかは
(
len(set([q.rank for q in queens])) == 8 and
len(set([(q.file + q.rank) for q in queens])) == 8 and
len(set([(q.file - q.rank) for q in queens])) == 8
)
により確認できるので，クイーンを移動する度にこれを求めます．
files, ranks, totals, diffs = zip(*[(q.file, q.rank, (q.file + q.rank), (q.file - q.rank)) for q in queens])
# 横の利き，左上─右下の利き，右上─左下の利きが重ならないか確認
if len(set(ranks)) == len(set(totals)) == len(set(diffs)) == 8:
yield files, ranks
また， permutations 関数を自作したついでに，探索の進捗を表示するようにします．
factorial = lambda n: 1 if n < 2 else n * factorial(n - 1); n_patterns = factorial(len(empty_files))
for i, pattern in enumerate(permutations(empty_ranks)):
print(f'\nProgress: {int(i / n_patterns * 100): >2d}%\033[1F', end = '')
for j, k in enumerate(pattern):
queens[empty_files[j]].rank = k
これで解となる配置をすべて求めることができますが，得られる出力は files = (0, 1, 2, 3, 4, 5, 6, 7), ranks = (0, 6, 3, 5, 7, 1, 4, 2) のような形式なので，見やすくするために盤面を表示するようにします．二次元配列 board を用意し， board[i][j] をファイル j + 1 ，ランク 8 - i に対応させます．
def print_solutions():
solutions = list(solve())
print(f'\n{len(solutions)} solution(s) found.') if solutions else print('\nNo solution found.')
for files, ranks in solutions:
# 解は， files = (0, 1, 2, 3, 4, 5, 6, 7), ranks = (0, 6, 3, 5, 7, 1, 4, 2) のような形で得られるので，
# 盤面を表示するためランクが8であるクイーンのファイル，ランクが7であるクイーンのファイル，……を取得する
sorted_files = list(zip(*sorted(zip(ranks, files), reverse = True)))[1]
board = [['Q' if sorted_files[i] == j else '.' for j in range(8)] for i in range(8)]
for i, line in enumerate(board):
print('\n{} {}'.format(8 - i, ' '.join(line)), end = '')
print('\n a b c d e f g h')
最後におまじない if __name__ == '__main__': をつけて完成です．
5. コード
class Queen:
def __init__(self, file, rank):
self.file = file
self.rank = rank
def get_initial_positions():
print(
'\nEnter the initial positions of the queens as an 8-digit number.'
'\nEach digit corresponds to a file from a to h in order, and indicates the queen’s rank (1–8, or 0 if no queen is placed).'
'\nFor instance, if queens are placed only on c4 and f2, enter \'00400200\'.'
)
while True:
try:
init_pos = [int(i) for i in input('\nINPUT> ')]
if len(init_pos) == 8 and all(0 <= i <= 8 for i in init_pos):
break
except ValueError:
pass
print('\n[ERROR] Invalid input. Please try again.')
# クイーンの置かれていないファイルとランクを取得する
# 例えば，入力が「00400200」なら empty_files = [0, 1, 3, 4, 6, 7], empty_ranks = [0, 2, 4, 5, 6, 7]
empty_files = [i for i, rank in enumerate(init_pos) if rank == 0]
empty_ranks = [i for i in range(8) if i + 1 not in init_pos]
queens = [Queen(file, rank - 1 if rank != 0 else 0) for file, rank in enumerate(init_pos)]
return empty_files, empty_ranks, queens
# リスト内の全要素を並べる順列をすべて挙げる
def permutations(empty_ranks):
if len(empty_ranks) == 1:
return [empty_ranks]
return [[empty_ranks[i]] + p for i in range(len(empty_ranks)) for p in permutations(empty_ranks[: i] + empty_ranks[i + 1: ])]
def print_solutions():
solutions = list(solve())
print(f'\n{len(solutions)} solution(s) found.') if solutions else print('\nNo solution found.')
for files, ranks in solutions:
# 解は， files = (0, 1, 2, 3, 4, 5, 6, 7), ranks = (0, 6, 3, 5, 7, 1, 4, 2) のような形式で得られるので，
# 盤面を表示するためランクが8であるクイーンのファイル，ランクが7であるクイーンのファイル，……を取得する
sorted_files = list(zip(*sorted(zip(ranks, files), reverse = True)))[1]
board = [['Q' if sorted_files[i] == j else '.' for j in range(8)] for i in range(8)]
for i, line in enumerate(board):
print('\n{} {}'.format(8 - i, ' '.join(line)), end = '')
print('\n a b c d e f g h')
def solve():
empty_files, empty_ranks, queens = get_initial_positions()
factorial = lambda n: 1 if n < 2 else n * factorial(n - 1); n_patterns = factorial(len(empty_files))
for i, pattern in enumerate(permutations(empty_ranks)):
print(f'\nProgress: {int(i / n_patterns * 100): >2d}%\033[1F', end = '')
for j, k in enumerate(pattern):
queens[empty_files[j]].rank = k
files, ranks, totals, diffs = zip(*[(q.file, q.rank, (q.file + q.rank), (q.file - q.rank)) for q in queens])
# 横の利き，左上─右下の利き，右上─左下の利きが重ならないか確認
if all(len(set(i)) == 8 for i in (ranks, totals, diffs)):
yield files, ranks
if __name__ == '__main__':
print_solutions()
6. 実行結果
Enter the initial positions of the queens as an 8-digit number.
Each digit corresponds to a file from a to h in order, and indicates the queen’s rank (1–8, or 0 if no queen is placed).
For instance, if queens are placed only on c4 and f2, enter '00400200'.
INPUT> 00000000
92 solution(s) found.
8 . . Q . . . . .
7 . . . . . Q . .
6 . . . Q . . . .
5 . Q . . . . . .
4 . . . . . . . Q
3 . . . . Q . . .
2 . . . . . . Q .
1 Q . . . . . . .
a b c d e f g h
...
8 Q . . . . . . .
7 . . . . . . Q .
6 . . . . Q . . .
5 . . . . . . . Q
4 . Q . . . . . .
3 . . . Q . . . .
2 . . . . . Q . .
1 . . Q . . . . .
a b c d e f g h
7. 終わりに
実はかなり前から取り組んでいたのですが，斜め（右上─左下）の攻撃判定を行う方法がなかなか思いつかず，気づけば時間が経ってしまっていました．工夫したのは，順列を用いて探索対象の配置を絞っている点で，これにより解を高速に求めることができるようになっています．