８人の女王：アニメーションでないtkinterのきれいな絵
ベテラン紫藤氏のPythonらしいコードを巧みなデバッグで解析する
Python3(3.10)で動くソースコード（.pyファイル .ipynbファイル）あります
「anaconda3」on .py「PyCharm」.ipynb「Jupyter Notebook」
見事なPythonの技法と見事なアルゴリズムを紹介する。特に再帰呼び出しの使い方が素晴らしくお薦めである。次のWebは Python の超ベテランがつくったと思われるプログラムがダウンロードできる。
http://www.shido.info/py/tkinter9.html
『9. ボードゲーム用 GUI を作ろう 』
（2023-11-14）Python3.10で動作確認済み
このWebは紫藤氏のサイトであり，題材はパズル「８人の女王」である。このWebから2つのソースファイルがダウンロードできる。1つはパズル「８人の女王」の解答プログラム，もう1つはチェス盤の描画プログラムである。
描画プログラムについては私のこのサイトの別記事で大いに参考にさせてもらった。描画には Tkinter が使われていて，私の別記事ではさらに発展させてアニメーションにしてある。
解答プログラムは私の別記事で参考にしたわけではないが，これを徹底的に解析して解説しようと試みる。実際に run させながら解析するのでデバッグの勉強にもなると思う。最近の開発環境IDEのデバッグ機能を使わなくても巧みなデバッグができてしまうところみてもらいたい。
私も自分のこのサイトでパズル「８人の女王」のプログラムを２つ書いている。私のプログラムは Python の文法を知らなくても読めるだろう。私は，FORTRAN，アセンブラ，C/C++，Javaなどで書いてきたが，言語固有な文法はあまり使わず，アルゴリズムを論理的に書いてきただけなので，そのコードは言語を知らなくも読めるかもしれない。
Python を勉強しようとしている人には私のプログラムよりも紫藤氏のプログラムの方が面白いでしょう。そこで Python のファンになろうしている私がこの美しいプログラムの解説を試みる。
◆◆プログラムファイルは2つある◆◆
pyファイルは，
queen.py ；8人の女王ゲームの解法
8queens.py ；ボードの描画
の2つあり，巻末にソースコードを掲載してある。
8人の女王ゲームの解だけ見たい場合は，queen.pyを run させれば出力します。
そのボードを見たい場合は，8queens.pyを run させれば出力します。
Jupyter Notebook 用の ipynb ファイルは，queen.pyと8queens.pyを並べただけのものです。
8queens.pyの8行目のqueen.pyをimportしているのをコメントアウトし，as Qとしているので，queen.pyの関数を呼んでいる33行目のQ.eight_queens()をただのeight_queens()としました。
次からは，解法であるqueen.pyを中心に解説します。Tkinterの描画プログラムは本サイトの別記事をご覧になってください。
◆◆queen.pyを単体で run させる◆◆
上のWebからソースファイルをダウンロードして run させてみよう。ソースコードは巻末に掲載してある。109行目の
if __name__=='__main__':
は単体で run させるときだけ必要であり，単体デバッグに使う。このまま実行すると，110行目がrunして
1: [3, 8, 20, 31, 37, 42, 54, 57]...
のように12コの解が表示される
関数 eight_queens() の戻り値は 8*12 の配列であり，109行目の
for i, a in enumerate(eight_queens()):
はこの配列のインデックスと要素を同時に取得するお決まりのコードである。この配列から取り出された要素はまた配列であり，解のうちの1つである。この配列のインデックスと要素を取り出すお決まりが関数enumerate()である。
◆◆描画プログラムへ解答を渡す◆◆
描画プログラム「8queens.py」は掲載してないがその8行目と33行目が
import queen as Q
self.q_answers = Q.eight_queens()
であり，解答プログラム「queen.py」から解答の配列を入力している。インポートの指定として
from queen import *
という書き方は名前空間の混乱を招くので推奨されていない。したがって，前の import文を使い関数の前に「Q.」を付ける。
◆◆関数 eight_queens() の戻り値◆◆
描画プログラム「8queens.py」が解答プログラム「queen.py」から入力する値は入力する側の「8queens.py」を run しなければ判らないのだろうか。そんなことはなく単体デバッグで表示できます。109行目に
print(eight_queens())
と書けば，
[[3, 8, 20, 31, 37, 42, 54, 57], [3, 14, 16, 31, 36, 41, 53, 58],...
のように12コの解が戻ってくる。この解はマスのIDとしてXY座標ではなく通し番号を付けている。描画プログラムの方ではチェス盤にクィーンを置くというよりは差分だけ移動させるという手法を使っているのでこのIDの付け方でも問題はない。最初の解答を XY 座標で書けば
[3, 0, 4, 7, 5, 2, 6, 1]
となる。8 の倍数を引けば得られる。X座標は配列インデックスである。あとで判るが通し番号のIDがでてくるのはこの return文で描画プログラムに解を渡すときだけであとはすべて XY 座標方式で解を表現している。
◆◆関数 eight_queens() の戻り値は何を表示しているのか◆◆
106行目の return文の後ろが関数 eight_queens() の関数値（戻り値）の式である。
[queen_decode(key) for key, val in q_hash.iteritems() if val]
この内容は上に示したように 8*12 の配列である。「q_hash」の内容を見てみよう。106行目のreturn文を
return q_hash
109行目に
print(eight_queens())
と書けば，
{3759875: True, 13433364: False,...
のように92コの解が取得できる。ハッシュは辞書配列でキーの数字は解答番号である。バリューとして 12コの True がある。92コの解のうち上下反転，左右反転，回転を除くと12コの解になる。この解答番号から解答配列に変換しているのが関数 queen_decode() である。109行目に
print(queen_decode(3759875))
とすると上のハッシュの値が変換されて
[3, 8, 20, 31, 37, 42, 54, 57]
が得られる。関数 eight_queens() の戻り値の最初の要素である。ハッシュのキーの範囲を確認するために109行目を
print(queen_decode(0), queen_decode(8**8-1))
とすると
[0, 8, 16, 24, 32, 40, 48, 56] [7, 15, 23, 31, 39, 47, 55, 63]
が得られる。これはクィーンが最上段と最下段に1列に並んだ状態である。このプログラムはクィーンを1マスずつ動かした 8**8コのパターンに番号を付け，そのうちの92コを「q_hash」に登録している。106行目の戻り値の式を簡略化すると
f(i) for j in k
となる。配列 k のなかにある要素ｊについての関数 f(j) の値のことである。 ハッシュ q_hashの中から key と value を .iteritems() によって順番に取り出しその key を関数 queen_decode() に代入する。最後の if val は，ハッシュの中から True だけ選択している。実際に if val 削除して print してみると92コの解が取得できる。
◆◆関数 queen_decode()（27行目）◆◆
解答番号から XY 座標の解答配列を得るには 8 で割り続けて余りを並べればよい。8で割るには2進数を c >> 3 で3ビット右シフトする。余りを取り出すには c & 7 で下から3ビットを取り出す。この関数では列番の 8 倍を足して全マスを通し番号にしているので， i << 3 で3ビット左シフトで列番を8倍して | （or）で足している。
関数の戻り値の確認方法は前項に書いた。
◆◆関数 queen_encode() （35行目）◆◆
どうやらこの関数の引数は XY 座標の解答配列のようだ。c << 3 つまり3ビット左シフトで8倍して配列の要素を足すことを繰り返す。109行目で関数の値を表示させよう。
print(queen_encode([3, 0, 4, 7, 5, 2, 6, 1])) # 1番目の解答の XY 座標型
print(queen_decode(6453937)) # 引数は上の答え
[1, 14, 18, 29, 39, 44, 48, 59]
が得られる。 XY 座標にすると
[1, 6, 2, 5, 7, 4, 0, 3]
となる。1番目の解答の左右反転である。つまり，エンコードとデコードが可逆でない。念のため XY 座標をまたエンコードしてみる。
print(queen_encode([1, 6, 2, 5, 7, 4, 0, 3]))
3759875
が得られた。1番目の解答番号である。関数 queen_decode() は106行目の return文でしか使っていないので可逆でなくても一意であれば問題はでない。
◆◆可逆なデコーダにつくりかえてみよう◆◆
【queen.py】
35 36 37 38 39 40 41 35 36 37 38 39 40 41
修正前
def queen_decode(c):
"""decode integer to list"""
ls1=[]
for i in range(8):
ls1.append((c & 7) | (i << 3))
c = c >> 3
return ls1
修正後
def queen_decode(c):
"""decode integer to list"""
ls1=[]
for i in range(8):
ls1.append(c & 7)
c = c >> 3
return nreverse(ls1)
190行目に print文を書いて確認してみるとちゃんと可逆になっている。
print(queen_decode(3759875))
print(queen_encode([1, 6, 2, 5, 7, 4, 0, 3]))
[1, 6, 2, 5, 7, 4, 0, 3]
3759875
描画プログラムも修正が必要である。
【8queens.py】
45 45
修正前 z = self.q_answers[0][i] 修正後 z = self.q_answers[0][i] + i * 8
◆◆関数 nreverse() （16行目），関数 reverse() （20行目）◆◆
1番目の解答でこの関数を確認してみよう。109行目で
print(nreverse([3, 0, 4, 7, 5, 2, 6, 1]))
print(reverse([3, 0, 4, 7, 5, 2, 6, 1]))
[1, 6, 2, 5, 7, 4, 0, 3]
[1, 6, 2, 5, 7, 4, 0, 3]
が得られ戻り値は同じである。17行目の .reverse() で左右反転にしている。関数 reverse() の戻り値が nreverse(ls[:]) となっているがその引数の ls[:] は ls と厳密に同じだと思うのだが？
◆◆関数 queen_usd() （43行目）◆◆
戻り値の式 [7 - o for o in ls0] は配列の各要素を 7 から引いている。これは Y 座標を上下反転していることになる。確認しよう。
print(queen_usd([3, 0, 4, 7, 5, 2, 6, 1]))
[4, 7, 3, 0, 2, 5, 1, 6]
◆◆関数 queen_90() （47行目）◆◆
print(queen_90([3, 0, 4, 7, 5, 2, 6, 1]))
[3, 6, 4, 2, 0, 5, 7, 1]
が得られる。時計回りに90度回転したものである（チェス盤を右から見たもの）。ls0.index(i) は数値 i を探してそのインデックスを返す。確認してみよう。
print([[3, 0, 4, 7, 5, 2, 6, 1].index(i) for i in range(8)])
[1, 7, 5, 0, 2, 4, 6, 3]
が得られる。これを左右反転すれば上の結果が得られる。
◆◆関数 queen_180() （51行目），関数 queen_270() （55行目）◆◆
180度回転する。
print(queen_180([3, 0, 4, 7, 5, 2, 6, 1]))
[6, 1, 5, 2, 0, 3, 7, 4]
上で得られた90度回転をさらに90度回転してみる。上と結果は同じである。
print(queen_90([3, 6, 4, 2, 0, 5, 7, 1]))
[6, 1, 5, 2, 0, 3, 7, 4]
270度回転する。
print(queen_270([3, 0, 4, 7, 5, 2, 6, 1]))
[6, 0, 2, 7, 5, 3, 1, 4]
上で得られた180度回転をさらに90度回転してみる。上と結果は同じである。
print(queen_90([6, 1, 5, 2, 0, 3, 7, 4]))
[6, 0, 2, 7, 5, 3, 1, 4]
◆◆関数 queen_dgla() （59行目），関数 queen_dglb() （63行目）◆◆
90度回転の左右反転と上下反転である。確認するまでもないと思う。
◆◆関数 queen_ok() （67行目）◆◆
解答配列が未完のとき次の列の解を探す手伝いをする。109行目で関数値（戻り値）を確認すると，
print(queen_ok(1, [3, 0, 4, 7]))
print(queen_ok(2, [3, 0, 4, 7]))
print(queen_ok(5, [3, 0, 4, 7]))
print(queen_ok(6, [3, 0, 4, 7]))
True
False
True
False
となった。73行目で，前に置いたクィーンの横筋，右斜め筋，左斜め筋に置けないことを確認している。この関数はクィーンを新たに置けるかを判定しているだけである。
◆◆関数 queen_pos()（77行目）◆◆
解答配列が未完のとき次の列の解の候補を探す。109行目で関数値（戻り値）を確認すると前項の結果がそのまま反映されていることが判る
print(queen_pos([3, 0, 4, 7]))
[1, 5]
◆◆関数 eight_queens()（81行目）◆◆
メインプログラムと呼べるものである。関数が入れ子 nesting になっていて，この関数のプログラムは104行目から3行しかない。変数宣言と return文を除けば105行目の
queen(0, [])
だけである。この呼ばれている関数 queen()がメインなサブルーチンである（妙な言い方？）。
関数 eight_queens()がこの形になっているのは return文で解答を描画プログラムに渡したいからである。渡す必要がなければこの3行は109行目以降に書いて retrurn文を print文にしてもよいわけである。
◆◆関数 queen_sethash()（84行目）◆◆
このプログラムでは8コのクィーンを置く8**8コのすべてのパターンに番号を付けその中から92の解を選択している。この解答番号は別にカウントしているわけではなく解答配列を関数 queen_encode()に渡して一意な番号を得ている。
この関数の働きを直接みてみよう。109行目に
print(eight_queens())
と書き，104～106行目の代わりに，次のコードを書く。解答配列はたぶん1番目に得られるものを想定している。
q_hash={}
queen_sethash([0, 4, 7, 5, 2, 6, 1, 3])
print(q_hash)
print(queen_encode([0, 4, 7, 5, 2, 6, 1, 3]))
queen_encode()の関数値（戻り値）として
1299851
queen_sethash()の関数値（戻り値）として
{6761440: False, 1733354: False, 1299851: True, 11165903: False, 5611312: False, 15477364: False, 15043861: False, 10015775: False}
解答配列を関数 queen()から受け取ったあと，91行目で解答番号に変換する。
92行目でその解答番号がハッシュの中に有るかを判定して有れば終了する。
93行目の sop には反転，回転の7つ関数そのものが代入される。
94行目でこの7つの関数から出力される解答配列を解答番号に変換しキーとして， バリューを False として，q_hash に登録する。
95行目で，関数 queen()から受け取ったものを True として q_hash に登録する。
ハッシュ（辞書配列）は自動的にキーの昇順に並び替えられる。
◆◆関数 queen()（84行目）◆◆
これがメインなサブルーチンである。この妙な言い方は，すべての解答配列をこの関数だけで出力しているからである。
この関数の引数は，未完の解答配列と次の列番である。
102行目に再帰呼び出しがある。この関数なかで次の1列の解を加え，再帰呼び出しでそのまた次の1列の解を加えることを繰り返す。
この関数の1ステップ目の98行目で，解答配列の要素が8コ揃ったことを確認し，揃ったなら関数 queen_sethash() を呼んでハッシュに登録する。
解答配列の要素が揃っていないなら次の列の解の候補を関数 queen_pos() から受け取りそれを解答配列に加えてまたこの関数じぶんじしんを呼ぶ。
この関数の働きは再帰呼び出しを注意深く追うことにより理解できる。
例えば，未完の解答配列 [3, 0, 4, 7] のとき次の列の解の候補「1」「5」について再帰呼び出しする。
以上で解説は終わりだが，この記事を書き始める前は私もさっぱり理解できていなかったプログラムを今は完璧に理解できたように思います。プログラムを書かれた紫藤氏に感謝します。
【queen.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
#! usr/bin/env python
"""
8 queens with symmetry operations of the board
this program gives
12 distinct solutions by taking symmetry operations
such as rotations and reflections of the board into consideration
"""
### functions
def set_difference(a, b):
return [x for x in a if not x in b]
def nreverse(ls):
ls.reverse()
return ls
def reverse(ls):
return nreverse(ls[:])
def qmod (n):
"""function to determine the board color, 0 white 1, green"""
return (n / 8 - n % 8) % 2
def queen_decode(c):
"""decode integer to list"""
ls1=[]
for i in range(8):
ls1.append((c & 7) | (i << 3))
c = c >> 3
return ls1
def queen_encode(ls0):
"""encode list into integer"""
c = 0
for obj in ls0:
c = (c << 3) | obj
return c
### symmetry operations
def queen_usd(ls0):
"""up side down"""
return [7 - o for o in ls0]
def queen_90(ls0):
"""rotating 90 degrees"""
return nreverse([ls0.index(i) for i in range(8)])
def queen_180(ls0):
"""rotating 180 degrees"""
return queen_90(queen_90(ls0))
def queen_270(ls0):
"""rotating 270 degrees"""
return queen_90(queen_180(ls0))
def queen_dgla(ls0):
"""reflection on diagonal (1)"""
return nreverse(queen_90(ls0))
def queen_dglb(ls0):
"""reflection on diagonal (2)"""
return queen_usd(queen_90(ls0))
def queen_ok(col, qpos):
"""check if the queen's position is ok"""
r = len(qpos)
for i in range(r):
c = qpos[i]
j = r - i
if c == col or col + j == c or col - j == c :
return False
return True
def queen_pos(qpos):
"""it retunrs possible queen positions"""
return [c for c in range(8) if queen_ok(c, qpos)]
def eight_queens():
"""solving 8 queens taking symmetry operations into account"""
def queen_sethash(ls0):
"""
setting hash table
'hash' is the hash table of the solution of the 8 queens
if the key is a distinct solution the value is True, else False
"""
c0 = queen_encode(ls0)
if not (c0 in q_hash):
for sop in (reverse, queen_usd, queen_90, queen_180,
queen_270, queen_dgla, queen_dglb):
q_hash[queen_encode(sop(ls0))] = False
q_hash[c0] = True
def queen(row, qpos):
if row == 8:
queen_sethash(qpos)
else:
for c in queen_pos(qpos):
queen(1+row, qpos+[c])
q_hash={}
queen(0, [])
return([queen_decode(key) for key, val in q_hash.items() if val])
if __name__=='__main__':
for i, a in enumerate(eight_queens()):
print('%2d: %s' % (i+1, a))
【8queens.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
#! /usr/bin/env python
"""
eight queens, whose gui uses Tkinter
"""
import tkinter as Tk
import queen as Q
Q_font = ("Times", 14)
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.q_answers = Q.eight_queens()
for i in range(8):
for j in range(8):
bcolor = (i-j)%2==0 and "#699C69" or "#D4D49F"
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.gif"))
z = self.q_answers[0][i]
x = self.cell_size*((z // 8)+0.5) + self.margin
y = self.cell_size*((z % 8)+0.5) + self.margin
self.q_figure.append(self.create_image(x, y, image=self.q_images[i], tags="queen"))
def refresh(self, now, next):
answer_now = self.q_answers[now]
answer_next = self.q_answers[now+next]
for i, j in move_queen(answer_now, answer_next):
self.move(self.q_figure[i], 0, j*self.cell_size)
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='Eight Queens', font=('Times', '24', ('italic', 'bold')),
fg='#191970', bg='#EEE8AA', 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/12" % (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.b_button = Tk.Button(self.f_footer, text="prev", font=Q_font, command = self.show_prev)
self.b_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):
if(self.q_counter < 11):
self.f_board.refresh(self.q_counter, 1)
self.change_counter(1)
def show_prev(self):
if(self.q_counter > 0):
self.f_board.refresh(self.q_counter, -1)
self.change_counter(-1)
def change_counter(self, i):
self.q_counter += i
self.s_counter.set("%d/12" % (1 + self.q_counter))
##---------------------------------------------------
if __name__ == "__main__":
app = Queen()
app.pack()
app.mainloop()