E:\MyBackups\goolgedrive\myprg_main\python_my_prg\wxpython\8queen_py3\queen.py
# coding: UTF-8
#以下のサイトのN Queenのコードを自分なりに解析してみました。
#参考サイト
#N Queen (Python 3.0 版 )
#http://www.shido.info/py/queen_py3.html
#Python3ではwxPythonはインストールできない
"""N Queen: taking symmetry into account"""
import sys
def comb(f1, f2):
"""2 つの 関数 を 合成 した 関数 を 返す """
return lambda x:f1(f2(x))
# 対称 操作
# REVはlsが上書きされてしまうのでは
REV = lambda ls: list(reversed(ls)) # 左右反転
#前のqueen.pyでは以下のコードだったので式的には合っている
#return [7 - o for o in ls0]
USD = lambda ls: [ len(ls)-x-1 for x in ls ] # 上下 反転
#前のコードのまま
#nreverse([ls0.index(i) for i in range(8)])
T90 = lambda ls: [ ls.index(x) for x in range(len(ls)) ] # 90 度 回転
#前のコードでは以下だったのに、上下反転＋左右反転が180度回転と等しい
#何か数学的に深い意味があるのだろうが
#queen_90(queen_90(ls0))
T180 = comb(USD, REV) # 180 度 回転
T270 = comb(T90, T180) # 270 度 回転
D1 = comb(REV, T90) # 対角線 での 反転 その 1
D2 = comb(USD, T90) # 対角線 での 反転 その 2
#is_different(cols, sols) で、解 (cols) と その対称操作によって生じた解
#が今まで見つかった解の集合 (sols) に含まれているか調べます。 cols に全
#ての対称操作を施しても、 sols の中に同じものが見つからなければTrueを
#返します。
def is_different(cols, sols):
""" 対称性 を 考慮し ても 固有 の 解か """
#タプルの内包表記ではなく、ジェネレーターを作成している
#opの中に対称性移動する関数をいれて
#solsは集合
#op(cols)はいずれもリスト形式
return all( tuple(op(cols)) not in sols for op in (REV, USD, T90, T180, T270, D1, D2) )
#qpos:今までに置いたqueenのリスト row1:これから置く行
#col=[4, 2]なら7列2行、6列4行にqueenがおいてある
def printBord(qpos, row1):
#print()
bord = [[0 for i in range(8)] for j in range(8)]
#colの順序を逆にする
ls = [qpos[i] for i in range(len(qpos)-1, -1, -1)]
c = 8
for row in ls:
c -= 1
bord[c][row] = 1
bord[c-1][row1] = "*"
for row in range(8):
for col in range(8):
#print(bord[col][row], end='')
#print(" ", end='')
pass
#print()
pass
#print()
#新しく置く Queen と既においてある Queen の縦の升目の差の絶対値が、横の
#升目の差と等しいとき、 斜めの利きがぶつかるので、 queen_ok() では、既
#に置いてある、すべての Queen について利きが 重ならないことを確かめてい
#ます。
def queen_ok(ls, row1):
"""row1 が ls にある queen と 利き が 重な らないとき True を 返す """
#abs(row1-row)!=col+1 for col, row in enumerate(ls) とすると、 ls
#中にある (盤中にある) すべてのこまについて、 新しく置くこまと利き
#が 重ならないかを返す generatorが 生成します( 重ならないとき
# True)。 Python 3.0では 、内包表現で generatorを 生成するこ
#とができます。
#all() 関数を使って、新しく置くこまと、既に置いてあるこま全ての利
#きが重ならないときTrue を返すようにします。
#all:全ての要素がTrueの時Trueとなる
#all(リスト)などと使うが、下のジェネレーターの場合allジェネレータ
#ーとなり()がぬけている。()をいれてジェネレーターなのにそのまま
#allをつけているだけ。でもこれで動作する
#enumerate col（列）:インデックス、row（行）:要素を取得
#abs(row1-row)==col+1 ならばqueenの利き筋が重なっている
#下の図の如く col+1が列の差を表している
#queen(cols, i)を調べてみる
#iは*に置くことになる。5が3の左に追加することになり（Trueであれば）
#列は2列 行は5
# (cols= (3, 1, 4, 2, 0) i= 5
# col 0 row 3
# True
#
# col 1 row 1
# True
#
# col 2 row 4
# True
#
# col 3 row 2
# True
#
# col=4 つまり7列0行と利き筋が重なっている
# col 4 row 0
# False
#
# 0 0 0 0 0 0 0 1
# 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 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
#ここで、 row1 は新しく置く駒の縦の升目、 row は既にあるこまの縦 の
#升目、 col は既にあるこまの横 の升目です。
#input------------------------
#input()
##print()
##print( [(col, row) for col, row in enumerate(ls)] )
#col=0なら今置くrow1の右隣りがcol=0 さらに右がcol=1となる
#qpos:今までに置いたqueenのリスト row1:これから置く行
#col=[4, 2]なら7列2行、6列4行にqueenがおいてある
for col, row in enumerate(ls):
if abs(row1-row)!=col+1:
#print("col", col,"row", row)
#print("True")
#printBord(ls, row1)
pass
else:
#print("col", col,"row", row)
#print("False")
#printBord(ls, row1)
#print()
pass
#print()
#print("queen_ok return ", end='')
#print( all( abs(row1-row)!=col+1 for col, row in enumerate(ls) ))
return all( abs(row1-row)!=col+1 for col, row in enumerate(ls) )
#タプルの内包表記ではなく、ジェネレーターを作成している
#ジェネレーターにすると途中でFalseになればall()でFalseにするようだ
#all([abs(row1-row)!=col+1 for col, row in enumerate(ls) ])
#とすると最後まで forをつづける？て無駄となる
#手持ちの駒 rows にある全ての駒について、駒が置けるのであれば
#(queen_ok() が True を返す ) 、 駒を置いて、再帰的に qiter() を呼び出
#します 。
#全ての駒を配置し終わる (手持ちの 駒が 無くなる) と対称操作の チェック
#を 行い、 対称操作を考慮しても別の解だったら、 見つかった解を sols (解
#の集合) に加えます。
#n:n×n のマス目の大きさを指定する
k = 0
def nqueen(n):
"""n x n マス の N-Queen パズル を 解く """
#col 列 row 行
#qiter(cols, rows) が盤上にQueenを 置いていく関数です。
#cols は既においてあるこまを表すタプル。 rows はまだ、盤上に無い縦
#の(行)升目の 集合です。
#colsはケツから置いていくから、7列目から6、5...と決まっていく
#前のNqueenと逆で墓穴を掘った
#colsはタプル rowsは0～7のいずれかの数字
def qiter(cols, rows):
global k
#例えば以下の時
#cols= (0,) rows= frozenset({1, 2, 3, 4, 5, 6, 7})
#for i in rows:
#i= 1
#queen_ok( (0,), 1 )を計算する
#if not rows:
# print()
# print(cols)
# print(USD(cols))
# print()
#rowsが空集合でないなら
if rows:
#input------------------------
#input()
for i in rows:
n = len(rows)
k = 8 - n + 1
#print(" " * k ,end='')
#print("for i in rows:")
#print(" " * k ,end='')
#print("i=", i,"rows=", rows)
#print(" " * k ,end='')
#print("cols=", cols, "i=",i)
if queen_ok(cols, i):
#print(" " * k ,end='')
#print("queen_ok(cols, i)はTrue")
#縦の升目 i に駒を置くと、 (i,) + cols でそれをタ
#プルの先頭に追加し、 rows - {i} で、 まだおかれて
#いない駒 の集合 から取り除きます。
#rows-{i}:集合同士の引き算
#print(" " * k ,end='')
#print("qiter( (i,)+cols, rows-{i})")
#print()
#要素が1個のタプルを生成する場合は、末尾にカンマ,が必要
#タプルは要素は変更できないが、+でタプル同士を連結
#して新しいタプルを作成できる
#rowsもfrozensetで要素を変更できない集合だが-で新
#しい集合を作成しているのか？
#n -= 1
#print(" " * k ,end='')
#print("qiter")
#print(" " * k ,end='')
#print("cols=", (i,)+cols,"rows=", rows-{i})
qiter( (i,)+cols, rows-{i})
else:
#もしiで利き筋だったら次のiに進む
#かつiがrowsの終わりまできたら
#print(" " * k ,end='')
#print("queen_ok(cols, i)はFalse")
#print(" " * k ,end='')
#print()
pass
#is_different(cols, sols) で、解 (cols) と その対称操作によって生じた解
#が今まで見つかった解の集合 (sols) に含まれているか調べます。 cols に全
#ての対称操作を施しても、 sols の中に同じものが見つからなければTrueを
#返します。
elif is_different(cols, sols):
#print("elif is_different(cols, sols):")
#print
#print
#対称パターンがなければsolsにいれる
sols.add(cols)
#空集合作成
sols=set()
#frozenset(range(n)): ({0, 1, 2, 3, 4, 5, 6, 7})
#tuple()で空のタプルを返すようだ
#8queenの解が(2, 6, 7, 4, 5, 3, 1, 0)とすると2行0列、6行1列、...と
#queenを置く事になる
#前回のqposとは逆になる
#8queenは利き筋に同じqueenを置いてはだめなので0～7の数字を取り出し
#て解のタプルの中に数字を入れていっていけばいい。
#ただし途中で、利き筋になっていないか又合同なパターンは取り除く事
#が必要
qiter(tuple(), frozenset(range(n)))
return sols
if __name__=='__main__':
#sols=nqueen(int(sys.argv[1]))
sols=nqueen(8)
print ('N of solutions:', len(sols))
for sol in sols:
print (sol)
# abs(row1-row)!=col+1 実行結果
# N of solutions: 12
# (4, 6, 0, 2, 7, 5, 3, 1)
# (5, 1, 6, 0, 3, 7, 4, 2)
# (3, 0, 4, 7, 5, 2, 6, 1)
# (5, 3, 6, 0, 7, 1, 4, 2)
# (2, 5, 3, 0, 7, 4, 6, 1)
# (3, 6, 0, 7, 4, 1, 5, 2)
# (4, 2, 7, 3, 6, 0, 5, 1)
# (4, 6, 3, 0, 2, 7, 5, 1)
# (3, 5, 7, 2, 0, 6, 4, 1)
# (4, 1, 3, 6, 2, 7, 5, 0)
# (2, 5, 7, 0, 3, 6, 4, 1)
# (3, 1, 6, 2, 5, 7, 4, 0)
#
0 件のコメント:
コメントを投稿