Python基于回溯法子集树模板解决马踏棋盘问题示例
作者:罗兵 时间:2021-08-01 15:45:43
本文实例讲述了Python基于回溯法子集树模板解决马踏棋盘问题。分享给大家供大家参考,具体如下:
问题
将马放到国际象棋的8*8棋盘board上的某个方格中,马按走棋规则进行移动,走遍棋盘上的64个方格,要求每个方格进入且只进入一次,找出一种可行的方案。
分析
说明:这个图是5*5的棋盘。
类似于迷宫问题,只不过此问题的解长度固定为64
每到一格,就有[(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1)]顺时针8个方向可以选择。
走到一格称为走了一步,把每一步看作元素,8个方向看作这一步的状态空间。
套用回溯法子集树模板。
代码
'''马踏棋盘'''
n = 5 # 8太慢了,改为5
p = [(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1)] # 状态空间,8个方向
entry = (2,2) # 出发地
x = [None]*(n*n) # 一个解,长度固定64,形如[(2,2),(4,3),...]
X = [] # 一组解
# 冲突检测
def conflict(k):
global n,p, x, X
# 步子 x[k] 超出边界
if x[k][0] < 0 or x[k][0] >= n or x[k][1] < 0 or x[k][1] >= n:
return True
# 步子 x[k] 已经走过
if x[k] in x[:k]:
return True
return False # 无冲突
# 回溯法(递归版本)
def subsets(k): # 到达第k个元素
global n, p, x, X
if k == n*n: # 超出最尾的元素
print(x)
#X.append(x[:]) # 保存(一个解)
else:
for i in p: # 遍历元素 x[k-1] 的状态空间: 8个方向
x[k] = (x[k-1][0] + i[0], x[k-1][1] + i[1])
if not conflict(k): # 剪枝
subsets(k+1)
# 测试
x[0] = entry # 入口
subsets(1) # 开始走第k=1步
效果图
希望本文所述对大家Python程序设计有所帮助。
来源:http://www.cnblogs.com/hhh5460/p/6960121.html
标签:Python,回溯法
0
投稿
猜你喜欢
python怎么判断素数
2021-09-30 11:10:33
打造“前端开发”程序员专用版EditPlus
2009-01-05 13:04:00
Python OpenCV简单的绘图函数使用教程
2023-08-02 23:22:22
设计与表达
2009-07-27 11:45:00
python 移除字符串尾部的数字方法
2023-03-18 19:38:21
如何判断SQL语句是否执行了?
2010-01-12 20:03:00
浅谈Python 中整型对象的存储问题
2021-08-12 10:33:58
XML教程—编写结构完整的XML文档
2008-10-11 13:43:00
Python操作word文档插入图片和表格的实例演示
2023-09-20 08:21:09
Python 'takes exactly 1 argument (2 given)' Python error
2022-04-19 00:26:05
Perl命令行应用程序详解
2023-08-09 19:01:18
Python 的AES加密与解密实现
2022-07-09 21:49:49
javascript封装的下拉导航菜单渐显效果
2007-08-04 20:11:00
让字体美起来
2011-06-14 09:50:21
python命令行参数argparse模块基本用法详解
2023-07-31 03:14:21
基于Django框架的权限组件rbac实例讲解
2022-09-27 17:11:51
[JS]用 或 || 来兼容FireFox
2013-06-26 14:50:47
Mysql数据库常用命令
2009-03-06 14:29:00
css3弹性盒模型
2010-05-10 20:47:00
详解Pycharm与anaconda安装配置指南
2022-09-24 01:51:45