Hammerwatch Puzzle; Solving with Python
Question: So, my wife was playing Hammerwatch on Steam. She came across a puzzle I
decided I'd try to program a solution for.

Here's how the puzzle works:  
Activating a switch either turns ON or OFF that switch, and toggles its
adjacent switches as well.  

Here's a YouTube video of the puzzle within the game:  
<http://www.youtube.com/watch?v=OM1XD7IZ0cg>

  
I figured out how to get the mechanics of the puzzle working correctly. I
eventually realized 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.  

Being a new programmer (halfway through CodeAcademy tutorials, halfway through
LPTHW, and currently working through the MIT edX computer science Python
course), I feel I'm a little limited in my abilities to figure this out. I've
come to learn! Please help!

## Please help with:

I need help either figuring out a better way to solve this randomly, or even
better, to have an algorithm that will allow the computer to _systematically_
solve the puzzle.  
  
The only thing I could thing of was to have the computer _store_ the puzzle's
states in a list or dictionary, assisting the program by skipping over those
stored states, point the program to new possible solutions

## How the current program works:

I intended to allow the user to input the current state of the puzzle-board
with the first 9 raw_inputs. It then enters a loop, randomly toggling the
puzzle-board's switches until they're all ON.

_P.S.: While I was signing up for a StackOverflow account and typing this
message, my computer has been running this program in the background to find a
solution. It's been about an hour, still hasn't found a solution, it is
currently on its ~92,000,000th iteration. I don't think it's working..._

    
    
    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: There's a well-known method for solving this problem. Let x_1, ..., x_n be
variables corresponding to whether you press the n'th button as part of the
solution, and let a_1, ..., a_n be the initial state.

Let's say you're solving a 3x3 problem, and the variables are set up like
this:

    
    
    x_1 x_2 x_3
    x_4 x_5 x_6
    x_7 x_8 x_9
    

and this initial state is:

    
    
    a_1 a_2 a_3
    a_4 a_5 a_6
    a_7 a_8 a_9
    

Now, you can write down some equations (in arithmetic modulo 2) that the
solution must satisfy. It's basically encoding the rule about which switches
cause a particular light to toggle.

    
    
    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
    

Now you can use gaussian elimination to solve this set of simultaneous
equations. Because you're working in arithmetic modulo 2, it's actually a bit
easier than simultaneous equations over real numbers. For example, to get rid
of x_1 in the 2nd equation, simply add the first equation to it.

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

Specifically, here's the Gaussian elimination algorithm in arithmetic modulo
2:

  * Pick an equation with an x_1 in it. Name it E_1.
  * Add E_1 to every other unnamed equation with an x_1 in it.
  * Repeat for x_2, x_3, ...., x_n.

Now, E_n is an equation which only contains x_n. You can substitute the value
for x_n you get from this into the earlier equations. Repeat for E_{n-1}, ...,
E_1.

Overall, this solves the problem in O(n^3) operations.

Here's some code.

    
    
    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]))
    

You give it the height and width of the switch array, and the initial state a
row at a time. It returns the switches that you need to press to turn all the
lights off.

