HOME | Python | download | 書き込む |
N Queen とは N x N のチェスの Queen を利きが互いに重ならないように配置するパズルです。 Queen は将棋の飛車と角を合わせた利きをもち、縦横斜めに好きなだけ移動することができます。 詳しくは wikipedia をみてください。 以前、 Scheme 版 , Python 2 版 を書いてみたのですが、 気が向いたので Python 3.0 でも書いてみました。うまく書けたので、アップします。
縦の升目は 全て異なるようにしないと利きがぶつかるので、 N Queen は 集合 {0,1, .... (n-1)} から要素を取り出し、それを斜めの利きが重ならないように並べていく 問題に 置き換えることができます。
abs(縦の升目の差) == 横の升目の差のときで、新しく置く駒は、すでに置いてある駒 全てと利きが 重ならない必要があります。
チェスの盤には 4 種類の反転と 3 種類の回転対称性があるので、 駒を置き終えたら、それらの対称操作をして、既知の解にならないかチェックをし、 新しい解だけを追加します。
[queen.py]
001: #! python 002: # coding:shift-jis 003: 004: """N Queen: taking symmetry into account""" 005: 006: import sys 007: 008: 009: 010: def comb(f1, f2): 011: """2 つの 関数 を 合成 した 関数 を 返す """ 012: return lambda x:f1(f2(x)) 013: 014: 015: # 対称 操作 016: REV = lambda ls: list(reversed(ls)) # 左右反転 017: USD = lambda ls: [ len(ls)-x-1 for x in ls ] # 上下 反転 018: T90 = lambda ls: [ ls.index(x) for x in range(len(ls)) ] # 90 度 回転 019: T180 = comb(USD, REV) # 180 度 回転 020: T270 = comb(T90, T180) # 270 度 回転 021: D1 = comb(REV, T90) # 対角線 での 反転 その 1 022: D2 = comb(USD, T90) # 対角線 での 反転 その 2 023: 024: 025: 026: 027: def is_different(cols, sols): 028: """ 対称性 を 考慮し ても 固有 の 解か """ 029: return all( tuple(op(cols)) not in sols for op in (REV, USD, T90, T180, T270, D1, D2) ) 030: 031: 032: 033: 034: def queen_ok(ls, row1): 035: """row1 が ls にある queen と 利き が 重な らないとき True を 返す """ 036: return all( abs(row1-row)!=col+1 for col, row in enumerate(ls) ) 037: 038: 039: 040: 041: def nqueen(n): 042: """n x n マス の N-Queen パズル を 解く """ 043: 044: def qiter(cols, rows): 045: 046: if rows: 047: for i in rows: 048: if queen_ok(cols, i): 049: qiter( (i,)+cols, rows-{i}) 050: elif is_different(cols, sols): 051: sols.add(cols) 052: 053: 054: sols=set() 055: qiter(tuple(), frozenset(range(n))) 056: return sols 057: 058: 059: 060: 061: 062: if __name__=='__main__': 063: sols=nqueen(int(sys.argv[1])) 064: print ('N of solutions:', len(sols)) 065: for sol in sols: 066: print (sol)以下のように、盤の大きさをコマンドライン引数で与えて実行します。
>python queen.py 8 N of solutions: 12 (4, 1, 3, 6, 2, 7, 5, 0) (4, 6, 0, 2, 7, 5, 3, 1) (5, 3, 6, 0, 7, 1, 4, 2) (5, 1, 6, 0, 3, 7, 4, 2) (3, 0, 4, 7, 5, 2, 6, 1) (2, 5, 3, 0, 7, 4, 6, 1) (3, 6, 0, 7, 4, 1, 5, 2) (4, 6, 3, 0, 2, 7, 5, 1) (3, 5, 7, 2, 0, 6, 4, 1) (4, 2, 7, 3, 6, 0, 5, 1) (2, 5, 7, 0, 3, 6, 4, 1) (3, 1, 6, 2, 5, 7, 4, 0)
is_different(cols, sols) で、解 (cols) と その対称操作によって生じた解が今まで見つかった解の集合 (sols) に含まれているか調べます。 cols に全ての対称操作を施しても、 sols の中に同じものが見つからなければTrueを 返します。
nqueen()で、is_different() が True を返したものだけを解 集合に加えていきます。
if __name__=='__main__' 以下で 、 nqueen() を呼んで、見つかった解を順に表示します。
[queen_tk.py]
001: #! /usr/bin/env python 002: # coding:shift_jis 003: """ 004: tkinter を使った 8-Queen の GUI 005: """ 006: 007: import tkinter as tk 008: import queen as q 009: 010: #global parameter 011: Q_font = ("Times", 14) 012: 013: 014: 015: def qmod (i,j): 016: """盤の背景色を決めます""" 017: return (i-j)%2==0 018: 019: 020: 021: def qdiff(a1, a0): 022: """8-Queen の2つの解の差をとります。効率的に表示を更新するのに使います""" 023: ls=[] 024: for i in range(8): 025: if not a0[i]==a1[i]: 026: ls.append((i, a0[i], False)) 027: ls.append((i, a1[i], True)) 028: return ls 029: 030: 031: 032: 033: class Queen(tk.Frame): 034: """Eight Queen を表示するチェス版です""" 035: 036: def init_title(self): 037: """表題""" 038: self.master.title("8 Queens") 039: self.f_title = tk.Frame(self) 040: self.i_title = tk.PhotoImage(file="8qsubtitle.ppm") 041: self.l_title = tk.Label(self.f_title, image = self.i_title) 042: self.l_title.pack() 043: self.f_title.pack(side=tk.TOP, padx=10, pady=10) 044: 045: 046: 047: def init_board(self): 048: """盤""" 049: self.f_board = tk.Frame(self, relief=tk.GROOVE, bd=3) 050: self.f_board.pack(side=tk.TOP, padx=10, pady=10) 051: self.cell_images = [tk.PhotoImage(file=ppm) for ppm in ("bw.ppm", "bg.ppm", "qw.ppm", "qg.ppm")] 052: answer = self.q_answers[0] 053: for i in range(8): 054: for j in range(8): 055: tk.Label(self.f_board, \ 056: image=self.cell_images[qmod(i,j)+(2 if answer[i]==j else 0)]).grid(row=i, column=j) 057: 058: 059: 060: def init_footer(self): 061: """脚注""" 062: self.f_footer = tk.Frame(self) 063: self.f_footer.pack(side=tk.TOP, fill=tk.X, expand=1) 064: self.s_counter = tk.StringVar() 065: self.s_counter.set("%d/12" % (1 + self.q_counter)) 066: self.f_label = tk.Label(self.f_footer, textvariable = self.s_counter, font=Q_font, width=8) 067: self.f_label.pack(side=tk.RIGHT, padx=10) 068: self.b_button = tk.Button(self.f_footer, text="back", font=Q_font, command = self.show_prev) 069: self.b_button.pack(side=tk.RIGHT, padx=1,pady=1) 070: self.a_button = tk.Button(self.f_footer, text="next", font=Q_font, command = self.show_next) 071: self.a_button.pack(side=tk.RIGHT, padx=1,pady=1) 072: 073: 074: 075: def __init__(self, set_answer): 076: self.q_counter = 0 077: self.q_answers = list(set_answer) 078: tk.Frame.__init__(self, None) 079: self.pack() 080: self.init_title() 081: self.init_board() 082: self.init_footer() 083: 084: 085: 086: def refresh(self, forward): 087: """前後の解を表示するのに使います""" 088: i_now = self.q_counter 089: self.q_counter += 1 if forward else -1 090: self.s_counter.set("%d/12" % (1 + self.q_counter)) 091: for i, j, is_add in qdiff(self.q_answers[self.q_counter], self.q_answers[i_now]): 092: tk.Label(self.f_board, image=self.cell_images[qmod(i,j) + (2 if is_add else 0)]).grid(row=i, column=j) 093: 094: 095: 096: def show_next(self): 097: """前の解を表示します""" 098: if(self.q_counter < 11): 099: self.refresh(True) 100: 101: 102: 103: def show_prev(self): 104: """次の解を表示します""" 105: if(self.q_counter > 0): 106: self.refresh(False) 107: 108: 109: 110: 111: 112: if __name__ == "__main__": 113: que = Queen(q.nqueen(8)) 114: que.pack() 115: que.mainloop()
$python queen_tk.py
とすると、図2のように表示されます。
Pythonの 内包表現は 便利です。 Python3.0ではリスト以外にも集合、 辞書、 イテレータで 内包表現が 使えるようになりました。
HOME | Python | download | 書き込む |