这里有新鲜出炉的Python多线程编程,程序狗速度看过来!
Python 是一种面向对象、解释型计算机程序设计语言,由Guido van Rossum于1989年底发明,第一个公开发行版发行于1991年。Python语法简洁而清晰,具有丰富和强大的类库。它常被昵称为胶水语言,它能够把用其他语言制作的各种模块(尤其是C/C++)很轻松地联结在一起。
这篇文章主要介绍了Python基于回溯法子集树模板解决马踏棋盘问题,简单描述了国际象棋马踏棋盘问题,并结合实例形式分析了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.phperz.com/article/17/1027/350902.html