幽灵资源网 Design By www.bzswh.com
本文实例讲述了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相关内容可查看本站专题：《Python数据结构与算法教程》、《Python Socket编程技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》
希望本文所述对大家Python程序设计有所帮助。
幽灵资源网 Design By www.bzswh.com
广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站文章均来自网站采集或用户投稿，网站不提供任何软件下载或自行开发的软件！ 如有用户或公司发现本站内容信息存在侵权行为，请邮件告知！ 858582#qq.com
免责声明：本站文章均来自网站采集或用户投稿，网站不提供任何软件下载或自行开发的软件！ 如有用户或公司发现本站内容信息存在侵权行为，请邮件告知！ 858582#qq.com
幽灵资源网 Design By www.bzswh.com
暂无评论...
苹果官宣WWDC 2024！预计会有大批AI功能 - 2025/2/8
3月27日消息，苹果宣布2024年全球开发者大会（WWDC）将于6月10日至6月14日举行，巧合的是，这次大会与端午假期重合。
苹果官方表示：
在线参加 Apple 每年规模最大的开发者盛会。亲眼见证 Apple 最新平台、技术和工具的发布。了解如何创建和改进你的 App 和游戏。与 Apple 设计师和工程师互动交流，与全球开发者社区建立联系。以上活动均免费在线举行。
探索各种新的工具、框架和功能，助力你打造出理想的 App 和游戏。通过视频讲座学习新技能，与 Apple 专家进行一对一会面，以推进你的项目，完善你的构思。
Swift Student Challenge 旨在支持和鼓舞下一代开发者、创作者和企业家。太平洋时间 3 月 28 日，我们将公布今年的获奖者名单。获奖者将有资格参加在 Apple Park 举办的特别活动。我们还会选出 50 名杰出获胜者，他们将受邀前往库比提诺，获得为期三天的非凡体验，包括参加 Apple Park 的特别活动。
3月27日消息，苹果宣布2024年全球开发者大会（WWDC）将于6月10日至6月14日举行，巧合的是，这次大会与端午假期重合。
苹果官方表示：
在线参加 Apple 每年规模最大的开发者盛会。亲眼见证 Apple 最新平台、技术和工具的发布。了解如何创建和改进你的 App 和游戏。与 Apple 设计师和工程师互动交流，与全球开发者社区建立联系。以上活动均免费在线举行。
探索各种新的工具、框架和功能，助力你打造出理想的 App 和游戏。通过视频讲座学习新技能，与 Apple 专家进行一对一会面，以推进你的项目，完善你的构思。
Swift Student Challenge 旨在支持和鼓舞下一代开发者、创作者和企业家。太平洋时间 3 月 28 日，我们将公布今年的获奖者名单。获奖者将有资格参加在 Apple Park 举办的特别活动。我们还会选出 50 名杰出获胜者，他们将受邀前往库比提诺，获得为期三天的非凡体验，包括参加 Apple Park 的特别活动。
RTX 5090要首发 性能要翻倍！三星展示GDDR7显存
三星在GTC上展示了专为下一代游戏GPU设计的GDDR7内存。
首次推出的GDDR7内存模块密度为16GB，每个模块容量为2GB。其速度预设为32 Gbps（PAM3），但也可以降至28 Gbps，以提高产量和初始阶段的整体性能和成本效益。
据三星表示，GDDR7内存的能效将提高20%，同时工作电压仅为1.1V，低于标准的1.2V。通过采用更新的封装材料和优化的电路设计，使得在高速运行时的发热量降低，GDDR7的热阻比GDDR6降低了70%。