0

我正在尝试解决这个类似于狼、山羊和卷心菜问题的谜语,并尝试以图形格式表示它(节点和边表示所有潜在路径)。

这就是问题:

2 个马戏团家庭有一个行为,其中一个家庭,由母亲、父亲和女儿组成,位于空中飞人的左侧,而另一个家庭,有两个兄弟和一个姐妹,位于空中飞人的右侧。空中飞人。每个人都从各自的秋千上吊起来,两个家庭之间有一个空荡荡的秋千,如下所示:

母亲,父亲,女儿,空,妹妹,弟弟,哥哥

一个人只能从他们的秋千摆动到一个空荡荡的秋千上,该空荡荡的秋千要么与他们当前的秋千相邻,要么被来自任一家庭的单个人与他们的位置隔开。诀窍的目的是让两个家庭交换双方。任何家庭成员都不得在任何阶段向后摆动。将导致成功执行该技巧的动作顺序是什么?

我将左侧的族标记为“A”族,将右侧的族标记为“B”,将空族标记为“É”,并从第一个位置开始,尝试绘制所有可能存在的排列。

现在我试着只做第一个可能的移动(移动到相邻的空荡荡),但我似乎遇到了一些技术问题,我不知道为什么会这样。

我正在尝试在每个步骤中列出可能的步骤。

这就是我所拥有的。

iC=['A','A','A','E','B','B','B']
newC=[]

for x in range(0,7):
    if iC[x]=='E':
        if iC[x-1]=='A' and iC[x+1]=='B':
            iC[x-1]='E'
            iC[x]='A'
            newC.append(iC)
            iC[x-1]='A'
            iC[x]='B'
            iC[x+1]='E'
            newC.append(iC)
        elif iC[x-1]=='A':
            iC[x-1]='E'
            iC[x]='A'
            newC.append(iC)
        elif iC[x+1]=='B':
            iC[x+1]=='E'
            iC[x]=='B'
            newC.append(iC)
        break

print(newC)

我正在尝试将新项目附加到新列表中,但它会更改项目。可能是因为 append 在 if 语句中两次并且只是更改了附加的项目吗?有没有更有效的方法来做到这一点?感谢任何帮助将不胜感激:)

4

1 回答 1

1

1,2,3为了更容易处理,我为左边-3,-2,-1的家庭和右边的家庭以及0空荡荡的秋千重命名了艺术家。这样,对正确最终顺序的测试只是对单调性的测试:[-3,-2,-1,0,1,2,3]

该算法分为两个函数,test_order测试是否达到最终顺序。如果不是,它会尝试通过生成所有后续订单,possible_swings并与每个订单一起递归到自身。如果达到最终订单,它将把它写出来并将成功返回给它的父调用,它反过来知道它可以输出自己的订单。因此,您以相反的顺序获得这些步骤。我把它作为练习留给你重写程序以产生“正确”的顺序(提示:从最终情况开始)。

需要注意的一件有趣的事情是,这个谜题在其解决方案中看起来像是镜像对称的,也就是说,只需交换元素的名称,就可以来回重播这些步骤。有没有人有更深入的见解?

def possible_swings(trapezes,empty_nr):
    def swing(a): # swing from a to empty_nr
        tmp_trapezes = trapezes[:]
        tmp_trapezes[empty_nr] = tmp_trapezes[a]
        tmp_trapezes[a] = 0
        return (tmp_trapezes,a)
    
    r_trapezes = []
    
    if empty_nr >= 2 and trapezes[empty_nr-2] > 0:
        r_trapezes.append(swing(empty_nr-2))
    if empty_nr >= 1 and trapezes[empty_nr-1] > 0:
        r_trapezes.append(swing(empty_nr-1))
    if empty_nr < len(trapezes)-2 and trapezes[empty_nr+2] < 0:
        r_trapezes.append(swing(empty_nr+2))
    if empty_nr < len(trapezes)-1 and trapezes[empty_nr+1] < 0:
        r_trapezes.append(swing(empty_nr+1))
    return r_trapezes

def is_monotonic(li):
     return all([li[i]<li[i+1] for i in range(len(li)-1)])
    
def test_order(trapezes,empty_nr):
    if empty_nr == 3 and is_monotonic(trapezes):
        print(trapezes)
        return True
    else:
        for next_swing,next_empty in possible_swings(trapezes,empty_nr):
            if test_order(next_swing,next_empty):
                print(trapezes)
                return True
    return False

print(test_order([1,2,3,0,-3,-2,-1],3))

编辑:

is_monotonic正在遍历给定的数组(0 到长度为 1),True如果找到严格单调递增的元素则返回。在我们的例子中,这表示谜语希望两个家庭到达的最终顺序。

test_order测试当前订单,正如我在上面解释的那样,生成所有后续订单,这些订单可能在下一个允许的摆动中出现。这是一个树搜索,深度优先:从梯形上的当前顺序开始,有许多“下一个”顺序。如果谜题可以解开,我们必须最终达到所寻求的顺序,在修剪所有非解决树下降的过程中。

于 2021-02-25T16:27:40.317 回答