问题出处
我最初是在OSChina上看到这个问题的，有人在论坛上把这个问题提了出来，寻求算法来解决。最初的问题其实是一个Flash小游戏，简单来说，就是一共有6只青蛙，左右各3只，中间还有一个空格，我们的任务是经过有限步的跳跃，将左右青蛙的位置交换。交换的时候会有一些限制条件：
- 青蛙只能前进，不能后退
- 每次只能前进1格或2格
当时试玩的时候，玩了好几次才成功……我实在太笨了-.-.
用算法求解
当考虑用算法求解这个问题的时候，首先要将这个题目数字化，就是如何在程序中表达这个游戏过程。如果把注意力集中在青蛙身上，一共有6只青蛙，那就是说需要设置6个变量，并且需要时刻跟踪这6个变量的变化，这样的程序难度太大了，而且如果青蛙数目继续增加的话，程序就更不好处理了，这显然不是一个好方法。我们可以换个角度来看待这个问题，不需要盯着青蛙是如何运动的，只需要盯着当中那个空格是如何运动的。因为所有的格子总会比青蛙多一个，所以我们只需要关注格子的位置就可以了。
因为在每次的移动过程中，空格只有四种情况:往左移动2格、往左移动1格、往右移动2格、往右移动1格。因此我把整个青蛙序列作为一个状态，每一个状态都可以经由4条不同的路径转移到下一个状态(对应于4种移动方案)，这样我就能把原问题转化为一个图搜索问题:从初始状态开始，找到一条达到目标状态的路径。
根据问题中的限制条件，空格只能和其左右2格以内的青蛙进行交换，并且空格往右移动的时候只能和原本在右边的青蛙交换，同样，往左移动的时候，只能和原本在左边的青蛙交换。因此我可以将整个青蛙序列用一个数组表示，原来在左侧的青蛙用-1表示，原来在右侧的青蛙用1表示，空格用0表示。同时，我用-2、-1、1、2分别表示空格往左移动2格，往左移动1格，往右移动1格，往右移动2格。注意，这里我使用了一个小技巧:空格能够往左(-1,-2)移动的条件是，左边要交换的位置上有一个原来在左侧(-1)的青蛙，这样的话，我只需要判断往左的代表值和青蛙的代表值是否同号，我就能判断能否进行交换了。
代码
#!python
#深度遍历，其中order参数是用来记录路径的
def deepexplore(table,order):
index = table.index(0)
#判断是否是终点状态
if index == len(table) // 2 and sum(table[:index]) == len(table)//2:
print('Swap Complete!')
return True
#顺序尝试四条路径
for i in range(-2,3):
#判断是否越界，是否倒退
if i == 0 or index + i < 0 or index + i >= len(table) or table[index+i] * i <=0:
continue
else:
table[index+i],table[index] = table[index],table[index+i]
order.append(table[:])
if deepexplore(table,order) == True:
return True
order.pop(-1)
table[index+i],table[index] = table[index],table[index+i]
def widthexplore(table):
stack = []
stack.append((table[:],False))
while len(stack)!=0:
state = stack.pop(0)
index = state[0].index(0)
#判断是否是终点
if index == len(state[0]) // 2 and sum(state[0][:index]) == len(state[0])//2:
print('Swap Complete!')
break
for i in range(-2,3):
#判断是否越界，是否倒退
if i == 0 or index + i < 0 or index + i >= len(state[0]) or state[0][index+i] * i <=0:
continue
else:
newstate = (state[0][:],state)
newstate[0][index+i],newstate[0][index] = newstate[0][index],newstate[0][index+i]
stack.append(newstate)
#还原路径
order = []
while state[1] != False:
order.append(state[0])
state = state[1]
order.append(state[0])
order.reverse()
return order
def frogchess(n):
table = [-1] * n + [0] + [1] * n
order=[]
order.append(table[:])
deepexplore(table,order)
order.reverse()
for item in order:
print(item)
if __name__ == '__main__':
frogchess(4)
上述代码中，我用了两种方法进行搜索，分别是深度优先和广度优先，本来以为广度优先能够找到最少的移动序列，但是程序跑下来，广度优先除了更加耗时间以外，找到的路径和深度优先是一样的。
总结
本来想从数学角度来推导得到一个比较美观的公式的，可是数学功底不扎实，实在找不到什么数学原理，只能直接用程序来计算，上面的算法只是利用计算机的高速计算的特点从解空间中寻找答案。 一旦青蛙的数量有所提高，计算量就迅速增大，这样的解法就不再适合了(\(N>20\))，应该要从数学角度寻求更优的解法。