８人の女王 tkinterアニメーションで人間の試行のように見せる
再起呼び出しを使わないバックトラックアルゴリズムで解く
Python3(3.10)で動くソースコード（.pyファイル .ipynbファイル）あります
「anaconda3」on .py「PyCharm」.ipynb「Jupyter Notebook」
◆◆パズル「８人の女王」◆◆
チェス盤（８×８）に，８人の女王をお互いに取り合わないように置いてください。
女王は嫉妬深いので，そのタテ・ヨコ・ナナメのライン（将棋の飛車と角）には，他の女王は置けません。
女王は嫉妬深いので，そのタテ・ヨコ・ナナメのライン（将棋の飛車と角）には，他の女王は置けません。
（2023-11-14）Python3.10で動作確認済み
◆◆ソースファイル◆◆
このWebの左上隅からダウンロードできます。
巻末のソースコードをドラッグしてコピペすればソースファイルがつくれます。もう一つ画像ファイルが必要です。次の画像をダウンロードしてまたは左上隅からダウンロードしてファイル名を「queen.png」とする。背景を透明にする（してあるはず）。この画像はソースファイルと同じディレクトリに置く。
◆◆バックトラックは使っていない◆◆
パズル「８人の女王」は Prolog で10行程度で解けるが，それは再帰呼び出しによるバックトラック・アルゴリズムを使っているからだ。
Python のような手続型言語で再帰呼び出しによるバックトラック・アルゴリズムを使うと少し長くなる。実際にrunするソースコードは次を参照してほしい。
https://yamakatsusan.web.fc2.com/hp_software/python05.html
『８人の女王 再帰呼び出しとバックトラックのアルゴリズム』
巻末のソースコードと上のWebのソースコードを比べてほしい。Tkinterによるアニメーションを実現するために再帰呼び出しが必要であるため，パズルを解くために再帰呼び出しによるバックトラックを使うことができない。
８人の女王をチェス盤に置くためのアルゴリズムは62行目から100行目に書かれている。まず，最初の列の最初のマスにコマを置く。そしてその横マス，右斜めマス，左斜めマスを置けないラインとして登録する。登録できたら次の列を試行する。３つめのマスに置くことができるのでまた置けないラインを登録する。
ある列の８つのマスの試行が失敗すると列を戻してそのコマを進めて同じことを繰り返す。このアルゴリズムは人間の思考（試行？）と同じである。何ら特別の技法を使っていない。コマを置くマスの位置が「row_put」「col_put」であり，これを基に解とアニメーションを表示している。
◆◆Tkinterによるアニメーション◆◆
Python のアニメーションのライブラリはいくつかあるらしいが，そのうち Tkinter がいいらしい（まったくのうけうり）。
Tkinter によるチェス盤のつくり方は次のサイトをマネさせてもらった。
http://www.shido.info/py/tkinter9.html
『9. ボードゲーム用 GUI を作ろう 』
Tkinter によるアニメーションやパズル「８人の女王」を解くアルゴリズムは私のオリジナルである。巻末に実際にrunするソースコードが掲載されている。
上のサイトの「8queens.py」はパズルを解いているのではなく解は外部ファイルから読み込んでいて，チェス盤に12の解を書き込んでいるだけである。実際に解くアルゴリズムは外部ファイル「queen.py」にあり，簡潔なアルゴリズムと見事な Python の技法で書かれている。
それに比べて，私のソースコードは Python 特有の技法はまったく使っていなく，言語に依存しないまるで疑似コードで書いたようなそれでいて人間の思考どおりの論理的な書き方になっている。
アニメーションのコマ送り間隔は，10行目で設定できる。1以上を設定すること。1秒（設定は 1000）以上にすると試行に人間の思考が追い付ける。
◆◆Tkinter.Canvasによるチェス盤◆◆
チェス盤は画像ではなくプログラムによって描かれている。チェス盤を書くのは「class Cboard」であり親クラス「Tkinter.Canvas」を継承している。import時に二つ名「Tk」を使っているので「Tk.Canvas」となる。これの詳細な使い方は上のサイトを参照してほしい。
チェス盤は22行目からのコンストラクタでつくっている。もちろん親クラスのコンストラクタを24行目で継承している。インスタンス変数の初期値設定を除いてこのメソッドがチェス盤をつくる。
クラスを使ったことのない人のために念のために言っておくと，「class Cboard」はチェス盤のテンプレート（型枠）に過ぎず，実際にチェス盤を描くにはテンプレート（型枠）から実際に中身をつくらなければならない。それが116行目で「class Cboard」をインスタンス化（具体化）してその中身を「f_board」と名付けた。
そのあとさらにチェス盤を具体化していくのだが，ほとんどが「class Cboard」の親クラスを参照しているのだ。その詳細は私には説明できないので上のサイトを参照してほしい。
◆◆Tkinterの使い方◆◆
クラスを使ったことのない人のために念のために言っておくと，クラスをつくっただけではプログラムはrunしない。Python 特有のプログラムの run する方法が144行目以降に書かれている。146，147行目は Tkinter のメソッドを呼び出している（上手く説明できない）。
Tkinterの使っているときはこの典型的な呼び出しを必ず使う。私は機械的にマネしているだけだが上手くいっている。
◆◆ソースコード◆◆
このWebページの左上隅からダウンロードできます。
ソースファイルは2つです。
・8queensanimation.py；8人の女王の解法とアニメーションの両方が入っています
・queen.png；アニメーション用のコマです
最初の解答は冒頭の図である。
【8queensanimation3X.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 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147
# -*- coding: utf-8 -*-
"""
8 queens animation
"""
import tkinter as Tk
import time
Q_font = ("Times", 14)
Timer = 1 # ミリ秒；アニメ更新間隔（1以上を設定）
def move_queen(now, next):
return [(i, z1-z0) for i,
(z0, z1) in enumerate(zip(now, next)) if z0 != z1]
class Cboard(Tk.Canvas):
cell_size = 46
margin = 5
q_images = []
q_figure = []
def __init__(self, master):
cwidth = 8*self.cell_size
Tk.Canvas.__init__(self, master, relief=Tk.RAISED, bd=4, bg='white',
width=cwidth, height=cwidth)
self.put_next = [0, 0, 0, 0, 0, 0, 0, 0]
self.put_now = [0, 0, 0, 0, 0, 0, 0, 0]
self.row_put = -1
self.col_put = 0
self.rowfull = [0 for i in range(8)]
self.upfull = [0 for i in range(15)]
self.downfull = [0 for i in range(15)]
for i in range(8):
for j in range(8):
bcolor = (i-j)%2==0 and "#E8B77D" or "#A06040"
x0 = i*self.cell_size + self.margin
y0 = j*self.cell_size + self.margin
self.create_rectangle(x0, y0, x0+self.cell_size,
y0+self.cell_size, fill=bcolor, width=0)
self.q_images.append(Tk.PhotoImage(file="queen.png"))
x = self.cell_size*(i+0.5) + self.margin
y = 28.0
self.q_figure.append(self.create_image
(x, y, image=self.q_images[i], tags="queen"))
def check_full(self, row, col):
return self.rowfull[row] == 0 and \
self.upfull[col - row + 7] == 0 and \
self.downfull[col + row] == 0
def set_full(self, row, col):
self.rowfull[row] = 1
self.upfull[col - row + 7] = 1
self.downfull[col + row] = 1
def reset_full(self, row, col):
self.rowfull[row] = 0
self.upfull[col - row + 7] = 0
self.downfull[col + row] = 0
def refresh(self, num_sol):
"""クィーンを動かす
"""
# まず最初にクィーンを下に動かす
self.row_put += 1
self.put_next[self.col_put] = self.row_put
if self.row_put == 8:
# クィーンが下にはみ出したら列を戻す
self.col_put -= 1
self.row_put = self.put_now[self.col_put]
self.reset_full(self.row_put, self.col_put)
return False
# print self.put_next, self.put_now # debug用
# print self.row_put, self.col_put, '-' #
# クィーンを置く
for i, j in move_queen(self.put_now, self.put_next):
self.move(self.q_figure[i], 0, j*self.cell_size)
# 今の位置を次の位置に更新する
for k in [0,1,2,3,4,5,6,7]:
self.put_now[k] = self.put_next[k]
if self.check_full(self.row_put, self.col_put):
# クィーンを置くことができるなら
self.put_next[self.col_put] = self.row_put
self.set_full(self.row_put, self.col_put)
if self.col_put == 7:
# 解発見
print(self.put_now) # 解出力
self.reset_full(self.row_put, self.col_put)
self.col_put = 6
self.row_put = self.put_now[self.col_put]
self.reset_full(self.row_put, self.col_put)
return True
else:
# 次の列を始める
self.col_put += 1
self.row_put = -1
return False
class Queen(Tk.Frame):
def __init__(self, master=None):
Tk.Frame.__init__(self, master)
self.master.title("8 Queens")
# title
l_title = Tk.Label(self, text='8 Queens',
font=('Times', '24', ('italic', 'bold')),
fg='#191970', bg='#E8B77D', width=12)
l_title.pack(padx=10, pady=10)
# chess board
self.f_board = Cboard(self)
self.f_board.pack(padx=10, pady=10)
# buttons and a counter
self.q_counter = 0
self.f_footer = Tk.Frame(self)
self.f_footer.pack()
self.s_counter = Tk.StringVar()
self.s_counter.set("%d/92" % (1 + self.q_counter))
self.a_button = Tk.Button(self.f_footer, text="next",
font=Q_font, command = self.show_next)
self.a_button.pack(side=Tk.LEFT, padx=5,pady=5)
self.f_label = Tk.Label(self.f_footer,
textvariable = self.s_counter, font=Q_font)
self.f_label.pack(side=Tk.LEFT, padx=5, pady=5)
def show_next(self):
sol = self.f_board.refresh(self.q_counter)
if sol:
self.change_counter(1)
return
self.after(Timer, self.show_next)
def change_counter(self, i):
self.q_counter += i
self.s_counter.set("%d/92" % (1 + self.q_counter))
if __name__ == "__main__":
app = Queen()
app.pack()
app.mainloop()