小青蛙过河求解答，急

Question

如何用Python实现六只小青蛙过河问题，知道大概路径即可，像这样，求解答，急

Answer 1

题目说一下

Answer 2

手机上有一款“小青蛙过河”游戏：如下图所示，有两组（同色的归为一组）共六只青蛙。每只青蛙只能向前跳，不能向后跳，每次只能跳过一只青蛙或跳至前方相邻的没有青蛙的石头上。两组青蛙交换位置即为游戏胜利。

Answer 3

先移左边和先移右边有两种移法，

def print_res(p):
    for i in p:
        print(i)
    print("completed")

def move_frog(f,p1,p2):
    f[p1],f[p2] = f[p2],f[p1]
    return f

def fun(frogs,target,p):
    p.append(frogs)
    if frogs == target:print_res(p)
    for frog in frogs:
        if frog == 0: continue
        pos_0 = frogs.index(0)
        pos = frogs.index(frog)
        if frog < 4:
            if pos_0 == pos+1 < len(frogs) or pos_0 == pos+2 < len(frogs):
                fun(move_frog(frogs[:],pos,pos_0),target,p[:])
        elif frog > 3:
            if pos_0 == pos-1 >= 0 or pos_0 == pos-2 >= 0:
                fun(move_frog(frogs[:],pos,pos_0),target,p[:])

frogs=[1,2,3,0,4,5,6]
target=[4,5,6,0,1,2,3]
p=[]
fun(frogs,target,p)

结果：

[1, 2, 3, 0, 4, 5, 6]
[1, 2, 0, 3, 4, 5, 6]
[1, 2, 4, 3, 0, 5, 6]
[1, 2, 4, 3, 5, 0, 6]
[1, 2, 4, 0, 5, 3, 6]
[1, 0, 4, 2, 5, 3, 6]
[0, 1, 4, 2, 5, 3, 6]
[4, 1, 0, 2, 5, 3, 6]
[4, 1, 5, 2, 0, 3, 6]
[4, 1, 5, 2, 6, 3, 0]
[4, 1, 5, 2, 6, 0, 3]
[4, 1, 5, 0, 6, 2, 3]
[4, 0, 5, 1, 6, 2, 3]
[4, 5, 0, 1, 6, 2, 3]
[4, 5, 6, 1, 0, 2, 3]
[4, 5, 6, 0, 1, 2, 3]
completed
[1, 2, 3, 0, 4, 5, 6]
[1, 2, 3, 4, 0, 5, 6]
[1, 2, 0, 4, 3, 5, 6]
[1, 0, 2, 4, 3, 5, 6]
[1, 4, 2, 0, 3, 5, 6]
[1, 4, 2, 5, 3, 0, 6]
[1, 4, 2, 5, 3, 6, 0]
[1, 4, 2, 5, 0, 6, 3]
[1, 4, 0, 5, 2, 6, 3]
[0, 4, 1, 5, 2, 6, 3]
[4, 0, 1, 5, 2, 6, 3]
[4, 5, 1, 0, 2, 6, 3]
[4, 5, 1, 6, 2, 0, 3]
[4, 5, 1, 6, 0, 2, 3]
[4, 5, 0, 6, 1, 2, 3]
[4, 5, 6, 0, 1, 2, 3]
completed

Answer 4

如果有8只青蛙，只要把参数改一下：

def print_res(p):
    for i in p:
        print(i)
    print("completed")

def move_frog(f,p1,p2):
    f[p1],f[p2] = f[p2],f[p1]
    return f

def fun(frogs,target,p):
    p.append(frogs)
    if frogs == target:print_res(p)
    for frog in frogs:
        if frog == 0: continue
        pos_0 = frogs.index(0)
        pos = frogs.index(frog)
        if frog < 5:
            if pos_0 == pos+1 < len(frogs) or pos_0 == pos+2 < len(frogs):
                fun(move_frog(frogs[:],pos,pos_0),target,p[:])
        elif frog > 4:
            if pos_0 == pos-1 >= 0 or pos_0 == pos-2 >= 0:
                fun(move_frog(frogs[:],pos,pos_0),target,p[:])

frogs=[1,2,3,4,0,5,6,7,8]
target=[5,6,7,8,0,1,2,3,4]
p=[]
fun(frogs,target,p)