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 回答