８人の女王（再帰呼び出し，バックトラック，matplotlibアニメーション）
Python3(3.10)で動くソースコード（.pyファイル .ipynbファイル）あります
「anaconda3」on .py「PyCharm」.ipynb「Jupyter Notebook」
パズル「８人の女王」は盤上に女王のコマを置いていき，人間の試行のように順序よく確認していく解き方が一番である。
このような場合は，バックトラックのアルゴリズムが一番簡単で確実です。そして，バックトラックは再帰呼び出しにするのがアルゴリズムが判りやすくなります。
左上隅からダウンロードできるプログラムの1つが，解を見つけるたびに出力して表示するもの。もう1つは女王のコマを置くことができる盤面を記憶しておきそれをアニメーションで見せるものです。
アニメは，matplotlibのArtistAnimationを使います。女王のコマを置くことができる盤面を保存して貯めておき，メインルーチンでArtistAnimationからそれを呼ぶだけです。ArtistAnimationの使い方は簡単ですのでアニメの解説は省略します。
再帰呼び出しを使うバックトラックは2つのプログラムでまったく同じものです。そのアルゴリズムを詳細に解説します。
◆◆パズル「８人の女王」◆◆
チェス盤（８×８）に，８人の女王をお互いに取り合わないように置いてください。
女王は嫉妬深いので，そのタテ・ヨコ・ナナメのライン（将棋の飛車と角）には，他の女王は置けません。
女王は嫉妬深いので，そのタテ・ヨコ・ナナメのライン（将棋の飛車と角）には，他の女王は置けません。
（2023-11-14）Python3.10で動作確認済み
◆◆８人の女王のtkinterアニメーションはこちらのWeb◆◆
トップページに戻ってもらえば判るが，同じパズルをtkinterアニメーションで見られるようになっている。
https://yamakatsusan.web.fc2.com/hp_software/python06.html
『８人の女王 Python3で動くソースコードあります Tkinterによるアニメーションの試行が人間思考と同じ』
◆◆バックトラックに使う再帰呼び出しとは◆◆
再帰呼び出し（recursive call）とは，次のようなものである。
・自分で自分を定義する
・自分が自分を呼び出す
簡単な例として階乗がある。次のように階乗を階乗で定義しているのである。
N ! = N×(N-1) !
これをプログラムすると，N ! を計算している途中で(N-1) ! の計算が始まることになる。単純にサブルーチンが自分を読んでしまうと計算途中のデータが破壊されてしまう。
これを解決するには，サブルーチンを再入可能（reentrant）な構造にすればよい。
再入可能な再帰呼び出しとバックトラックが実際にどのような構造になるのかはアルゴリズムの中で説明する。
◆◆バックトラック・アルゴリズム◆◆
１．イニシャライズする ２．ＣＡＬＬ ＳＵＢ（１番目のステップ） ３．ＥＮＤ ＳＵＢ（Ｎ番目のステップ） １．ＷＨＩＬＥ 方法がまだある Ａ．次の方法を探す Ｂ．ＩＦ その方法が可能なら ＴＨＥＮ １．その方法を実行する ２．ＩＦ ゴールに達したなら ＴＨＥＮ Ａ．解を出力する ３．ＥＬＳＥ Ａ．ＣＡＬＬ ＳＵＢ ４．その方法を取り消す ２．ＲＥＴＵＲＮ
命令文の簡単な説明は次である（特定の言語と関係ない）。
ＣＡＬＬ文はサブルーチンコールである。ＳＵＢは再入可能とする。ＷＨＩＬＥ文は，条件が満足すればループする（このプログラムではＲＥＴＵＲＮ文の前まで）。ＩＦ ＴＨＥＮ ＥＬＳＥ文は，条件が満足か否かにより分岐する。
下から３行目に再帰呼び出しがある。
再帰呼び出しするためには，再入可能でなければならない。
これを実現するために，もう少し詳細なアルゴリズムを説明する。
◆◆「８人の女王」の詳細アルゴリズム◆◆
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
Main ８人の女王
イニシャライズ
Gosub EightQueens
End Main
Sub EightQueens:
Y=1
While Y <= 8:
Yを1～8まで順に選択
試行の計算
If 干渉がなく置くことができるなら Then
仮に実行して結果を記録する
If X=8なら Then
解を出力
Else
Stackに保存する
Stack Pointer１増
X=X+1
Gosub EightQueens（recursiveなcall）
次のステップがもうなく戻ってきた
試行を取り消す
Y=Y+1
Else
Stackがまだ残っていれば
Stack Pointer１減
Stackから戻す
Return
再帰的ＣＡＬＬ文は16～19行目で，再帰的ＲＥＴＵＲＮ文は24～27行目で実現している。ＷＨＩＬＥ文が終わるとＥＬＳＥ文が実行される。
７行目の変数 Y は試行方法である。
「８人の女王」では，マス目の番号（座標）である。Python の配列では 0～7 となる。
ループの先頭で，ある方法を試行し，成功すればさらに再帰的に試行し，失敗すればその試行を破棄しループの先頭に戻る。これを繰り返すのである。
ある試行が成功しかつ問題全体が成功したら解を出力する。
実際のコードは巻末を見てください。
◆◆「８人の女王」の解◆◆
巻末の Python のソースコードをドラッグして開発環境にコピペしてrunさせればよい。解の図を表示して一時停止する。「×」をクリックすれば次の解を計算する。解は92コある。
92コの解のうち最初の解の図を示す。
◆◆「８人の女王」の Python のソースコードと92コの解◆◆
次がPython のソースコードである。ドラッグして開発環境にコピペしてrunさせることができる。上に詳細アルゴリズムを表示しているので改めて説明は不要であろう。
解の配列を別のモジュールが使うときのために98行目の return文に戻り値をつけてある。94行目の関数を呼べば関数値となる。
チェス盤に8人のクィーンの置き方のパターンは 8**8 = 16,777,216 通りある。アニメーションプログラムに渡せる数ではない。92コの解を渡してもアニメーションはつくれないので，アニメーションにするためには再帰呼び出しを使わないバックトラックを実装しなければならない。それは冒頭に紹介した。
42行目で解を表示する関数Solutionを呼んでいる。92コの解をいっぺんにを表示する関数Solutionは69行目にある。解のグラフを表示するには 86行目と92行目のコメントアウトを外します。
92コの解はここに表示しきれないので実際にプログラムをrunさせて確認してください。すべての解は最後に表示されます。
◆◆ソースコード◆◆
このWebページの左上隅からダウンロードできます。
ソースファイルは1つです。
・8queens3X.py；８人の女王の解法（解を見つけるたびに表示する）
・8queens3X.ipynb；上のJupyter Notebook版
・8queens_ArtistAnimation.ipynb；matplotlibのArtistAnimation
【8queens3X.py】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103
# -*- coding: utf-8 -*-
# EithtQueens
import numpy as np
import matplotlib.pyplot as plt
import sys
# Initialize
Num = 1 # 試行の回数
NumDebug = 0 # debug用
# 過去の試行パターンの記録
Old = [[0 for i in range(8)] for j in range(8)]
Xpos = 0
NumSolution = 1
RowIsFull = [0 for col in range(8)]
UpIsFull = [0 for col in range(15)]
DownIsFull = [0 for col in range(15)]
StackYpos = [0 for col in range(8)] # スタック
StackXpos = [0 for col in range(8)]
StackPointer = 1 # スタックポインタ
sol = []
def QueensLayout():
"""メインなサブルーチン
"""
global Num, NumDebug, Ypos, Xpos, NumSolution
global Old, RowIsFull, UpIsFull, DownIsFull
global StackPointer, StackYpos, StackXpos
Ypos = 0
while Ypos <= 7:
# あるXposにおいてYposを順に試みる
if RowIsFull[Ypos] == 0 and UpIsFull[Xpos - Ypos + 7] == 0 \
and DownIsFull[Xpos + Ypos] == 0:
# 干渉がなく置くことができるなら仮に試みる
NumDebug += 1
Old[Xpos][Ypos] = 1
RowIsFull[Ypos] = 1
UpIsFull[Xpos - Ypos + 7] = 1
DownIsFull[Xpos + Ypos] = 1
# Progress(Num) # 途中経過を表示する
# print raw_input(u'女王を置くことができる')
if Xpos == 7:
Solution(Num) # 解を発見
NumSolution += 1
# print raw_input(u'解を発見')
else:
# 次のステップに進める
StackYpos[StackPointer] = Ypos
StackXpos[StackPointer] = Xpos
StackPointer += 1
Xpos += 1
QueensLayout() # recursiveなcall
# 次のステップがもうなく戻ってきた
RowIsFull[Ypos] = 0
UpIsFull[Xpos - Ypos + 7] = 0
DownIsFull[Xpos + Ypos]= 0
Old[Xpos][Ypos] = 0
Num -= 1
# 同じXposで次のYposを試みる準備
Ypos += 1
# while文の終了
else: # while文の終了後に実行
# recursiveなreturn
StackPointer
if StackPointer != 1:
StackPointer -= 1
Ypos = StackYpos[StackPointer]
Xpos = StackXpos[StackPointer]
def Solution(Num):
"""解を表示
"""
global sol
x = [0.5, 1.5, 2.5, 3.5, 4.5, 5.5, 6.5, 7.5]
y = [0 for col in range(8)]
Ysol = [0 for col in range(8)]
for i in range(8):
for j in range(8):
if Old[i][j] == 1:
y[i] = j + 0.5
Ysol[i] = j
sol = sol + [Ysol]
# チェス盤を表示
# print(input(u'「OK」続行：グラフの「×」をクリック，「Cancel」終了'))
plt.plot(x, y, 'o', markersize=30)
plt.xlim([0,8])
plt.ylim([0,8])
plt.grid()
plt.show()
def main_8queens():
"""main program
"""
QueensLayout()
return sol
if __name__ == "__main__":
sol_8queens = main_8queens()
print(sol_8queens)