Hammerwatch难题；用Python解决

Question

所以，我妻子在玩蒸汽锤表。她遇到了一个难题，我决定试着编写一个解决方案。在

下面是谜题的工作原理：
激活开关可以打开或关闭该开关，也可以切换相邻的开关。

下面是一段YouTube游戏中的谜题视频：
http://www.youtube.com/watch?v=OM1XD7IZ0cg

我想出了如何使拼图的机制正确工作。我最终意识到我有两个选择让电脑来解决这个问题：

A）允许计算机通过随机选择开关进行求解
…或…
B）创建一个算法，使计算机能够更有效地解决难题。

作为一个新的程序员（代码学院教程的一半，LPTHW的一半，目前正在麻省理工学院edX计算机科学Python课程的学习者），我觉得我的能力有点有限。我是来学习的！请帮忙！在

请帮助：

我需要帮助，要么找出一个更好的方法随机解决这个问题，要么更好，有一个算法，让计算机系统地解决这个难题。

我唯一能做的就是让计算机把拼图的状态存储在列表或字典中，通过跳过这些存储的状态来帮助程序，为程序指出新的可能的解决方案

当前程序的工作原理：

我打算允许用户输入拼图板的当前状态与前9个原始输入。然后它进入一个循环，随机切换拼图板的开关，直到它们全部打开。在

p.S.：当我注册StackOverflow帐户并键入此消息时，我的计算机一直在后台运行该程序以找到解决方案。大约一个小时了，仍然没有找到解决方案，目前正在进行第9200000次迭代。我觉得没用。。。

import random

def switcheroo(x):
    """
    switches 'x' to 1 if it's a 0 and vice-versa
    """
    if x == 0:
        x = 1
    else:
        x = 0
    return x

# original input variables
a1 = 0
a2 = 0
a3 = 0
b1 = 0
b2 = 0
b3 = 0
c1 = 0
c2 = 0
c3 = 0


# puzzleboard   
print "\n\n"
print "    1   2   3   "
print "  -------------"
print "a |",a1,"|",a2,"|",a3,"|"
print "  -------------"
print "b |",b1,"|",b2,"|",b3,"|"
print "  -------------"
print "c |",c1,"|",c2,"|",c3,"|"
print "  -------------"
print "\n\n"



print "What's ON/OFF? (type 0 for OFF, 1 for ON)"
a1 = int(raw_input("a1: "))
a2 = int(raw_input("a2: "))
a3 = int(raw_input("a3: "))
b1 = int(raw_input("b1: "))
b2 = int(raw_input("b2: "))
b3 = int(raw_input("b3: "))
c1 = int(raw_input("c1: "))
c2 = int(raw_input("c2: "))
c3 = int(raw_input("c3: "))

# for counting the iterations within the loop
iteration = 0

# to stop loop if all switches are ON
ans = a1 and a2 and a3 and b1 and b2 and b3 and c1 and c2 and c3


while ans == False:
    # randomly generates number, flipping random switches
    counter = random.randint(1,9)
    if counter == 1:
        switch = "a1"
    elif counter == 2:
        switch = "a2"
    elif counter == 3:
        switch = "a3"
    elif counter == 4:
        switch = "b1"
    elif counter == 5:
        switch = "b2"
    elif counter == 6:
        switch = "b3"
    elif counter == 7:
        switch = "c1"
    elif counter == 8:
        switch = "c2"
    elif counter == 9:
        switch = "c9"


    # PUZZLE MECHANICES #
    if switch == "a1":
        a1 = switcheroo(a1)
        a2 = switcheroo(a2)
        b1 = switcheroo(b1)

    if switch == "a2":
        a2 = switcheroo(a2)
        a1 = switcheroo(a1)
        a3 = switcheroo(a3)
        b2 = switcheroo(b2)        

    if switch == "a3":
        a3 = switcheroo(a3)
        a2 = switcheroo(a2)
        b3 = switcheroo(b3)

    if switch == "b1":
        b1 = switcheroo(b1)
        b2 = switcheroo(b2)
        a1 = switcheroo(a1)
        c1 = switcheroo(c1)

    if switch == "b2":
        b2 = switcheroo(b2)
        a2 = switcheroo(a2)
        b1 = switcheroo(b1)
        b3 = switcheroo(b3)
        c2 = switcheroo(c2)

    if switch == "b3":
        b3 = switcheroo(b3)
        b1 = switcheroo(b1)
        b2 = switcheroo(b2)
        c3 = switcheroo(c3)
    # Edit 1
    if switch == "c1":
        c1 = switcheroo(c1)
        c2 = switcheroo(c2)
        b1 = switcheroo(b1)

    if switch == "c2":
        c2 = switcheroo(c2)
        c1 = switcheroo(c1)
        c3 = switcheroo(c3)
        b2 = switcheroo(b2)

    if switch == "c3":
        c3 = switcheroo(c3)
        c2 = switcheroo(c2)
        b3 = switcheroo(b3)
    if switch == "stop":
        break

    # prints puzzle-board state at end of loop iteration
    print "\n\n"
    print "    1   2   3   "
    print "  -------------"
    print "a |",a1,"|",a2,"|",a3,"|"
    print "  -------------"
    print "b |",b1,"|",b2,"|",b3,"|"
    print "  -------------"
    print "c |",c1,"|",c2,"|",c3,"|"
    print "  -------------"
    print "\n\n"

    # prints which # was randomly generated
    print "random #: ", counter

    # tracks loop iteration
    iteration += 1
    print "iteration", iteration



