马踏棋盘python_Python基于回溯法子集树模板解决马踏棋盘问题示例

2023-11-09 05:10

本文主要是介绍马踏棋盘python_Python基于回溯法子集树模板解决马踏棋盘问题示例,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本文实例讲述了Python基于回溯法子集树模板解决马踏棋盘问题。分享给大家供大家参考,具体如下:

问题

将马放到国际象棋的8*8棋盘board上的某个方格中,马按走棋规则进行移动,走遍棋盘上的64个方格,要求每个方格进入且只进入一次,找出一种可行的方案。

分析

e04d785de4ac09405fdf6aec30c54066.png

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

效果图

49c42d2cd07f7520e0ba2ab9abeab206.png

希望本文所述对大家Python程序设计有所帮助。

这篇关于马踏棋盘python_Python基于回溯法子集树模板解决马踏棋盘问题示例的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/374135

相关文章

揭秘Python Socket网络编程的7种硬核用法

《揭秘PythonSocket网络编程的7种硬核用法》Socket不仅能做聊天室,还能干一大堆硬核操作,这篇文章就带大家看看Python网络编程的7种超实用玩法,感兴趣的小伙伴可以跟随小编一起... 目录1.端口扫描器:探测开放端口2.简易 HTTP 服务器:10 秒搭个网页3.局域网游戏:多人联机对战4.

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

C#使用SQLite进行大数据量高效处理的代码示例

《C#使用SQLite进行大数据量高效处理的代码示例》在软件开发中,高效处理大数据量是一个常见且具有挑战性的任务,SQLite因其零配置、嵌入式、跨平台的特性,成为许多开发者的首选数据库,本文将深入探... 目录前言准备工作数据实体核心技术批量插入:从乌龟到猎豹的蜕变分页查询:加载百万数据异步处理:拒绝界面

Python使用自带的base64库进行base64编码和解码

《Python使用自带的base64库进行base64编码和解码》在Python中,处理数据的编码和解码是数据传输和存储中非常普遍的需求,其中,Base64是一种常用的编码方案,本文我将详细介绍如何使... 目录引言使用python的base64库进行编码和解码编码函数解码函数Base64编码的应用场景注意

用js控制视频播放进度基本示例代码

《用js控制视频播放进度基本示例代码》写前端的时候,很多的时候是需要支持要网页视频播放的功能,下面这篇文章主要给大家介绍了关于用js控制视频播放进度的相关资料,文中通过代码介绍的非常详细,需要的朋友可... 目录前言html部分:JavaScript部分:注意:总结前言在javascript中控制视频播放

Python基于wxPython和FFmpeg开发一个视频标签工具

《Python基于wxPython和FFmpeg开发一个视频标签工具》在当今数字媒体时代,视频内容的管理和标记变得越来越重要,无论是研究人员需要对实验视频进行时间点标记,还是个人用户希望对家庭视频进行... 目录引言1. 应用概述2. 技术栈分析2.1 核心库和模块2.2 wxpython作为GUI选择的优

Java中StopWatch的使用示例详解

《Java中StopWatch的使用示例详解》stopWatch是org.springframework.util包下的一个工具类,使用它可直观的输出代码执行耗时,以及执行时间百分比,这篇文章主要介绍... 目录stopWatch 是org.springframework.util 包下的一个工具类,使用它

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

springboot security快速使用示例详解

《springbootsecurity快速使用示例详解》:本文主要介绍springbootsecurity快速使用示例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录创www.chinasem.cn建spring boot项目生成脚手架配置依赖接口示例代码项目结构启用s