3*3拼图复原 (8数码问题) 每步穷举搜索(BFS广度搜索) Python解法

2023-11-11 19:30

本文主要是介绍3*3拼图复原 (8数码问题) 每步穷举搜索(BFS广度搜索) Python解法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

最近有同学 让我复原一个拼图 就想用代码解决 写了个 python的解决方案.
原始图片
原始输入图片
在这里插入图片描述
复原完成图片

解题思路就是 遍历每个可能步数 如下图的遍历方式
在这里插入图片描述
想法就是用 for 遍历.
难点1.如果要记住所有遍历过程, 拼图越来越大的话,会爆内存, 需要占用的储存空间太大了.
解决方案1.就是每步都只记住上一步得出的 所有输出,在之前的输出就都忘记掉.然后输出本步所有的(拼图形状,空白块位置,本次移动方向), 作为下一次迭代的输入

难点2. 如果每次都丢掉所有数据,最后只能得出 拼图是否可以完成,在多少步内完成的输出结果,并不能显示出 如何移动方块使得拼图复原的所有步骤.
解决方案2. 在函数内加入一个空列表, 列表每次记录这次行走的方向.
也就是 最终还是要有一个列表记录所有走法的全部数据.并且给每个数据特殊的标识, 使得系统可以识别出这个数据是在第几步.
(当然也可以 上次方向+本次方向 生成一个新的单一识别化数据, 然后这个数据与下次 方向又生成一个单一识别化数据, 这样每次用完上次数据 就可以丢弃了,也节省了内存, 不过这个方法我暂时没有去实现, 下面会给出 实现的逻辑思维,)

#  将 行走方向 数字化
字典 = {'上':-3, '下':3, '左':-1, '右':1}
翻译字典 = {-3:'上', 3:'下', -1:'左', 1:'右'}

记录出的所有数据

for 遍历 in randomlist_new:#选定随机走位, 但不得走回上次位置count2 += 1if 遍历 >0:每步所有数据1.append(遍历+count*10)else:每步所有数据1.append(遍历-count*10)

重点 1.每做一次遍历 也就是每走记录 , 让count数+1, 然后让count+上本次步数,就得出了特征化的新数据如下图所示
在这里插入图片描述
个位数和正负号表示这次所走的方向, 个位数之前的数字就代表是第几步.
比如 81 也就是 第8步的策略,走了1 ,1也就是走了右.
最后再将步数数据 翻译成中文即可
PS: 当然有想法的兄弟们 可以不用累计记录这么多冗杂数据. 每次只用上次 数据 + 本次 数据 ,输出新数据. 这样是最简化也是 最优化的方法, 非常省内存! 比如 上下左右 使用 1234 标记.
然后比如 一个步数记录应该是 [上左左下右右]
第一步输出: 1
第二步输出: 1+3 = 31
第三步输出: 31 + 3 = 331
第4步输出: 331 + 2 = 2331
第5步输出: 2331+ 4 = 42331
第6步输出: 42331 + 4 = 442331

很明显 只要通过 最后 第六步的一个数据 442331 我们就可以得出 以前所有的步数 内容,
输入 也仅需要 第五步的结果输入 和 本部生成的步数

不过我这个没有在我的代码里实现, 有兴趣的兄弟们可以自己实现一下.

2.我比较笨 想来想去, 只想出了一个拼图逻辑, 也就是 禁止拼图,回走上一步, 其他所有可能都需要遍历

以下贴出 所有代码

