![]() |
![]() |
![]() |
![]() |
Queen は縦横斜めに利いているので、各行には1つの Queen しか置けません。 n 行目に Queen を置くときは すでに 0--(n-1) 行に置かれている Queen と縦、斜めの利きが 衝突しないように置きます。利きが衝突しないかどうかは queen_ok で調べます。 また、queen_pos は n 行目の衝突しない列全てを返します。
解を求める関数は queen(row, qpos) です。
この関数は、row 行までの Queen の位置を qpos に保持し、それを元に
(row + 1) 行目の安全な Queen の位置を queen_pos で求め、
それを qpos に足していきます。row=8 となったら解をハッシュテーブルに登録します。
詳しくは
Hiroi さんのページを見てください。
01: #! usr/bin/env python
02:
03: """
04: 8 queens with symmetry operations of the board
05:
06: this program gives
07: 12 distinct solutions by taking symmetry operations
08: such as rotations and reflections of the board into consideration
09: """
10:
11: ### functions
12:
13: def set_difference(a, b):
14: return [x for x in a if not x in b]
15:
16: def nreverse(ls):
17: ls.reverse()
18: return ls
19:
20: def reverse(ls):
21: return nreverse(ls[:])
22:
23: def qmod (n):
24: """function to determine the board color, 0 white 1, green"""
25: return (n / 8 - n % 8) % 2
26:
27: def queen_decode(c):
28: """decode integer to list"""
29: ls1=[]
30: for i in range(8):
31: ls1.append((c & 7) | (i << 3))
32: c = c >> 3
33: return ls1
34:
35: def queen_encode(ls0):
36: """encode list into integer"""
37: c = 0
38: for obj in ls0:
39: c = (c << 3) | obj
40: return c
41:
42: ### symmetry operations
43: def queen_usd(ls0):
44: """up side down"""
45: return [7 - o for o in ls0]
46:
47: def queen_90(ls0):
48: """rotating 90 degrees"""
49: return nreverse([ls0.index(i) for i in range(8)])
50:
51: def queen_180(ls0):
52: """rotating 180 degrees"""
53: return queen_90(queen_90(ls0))
54:
55: def queen_270(ls0):
56: """rotating 270 degrees"""
57: return queen_90(queen_180(ls0))
58:
59: def queen_dgla(ls0):
60: """reflection on diagonal (1)"""
61: return nreverse(queen_90(ls0))
62:
63: def queen_dglb(ls0):
64: """reflection on diagonal (2)"""
65: return queen_usd(queen_90(ls0))
66:
67: def queen_ok(col, qpos):
68: """check if the queen's position is ok"""
69: r = len(qpos)
70: for i in range(r):
71: c = qpos[i]
72: j = r - i
73: if c == col or col + j == c or col - j == c :
74: return False
75: return True
76:
77: def queen_pos(qpos):
78: """it retunrs possible queen positions"""
79: return [c for c in range(8) if queen_ok(c, qpos)]
80:
81: def eight_queens():
82: """solving 8 queens taking symmetry operations into account"""
83:
84: def queen_sethash(ls0):
85: """
86: setting hash table
87: 'hash' is the hash table of the solution of the 8 queens
88: if the key is a distinct solution the value is True, else False
89: """
90:
91: c0 = queen_encode(ls0)
92: if not (c0 in q_hash):
93: for sop in (reverse, queen_usd, queen_90, queen_180, queen_270, queen_dgla, queen_dglb):
94: q_hash[queen_encode(sop(ls0))] = False
95: q_hash[c0] = True
96:
97: def queen(row, qpos):
98: if row == 8:
99: queen_sethash(qpos)
100: else:
101: for c in queen_pos(qpos):
102: queen(1+row, qpos+[c])
103:
104: q_hash={}
105: queen(0, [])
106: return [queen_decode(key) for key, val in q_hash.iteritems() if val]
107:
108: if __name__=='__main__':
109: for i, a in enumerate(eight_queens()):
110: print '%2d: %s' % (i+1, a)
111:
行 | 説明 |
---|---|
13 | set_difference(a ,b): リスト a から、リスト b に含まれる要素を除いたリストを返します。 |
16 | nreverse(ls): ls の要素を破壊的に反転させます。 |
20 | reverse(ls): ls の要素を反転させます。 |
23 | qmod(n): チェス盤の升目の色を決めます。 |
27 | queen_decode(c): 正の整数 c をリストに変換します。 |
35 | queen_encode(ls0): queen の位置のリスト ls0 を整数に変換します。リストは辞書型のキーになれないため、整数かタプルに変換する必要がある。タプルより整数のほうが検索が早そうなのでここでは整数に変換。 |
43--65 | チェス盤の対称操作です。90, 180, 270 度回転、上下、左右、対角線(2つ)の反転 |
77 | queen_ok(col, qpos): 新しく col に置いた Queen がすでに盤上にある Queen (qpos) と利き筋が重ならなければ True を返す。 |
77 | queen_pos(qpos): すでに盤上にある Queen と重ならない Queen の位置を返します。 |
81 | eight_queens(): Eight Queens を解く関数です。二つの内部関数 queen_sethash と queen があります。まず、queen で解をもとめて、それを queen_sethash でハッシュテーブル(辞書型のデータ)に登録します。個別の解の値は True、対称操作で生成される解の値は False とします。最後に、固有の解からなるリストを返します。 |
01: #! usr/bin/env python 02: 03: """ 04: eight queens, whose gui uses wx sizer 05: """ 06: 07: import wx, wx.lib.rcsizer 08: import queen as q 09: #global parameter 10: Q_font = ("Times", 14) 11: 12: # gui 13: class Board(wx.Panel): 14: def __init__(self, frame): 15: # 8 queens answers 16: self.q_answers = q.eight_queens() 17: answer = self.q_answers[0] 18: self.counter = 0 19: 20: # images 21: #title 22: self.i_title = wx.Image('8qsubtitle.png', wx.BITMAP_TYPE_PNG).ConvertToBitmap() 23: #cell 24: self.cell_images = [wx.Image(png, wx.BITMAP_TYPE_PNG).ConvertToBitmap() \ 25: for png in ('bw.png', 'bg.png', 'qw.png', 'qg.png')] 26: 27: # Panel 28: wx.Panel.__init__(self, frame, -1) 29: self.box = wx.BoxSizer(wx.VERTICAL) 30: 31: # Title 32: self.box.Add(wx.StaticBitmap(self, -1, self.i_title), \ 33: 0, wx.ALIGN_CENTER | wx.ALL, 10) 34: 35: #Chess Board 36: self.grid = wx.lib.rcsizer.RowColSizer() 37: 38: for i in range(64): 39: j = q.qmod(i) + ((i in answer) and 2 or 0) 40: self.grid.Add( \ 41: wx.StaticBitmap(self, -1, self.cell_images[j]), \ 42: flag=wx.EXPAND, row=i/8, col=i%8) 43: 44: self.box.Add(self.grid, 0, wx.ALIGN_CENTER | wx.ALL, 10) 45: 46: # Footer 47: self.footer = wx.BoxSizer(wx.HORIZONTAL) 48: 49: btn1 = wx.Button(self, wx.ID_FORWARD, "") 50: self.Bind(wx.EVT_BUTTON, self.show_next, btn1) 51: self.footer.Add(btn1, 0, wx.ALIGN_CENTER_VERTICAL | wx.LEFT, 20) 52: 53: btn2 = wx.Button(self, wx.ID_BACKWARD, "") 54: self.Bind(wx.EVT_BUTTON, self.show_prev, btn2) 55: self.footer.Add(btn2, 0, wx.ALIGN_CENTER_VERTICAL | wx.LEFT, 20) 56: 57: self.label = wx.StaticText(self, -1, ("%d/12" % (self.counter+1))) 58: self.footer.Add(self.label, 0, wx.ALIGN_CENTER_VERTICAL | wx.LEFT, 20) 59: 60: self.box.Add(self.footer, 0, wx.ALIGN_CENTER | wx.ALL, 10) 61: 62: # Layout 63: self.SetSizer(self.box) 64: self.Layout() 65: 66: #refresh board and counter 67: def refresh(self, forward): 68: i_now = self.counter 69: self.counter += forward and 1 or -1 70: self.label.SetLabel("%d/12" % (1 + self.counter)) 71: a_next = self.q_answers[self.counter] 72: a_now = self.q_answers[i_now] 73: q_or_b=0 74: for cells in [q.set_difference(a_now, a_next), q.set_difference(a_next, a_now)]: 75: for i in cells: 76: j = q.qmod(i) + q_or_b 77: self.grid.Add( \ 78: wx.StaticBitmap(self, -1, self.cell_images[j]), \ 79: flag=wx.EXPAND, row=i/8, col=i%8) 80: q_or_b += 2 81: # self.SetSizer(self.box) 82: self.Layout() 83: 84: def show_next(self, event): 85: if(self.counter < 11): 86: self.refresh(True) 87: 88: def show_prev(self, event): 89: if(self.counter > 0): 90: self.refresh(False) 91: 92: class Queen(wx.App): 93: def OnInit(self): 94: frame = wx.Frame(None, -1, "8 queens" , size=(450,500), \ 95: style=wx.DEFAULT_FRAME_STYLE | wx.ST_NO_AUTORESIZE) 96: Board(frame) 97: self.SetTopWindow(frame) 98: frame.Show(True) 99: return True 100: 101: if __name__ == "__main__": 102: que = Queen(redirect=False) 103: que.MainLoop()
行 | 説明 |
---|---|
08 | Eight Queen を解くプログラム queen を import します。 |
13 | wx.Panel の子クラス Board を定義します。 |
16 | Eight Queen の解を self.q_answers に代入します。 |
22 | タイトルのイメージを作ります。 |
24 | チェス盤の枡のイメージを作ります。黒地、白地、黒地+Queen、白地+Queen の四種類があります。 |
28 | wx.Panel の __int__ を呼び出します。引数は自分自身、結合するフレーム、ID です。 |
29 | 縦に並べる boxsizer self.box を作ります。。 |
32 | タイトルイメージから StaticBitmat をつくり、それを self.box を使って縦に並べます。 StatucBitmap は Panel, id, Image の3つの引数をとります。 また、Add は、Widget, proportion, flag, border の4つの引数をとります。 これらの引数の意味はwxpython.org/docs を見てください。 |
36 | チェス盤を定義します。 |
38--42 | チェス盤に枡のイメージを貼り付けます。 |
38 | 64 個の枡に、 |
39 | 貼り付ける画像を選びます。 q.qmod(i): 白か黒、 ((i in answer) and 2 or 0): Queen があるかないか。 j=0,1,2,3 はそれぞれ白枡、黒枡、白枡+Queen、黒枡+Queen をあらわします。 |
40 | RowColSizer のメソッド Add は、 item, option, flag, border, row, col, rowspan, colspan, pos, size の 10 個の引数をとります。 item と row、col は指定する必要があります。 row, col で貼り付ける位置を指定します。ここでは、row は i を 8 で割った商、col は 余りです。 |
44 | self.box にチェス盤 (self.grid) を加えます。 |
47 | 横向きの BoxSizer self.footer を定義します。 |
49 | 次の解を表示するボタン "btn1" を作ります。wx.Button の引数は、 wx.Panel, id, 表示文字の3つです。id には予約済みの値があるので一般的な Button を作るときは それを使えばよいでしょう。詳しくは、wxpython.org/docsを見てください。 |
50 | btn1 と self.show_next というメソッドを結び付けます。 |
51 | btn1 を self.footer に加えます。 |
53--55 | 1つ前の解を表示するボタン btn2 をつくり、 btn1 と同様の処理をします。 |
57 | 現在、何番目の解を表示しているかのラベル (self.label) をつくります。 |
58 | self.label を self.footer に加えます。 |
60 | self.footer を self.box に加えます。 |
63 | self(wx.Panel) の Sizer を self.box にセットします。 |
64 | レイアウトします。 |
67 | 次または前の解を表示するメソッド refresh を定義します。 |
68 | 現在の解の番号を i_now に保持し、 |
69 | 解の番号を forward==True のときは1つ増やし、forward==False のときは1つ減らします。 |
70 | self.label の表示文字を変更します。 |
74--80 | 今表示している解の Queen の位置で、 次に表示する解では Queen がいなくなる枡の画像を Queen ありから Queen 無しに張り替えます。 また、次に表示する解の Queen の位置で、今表示している解では Queen が無い枡の画像を Queen 無しから、 Queen ありに張り替えます。 こうすると、画像全てを張り替える必要が無いので応答が速くなります。 |
84 | 次の解を表示するメソッド show_next を定義します。 イベントと結びつけるメソッドは、自分自身とイベントのきっかり2つの引数を取る必要があります。 |
88 | 1つ前の解を表示するメソッド show_prev を定義します。これで、パネル (Board) の定義は終わりです。 |
92 | wx.App の導出クラス Queen を定義します。 |
93 | wx.App クラスの __init__ に加えてインスタンス生成の際に加えたい操作を OnInit を使って定義します。 |
94 | wx.Frame のインスタンス frame を定義します。 parent, id, title, pos, size, style, name の 7つの引数をとります。 |
96 | Board のフレームを frame にしてインスタンスを生成します。 |
97 | frame を TopWindow にします。 |
98 | frame を表示します。 |
99 | OnInit はブーリアンを返す必要があります。これで、Queen の定義は終わりです。 |
102 | Queen のインスタンス que を作って、 |
103 | 実行します。 |
01: #! usr/bin/env python 02: 03: """ 04: eight queens, whose gui uses wx absolute positioning 05: """ 06: import wx 07: import queen as q 08: 09: #global parameter 10: Q_font = ("Times", 14) 11: X_Margin = 20 12: Y_Margin = 20 13: 14: # gui 15: class Board(wx.Panel): 16: def init_title(self): 17: self.i_title = wx.Image('8qsubtitle.png', wx.BITMAP_TYPE_PNG).ConvertToBitmap() 18: wx.StaticBitmap(self, -1, self.i_title, \ 19: (5, 5), (self.i_title.GetWidth(), self.i_title.GetHeight())) 20: 21: def init_board(self): 22: self.cell_images = [wx.Image(png, wx.BITMAP_TYPE_PNG).ConvertToBitmap() \ 23: for png in ('bw.png', 'bg.png', 'qw.png', 'qg.png')] 24: answer = self.q_answers[0] 25: self.i_width = self.cell_images[0].GetWidth() 26: self.i_height = self.cell_images[0].GetHeight() 27: for i in range(64): 28: j = q.qmod(i) + (((i in answer) and 2) or 0) 29: wx.StaticBitmap(self, -1, self.cell_images[j], \ 30: (self.i_width*(i%8)+self.xmargin, self.i_height*(i/8)+self.ymargin), \ 31: (self.i_width, self.i_height)) 32: 33: def init_footer(self): 34: self.counter = 0 35: btn1 = wx.Button(self, 10, "Forward", (20, 420)) 36: self.Bind(wx.EVT_BUTTON, self.show_next, btn1) 37: btn2 = wx.Button(self, 20, "Backward", (100, 420)) 38: self.Bind(wx.EVT_BUTTON, self.show_prev, btn2) 39: self.label = wx.StaticText(self, -1, ("%d/12" % (self.counter+1)), (180, 430)) 40: 41: def init_all(self): 42: self.q_answers = q.eight_queens() 43: self.init_title() 44: self.init_board() 45: self.init_footer() 46: 47: def __init__(self, frame): 48: wx.Panel.__init__(self, frame, style=wx.NO_FULL_REPAINT_ON_RESIZE) 49: self.xmargin = 40 50: self.ymargin = 60 51: self.init_all() 52: self.Layout() 53: 54: 55: #refresh board and counter 56: def refresh(self, forward): 57: i_now = self.counter 58: self.counter += forward and 1 or -1 59: self.label.SetLabel("%d/12" % (1 + self.counter)) 60: a_next = self.q_answers[self.counter] 61: a_now = self.q_answers[i_now] 62: q_or_b=0 63: for cells in [q.set_difference(a_now, a_next), q.set_difference(a_next, a_now)]: 64: for i in cells: 65: j = q.qmod(i) + q_or_b 66: wx.StaticBitmap(self, -1, self.cell_images[j], \ 67: (self.i_width*(i%8)+self.xmargin, self.i_height*(i/8)+self.ymargin), \ 68: (self.i_width, self.i_height)) 69: q_or_b += 2 70: 71: def show_next(self, event): 72: if(self.counter < 11): 73: self.refresh(True) 74: 75: def show_prev(self, event): 76: if(self.counter > 0): 77: self.refresh(False) 78: 79: 80: class Queen(wx.App): 81: def OnInit(self): 82: frame = wx.Frame(None, -1, "8 queens", pos=(150, 150), size=(420, 500)) 83: Board(frame) 84: self.SetTopWindow(frame) 85: frame.Show(True) 86: return True 87: 88: if __name__ == "__main__": 89: que = Queen(redirect=False) 90: que.MainLoop()
01: #! usr/bin/env python 02: 03: """ 04: eight queens, whose gui uses Tkinter 05: """ 06: 07: import Tkinter as tk 08: import queen as q 09: 10: #global parameter 11: Q_font = ("Times", 14) 12: 13: # gui 14: class Queen(tk.Frame): 15: q_counter = 0 16: 17: def init_title(self): 18: self.master.title("8 Queens") 19: self.f_title = tk.Frame(self) 20: self.i_title = tk.PhotoImage(file="8qsubtitle.ppm") 21: self.l_title = tk.Label(self.f_title, image = self.i_title) 22: self.l_title.pack() 23: self.f_title.pack(side=tk.TOP, padx=10, pady=10) 24: 25: def init_board(self): 26: self.f_board = tk.Frame(self, relief=tk.GROOVE, bd=3) 27: self.f_board.pack(side=tk.TOP, padx=10, pady=10) 28: self.cell_images = [tk.PhotoImage(file=ppm) for ppm in ("bw.ppm", "bg.ppm", "qw.ppm", "qg.ppm")] 29: self.q_answers = q.eight_queens() 30: answer = self.q_answers[0] 31: for i in range(64): 32: tk.Label(self.f_board, \ 33: image=self.cell_images[q.qmod(i)+((i in answer) and 2 or 0)]).grid(row=i/8, column=i%8) 34: 35: def init_footer(self): 36: self.f_footer = tk.Frame(self) 37: self.f_footer.pack(side=tk.TOP, fill=tk.X, expand=1) 38: self.s_counter = tk.StringVar() 39: self.s_counter.set("%d/12" % (1 + self.q_counter)) 40: self.f_label = tk.Label(self.f_footer, textvariable = self.s_counter, font=Q_font, width=8) 41: self.f_label.pack(side=tk.RIGHT, padx=10) 42: self.b_button = tk.Button(self.f_footer, text="back", font=Q_font, command = self.show_prev) 43: self.b_button.pack(side=tk.RIGHT, padx=1,pady=1) 44: self.a_button = tk.Button(self.f_footer, text="next", font=Q_font, command = self.show_next) 45: self.a_button.pack(side=tk.RIGHT, padx=1,pady=1) 46: 47: 48: def __init__(self, master=None): 49: tk.Frame.__init__(self, master) 50: self.pack() 51: self.init_title() 52: self.init_board() 53: self.init_footer() 54: 55: #refresh board and counter 56: def refresh(self, forward): 57: i_now = self.q_counter 58: self.q_counter += forward and 1 or -1 59: self.s_counter.set("%d/12" % (1 + self.q_counter)) 60: a_next = self.q_answers[self.q_counter] 61: a_now = self.q_answers[i_now] 62: q_or_b=0 63: for cells in [q.set_difference(a_now, a_next), q.set_difference(a_next, a_now)]: 64: for i in cells: 65: tk.Label(self.f_board, image=self.cell_images[q.qmod(i) + q_or_b]).grid(row=i/8, column=i%8) 66: q_or_b += 2 67: 68: def show_next(self): 69: if(self.q_counter < 11): 70: self.refresh(True) 71: 72: def show_prev(self): 73: if(self.q_counter > 0): 74: self.refresh(False) 75: 76: 77: if __name__ == "__main__": 78: que = Queen() 79: que.mainloop()
行 | 説明 |
---|---|
17 | init_title: タイトルを初期化します。 |
18 | window の上部のフレームに表示する文字列を指定します。 |
19 | self を親フレームにしてタイトル用のFrame self.f_title を定義します。 |
20 | タイトル用のイメージ self.i_image を定義します。 |
21 | self.f_frame を親フレームにし、self.i_title を表示するタイトル用のラベル self.l_title を定義します。 |
22 | self.l_title を pack します。 |
23 | self.f_title を pack します。方向は上下(side=tk.TOP)で、上下左右の余白は 10 です。(padx=10, pady=10) |
25 | init_board: チェス盤を初期化します。 |
26 | チェス盤用のフレーム selff_board を定義します。ボーダーのスタイルを tk.GROOVE にし、ボーダーの幅は 3 です。 |
27 | self.f_board を pack します。 |
28 | 枡のイメージを用意します。 |
29 | Eight Queens を解きます。 |
31--33 | self.f_board を親にして tk.Label を作り、8x8 に配置します。画像の選び方は wx 版と同様。 |
35 | init_footer: ボタンとラベルを初期化します。 |
36 | footer 用のフレーム self.f_footer を作ります。 |
37 | f_footer を pack します。 左右に広がるように fill=tk.X, expand=1 を指定します。 |
38 | ラベルに表示する文字列 self.s_counter を定義します。変更可能な文字列は tk.StringVar クラスです。 |
39 | self.s_counter の set メソッドを使って文字列をセットします。 |
40 | self.f_label を定義します。変更可能な文字列を表示する場合は textvariable を使います。 |
41 | self.f_label 右詰で pack します。 |
42--43 | "back" 用のボタンを定義し、右詰で pack します。command は関数へのポインターを与えます。command に記述する関数は self 以外の引数をとりません。 |
44--45 | "forward" 用のボタンを定義し、右詰で pack します。 |
48--53 | Queen クラスのインスタンスを作ります。 |
56--74 | 次の解を表示する関数は wx 版と同様です。 |
78,79 | Queen クラスのインスタンス que を作って、メソッド mainloop を呼び出します。 |
コードは Tkinter 入門 9. ボードゲーム用 GUI を作ろう にあります。
![]() |
![]() |
![]() |
![]() |