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: http://stackoverflow.com/questions/1216176/gaussian-elimination-with-custom-operators

Getting closer. Almost ready to post full solution: http://stackoverflow.com/questions/1248216/inverting-binary-networks

Answer 1

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 2

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 3

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 4

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