先用最笨的穷举法求解,有空再研究更好的解法:
# -*- coding: gb2312 -*-
size = 8 # 棋盘大小
EMPTY = "O" # 空位
QUEEN = "X" # 皇后
# 查看棋盘的信息
def show_board(cols):
for i in range(1, size + 1):
for j in range(1, size + 1):
if j == cols[i]:
print QUEEN,
else:
print EMPTY,
print "\n",
# 检测棋盘上皇后摆法是否合法
# return:
# True(不冲突), False(有冲突)
def check_board(cols):
for i in range(1, size):
for j in range(i + 1, size + 1):
if (j - i) == abs(cols[j] - cols[i]):
return False
return True
solve_count = 0
for a in range(1, size + 1):
for b in range(1, size + 1):
for c in range(1, size + 1):
for d in range(1, size + 1):
for e in range(1, size + 1):
for f in range(1, size + 1):
for g in range(1, size + 1):
for h in range(1, size + 1):
if a <> b and a <> c and a <> d and a <> e and a <> f and a <> g and a <> h and b <> c and b <> d and b <> e and b <> f and b <> g and b <> h and c <> d and c <> e and c <> f and c <> g and c <> h and d <> e and d <> f and d <> g and d <> h and e <> f and e <> g and e <> h and f <> g and f <> h and g <> h:
cols = [0,a,b,c,d,e,f,g,h]
if check_board(cols):
solve_count += 1
show_board(cols)
print "\n",
print "found %i solves." % solve_count
posted on 2006-01-08 16:40 木野狐(Neil Chen) 阅读(541) 评论(1) 编辑 收藏 所属分类: 编程思考 、Python
Feedback
#1楼 [楼主] 2006-01-13 00:43 木野狐
参考 All Start From A Game 改进了程序,速度提高了很多,并且能计算 n 皇后问题了:
# -*- coding: gb2312 -*-
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
责任编辑:小草