September 18, 2006

找到的一个八皇后问题Python版解法

原文称参考了All Start From A Game
觉得有参考价值,虽然好像还不够快和简洁。以后我来自己写一个递归版的罢。
排版了一下,加了点注释。

size = 8 # 棋盘大小
EMPTY = "O" # 空位
QUEEN = "X" # 皇后

# 查看棋盘的信息
def show_board(cols):
for i in range(size):
for j in range(size):
if j == int(cols[i]) - 1:
print QUEEN,
else:
print EMPTY,
print "\n",

# 检测棋盘上皇后摆法是否合法
# return:
# True(不冲突), False(有冲突)
def check_board(cols):
for i in range(size - 1):
for j in range(i + 1, size):
if j - i == abs(int(cols[j]) - int(cols[i])):
return False
return True

# 得到全排列
def permute(seq):
seqn = [ seq.pop() ]
while seq:
newseq = []
new = seq.pop()
#print "seq:",seq,'seqn', seqn ,'new', new
for i in range(len(seqn)):
item = seqn[i]
for j in range(len(item)+1):
newseq.append(
''.join([item[:j],new,item[j:]]))
seqn = newseq
#print 'newseq',newseq
return seqn

#测试代码
if __name__ == "__main__":
solve_count = 0
numbers =
''.join([str(i) for i in range(1, size + 1)])

for x in permute(list(numbers)):
y = list(x)
if check_board(y):
solve_count += 1
show_board(y)
print "\n",

print "found %i solves." % solve_count

No comments: