自己的网站打不开,大港网站开发,沈阳网站制作系统,建网站的工具有哪些问题 88格的国际象棋上摆放八个皇后#xff0c;使其不能互相攻击#xff0c;即任意两个皇后都不能处于同一行、同一列或同一斜线上#xff0c;问有多少种摆法。 分析 为了简化问题#xff0c;考虑到8个皇后不同行#xff0c;则每一行放置一个皇后#xff0c;每一行的皇后… 问题 8×8格的国际象棋上摆放八个皇后使其不能互相攻击即任意两个皇后都不能处于同一行、同一列或同一斜线上问有多少种摆法。 分析 为了简化问题考虑到8个皇后不同行则每一行放置一个皇后每一行的皇后可以放置于第0、1、2、...、7列我们认为每一行的皇后有8种状态。那么我们只要套用子集树模板从第0行开始自上而下对每一行的皇后遍历它的8个状态即可。 代码
8皇后问题
n 8
x [] # 一个解n元数组
X [] # 一组解# 冲突检测判断 x[k] 是否与前 x[0~k-1] 冲突
def conflict(k):global xfor i in range(k): # 遍历前 x[0~k-1]if x[i]x[k] or abs(x[i]-x[k])abs(i-k): # 判断是否与 x[k] 冲突return Truereturn False# 套用子集树模板
def queens(k): # 到达第k行global n, x, Xif k n: # 超出最底行#print(x)X.append(x[:]) # 保存一个解注意x[:]else:for i in range(n): # 遍历第 0~n-1 列即n个状态x.append(i) # 皇后置于第i列入栈if not conflict(k): # 剪枝queens(k1)x.pop() # 回溯出栈# 解的可视化根据一个解x复原棋盘。X表示皇后
def show(x):global nfor i in range(n):print(. * (x[i]) X . *(n-x[i]-1))# 测试
queens(0) # 从第0行开始print(X[-1], \n)
show(X[-1]) 效果图 本文转自罗兵博客园博客原文链接http://www.cnblogs.com/hhh5460/p/6919204.html如需转载请自行联系原作者
