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 1

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.

Answer 2

To start with you're only setting ans once. You need to evaluate it inside the loop. (though that might be due to munged indentation). That's probably why your current approach isn't finishing.

As an aside, a more "natural" representation might be to use arrays of bools (or even a number from 0-511) so switcheroo becomes

a1 = not a1

Also the random approach is going to give you a lot of typing to do. I suspect you want to think of this in terms of walking from a solution to your current configuration. Think of it like a maze. There's 2^9 = 512 possible configurations (or places in the maze). Every time you hit a switch is like taking a step in the maze. Now what you really want is to find the shortest path from the initial configuration to the solution. So take a look at Dijkstra's algorithm: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Answer 3

I think you should be able to figure out an algorithm for this. Should not be too difficult.

For one thing, there is no need to press on any switch more than once. Since the second time only cancels what you did with the first hit and returns to the initial state (no matter what you did with other switches in the meantime).

Then let's call

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

The states of the switches when you start.

And using the same coordinate system, let's use T for the number of touches. Based on what we said earlier, each T is either 0 or 1.

If you can do a little bit of math, and you know about algebra to do operations in a domain where values only take 0 or 1 and then I think you should be able to reduce the problem to a problem in that space with something like:

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

If you put that in as matrix operations, you might be able to just invert one matrix and then find the Ts based on the As.

Maybe this is more appropriate for another site more Math oriented than Stackoverflow...