Python基于回溯法子集树模板解决马踏棋盘问题示例
作者：罗兵 发布时间：2021-08-01 15:45:43
标签：Python,回溯法
本文实例讲述了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
0
投稿猜你喜欢
- function is_email($str){ //检验email return preg_match("/
1. 警告不是异常你是不是经常在使用一些系统库或者第三方模块的时候，会出现一些既不是异常也不是错误的警告信息？这些警告信息，有时候非常多，对- 创建表create table 表名create table if not exists 表名mysql> create databa
- 在这篇文章中，将向您展示如何使用Python链接目前主流的MongoDB(V3.4.0)数据库，主要使用PyMongo(v3.4.0)和Mo
- 说明本文根据https://github.com/liuchengxu/blockchain-tutorial的内容，用python实现的，
- 目录一．准备工作二．预览1.主界面2.翻译3.支持多种语言哦三．源代码3.1 My_Translator-v2.0.py3.2 Transl
- join toString该两种方法会将数组元素的类型转换为字符串var arr = [1, [2, [3, [4, 5]]], 6];co
- 简单的XML操作：XML文件创建把下面的代码复制到按钮事件中编译执行后可在相应物理路径中产生Pos.xml文件XmlTextWriter x
- 在右键菜单中加入复制目标文件的有效存放路径（单斜杠或者双反斜杠）引言由于win10电脑自带的获取文件路径为双引号括起来的单反斜杠，如下图。&
- 本文实例总结了PHP session会话操作技巧。分享给大家供大家参考，具体如下：会话技术session将会话数据存储与服务器端，同时使会话
- Python3异步asyncio问题官方文档：https://docs.python.org/zh-cn/3/library/asyncio
- 1.将经常要用到的字段（比如经常要用这些字段来排序，或者用来做搜索），则最好将这些字段设为索引。2.字段的种类尽可能用int 或者tinyi
- 这几天想统计一下《中国人文社会科学期刊 AMI 综合评价报告（2018 年）：A 刊评价报告》中的期刊，但是只找到了该报告的PDF版，对于表
- 1. 直方图概述（1）基本概念直方图就是对图像的另外一种解释，它描述了整幅图像的灰度分布。直方图的 x 轴代表灰度值（0~255），y 轴代
- 将一个 awk 脚本移植到 Python 主要在于代码风格而不是转译。脚本是解决问题的有效方法，而 awk 是编写脚本的出色语言。它特别擅长
- 最近一直在研究网页特效,看到qq界面的折叠菜单,于是冒出个想法,自己写一个类似的,上网查了一下,发现已经有不少类似的菜单效果,不管那么多,先
- 本文主要研究的是Python对内存的使用（深浅拷贝）的相关问题，具体介绍如下。浅拷贝就是对引用的拷贝（只拷贝父对象） 深拷贝就是对对象的资源
- 前言SQLAlchemy是Python编程语言下的一款ORM框架，该框架建立在数据库API之上，使用关系对象映射进行数据库操作，简言之便是：
- 接下来我们会进入 字符串常用方法的应用阶段，重点学习字符串的内置函数。正式学习之前，我们要先了解一个词 对象 (划重点，不是男女朋友！)，只
- 一个用asp来处理jmail发信的过程，及使用方法. 发信时，直接调用这个过程就行了，很方便。<％ dim
