python小练习（064）：探索法（广度优先搜索）不到40行代码求解拼图游戏的最优路径
本帖最后由 jerryxjr1220 于 2017-2-7 11:23 编辑在python小练习（012）中介绍了探索解法求解不确定的路径问题，在python小练习（060）中又介绍了拼图小游戏，今天我们把这2个内容结合起来，利用探索法求解拼图游戏的最优路径。
这题原本是一道面试笔试题。
原文题目：
There're 7 red tiles, 8 blue titles and one white title in a 4 x 4 plane. We could only move the white tile. When moving it, the white tile swaps the position with the adjacent tile. L, R, U, D are corresponding to four directions which the tile could be moved to (Left, Right, Up, Down) For example, starting from configuration (S), by the move sequence RDRDLwe reach the configuration (E). Now, starting from configuration (S), find the shortest way to reach configuration (T).
简单翻译一下：
在如图4x4的16宫格内，有7个红块和8个蓝块以及1个白块，这个白块可以上下左右移动（对应关系为：L左、R右、U上、D下）与其他颜色的方块交换位置。如果起始状态为S，通过RDRDL后，我们可以得到E的状态。
那么如何从起始状态S通过最短路径得到T的最终状态。请给出最短交换路径。
先给个参考答案：
R R D L L U R R R D L L U R D D L D R U R D L U L L D R U U L U
不到40行的源代码：
**** Hidden Message ***** 探索法是我取的名字，科学一点的叫法应该称作“广度搜索”，与“深度搜索”正好相反，是解决不确定性路径问题的很好的解法。 我只是来赚鱼币的~
表示没有看懂~
听说回复有鱼币～ sda {:10_254:}{:10_254:}{:10_254:} 好高深，好牛逼~~~ 学院报到要用Python编个小游戏 简直了有点小麻烦 还没有找到源码 不错，学习了，谢谢~！~！！~ 好棒呀！ 感谢分享 感觉思路和那个象棋马走的路线有点像 看答案 谢谢分享~~！！！！ 学习一下算法 感谢！！！！！！！！！！！ 学习下
求教~这种问题一般是如何避免queue中的状态回到之前遍历过的状态？ WelanceLee 发表于 2017-6-15 20:23
求教~这种问题一般是如何避免queue中的状态回到之前遍历过的状态？
所以会有visited来记录遍历过的状态 import copy
##start = [, , , ]
##end = [, , , ]
start = ['0122112211221122', 0, 0]
end = ['0212212112122121', 0, 0]
moves = [, [-1,0], , ]
action = {}
queue =
index = 0
flag = True
while flag:
for each in moves:
q = queue
qx = copy.deepcopy(q)
if qx == end:
flag = False
break
x = qx + each
y = qx + each
if -1 < x < 4 and -1 < y < 4:
qy = list(qx)
l = 4*x + y
m = 4*qx + qx
tmp = qy
qy = qy
qy = tmp
qx = x
qx = y
qx = ''.join(qy)
if qx not in queue:
queue.append(qx)
## action[(qx, qx)] = (q, q)
action = q
index += 1
while qx != start:
qx = action
print(qx)
修修补补总算把答案整出来了，但是真的丑~{:5_107:}