if ans == True:
    print "I figured it out!"

Answer 1

首先，你只设置了一次。你需要在循环中评估它。（虽然这可能是由于咀嚼压痕）。这可能就是你目前的方法没有完成的原因。在

另外，一个更“自然”的表示可能是使用bool数组（甚至是0-511之间的数字），这样switcheroo就变成了

a1 = not a1

另外，随机方法会给你大量的打字工作。我想您应该从从解决方案到当前配置的角度来考虑这一点。把它想象成一个迷宫。有2^9=512个可能的配置（或迷宫中的位置）。每次你按下开关就像是在迷宫里迈出一步。现在您真正想要的是找到从初始配置到解决方案的最短路径。看看Dijkstra的算法： http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Answer 2

有一种众所周知的解决这个问题的方法。设x_1，…，x帴n是变量，对应于您是否按第n个按钮作为解决方案的一部分，让a_1，…，a帴n是初始状态。在

假设您正在解决一个3x3问题，变量设置如下：

x_1 x_2 x_3
x_4 x_5 x_6
x_7 x_8 x_9

这个初始状态是：

^{pr2}$

现在，你可以写下一些方程（在算术模2中），这些方程的解必须满足。它基本上是编码规则，关于哪些开关导致特定的灯光切换。在

a_1 = x_1 + x_2 + x_4
a_2 = x_1 + x_2 + x_3 + x_5
...
a_5 = x_2 + x_4 + x_5 + x_6 + x_8
...
a_9 = x_6 + x_8 + x_9

现在你可以用高斯消去来解这组联立方程。因为你用的是算术模2，它实际上比联立方程要比实数简单一些。例如，要去掉第二个方程式中的x_1，只需将第一个方程式加入其中即可。在

a_1 + a_2 = (x_1 + x_2 + x_4) + (x_1 + x_2 + x_3 + x_5) = x_3 + x_4 + x_5

具体来说，下面是算术模2中的高斯消去算法：

• 选择一个包含x_1的等式。把它命名为E_1。在
• 将E_1添加到其他未命名的方程中，其中包含x_1。在
• 对x_2，x_3，…，x n重复

现在，E峎n是一个只包含x峎n的方程，你可以用它来代替先前的方程。对E{n-1}，…，eu 1重复。在

在这个操作中，解决了这个问题。在

这里有一些代码。在

class Unsolvable(Exception):
    pass

def switches(n, m, vs):
    eqs = []
    for i in xrange(n):
        for j in xrange(m):
            eq = set()
            for d in xrange(-1, 2):
                if 0 <= i+d < n: eq.add((i+d)*m+j)
                if d != 0 and 0 <= j+d < m: eq.add(i*m+j+d)
            eqs.append([vs[i][j], eq])

    N = len(eqs)
    for i in xrange(N):
        for j in xrange(i, N):
            if i in eqs[j][1]:
                eqs[i], eqs[j] = eqs[j], eqs[i]
                break
        else:
            raise Unsolvable()
        for j in xrange(i+1, N):
            if i in eqs[j][1]:
                eqs[j][0] ^= eqs[i][0]
                eqs[j][1] ^= eqs[i][1]

    for i in xrange(N-1, -1, -1):
        for j in xrange(i):
            if i in eqs[j][1]:
                eqs[j][0] ^= eqs[i][0]
                eqs[j][1] ^= eqs[i][1]
    return [(i//m,i%m) for i, eq in enumerate(eqs) if eq[0]]

print switches(4, 3, ([1, 0, 0], [0, 1, 0], [0, 0, 1], [0, 0, 0]))

将开关数组的高度和宽度以及初始状态一次指定一行。它会返回您需要按下以关闭所有灯的开关。在

Answer 3

我想你应该能想出一个算法。应该不会太难。在

首先，没有必要多次按下任何开关。因为第二次只会取消第一次点击时所做的操作，并返回到初始状态（不管您同时对其他开关做了什么）。在

那我们打电话吧

A11, A12, A13
A21, A22, A23
A31, A32, A33

启动时开关的状态。在

使用相同的坐标系，让我们用T表示接触的次数。 根据我们前面所说的，每个T不是0就是1。在

如果你能做一点数学，并且你知道在一个值只取0或1的域中进行运算的代数，那么我认为你应该能够将问题归结为一个空间中的问题，比如：

^{pr2}$

如果你把它放在as矩阵运算中，你可能只需要反转一个矩阵，然后根据as找到Ts。在

也许这更适合另一个比Stackoverflow更注重数学的站点。。。在