E:\MyBackups\goolgedrive\myprg_main\python_my_prg\wxpython\8queen_py\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
#! usr/bin/env python
"""
eight queens, whose gui uses wx sizer
"""
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):
#qmod:01の繰り返し
#answer:queen()の最初の答え [3, 8, 20, 31, 37, 42, 54, 57]
#qmod(i)は 010101...... となる
#self.counter += ((forward and 1) or -1) において
#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)
#参照 qmod_test.py
j = q.qmod(i) + ((i in answer) and 2 or 0)
# 実行結果
# i 0
# qmod(i) 0
# i in answer False 0がanswerになければFalse
# (i in answer) and 2 False 上がFalseなら False
# ((i in answer) and 2 or 0) 0 上がFalseなら 0
# j = qmod(i) + ((i in answer) and 2 or 0) 0
#
#
# i 1
# qmod(i) 1
# i in answer False
# (i in answer) and 2 False
# ((i in answer) and 2 or 0) 0
# j = qmod(i) + ((i in answer) and 2 or 0) 1
#
#
# i 2
# qmod(i) 0
# i in answer False
# (i in answer) and 2 False
# ((i in answer) and 2 or 0) 0
# j = qmod(i) + ((i in answer) and 2 or 0) 0
#
#
# i 3
# qmod(i) 1
# i in answer True 3がanswerにあれば True
# (i in answer) and 2 2 上がTrueなら 2
# ((i in answer) and 2 or 0) 2 上が0でない(Trueなら) 2
# j = qmod(i) + ((i in answer) and 2 or 0) 3
#
#元コードを以下に変更した
#self.grid.Add( \
# wx.StaticBitmap(self, -1, self.cell_images[j]), \
# flag=wx.EXPAND, row=i/8, col=i%8)
self.bmpFlag.append(wx.StaticBitmap(self, -1, self.cell_images[j]))
self.grid.Add(self.bmpFlag[i], flag=wx.EXPAND)
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
self.SetSizer(self.box)
# self.Bind(wx.EVT_SIZE, self.on_size)
#ウィンドウのサイズを変更したときにLayout関数を自動的に呼び出すかどうかを決
#定します。
#元コードには有効になっているが、コード変更したので以下はコメントアウトでよい
#self.Layout()
#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
#set_difference(a,b):リストaからリストbに含まれる要素を除いたリストを返す
#for cells in ....
#最初に元のリストに対して新しいリストにない要素を返す
#次にに新しいリストに対して古いリストにない要素を返す
for cells in [q.set_difference(a_now, a_next), q.set_difference(a_next, a_now)]:
for i in cells:
#bw.png:薄い橙色の背景色のみ bg.png:緑色の背景色のみ
#qw.png:背景色がbw.pngのqueen qg.png:背景色がbg.pngのqueen
#set_difference(a_now, a_next)の要素の時は背景画像のみにする
#qmod(i)==0→j=0 qmod(i)==1→j=1 にする
#set_difference(a_next, a_now)の要素の時はqueen付き画像にする
#qmod(i)==0→j=2 qmod(i)==1→j=3 にする
#最初に元のリストに対して新しいリストにない要素を返す
#つまり背景画像を表示するのだから、q_or_b=0 としてj=q.qmod(i)だけで
#いい
#次にに新しいリストに対して古いリストにない要素を返す
#qmod(i)にしたがったqueen付き画像を表示するのだから、j=q.qmod(i)+2と
#なる
j = q.qmod(i) + q_or_b
#元コードで一部チェス盤に背景画像とタイトル画像が混じって表示される
#self.grid.Add( \
# wx.StaticBitmap(self, -1, self.cell_images[j]), \
# flag=wx.EXPAND, row=i/8, col=i%8)
#
#以下のように変更してＯＫとなる
#参考サイト
#理想のユーザ・インターフェイスを求めて
#表示されている画像の切り替え方法の練習
#https://ideal-user-interface.hatenablog.com/entry/20100402/1271661045
bmp = self.cell_images[j]
self.bmpFlag[i].SetBitmap(bmp)
q_or_b += 2
#元リスト [3, 8, 20, 31, 37, 42, 54, 57]
#新リスト [3, 14, 16, 31, 36, 41, 53, 58] とすると
# 実行結果
# q.set_difference(a_now, a_next) [8, 20, 37, 42, 54, 57]
# q.set_difference(a_next, a_now) [14, 16, 36, 41, 53, 58]
#
# q.set_difference(a_now, a_next) [8, 20, 37, 42, 54, 57]
# i 8
# q.qmod(i) 1
# q_or_b 0
# j = q.qmod(i) + q_or_b 1
# row 4
# col 0
# i 20
# q.qmod(i) 0
# q_or_b 0
# j = q.qmod(i) + q_or_b 0
# row 10
# col 4
# i 37
# q.qmod(i) 1
# q_or_b 0
# j = q.qmod(i) + q_or_b 1
# row 18
# col 5
# i 42
# q.qmod(i) 1
# q_or_b 0
# j = q.qmod(i) + q_or_b 1
# row 21
# col 2
# i 54
# q.qmod(i) 0
# q_or_b 0
# j = q.qmod(i) + q_or_b 0
# row 27
# col 6
# i 57
# q.qmod(i) 0
# q_or_b 0
# j = q.qmod(i) + q_or_b 0
# row 28
# col 1
# q.set_difference(a_next, a_now) [14, 16, 36, 41, 53, 58]
# i 14
# q.qmod(i) 1
# q_or_b 2
# j = q.qmod(i) + q_or_b 3
# row 7
# col 6
# i 16
# q.qmod(i) 0
# q_or_b 2
# j = q.qmod(i) + q_or_b 2
# row 8
# col 0
# i 36
# q.qmod(i) 0
# q_or_b 2
# j = q.qmod(i) + q_or_b 2
# row 18
# col 4
# i 41
# q.qmod(i) 0
# q_or_b 2
# j = q.qmod(i) + q_or_b 2
# row 20
# col 1
# i 53
# q.qmod(i) 1
# q_or_b 2
# j = q.qmod(i) + q_or_b 3
# row 26
# col 5
# i 58
# q.qmod(i) 1
# q_or_b 2
# j = q.qmod(i) + q_or_b 3
# row 29
# col 2
#self.box.Add(self.grid, 0, wx.ALIGN_CENTER | wx.ALL, 10)
#self.SetSizer(self.box)
#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)
# def on_size(self, event):
# self.Layout()
# self.Refresh()
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_py\queen.py
# coding: UTF-8
#参考サイト
#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
#! 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
#リストaからリストbに含まれる要素を除いたリストを返す
def set_difference(a, b):
return [x for x in a if not x in b]
#元のリストの逆順にしたリストを返す
#nreverseにlsをいれるとls自体が上書きされて並び替えられるが、ls[:]とし
#てlsの要素全部を取り出して新しいリストを作成しているので、lsは破壊されない
def reverse(ls):
return nreverse(ls[:])
#引数にはqposの連続番号表示のリストの要素が入る。以下のようなかんじで
#for i in range(64):
#for i in [8, 20, 37]
#n / 8 #行インデックス
#n % 8 #列インデックスdef qmod(n):
#(n / 8 - n % 8) #行インデックス-列インデックス
#(n / 8 - n % 8)の結果をチェス盤位値にいれたもの
# 0 -1 -2 -3 -4 -5 -6 -7
# 1 0 -1 -2 -3 -4 -5 -6
# 2 1 0 -1 -2 -3 -4 -5
# 3 2 1 0 -1 -2 -3 -4
# 4 3 2 1 0 -1 -2 -3
# 5 4 3 2 1 0 -1 -2
# 6 5 4 3 2 1 0 -1
# 7 6 5 4 3 2 1 0
#(n / 8 - n % 8) % 2 #0101の数列になる
#
def qmod(n):
return (n / 8 - n % 8) % 2
#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
#参照 queen_decode_test.py
#入力 1299851 リスト表示では[0, 4, 7, 5, 2, 6, 1, 3] で考えてみる
#出力 [3, 9, 22, 26, 37, 47, 52, 56] となる
#リストの要素:x座標 リストのインデックス:y座標 表示から
#チェス盤の左端から0で始まるの連続番号表示形式となる
def queen_decode(c):
"""decode integer to list"""
ls1=[]
for i in range(8):
#c=1299851とすると2進数表示で c=100111101010110001011
#7=111 c & 7 でcの末の3ビットを取り出している
#1299851はリスト表示では[0, 4, 7, 5, 2, 6, 1, 3] なので
#インデックス最後の3を取り出している。
#i: 0～7 では i<<3 は以下のようになる
# i 0
# i<<3 0
# i 1
# i<<3 8
# i 2
# i<<3 16
# i 3
# i<<3 24
# i 4
# i<<3 32
# i 5
# i<<3 40
# i 6
# i<<3 48
# i 7
# i<<3 56
# | 演算子で各数値を足していることになる
#これでリストが、0から63までの連続番号表示となる
ls1.append((c & 7) | (i << 3))
# c = c >> 3 で cの末の3ビットを消して、上に戻り又cの末3ビッ
# トを取り出している。 以下これを繰り返している
c = c >> 3
return ls1
#実行結果
#入力 1299851 リスト表示では[0, 4, 7, 5, 2, 6, 1, 3]
#出力 [3, 9, 22, 26, 37, 47, 52, 56]"
#c(10進数) 1299851
#c 100111101010110001011
#7 111
#c & 7 11
#i(10進数) 0
#i 0
#i<<3 0
#i<<3(10進数) 0
#(c & 7) | (i << 3) 11
#(c & 7) | (i << 3)(10進数) 3
#(c & 7) | i (10進数) 3
#c = c >> 3 100111101010110001
#
#c(10進数) 162481
#c 100111101010110001
#7 111
#c & 7 1
#i(10進数) 1
#i 1
#i<<3 1000
#i<<3(10進数) 8
#(c & 7) | (i << 3) 1001
#(c & 7) | (i << 3)(10進数) 9
#(c & 7) | i (10進数) 1
#c = c >> 3 100111101010110
#
#c(10進数) 20310
#c 100111101010110
#7 111
#c & 7 110
#i(10進数) 2
#i 10
#i<<3 10000
#i<<3(10進数) 16
#(c & 7) | (i << 3) 10110
#(c & 7) | (i << 3)(10進数) 22
#(c & 7) | i (10進数) 6
#c = c >> 3 100111101010
# .....
# .....
# .....
# .....
#[3, 9, 22, 26, 37, 47, 52, 56]
#qposのリストを一意の数値に変換している
#ls0 = [0, 4, 7, 5, 2, 6, 1, 3] なら1299851 となる
#参照 queen_encode_test.py
def queen_encode(ls0):
"""encode list into integer"""
c = 0
for obj in ls0:
#7は2進数で111
#cが 100111ならば c << 3 で 100111000 と右に000とつく
#objが最高でも7なので、obj=7とする | 演算子で100111111 となる
#これを繰り返すのだから
# つまり3ビットごとにリストの要素が入っていく事になる
c = (c << 3) | obj
return c
#実行結果
# 入力 [0, 4, 7, 5, 2, 6, 1, 3]
# 出力 1299851
#
# c 0
# c<<3 0
# obj (10進数) 0
# obj 0
# c = (c << 3) | obj 0
#
# c 0
# c<<3 0
# obj (10進数) 4
# obj 100
# c = (c << 3) | obj 100
#
# c 100
# c<<3 100000
# obj (10進数) 7
# obj 111
# c = (c << 3) | obj 100111
#
# c 100111
# c<<3 100111000
# obj (10進数) 5
# obj 101
# c = (c << 3) | obj 100111101
#
#対象操作して合同なパターンをさがす---------------------------------
#チェス盤の対称操作です。90, 180, 270 度回転、上下、左右、対角線（２つ
#） の反転
### symmetry operations
#この操作で上下反転となる。
#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
#
# 実行結果
# 0 0 0 0 0 0 0 1
# 0 0 0 0 0 1 0 0
# 0 0 1 0 0 0 0 0
# 0 0 0 0 0 0 1 0
# 0 1 0 0 0 0 0 0
# 0 0 0 1 0 0 0 0
#
# [ls0.index(i) for i in range(8)]
# [0, 6, 4, 7, 1, 3, 5, 2]
# [[0, 0], [1, 4], [2, 7], [3, 5], [4, 2], [5, 6], [6, 1], [7, 3]]
# ls0のxy表示のxy要素を入れ替えたリストにとなっている
# この操作は、[0,0]～[7,7]の線対象変換になっている
#
# 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
#
# nreverse([ls0.index(i) for i in range(8)])
# [2, 5, 3, 1, 7, 4, 6, 0]
# [[0, 7], [1, 3], [2, 0], [3, 2], [4, 5], [5, 1], [6, 6], [7, 4]]
# [ls0.index(i) for i in range(8)]の結果のls0のxy表示のy要素を
# 新y要素 = 7 - 元y要素 としたリストとなっている
# reverse(ls) で上下反転変換となる
#
# 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 -------------------------
#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
#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"""
#解を辞書に登録 ls0はqpos リストのxy座標表示
#print eight_queens()
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
キーが個別の解である場合、値はTrueです。それ以外の場合はFalseです。
"""
#qposのリストから一意にきまる数値に変換
c0 = queen_encode(ls0)
if not (c0 in q_hash):
#関数のタプル？から、各関数名自体をsopに投げてsop(ls0)の処
#理をしている
#対象操作で合同となるパターンのものは、数値変換後その値をFalse
#とする
for sop in (reverse, queen_usd, queen_90,
queen_180, queen_270, queen_dgla, queen_dglb):
#http://www.geocities.jp/hp_yamakatsu/python09.html
#94行目でこの7つの関数から出力される解答配列を解答番号
#に変換しキーとして， バリューを False として，q_hash
#に登録する
q_hash[queen_encode(sop(ls0))] = False
#95行目で，関数 queen()から受け取ったものを True として
#q_hash に登録する。ハッシュ（辞書配列）は自動的にキー
#の昇順に並び替えられる。
q_hash[c0] = True
# メイン関数の中のメイン関数 ---------------------------------
#エイトクィーンは８行×８列
#解を求める関数は queen(row, qpos) です。 この関数は、row 行までの
#Queen の位置を qpos に保持し、それを元に (row + 1) 行目の安全な
#Queen の位置をqueen_pos で求め、 それを qpos に足していきます。
#row=8 となったら解をハッシュテーブルに登録します
def queen(row, qpos):
if row == 8:
queen_sethash(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_hash={}
queen(0, [])
#辞書オブジェクト.iteritems()」はキーと値のペアのタプルを返します
#print [queen_decode(key) for key, val in q_hash.iteritems() if val]
#[[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]]
#q_hashの中から対象操作で合同となるものを省いたもの、値がTrueのも
#のだけ返す
return [queen_decode(key) for key, val in q_hash.iteritems() if val]
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]
#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, 4, 7, 5, 2, 6, 1, 3]
# [0, 5, 7, 2, 6, 3, 1, 4]
# [0, 6, 3, 5, 7, 1, 4, 2]
# [0, 6, 4, 7, 1, 3, 5, 2]
# [1, 3, 5, 7, 2, 0, 6, 4]
# [1, 4, 6, 0, 2, 7, 5, 3]
# [1, 4, 6, 3, 0, 7, 5, 2]
# [1, 5, 0, 6, 3, 7, 2, 4]
# [1, 5, 7, 2, 0, 3, 6, 4]
# [1, 6, 2, 5, 7, 4, 0, 3]
# [1, 6, 4, 7, 0, 3, 5, 2]
# [1, 7, 5, 0, 2, 4, 6, 3]
# [2, 0, 6, 4, 7, 1, 3, 5]
# [2, 4, 1, 7, 0, 6, 3, 5]
# [2, 4, 1, 7, 5, 3, 6, 0]
# [2, 4, 6, 0, 3, 1, 7, 5]
# [2, 4, 7, 3, 0, 6, 1, 5]
# [2, 5, 1, 4, 7, 0, 6, 3]
# [2, 5, 1, 6, 0, 3, 7, 4]
# [2, 5, 1, 6, 4, 0, 7, 3]
# [2, 5, 3, 0, 7, 4, 6, 1]
# [2, 5, 3, 1, 7, 4, 6, 0]
# [2, 5, 7, 0, 3, 6, 4, 1]
# [2, 5, 7, 0, 4, 6, 1, 3]
# [2, 5, 7, 1, 3, 0, 6, 4]
# [2, 6, 1, 7, 4, 0, 3, 5]
# [2, 6, 1, 7, 5, 3, 0, 4]
# [2, 7, 3, 6, 0, 5, 1, 4]
# [3, 0, 4, 7, 1, 6, 2, 5]
# [3, 0, 4, 7, 5, 2, 6, 1]
# [3, 1, 4, 7, 5, 0, 2, 6]
# [3, 1, 6, 2, 5, 7, 0, 4]
# [3, 1, 6, 2, 5, 7, 4, 0]
# [3, 1, 6, 4, 0, 7, 5, 2]
# [3, 1, 7, 4, 6, 0, 2, 5]
# [3, 1, 7, 5, 0, 2, 4, 6]
# [3, 5, 0, 4, 1, 7, 2, 6]
# [3, 5, 7, 1, 6, 0, 2, 4]
# [3, 5, 7, 2, 0, 6, 4, 1]
# [3, 6, 0, 7, 4, 1, 5, 2]
# [3, 6, 2, 7, 1, 4, 0, 5]
# [3, 6, 4, 1, 5, 0, 2, 7]
# [3, 6, 4, 2, 0, 5, 7, 1]
# [3, 7, 0, 2, 5, 1, 6, 4]
# [3, 7, 0, 4, 6, 1, 5, 2]
# [3, 7, 4, 2, 0, 6, 1, 5]
# [4, 0, 3, 5, 7, 1, 6, 2]
# [4, 0, 7, 3, 1, 6, 2, 5]
# [4, 0, 7, 5, 2, 6, 1, 3]
# [4, 1, 3, 5, 7, 2, 0, 6]
# [4, 1, 3, 6, 2, 7, 5, 0]
# [4, 1, 5, 0, 6, 3, 7, 2]
# [4, 1, 7, 0, 3, 6, 2, 5]
# [4, 2, 0, 5, 7, 1, 3, 6]
# [4, 2, 0, 6, 1, 7, 5, 3]
# [4, 2, 7, 3, 6, 0, 5, 1]
# [4, 6, 0, 2, 7, 5, 3, 1]
# [4, 6, 0, 3, 1, 7, 5, 2]
# [4, 6, 1, 3, 7, 0, 2, 5]
# [4, 6, 1, 5, 2, 0, 3, 7]
# [4, 6, 1, 5, 2, 0, 7, 3]
# [4, 6, 3, 0, 2, 7, 5, 1]
# [4, 7, 3, 0, 2, 5, 1, 6]
# [4, 7, 3, 0, 6, 1, 5, 2]
# [5, 0, 4, 1, 7, 2, 6, 3]
# [5, 1, 6, 0, 2, 4, 7, 3]
# [5, 1, 6, 0, 3, 7, 4, 2]
# [5, 2, 0, 6, 4, 7, 1, 3]
# [5, 2, 0, 7, 3, 1, 6, 4]
# [5, 2, 0, 7, 4, 1, 3, 6]
# [5, 2, 4, 6, 0, 3, 1, 7]
# [5, 2, 4, 7, 0, 3, 1, 6]
# [5, 2, 6, 1, 3, 7, 0, 4]
# [5, 2, 6, 1, 7, 4, 0, 3]
# [5, 2, 6, 3, 0, 7, 1, 4]
# [5, 3, 0, 4, 7, 1, 6, 2]
# [5, 3, 1, 7, 4, 6, 0, 2]
# [5, 3, 6, 0, 2, 4, 1, 7]
# [5, 3, 6, 0, 7, 1, 4, 2]
# [5, 7, 1, 3, 0, 6, 4, 2]
# [6, 0, 2, 7, 5, 3, 1, 4]
# [6, 1, 3, 0, 7, 4, 2, 5]
# [6, 1, 5, 2, 0, 3, 7, 4]
# [6, 2, 0, 5, 7, 4, 1, 3]
# [6, 2, 7, 1, 4, 0, 5, 3]
# [6, 3, 1, 4, 7, 0, 2, 5]
# [6, 3, 1, 7, 5, 0, 2, 4]
# [6, 4, 2, 0, 5, 7, 1, 3]
# [7, 1, 3, 0, 6, 4, 2, 5]
# [7, 1, 4, 2, 0, 6, 3, 5]
# [7, 2, 0, 5, 1, 4, 6, 3]
# [7, 3, 0, 2, 5, 1, 6, 4]
0 件のコメント:
コメントを投稿