数据结构算法中写了一个八皇后解法-软件水平考试-优易学网

数据结构算法中写了一个八皇后解法

来源：优易学 2011-12-26 11:22:48 【优易学：中国教育考试门户网】资料下载 IT书店

　　先用最笨的穷举法求解，有空再研究更好的解法：
　　# -*- 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

责任编辑：小草