Game solving algorithm (Buttonia, lights-out variant)

Question

I am trying to create a solvability function for a game algorithm. Basically a function that returns true or false for a given game it if is solvable or not.

The game is Buttonia.com (which does not implement the algorithm as yet), a type of lights-out game. Basically You have a grid of buttons, each of which, when pressed, will change the state of some of it's neighbors. Currently I generate a random game configuration and then apply heuristics as far as possible. The rest is decided by brute force search.

My progress so far was to create a system of equations to model the game. As each button needs to change state an odd number of times to end up in a down state, It's equation would be this:

button_A = 1 - (button_1 + button_2 + ... + button_X) % 2

Where button_1 through button_X are the states of the buttons with an effect on button_A. Some buttons may be immediately resolved, if they are not dependent on others. For the rest, I try one configuration until I get a conflict and then back track.

Currently this algorithm is practical for smaller configurations of games. I've tested it from 3x3 games up to sizes of 10x10. Where 6x6 is near an upper limit for practical play.

The equations hugely cut down the search space from brute-force, making it practical. There might be a purely mathematical way of solving the system of equations.

---

Sample 3x3 game in ascii (from buttonia.com/?game=2964):

||#
-o-
+#|

Legend:
o = affect only self
- = affect left and right neighbors
| = affect above and below neighbors
+ = affect left, right, above and below neighbors
# = affect all 8 surrounding neighbors

Solution, press these: (0,0), (2,0), (1, 2), (0, 1), (1, 1), (2,1)

Equations for this game:

Button_0_0 = 1 - (0) % 2
Button_1_0 = 1 - (Button_2_0) % 2
Button_2_0 = 1 - (0) % 2
Button_0_1 = 1 - (Button_0_0 + Button_0_2 + Button_1_2) % 2
Button_1_1 = 1 - (Button_1_0 + Button_2_0 + Button_0_1 + Button_2_1 + Button_1_2) % 2
Button_2_1 = 1 - (Button_2_0 + Button_1_2 + Button_2_2) % 2
Button_0_2 = 1 - (Button_1_2) % 2
Button_1_2 = 1 - (Button_0_2) % 2
Button_2_2 = 1 - (Button_1_2) % 2

Potential solution:

Changing the mathematical functions to avoid the need for the modulus lets us move the terms on the left side to the right, creating the neat matrix setup we need for the Gaussian method. So the first two equations would respectively convert to:

-1 = -1*B00 +  0*B10 +  0*B20 +  0*B01 +  0*B11 +  0*B21 +  0*B02 +  0*B12 +  0*B22
-1 =  0*B00 + -1*B10 + -1*B20 +  0*B01 +  0*B11 +  0*B21 +  0*B02 +  0*B12 +  0*B22

Discussed solution here: Gaussian Elimination with custom operators

Getting closer. Almost ready to post full solution: Inverting binary networks

Answer 1

This is a system of linear equations over F₂, the field containing the two elements 0 and 1.

You can solve it just like normal linear equations, but you have to do the arithmetic modulo 2.

Edit: Linear algebra for this case works exactly like for real numbers, except that you have to replace the operations:

• Addition and subtraction become exclusive or, i.e. 0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 0.

• Multiplication becomes AND: 0 * 0 = 0, 0 * 1 = 0, 1 * 1 = 1

• Division is only possible by one: 0 / 1 = 0, 1 / 1 = 1.

All the coefficients in your equations and the possible values of unknowns are either 0 or 1.

So the modulo is not slapped on the outside of the equations like you wrote, it is implicit in the operations.

If your system of equations is not solvable you'll get an equation 0 = 1, which is obviously not solvable.

Answer 2

Instead of starting with a random state, why not generate the starting position by flipping random switches, i.e. work backwards from a solved state to a starting state. That way you only generate solvable puzzles.

Answer 3

This looks almost like a system of linear equations (except the mod 2), so you might be able to adapt one of the normal techniques for solving those - e.g. row reduction of the system in matrix form (wikipedia).

Answer 4

As this is not a time-limited problem (well, assuming it can be done in less than a day), I would probably go for a depth-limited breadth-first search, taking each possible move on a level and then each move that follows on from each move.

It will be slow, however it is almost guaranteed to find an answer, if there is one!

Answer 5

Suppose you built a system of equations and solved them as best you could, but some rows ended up with all 0's on the left hand side of the equation (I'm representing the equations as an augmented matrix) Suppose you tried to solve the system in the Z2 ring (which in practical terms for this particular example means that the only change is that 1+1=0, else everything remains the same... ergo the only operator we need is XOR) and ended up with the following matrix:

1001 1
0100 1
0011 0
0000 0

As you can see in this example, the 4th row is all 0, meaning that we haven't got an answer for it. However think of it this way: a row of all 0 means that that variable does not affect the solution. That's actually a poor choice of words... it just means that they can have any value (and we're in luck here, since all values means 1 or 0, unlike in real numbers... So this means that we have 2 solutions for this system).

Here's why: what you need to know at this point is that the rightmost column still contains a valid solution for your game. Let's take the first line for example. It says that

button_0 + button_3 = 1

but we know that button 3 can be anything (since line 3 is all 0s). At this point button 3 is 0 (the rightmost column on row 3 is 0 at this point) so now we know it means

button_0 + 0 = 1

so we know for a fact that button_0 is 1. Therefore in this system even though we couldn't directly find out button_3, we still have a valid solution.

The matrix generated above is enough to check for solvability. If a row contains all 0s then it is essentially saying that

nothing = nothing

or, to better visualize why this works,

0x = 0

which makes sense, the system is still valid. If however we encounter a row that is all 0s except the rightmost bit, i.e.

0000 1

that would be saying

0x = 1

which is impossible therefore we now know that the system cannot be solved, since we cannot solve an impossible situation like this.

Therefore in a nutshell, try and solve the equation as best you can, don't worry if you cannot exactly find out what some of the variables are, as long as you don't encounter, at any point, the impossible row I just mentioned then the game is solvable.

But what if we want the shortest solution to the system? Here we'll have to examine all possible solutions. We have button_3 that can be any value, so that means that any 1 in column 3 means that the row in which it is found, is affected by button_3. So suppose we want to check if the solution using button_3 will be shorter. We create another matrix, but set button_3 to 1 now (since we established earlier that it could be anything, and we already had a 0 in there, so now we check for 1). We now end up with the following matrix:

1001 1
0100 1
0011 0
0001 1

We reduce that as much as we can and now end up with this matrix:

1000 0
0100 1
0010 1
0001 1

This is still a valid solution, however we can see that the solution is longer (requiring 3, instead of 2 button presses) therefore we discard it. We have to do this for every permutation of setting the rows we found as all 0s to 1. Therefore if we have x rows that were all 0s, then the system has x^2 solutions, and we have to check all of them.