python 回溯法 子集树模板 系列 —— 18、马踏棋盘

简介: 问题将马放到国际象棋的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*8棋盘board上的某个方格中,马按走棋规则进行移动,走遍棋盘上的64个方格,要求每个方格进入且只进入一次,找出一种可行的方案。

分析

img_889dcf25b72e311532dab8f5d27b149e.jpg
说明:这个图是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步

效果图

img_bbd370a418da02371e64ddecca7957e2.jpg

目录
相关文章
|
Python 数据可视化
python 回溯法 子集树模板 系列 —— 1、8 皇后问题
问题 8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。 分析 为了简化问题,考虑到8个皇后不同行,则每一行放置一个皇后,每一行的皇后可以放置于第0、1、2、...、7列,我们认为每一行的皇后有8种状态。
981 0
|
Python 机器学习/深度学习 安全
python 回溯法 子集树模板 系列 —— 19、野人与传教士问题
问题 在河的左岸有N个传教士、N个野人和一条船,传教士们想用这条船把所有人都运过河去,但有以下条件限制: (1)修道士和野人都会划船,但船每次最多只能运M个人; (2)在任何岸边以及船上,野人数目都不能超过修道士,否则修道士会被野人吃掉。
1405 0
|
23天前
|
存储 缓存 Java
Python高性能编程:五种核心优化技术的原理与Python代码
Python在高性能应用场景中常因执行速度不及C、C++等编译型语言而受质疑,但通过合理利用标准库的优化特性,如`__slots__`机制、列表推导式、`@lru_cache`装饰器和生成器等,可以显著提升代码效率。本文详细介绍了这些实用的性能优化技术,帮助开发者在不牺牲代码质量的前提下提高程序性能。实验数据表明,这些优化方法能在内存使用和计算效率方面带来显著改进,适用于大规模数据处理、递归计算等场景。
58 5
Python高性能编程:五种核心优化技术的原理与Python代码
|
2月前
|
Python
[oeasy]python055_python编程_容易出现的问题_函数名的重新赋值_print_int
本文介绍了Python编程中容易出现的问题,特别是函数名、类名和模块名的重新赋值。通过具体示例展示了将内建函数(如`print`、`int`、`max`)或模块名(如`os`)重新赋值为其他类型后,会导致原有功能失效。例如,将`print`赋值为整数后,无法再用其输出内容;将`int`赋值为整数后,无法再进行类型转换。重新赋值后,这些名称失去了原有的功能,可能导致程序错误。总结指出,已有的函数名、类名和模块名不适合覆盖赋新值,否则会失去原有功能。如果需要使用类似的变量名,建议采用其他命名方式以避免冲突。
52 14
|
2月前
|
分布式计算 大数据 数据处理
技术评测:MaxCompute MaxFrame——阿里云自研分布式计算框架的Python编程接口
随着大数据和人工智能技术的发展,数据处理的需求日益增长。阿里云推出的MaxCompute MaxFrame(简称“MaxFrame”)是一个专为Python开发者设计的分布式计算框架,它不仅支持Python编程接口,还能直接利用MaxCompute的云原生大数据计算资源和服务。本文将通过一系列最佳实践测评,探讨MaxFrame在分布式Pandas处理以及大语言模型数据处理场景中的表现,并分析其在实际工作中的应用潜力。
116 2
|
2月前
|
Unix Linux 程序员
[oeasy]python053_学编程为什么从hello_world_开始
视频介绍了“Hello World”程序的由来及其在编程中的重要性。从贝尔实验室诞生的Unix系统和C语言说起,讲述了“Hello World”作为经典示例的起源和流传过程。文章还探讨了C语言对其他编程语言的影响,以及它在系统编程中的地位。最后总结了“Hello World”、print、小括号和双引号等编程概念的来源。
126 80
|
2月前
|
存储 数据采集 人工智能
Python编程入门:从零基础到实战应用
本文是一篇面向初学者的Python编程教程,旨在帮助读者从零开始学习Python编程语言。文章首先介绍了Python的基本概念和特点,然后通过一个简单的例子展示了如何编写Python代码。接下来,文章详细介绍了Python的数据类型、变量、运算符、控制结构、函数等基本语法知识。最后,文章通过一个实战项目——制作一个简单的计算器程序,帮助读者巩固所学知识并提高编程技能。
|
2月前
|
人工智能 数据挖掘 开发者
探索Python编程之美:从基础到进阶
本文是一篇深入浅出的Python编程指南,旨在帮助初学者理解Python编程的核心概念,并引导他们逐步掌握更高级的技术。文章不仅涵盖了Python的基础语法,还深入探讨了面向对象编程、函数式编程等高级主题。通过丰富的代码示例和实践项目,读者将能够巩固所学知识,提升编程技能。无论你是编程新手还是有一定经验的开发者,这篇文章都将为你提供有价值的参考和启示。让我们一起踏上Python编程的美妙旅程吧!
|
2月前
|
小程序 开发者 Python
探索Python编程:从基础到实战
本文将引导你走进Python编程的世界,从基础语法开始,逐步深入到实战项目。我们将一起探讨如何在编程中发挥创意,解决问题,并分享一些实用的技巧和心得。无论你是编程新手还是有一定经验的开发者,这篇文章都将为你提供有价值的参考。让我们一起开启Python编程的探索之旅吧!
65 10
|
2月前
|
人工智能 数据可视化 数据挖掘
探索Python编程:从基础到高级
在这篇文章中,我们将一起深入探索Python编程的世界。无论你是初学者还是有经验的程序员,都可以从中获得新的知识和技能。我们将从Python的基础语法开始,然后逐步过渡到更复杂的主题,如面向对象编程、异常处理和模块使用。最后,我们将通过一些实际的代码示例,来展示如何应用这些知识解决实际问题。让我们一起开启Python编程的旅程吧!

热门文章

最新文章

推荐镜像

更多