E:\MyBackups\goolgedrive\myprg_main\python_my_prg\wxpython\8queen_py2\8queens_wx_sizer.py
# coding: UTF-8
#wxPython と Tkinter で Eight Queens を作る
#上サイトのコードを分析してみる
#参考サイト
#wxPython と Tkinter で Eight Queens を作る
#http://www.shido.info/py/python5.html
#Python2，Python3 超入門
#ベテランが書いた「８人の女王」プログラムから学ぶ巧みなデバッグでプログラムを解析する
#http://www.geocities.jp/hp_yamakatsu/python09.html
#Python で10進数とn進数の変換
#http://iatlex.com/python/base_change
import wx, wx.lib.rcsizer
import queen as q
#global parameter
Q_font = ("Times", 14)
# gui
class Board(wx.Panel):
def __init__(self, frame):
# 8 queens answers
# eight_queens()の出力は以下になる 解は12個
# [3, 8, 20, 31, 37, 42, 54, 57] の3なら0行3列にqueenを置く
# 8なら 1行8列にqueenを置く事になる
#print q.eight_queens()
#[
#[3, 8, 20, 31, 37, 42, 54, 57]
#[3, 14, 16, 31, 36, 41, 53, 58]
#[4, 14, 16, 26, 39, 45, 51, 57]
#[4, 9, 19, 30, 34, 47, 53, 56]
#[2, 13, 19, 24, 39, 44, 54, 57]
#[4, 14, 19, 24, 34, 47, 53, 57]
#[5, 9, 22, 24, 35, 47, 52, 58]
#[3, 13, 23, 26, 32, 46, 52, 57]
#[3, 9, 22, 26, 37, 47, 52, 56]
#[5, 11, 22, 24, 39, 41, 52, 58]
#[4, 10, 23, 27, 38, 40, 53, 57]
#[2, 13, 23, 24, 35, 46, 52, 57]
#]
self.q_answers = q.eight_queens()
answer = self.q_answers[0]
#ボタンを押す事によりカウンターの数を進めたり戻したりする
#カウンターの表示はcounter+1 となっている。
self.counter = 0
# images
#title 8qsubtitle.png:タイトルが描いてある画像
self.i_title = wx.Image('8qsubtitle.png', wx.BITMAP_TYPE_PNG).ConvertToBitmap()
#cell
#bw.png:薄い橙色の背景色のみ bg.png:緑色の背景色のみ
#qw.png:背景色がbw.pngのqueen qg.png:背景色がbg.pngのqueen
self.cell_images = [wx.Image(png, wx.BITMAP_TYPE_PNG).ConvertToBitmap() \
for png in ('bw.png', 'bg.png', 'qw.png', 'qg.png')]
# Panel
wx.Panel.__init__(self, frame, -1)
self.box = wx.BoxSizer(wx.VERTICAL)
#----------BoxSizer(box)--------------------------
#
# i_title(タイトル画像)
#
# *******RowColSizer(grid)*******
#
# 'bw.png', 'bg.png'を交互に表示
# (eight_queensの盤面)
#
# ********************************
#
# +++++++ BoxSizer(footer) ++++++
# bt1 bt2 counter
# ++++++++++++++++++++++++++++++++
#--------------------------------------------
# Title
self.box.Add(wx.StaticBitmap(self, -1, self.i_title), \
0, wx.ALIGN_CENTER | wx.ALL, 10)
#Chess Board
#GridBagSizerは一般的でないので GridSizerに変更した
#self.grid = wx.lib.rcsizer.RowColSizer()
self.grid = wx.GridSizer(8,8)
#以下のように盤面の画像がリストにはいっている
#self.cell_images = [wx.Image(png, wx.BITMAP_TYPE_PNG).ConvertToBitmap() \
# for png in ('bw.png', 'bg.png', 'qw.png', 'qg.png')]
#bw bg は背景色のみ 互い違いに色をかえてqueenのあたり筋をわかりやすい
#ようにしてある
#qw,qg はqueenを表示するが、bw,bgの背景色によって色を変えている
#jによって盤面の表示する画像を変える
#j=0でbw.png j=1でbg.png さらにそこにqueenがあれば j=2でqw.png j=3で
#qg.png となる
#queenがなければ ((i in answer) and 2 or 0)は0を返し j=qmod(i) となり盤面は010101...
#盤面画像も qw,qg,qw,qg,.....
#queenがあれば ((i in answer) and 2 or 0)は2を返し j=qmod(i)+2 となり
#盤面0に対して2 つまりbwに対してqw、 盤面1に対して3 つまりbgに対して
#qgとなる
self.bmpFlag = []
for i in range(64):
#チェス盤のみを表示
k = q.qmod(i)
self.bmpFlag.append(wx.StaticBitmap(self, -1, self.cell_images[k]))
self.grid.Add(self.bmpFlag[i], flag=wx.EXPAND)
#チェス盤の色によりqueenの色を変える
for i in answer:
k = q.qmod(i)
if k == 0:
bmp = self.cell_images[2]
self.bmpFlag[i].SetBitmap(bmp)
else:
bmp = self.cell_images[3]
self.bmpFlag[i].SetBitmap(bmp)
self.box.Add(self.grid, 0, wx.ALIGN_CENTER | wx.ALL, 10)
# Footer
self.footer = wx.BoxSizer(wx.HORIZONTAL)
#wx.ID_FORWARD,wx.ID_BACKWARD は標準IDと呼ばれるもの
#これを使うと自動的にラベル(Forward , Back) が表示される
btn1 = wx.Button(self, wx.ID_FORWARD, "")
self.Bind(wx.EVT_BUTTON, self.show_next, btn1)
self.footer.Add(btn1, 0, wx.ALIGN_CENTER_VERTICAL | wx.LEFT, 20)
btn2 = wx.Button(self, wx.ID_BACKWARD, "")
self.Bind(wx.EVT_BUTTON, self.show_prev, btn2)
self.footer.Add(btn2, 0, wx.ALIGN_CENTER_VERTICAL | wx.LEFT, 20)
self.label = wx.StaticText(self, -1, ("%d/12" % (self.counter+1)))
self.footer.Add(self.label, 0, wx.ALIGN_CENTER_VERTICAL | wx.LEFT, 20)
self.box.Add(self.footer, 0, wx.ALIGN_CENTER | wx.ALL, 10)
# Layout
#おお元のサイザーをPanelにつけるのに、SetSizerが必要だが、サイ
#ザーにサイザーをつけるのには、AddだけでSetSizerはいらない
self.SetSizer(self.box)
#refresh board and counter
def refresh(self, forward):
#counter初期値0
i_now = self.counter
#forward and 1 : forwardがFalseなら0を返す。Trueなら1を返す。
#()or -1 : ()がTrueなら()の中の数値を返す。()がFalseなら-1を返す
#つまり全体では、
#forward = Trueなら1 forward = Falseなら-1を返す
#https://qiita.com/keisuke-nakata/items/e0598b2c13807f102469
#下の式は右の式と等価 self.counter += ((forward and 1) or -1)
#self.counter += forward and 1 or -1
self.counter += ((forward and 1) or -1)
#カウンターを表示 counter初期値は0
self.label.SetLabel("%d/12" % (1 + self.counter))
a_next = self.q_answers[self.counter]
a_now = self.q_answers[i_now]
q_or_b=0
#queenの位値をコンソールで表示
q.printBord([i%8 for i in a_next])
#盤面を表示のアップデート
#新しいチェス盤表示でqueenのないところは、bw,bgの画像に
#新しいチェス盤表示でqueenのあるところは、qw,qgの画像にしている
#cell_images
#bw.png:薄い橙色の背景色のみ bg.png:緑色の背景色のみ
#qw.png:背景色がbw.pngのqueen qg.png:背景色がbg.pngのqueen
for i in range(64):
#チェス盤をクリア
k = q.qmod(i)
bmp = self.cell_images[k]
self.bmpFlag[i].SetBitmap(bmp)
#チェス盤の色によりqueenの色を変える
for i in a_next:
k = q.qmod(i)
if k == 0:
bmp = self.cell_images[2]
self.bmpFlag[i].SetBitmap(bmp)
else:
bmp = self.cell_images[3]
self.bmpFlag[i].SetBitmap(bmp)
#Layout()これがないとチェス盤が更新されない
#wx.Pane内の関数
#ウィンドウのサイズを変更したときにLayout関数を自動的に呼び出すかどうかを決
#定します。
#self.Layout()
#
#しかし以下のように
#__init__で
# self.bmpFlag.append(wx.StaticBitmap(self, -1, self.cell_images[j]))
# self.grid.Add(self.bmpFlag[i], flag=wx.EXPAND)
#queen.pyの回答に従ってチェス盤の画像を変更する所で
# bmp = self.cell_images[j]
# self.bmpFlag[i].SetBitmap(bmp)
#とすると self.Layout()は必要ではなくなる
#これにより、元コードで一部チェス盤に背景画像とタイトル画像が混じって表示さ
#れる事がなくなった。
def show_next(self, event):
if(self.counter < 11):
self.refresh(True)
def show_prev(self, event):
if(self.counter > 0):
self.refresh(False)
class Queen(wx.App):
def OnInit(self):
frame = wx.Frame(None, -1, "8 queens" , size=(450,500), \
style=wx.DEFAULT_FRAME_STYLE | wx.ST_NO_AUTORESIZE)
Board(frame)
self.SetTopWindow(frame)
frame.Show(True)
return True
if __name__ == "__main__":
que = Queen(redirect=False)
que.MainLoop()
E:\MyBackups\goolgedrive\myprg_main\python_my_prg\wxpython\8queen_py2\queen.py
# coding: UTF-8
#wxPython と Tkinter で Eight Queens を作る のサイトのコードを
#やや簡略化した。
#参考サイト
#wxPython と Tkinter で Eight Queens を作る
#http://www.shido.info/py/python5.html
#Python2，Python3 超入門
#ベテランが書いた「８人の女王」プログラムから学ぶ巧みなデバッグでプログラムを解析する
#http://www.geocities.jp/hp_yamakatsu/python09.html
#Python で10進数とn進数の変換
#http://iatlex.com/python/base_change
#エイトクィーンを解く関数群 ***************************************
#xをｎ進数にする
#ここでは使用しないがテストコードでよく使ったので表示しておく
#参考サイト
#Python で10進数とn進数の変換
#http://iatlex.com/python/base_change
def Base_10_to_n(X, n):
X_dumy = X
out = ''
if X_dumy == 0:
out = 0
while X_dumy>0:
out = str(X_dumy%n)+out
X_dumy = int(X_dumy/n)
#print out
return out
#qpos:queenを置いたところ *ok_pos:queen_pos(qpos)がはいり次にqueenを
#置いても大丈夫なところ
#0:queenなし 1:queenありでチェス盤を表示する
#ここでは使用しないがテストコードでよく使ったので表示しておく
def printBord(qpos, *ok_qpos):
print
bord = [[0 for i in range(8)] for j in range(8)]
for i,p in enumerate(qpos):
bord[i][p] = 1
#引数が2以上あれば
if ok_qpos != ():
#引数そのものを取り出す
ls = ok_qpos[0]
n = len(ls)
row = ok_qpos[1]
for col in ls:
bord[row][col] = "*"
for i in range(8):
for j in range(8):
print bord[i][j],
print
#チェス盤背景色を互い違いの色にする
def qmod(i):
#for i in range(64):
# qmod(i)
#とすると以下の式で iと最後の%2で0101...となるが
#0行の最後が1で終わり1行が1で始まらなければならないので
#iにi/8%2をたしている。i/8%2で奇数行は0偶数行は1となる
#ＯＫ
a = (i+i/8%2)%2
return a
#対象操作して合同なパターンをさがす---------------------------------
#チェス盤の対称操作です。90, 180, 270 度回転、上下、左右、対角線（２つ
#） の反転
#元のリストの逆順にしたリストを返す
#nreverseにlsをいれるとls自体が上書きされて並び替えられるが、ls[:]とし
#てlsの要素全部を取り出して新しいリストを作成しているので、lsは破壊されない
def reverse(ls):
return nreverse(ls[:])
#この操作で上下反転となる。
#reverse:元のリスト自体を逆順に並び替え
#ls自体が変わってしまう
def nreverse(ls):
ls.reverse()
return ls
#左右反転
def queen_usd(ls0):
"""up side down"""
return [7 - o for o in ls0]
#チェス盤を反時計回りに90度回転
#参照 taisyou_sousa.py
# 下の操作で反時計回りに90度回転の操作となる
def queen_90(ls0):
"""rotating 90 degrees"""
#[ls0.index(i) for i in range(8)] の操作により、各要素のxy座標を入
#れ替えている。
#その操作は、(0,0)～(7,7)の線対象変換していると思う。
#reverse:元のリスト自体を逆順に並び替え
#その操作は、reverse(ls) で上下反転変換している
return nreverse([ls0.index(i) for i in range(8)])
#ls0 = [0, 4, 7, 5, 2, 6, 1, 3] とすると
#リストの要素を[x座標、y座標] と表現していくと
#ls0 = [[0, 0], [4, 1], [7, 2], [5, 3], [2, 4], [6, 5], [1, 6], [3, 7]]
#線対称変換(x,y値を入れ替えると線対称変換になるようだ)
# [ls0.index(i) for i in range(8)] は
#[[0, 0], [1, 4], [2, 7], [3, 5], [4, 2], [5, 6], [6, 1], [7, 3]]
# nreverse([ls0.index(i) for i in range(8)])は
#上下反転変換(変換後のy値=7-変換前のy値)
#[[0, 7], [1, 3], [2, 0], [3, 2], [4, 5], [5, 1], [6, 6], [7, 4]]
#最終的に以下の変換となる
#入力 [[7, 2], [6, 5], [5, 3], [4, 1], [3, 7], [2, 4], [1, 6], [0, 0]]
#90度左回転[[2, 0], [5, 1], [3, 2], [1, 3], [7, 4], [4, 5], [6, 6], [0, 7]]
# 入力値
# [0, 4, 7, 5, 2, 6, 1, 3]
#o1 上の入力値と90度左反転値を比べると
#___________________x 座標が左90度回転すると原点o1がo2へ移動
#| ｙ値がそのままｘ値になる
#| o2
#| 1 0 0 0 0 0 0 0
#| 0 0 0 0 1 0 0 0 90度反転後のｙ軸は元のｘ軸と重なるが
#| 0 0 0 0 0 0 0 1 ここからみて左右対称変換（左右が入れ替わる）
#| 0 0 0 0 0 1 0 0 する。つまり
#| 0 0 1 0 0 0 0 0 反転後のy値=7-元のy値
#| 0 0 0 0 0 0 1 0
#| 0 1 0 0 0 0 0 0 頭を右に傾けて座標が左90度回転した様子を
#| 0 0 0 1 0 0 0 0 想像してみてください。
#y
#
# (0,0)～(63,63)線対称変換
# [0, 6, 4, 7, 1, 3, 5, 2]
#
# 1 0 0 0 0 0 0 0
# 0 0 0 0 0 0 1 0
# 0 0 0 0 1 0 0 0
# 0 0 0 0 0 0 0 1
# 0 1 0 0 0 0 0 0
# 0 0 0 1 0 0 0 0
# 0 0 0 0 0 1 0 0
# 0 0 1 0 0 0 0 0
#
#
# 出力値
# [2, 5, 3, 1, 7, 4, 6, 0]
#
# 0 0 1 0 0 0 0 0
# 0 0 0 0 0 1 0 0
# 0 0 0 1 0 0 0 0
# 0 1 0 0 0 0 0 0
# 0 0 0 0 0 0 0 1
# 0 0 0 0 1 0 0 0
# 0 0 0 0 0 0 1 0
# 1 0 0 0 0 0 0 0
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))
#queen_dgl_test.py
#90度回転＋上下反転
#(0,0)～(7,7)対角線対象変換
def queen_dgla(ls0):
"""reflection on diagonal (1)"""
return nreverse(queen_90(ls0))
#90度回転＋左右反転
#(0,7)～(0,7)対角線対象変換
def queen_dglb(ls0):
"""reflection on diagonal (2)"""
return queen_usd(queen_90(ls0))
#対象操作して合同なパターンをさがす-- end -------------------------
#queen_pos queen_ok queen の動作はqueen_ok_test.pyを参照
#以下の例で考える
#行数 queenを置いたところ queenを置いても大丈夫なところ,
#row qpos queen_pos(qpos)
#3 [0, 2, 4] [1, 6, 7]
# 1 0 0 0 0 0 0 0
# 0 0 1 0 0 0 0 0
# 0 0 0 0 1 0 0 0
# 0 * 0 # 0 0 * *
# 0 0 0 0 0 0 0 0
# 0 0 0 0 0 0 0 0
# 0 0 0 0 0 0 0 0
# 0 0 0 0 0 0 0 0
#queen_ok(col, qpos): 新しく col に置いた Queen がすでに盤上にある
#Queen (qpos) と利き筋が重ならなければ True を返す。
#現在の、あるcolの列に対して検査をしている。
def queen_ok(col, qpos):
"""check if the queen's position is ok"""
r = len(qpos) #3
for i in range(r):
c = qpos[i] #c = 0, 2 ,4
j = r - i #j = 3, 2, 1
#次3行のcolに置くとして、
# col = 0～7
# c == col: 列が同じ
# col=3に置くとしてc=0ならj=3 3+3!=0 3-3=0
# つまり3行col列に置くとしてそれから上離れた分（j）だけcol-+jと
# すると行が同じ、言い換えれば斜めに利き筋が重なる事になる
if c == col or col + j == c or col - j == c :
return False
return True
#すでに盤上にある Queen と重ならない Queen の位置を返します。
#現在の行の全ての列にたいして検査をしている。cは列数字
def queen_pos(qpos):
"""it retunrs possible queen positions"""
return [c for c in range(8) if queen_ok(c, qpos)]
#エイトクィーンを解く関数群 end *************************************
# メイン関数 ******************************************************
#エイトクィーンは８行×８列
#解を求める関数は queen(row, qpos) です。 この関数は、row 行までの
#Queen の位置を qpos に保持し、それを元に (row + 1) 行目の安全な
#Queen の位置をqueen_pos で求め、 それを qpos に足していきます。
#row=8 となったら解をハッシュテーブルに登録します
def eight_queens():
"""solving 8 queens taking symmetry operations into account"""
def queen_setlist(qpos):
if q_list == []:
q_list.append(qpos)
return
else:
flg_break = 0
flg_app = 0
for ls in q_list:
for sop in (reverse, queen_usd, queen_90,
queen_180, queen_270, queen_dgla, queen_dglb):
if sop(ls) == qpos:
flg_app = 0
flg_break = 1
break
else:
flg_app = 1
if flg_break == 1:
break
if flg_app == 1:
q_list.append(qpos)
return
#qposを連続番号方式のリストにする
def changeList(lss):
new_q_list = []
new_ls = []
for ls in lss:
new_ls = []
for i in ls:
n = ls.index(i)
new_i = i + n * 8
new_ls.append(new_i)
new_q_list.append(new_ls)
return new_q_list
# メイン関数の中のメイン関数 ---------------------------------
#エイトクィーンは８行×８列
#解を求める関数は queen(row, qpos) です。 この関数は、row 行までの
#Queen の位置を qpos に保持し、それを元に (row + 1) 行目の安全な
#Queen の位置をqueen_pos で求め、 それを qpos に足していきます。
#row=8 となったら解をハッシュテーブルに登録します
def queen(row, qpos):
if row == 8:
queen_setlist(qpos)
else:
#queen_pos: すでに盤上にある Queen と重ならない Queen の位
#置を返します。
#queen_pos: すでに盤上にある Queen と重ならない Queen の位
#置を返します。
#解のひとつが [0, 6, 4, 7, 1, 3, 5, 2] とするならば
#例えばqposが[0.6] まで行ったら queen_pos(qpos)=[ 4, 7, 1, 3,
#5, 2] を含む複数の要素数6のリストを返す
for c in queen_pos(qpos):
queen(1+row, qpos+[c])
# 実行結果
# 行数 queenを置いたところ queenを置いても大丈夫なところ,
# row qpos queen_pos(qpos)
# 0 [] [0, 1, 2, 3, 4, 5, 6, 7]
#
# * * * * * * * *
# 0 0 0 0 0 0 0 0
# 0 0 0 0 0 0 0 0
# 0 0 0 0 0 0 0 0
# 0 0 0 0 0 0 0 0
# 0 0 0 0 0 0 0 0
# 0 0 0 0 0 0 0 0
# 0 0 0 0 0 0 0 0
#
# 行数 queenを置いたところ queenを置いても大丈夫なところ,
# row qpos queen_pos(qpos)
# 1 [0] [2, 3, 4, 5, 6, 7]
#
# 1 0 0 0 0 0 0 0
# 0 0 * * * * * *
# 0 0 0 0 0 0 0 0
# 0 0 0 0 0 0 0 0
# 0 0 0 0 0 0 0 0
# 0 0 0 0 0 0 0 0
# 0 0 0 0 0 0 0 0
# 0 0 0 0 0 0 0 0
#
# 行数 queenを置いたところ queenを置いても大丈夫なところ,
# row qpos queen_pos(qpos)
# 2 [0, 2] [4, 5, 6, 7]
#
# 1 0 0 0 0 0 0 0
# 0 0 1 0 0 0 0 0
# 0 0 0 0 * * * *
# 0 0 0 0 0 0 0 0
# 0 0 0 0 0 0 0 0
# 0 0 0 0 0 0 0 0
# 0 0 0 0 0 0 0 0
# 0 0 0 0 0 0 0 0
#
# 行数 queenを置いたところ queenを置いても大丈夫なところ,
# row qpos queen_pos(qpos)
# 3 [0, 2, 4] [1, 6, 7]
#
# 1 0 0 0 0 0 0 0
# 0 0 1 0 0 0 0 0
# 0 0 0 0 1 0 0 0
# 0 * 0 0 0 0 * *
# 0 0 0 0 0 0 0 0
# 0 0 0 0 0 0 0 0
# 0 0 0 0 0 0 0 0
# 0 0 0 0 0 0 0 0
#ここが全体のコードの出発点
q_list = []
queen(0, [])
return changeList(q_list)
if __name__=='__main__':
#enumerate:リストなどの要素と共にインデックスを取得
#エイトクィーンの12の解が出力される
for i, a in enumerate(eight_queens()):
print '%2d: %s' % (i+1, a)
# 元コードの実行結果
# queen.py だけの実行結果
# 1: [3, 8, 20, 31, 37, 42, 54, 57]
# 2: [3, 14, 16, 31, 36, 41, 53, 58]
# 3: [4, 14, 16, 26, 39, 45, 51, 57]
# 4: [4, 9, 19, 30, 34, 47, 53, 56]
# 5: [2, 13, 19, 24, 39, 44, 54, 57]
# 6: [4, 14, 19, 24, 34, 47, 53, 57]
# 7: [5, 9, 22, 24, 35, 47, 52, 58]
# 8: [3, 13, 23, 26, 32, 46, 52, 57]
# 9: [3, 9, 22, 26, 37, 47, 52, 56]
# 10: [5, 11, 22, 24, 39, 41, 52, 58]
# 11: [4, 10, 23, 27, 38, 40, 53, 57]
# 12: [2, 13, 23, 24, 35, 46, 52, 57]
# 改変コードの実行結果
# 1: [0, 12, 23, 29, 34, 46, 49, 59]
# 2: [0, 13, 23, 26, 38, 43, 49, 60]
# 3: [1, 11, 21, 31, 34, 40, 54, 60]
# 4: [1, 12, 22, 24, 34, 47, 53, 59]
# 5: [1, 12, 22, 27, 32, 47, 53, 58]
# 6: [1, 13, 16, 30, 35, 47, 50, 60]
# 7: [1, 13, 23, 26, 32, 43, 54, 60]
# 8: [1, 14, 18, 29, 39, 44, 48, 59]
# 9: [1, 14, 20, 31, 32, 43, 53, 58]
# 10: [2, 12, 17, 31, 32, 46, 51, 61]
# 11: [2, 12, 23, 27, 32, 46, 49, 61]
# 12: [2, 13, 17, 28, 39, 40, 54, 59]
#qposは以下となる
#qposのリストからqueenの置き方は 盤面の一行目0番目、2行4番目...と置く
#事になる
#92コの解のうち上下反転，左右反転，回転を除くと12コの解になる。
#それが上の実行結果となる
#上のリストからqueenを置くには一行目の左端が0番から右端7番、2行目の左
#端が8番と連続番号になっている
# [3, 8, 20, 31, 37, 42, 54, 57] をqposに変換するには各要素に-0, -8,
# -16,....とすればいい
0 件のコメント:
コメントを投稿