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

本文主要是介绍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)