Hammerwatch Puzzle; Python solutions

Question

So, my wife played Hammerwatch on Steam. She came across a riddle, I decided that I would try to program the solution.

Here's how the puzzle works:
Activating a switch turns this switch on or off, and also switches its adjacent switches.

Here's a YouTube video about the in-game puzzle:
http://www.youtube.com/watch?v=OM1XD7IZ0cg

I understood how the puzzle mechanics work properly. In the end, I realized that I have two options to get the computer to solve this:

A) Allow the computer to solve by randomly selecting switches
... or ...
B) Create an algorithm that will allow the computer to solve the puzzle more efficiently.

As a new programmer (halfway through CodeAcademy tutorials, halfway through LPTHW and currently working through the PITON MIT edX IT course), I feel a little limited in my ability to figure this out. I came to study! Please, help!

Please help with:

, , , , .

, , , , , .

:

9 raw_inputs. , , .

P.S.: StackOverflow , , . , , ~ 92 000 000- . , ...

import random

def switcheroo(x):
    """
    switches 'x' to 1 if it 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 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

. x_1,..., x_n - , , n'th , a_1,..., a_n - .

, 3x3, :

x_1 x_2 x_3
x_4 x_5 x_6
x_7 x_8 x_9

:

a_1 a_2 a_3
a_4 a_5 a_6
a_7 a_8 a_9

( 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. x_n, , . E_ {n-1},..., E_1.

, O (n ^ 3).

.

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 2

. . ( ). , .

, "" bools ( 0-511), switcheroo

a1 = not a1

. , . , . 2 ^ 9 = 512 ( ). , , . . , : http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Answer 3

, . .

, - . , , ( , ).

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

.

, T . , , T 0 1.

, , , 0 1, , - :

A11 + T11 + T12 + T21 = 1
A12 + T11 + T12 + T13 + T22 = 1
A13 + T12 + T13 + T23 = 1
...

, , Ts As.

, , Math, Stackoverflow...