import numpy as np
def 交换位置(数据汇总,完成迷宫):   #移动一个拼图方块,本质上就是两个方块交换位置 所以这是一个 N次交换方块位置的 实质
# 给出两个输入  数据汇总就是 1.上步所有可能的迷宫形状 2.所有迷宫形状下 空白格所在位置 3.所有上次行走的方向  
# 完成迷宫 就是 最后需要 打到的迷宫形状 一般就是  123456789是否完成 = 0上步数据 = 数据汇总数据汇总 = []每步所有数据1 = []count = 0count2 = -1for 初始迷宫,初始位置,前位置随机数 in 上步数据:count += 1if 初始位置==1:  # 手写给出 每个位置方块可以走的情况, 比如四个角 明显只有两个走法可以走randomlist = np.array([字典['右'], 字典['下']])if 初始位置==2:randomlist = np.array([字典['右'], 字典['左'], 字典['下']])if 初始位置==3:randomlist = np.array([字典['左'], 字典['下']])if 初始位置==4:randomlist = np.array([字典['右'], 字典['上'], 字典['下']])   if 初始位置==5:randomlist = np.array([字典['右'], 字典['下'], 字典['上'], 字典['左']])if 初始位置==6:randomlist = np.array([字典['上'], 字典['左'], 字典['下']])if 初始位置==7:randomlist = np.array([字典['右'], 字典['上']])if 初始位置==8:randomlist = np.array([字典['右'], 字典['左'], 字典['上']])if 初始位置==9:randomlist = np.array([字典['左'], 字典['上']])randomlist_new = np.setdiff1d(randomlist, 前位置随机数*-1) #给出随机走位所有可能, 但不得走回上次位置  ,也就是将上述 randomlist去除上次走路方向的元素初始位置 = 初始位置-1 #我的输入是123456789大家容易看懂  但需要转换为python 表达方式 012 345678for 遍历 in randomlist_new:count2 += 1if 遍历 >0:  #将每步特征化,将每步走的方向 放入到列表中每步所有数据1.append(遍历+count*10)else:每步所有数据1.append(遍历-count*10)初始迷宫_copy = 初始迷宫.copy()初始迷宫_copy[初始位置], 初始迷宫_copy[初始位置+遍历] = 初始迷宫_copy[初始位置+遍历], 初始迷宫_copy[初始位置]  #完成走位,得到新迷宫图  也就是交换两个元素位置数据汇总.append((初始迷宫_copy, 初始位置+遍历+1, 遍历))判断 = (初始迷宫_copy==完成迷宫)  #判断得到的新迷宫 是不是 需要完成的迷宫if 判断.all() :count2合集.append(count2)是否完成 = 1print('''完成拼图:{}'''.format(count2))break步数记录.append(每步所有数据1)return(数据汇总, 是否完成, count2合集)
count2合集 = []
字典 = {'上':-3, '下':3, '左':-1, '右':1}
翻译字典 = {-3:'上', 3:'下', -1:'左', 1:'右'}
完成迷宫1  = np.array([1,2,3,4,5,6,7,8,9])            # 最终迷宫形状
数据汇总1  = [[np.array([6,3,8,1,4,5,2,7,9]), 9, 0]]  # 初始迷宫形状  空白格位置  以及 前置步数操作(第一步也就是没有前置操作.设为0)
步数记录 = []
for i in range(21):  #重点 我的函数是每调用一次走一步, 所以我们需要 用for函数 指定拼图所要走的步数, 我们假定一开始 不知道多少步可以复原迷宫 可以 range里面输入100,也就是要求100步内完成迷宫,当然我们在看到有步数 输出的时候就可以暂停运行, 降低步数.  这里我给的数据是 必须在21步内完成.最终输出就是20步之内就可以完成数据汇总1, 是否完成,完成路线 = 交换位置(数据汇总1,完成迷宫1)ans1 = []     #以下代码是对 输出的 每步步数回溯翻译成 中文的行走方向, 这个我个人觉得也是重点.
for a in 完成路线:test = []ans2 = []for i in range(20):test.append(a)a = np.abs(步数记录[-1*(i+1)][a])//10 - 1for i,j in enumerate(test[::-1]):if 步数记录[i][j] < 0:ans2.append(翻译字典[np.abs(步数记录[i][j])%10*-1])else:ans2.append(翻译字典[np.abs(步数记录[i][j])%10])ans1.append(ans2)
for i in ans1:print(i)

展示输出
在这里插入图片描述
也就是 在限定小于等于20步之内完成拼图,只有两种走法
分别是571号, 6247号 策略
翻译成如下 两个列表的中文走法形式

这篇关于3*3拼图复原 (8数码问题) 每步穷举搜索(BFS广度搜索) Python解法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Python如何使用__slots__实现节省内存和性能优化

《Python如何使用__slots__实现节省内存和性能优化》你有想过,一个小小的__slots__能让你的Python类内存消耗直接减半吗,没错,今天咱们要聊的就是这个让人眼前一亮的技巧,感兴趣的... 目录背景:内存吃得满满的类__slots__:你的内存管理小助手举个大概的例子:看看效果如何?1.

Python+PyQt5实现多屏幕协同播放功能

《Python+PyQt5实现多屏幕协同播放功能》在现代会议展示、数字广告、展览展示等场景中,多屏幕协同播放已成为刚需,下面我们就来看看如何利用Python和PyQt5开发一套功能强大的跨屏播控系统吧... 目录一、项目概述:突破传统播放限制二、核心技术解析2.1 多屏管理机制2.2 播放引擎设计2.3 专

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2

Python实现无痛修改第三方库源码的方法详解

《Python实现无痛修改第三方库源码的方法详解》很多时候,我们下载的第三方库是不会有需求不满足的情况,但也有极少的情况,第三方库没有兼顾到需求,本文将介绍几个修改源码的操作,大家可以根据需求进行选择... 目录需求不符合模拟示例 1. 修改源文件2. 继承修改3. 猴子补丁4. 追踪局部变量需求不符合很

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步:深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步

Python Dash框架在数据可视化仪表板中的应用与实践记录

《PythonDash框架在数据可视化仪表板中的应用与实践记录》Python的PlotlyDash库提供了一种简便且强大的方式来构建和展示互动式数据仪表板,本篇文章将深入探讨如何使用Dash设计一... 目录python Dash框架在数据可视化仪表板中的应用与实践1. 什么是Plotly Dash?1.1

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调

Python下载Pandas包的步骤

《Python下载Pandas包的步骤》:本文主要介绍Python下载Pandas包的步骤,在python中安装pandas库,我采取的方法是用PIP的方法在Python目标位置进行安装,本文给大... 目录安装步骤1、首先找到我们安装python的目录2、使用命令行到Python安装目录下3、我们回到Py