python小练习（064）：探索法（广度优先搜索）不到40行代码求解拼图游戏的最优路径

jerryxjr1220

在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
[Finished in 1.0s]

不到40行的源代码：

游客，如果您要查看本帖隐藏内容请回复

jerryxjr1220

探索法是我取的名字，科学一点的叫法应该称作“广度搜索”，与“深度搜索”正好相反，是解决不确定性路径问题的很好的解法。

新手·ing

我只是来赚鱼币的~
表示没有看懂~

Tyrant熊

听说回复有鱼币～

1192425304

sda

panda小正太

五行缺五行

好高深，好牛逼~~~

yangyang31707

学院报到要用Python编个小游戏 简直了  有点小麻烦 还没有找到源码

haojie99

不错，学习了，谢谢~！~！！~

千山暮雪归人晚

好棒呀！

maizi

感谢分享

大补的小甲鱼粉

感觉思路和那个象棋马走的路线有点像

新乐乐

看答案

derfdf

谢谢分享~~！！！！

dangyan199219

学习一下算法

tobe_xly

感谢！！！！！！！！！！！

WelanceLee

学习下

WelanceLee

求教~这种问题一般是如何避免queue中的状态回到之前遍历过的状态？

jerryxjr1220

WelanceLee 发表于 2017-6-15 20:23
求教~这种问题一般是如何避免queue中的状态回到之前遍历过的状态？

所以会有visited来记录遍历过的状态

WelanceLee

import copy
##start = [[0,1,2,2], [1,1,2,2], [1,1,2,2], [1,1,2,2]]
##end = [[0,2,1,2], [2,1,2,1], [1,2,1,2], [2,1,2,1]]
start = ['0122112211221122', 0, 0]
end = ['0212212112122121', 0, 0]
moves = [[1,0], [-1,0], [0,1], [0, -1]]
action = {}
queue = [start]
index = 0
flag = True
while flag:
    for each in moves:
        q = queue[index]
        qx = copy.deepcopy(q)
        if qx == end:
            flag = False
            break
        x = qx[1] + each[0]
        y = qx[2] + each[1]
        if -1 < x < 4 and -1 < y < 4:
            qy = list(qx[0])
            l = 4*x + y
            m = 4*qx[1] + qx[2]
            tmp = qy[l]
            qy[l] = qy[m]
            qy[m] = tmp
            qx[1] = x
            qx[2] = y
            qx[0] = ''.join(qy)
            if qx not in queue:
                queue.append(qx)
##                action[(qx[1], qx[2])] = (q[1], q[2])
                action[str(qx)] = q
    index += 1

while qx != start:
    qx = action[str(qx)]
    print(qx)

修修补补总算把答案整出来了，但是真的丑~