【出典】「新・明解Pythonで学ぶアルゴリズムとデータ構造」
前回の記事はこちら
5-4 8王妃問題
今回もハノイの塔と同様に、問題を小さく分割することで8王妃問題を学習します。
8王妃問題とは
互いに取りあえないように、8個の王妃(チェスのクイーン)をチェス盤に配置せよ。という問題です。
王妃の配置
8個の王妃を配置する組み合わせは全部で、64×63×62×61×60×59×58×57=178462987637760通りあります。そこで、
【方針1】各列には王妃を1個だけ配置する
とすると、8の8乗=16777216通りになります。
これでも、すべての配置が8王妃問題の会ではありません。
そこで、
【方針2】各行には王妃を1個だけ配置する
とします。
分枝操作
次々と枝分かれを行うことによって、すべての組み合わせを列挙するプログラムを作ります。
#各列に1個の王妃を配置する組み合わせを再帰的に列挙
pos = [0] * 8 #各列の王妃の位置
def put() -> None:
"""盤面(各列の王妃の位置)を出力"""
for i in range(8):
print(f'{pos[i]:2}', end=' ')
print()
def set(i: int) -> None:
"""j列目に王妃を位置"""
for j in range(8):
pos[i] = j #王妃をj行に配置
if i == 7: #全列に配置終了
put()
else:
set(i + 1) #次の列に王妃を配置
set(0) #0列目に王妃を配置
次々と枝分かれを行っていくことによって、配置の組み合わせを列挙する手法を分枝操作といいます。
また、ハノイの塔や、8王妃問題のように問題を小問題に分割し、小問題の解を統合して全体の解を得ようとする手法を、分割統治法と呼びます。
限定操作と分枝限定法
先ほどは列挙しただけで、解を得ることはできません。そこで【方針2】の考えを組み入れます。
# 各行・各列に1個の王妃を配置する組み合わせを再帰的に列挙
pos = [0] * 8 #各列の王妃の位置
flag = [False] * 8 #各行に王妃が配置済みか
def put() -> None:
"""盤面(各列の王妃の位置)を出力"""
for i in range(8):
print(f'{pos[i]:2}', end=' ')
print()
def set(i: int) -> None:
"""j列目に王妃を位置"""
for j in range(8):
if not flag[j]: #j行には王妃は未配置
pos[i] = j #王妃をj行に配置
if i == 7: #全列に配置終了
put()
else:
flag[j] = True
set(i + 1) #次の列に王妃を配置
flag[j] = False
set(0) #0列目に王妃を配置
新たに flagというlist型の配列を導入しており、同一行に重複して王妃を配置しないようにするための目印です。
配置済みであればflag[j]をTrue、未配置であれば、Falseとします。
関数setでは、王妃が未配置の行(flag[j]がFalseである行)に対してのみ王妃を配置していきます。このように必要のない枝分かれを抑制して、不要な組み合わせの列挙を省く手法を限定操作と呼び、分枝操作と組み合わせて問題を解くのが、分枝限定法です。
8王妃問題を解くプログラム
list5-8のプログラムは、王妃が行方向と列方向に重複しない組み合わせを列挙しました。ここで、斜め方向にも1つしか配置できないように限定操作の追加採用が必要になります。
#8王妃問題
pos = [0] * 8 #各列の王妃の位置
flag_a = [False] * 8 #各行に王妃が配置済みか
flag_b = [False] * 15 #右上がりの対角線に王妃が配置済みか
flag_c = [False] * 15 #右下がりの対角線に王妃が配置済みか
def put() -> None:
"""盤面(各列の王妃の位置)を出力"""
for i in range(8):
print(f'{pos[i]:2}', end=' ')
print()
def set(i: int) -> None:
"""j列目に王妃を位置"""
for j in range(8):
if ( not flag_a[j] #j行には王妃は未配置
and not flag_b[i + j] #右上がり対角線に王妃は未配置
and not flag_c[i - j + 7]): #右下がり対角線に王妃は未配置
pos[i] = j #王妃をj行に配置
if i == 7: #全列に配置終了
put()
else:
flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = True
set(i + 1) #次の列に王妃を配置
flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = False
set(0) #0列目に王妃を配置
数字だけだとイメージが付きづらいため盤面に合わせるような改良をしたのが次になります。
pos = [0] * 8 #各列の王妃の位置
flag_a = [False] * 8 #各行に王妃が配置済みか
flag_b = [False] * 15 #右上がりの対角線に王妃が配置済みか
flag_c = [False] * 15 #右下がりの対角線に王妃が配置済みか
def put() -> None:
"""盤面を□と■で出力"""
for j in range(8):
for i in range(8):
print('■' if pos[i] == j else '□', end=' ')
print()
print()
def set(i: int) -> None:
"""j列目に王妃を位置"""
for j in range(8):
if ( not flag_a[j] #j行には王妃は未配置
and not flag_b[i + j] #右上がり対角線に王妃は未配置
and not flag_c[i - j + 7]): #右下がり対角線に王妃は未配置
pos[i] = j #王妃をj行に配置
if i == 7: #全列に配置終了
put()
else:
flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = True
set(i + 1) #次の列に王妃を配置
flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = False
set(0) #0列目に王妃を配置
一見すると頭が混乱するのですが、再帰呼び出しをした際どのように処理が行われるかしっかり考えれば何とか理解できそうです。
ただ、ゼロからこういったコードがスラスラ書けるようになるかといわれるとまだまだ先は長そうです…。
これで、第5章が終了です。
ありがとうございました。