HOME

Python

download

書き込む

N Queen (Python 3.0 版 )

1. 初めに

N Queen とは N x N のチェスの Queen を利きが互いに重ならないように配置するパズルです。 Queen は将棋の飛車と角を合わせた利きをもち、縦横斜めに好きなだけ移動することができます。 詳しくは wikipedia をみてください。 以前、 Scheme 版 , Python 2 版 を書いてみたのですが、 気が向いたので Python 3.0 でも書いてみました。うまく書けたので、アップします。

2. プログラミングの戦略

縦の升目は 全て異なるようにしないと利きがぶつかるので、 N Queen は 集合 {0,1, .... (n-1)} から要素を取り出し、それを斜めの利きが重ならないように並べていく 問題に 置き換えることができます。

図 1: Queen の配置。この配置をタプルで表すと (5, 0, 4, 1, 7, 2, 6, 3) になる。

2.1. 利きの重ならない配置を求める

abs(縦の升目の差) == 横の升目の差

2.2. 対称操作を考慮する

チェスの盤には 4 種類の反転と 3 種類の回転対称性があるので、 駒を置き終えたら、それらの対称操作をして、既知の解にならないかチェックをし、 新しい解だけを追加します。

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)

3.1. 盤 に Queen を配置していく

3.1.1. 利きのチェック

• 横の升目はタプルのインデックスで、縦の升目は各要素の値で表します
• 縦の升目として選べる 値の集合の 初期値を frozenset(range(n)) として、配置するごとに 取り除いていくので、

1. abs(row1-row)==col+1 だと利きが重なります。
   ここで、 row1 は新しく置く駒の縦の升目、 row は既にあるこまの縦 の升目、 col は既にあるこまの横 の升目です。
2. abs(row1-row)!=col+1 for col, row in enumerate(ls) とすると、 ls 中にある (盤中にある) すべてのこまについて、 新しく置くこまと利きが 重ならないかを返す generatorが 生成します( 重ならないときTrue)。 Python 3.0では 、内包表現で generatorを 生成することができます。
3. all() 関数を使って、新しく置くこまと、既に置いてあるこま全ての利きが重ならないときTrue を返すようにします。

3.1.2. Queen を盤に置いていく

3.2. 対称操作

• 上下、左右、対角線での反転 (あわせて 4 つ)
• 90, 180, 270 度 の 回転 (3 つ)

is_different(cols, sols) で、解 (cols) と その対称操作によって生じた解が今まで見つかった解の集合 (sols) に含まれているか調べます。 cols に全ての対称操作を施しても、 sols の中に同じものが見つからなければTrueを 返します。

nqueen()で、is_different() が True を返したものだけを解 集合に加えていきます。

if __name__=='__main__' 以下で 、 nqueen() を呼んで、見つかった解を順に表示します。

4. tkinter で表示する

[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 の２つの解の差をとります。効率的に表示を更新するのに使います"""
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()

図２: 8-Queen の解を tkinter を使って表示する。

5. 終わりに

Pythonの 内包表現は 便利です。 Python3.0ではリスト以外にも集合、 辞書、 イテレータで 内包表現が 使えるようになりました。

HOME

Python

download

書き込む