Python基于回溯法子集树模板实现8皇后问题

yipeiwu_com5年前Python基础

本文实例讲述了Python基于回溯法子集树模板实现8皇后问题。分享给大家供大家参考,具体如下:

问题

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 x
 for 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 True
 return False
# 套用子集树模板
def queens(k): # 到达第k行
 global n, x, X
 if 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(k+1)
   x.pop()   # 回溯,出栈
# 解的可视化(根据一个解x,复原棋盘。'X'表示皇后)
def show(x):
 global n
 for i in range(n):
  print('. ' * (x[i]) + 'X ' + '. '*(n-x[i]-1))
# 测试
queens(0) # 从第0行开始
print(X[-1], '\n')
show(X[-1])

效果图

更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程

希望本文所述对大家Python程序设计有所帮助。

相关文章

Python绘制二维曲线的日常应用详解

Python绘制二维曲线的日常应用详解

使用Python绘制出类似Excel或者MATLAB的曲线还是比较容易就能够实现的,需要用到的额外库有两个,numpy和matplotlib。使用这两个模块实现的曲线绘制其实在一定程度上...

python计算二维矩形IOU实例

python计算二维矩形IOU实例

计算交并比:交的面积除以并的面积。 要求矩形框的长和宽应该平行于图片框。不然不能用这样的公式计算。 原理,从一维上来理解:两条红线的距离之和减去黑色线之间的距离就是相交的距离。两条红线之...

python 提取tuple类型值中json格式的key值方法

标题比较麻烦,都有些叙述不清;昨天下午在调试接口框架的时候,遇到了一个问题是这样的: 使用python 写了一个函数,return 了两个返回值比如 return a,b 于是返回的a,...

python批量下载网站马拉松照片的完整步骤

python批量下载网站马拉松照片的完整步骤

前言 目前学习python几个月了,由于自己比较喜欢跑马拉松,已经跑过了很多场比赛,前些天就写了个简单的爬虫爬取了网上三千多场马拉松比赛的报名信息。 今年5月27日,我又参加了巴图鲁...

更新pip3与pyttsx3文字语音转换的实现方法

我使用的python版本是3.5.2 今天想做个语音读取的小脚本,在网上查了一下发现python里有个pyttsx可以识别文字, 打算通过pip3 install pyttsx安装包,结...