Game solution algorithm (Buttonia, backlight option)

Question

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

The game is Buttonia.com (which does not yet implement the algorithm), a type of game with lights. Basically, you have a grid of buttons, each of which, when pressed, changes the state of some of its neighbors. I am currently generating an arbitrary game configuration and then apply heuristics as much as possible. The rest is determined by the search for brute force.

My progress so far has been to create a system of equations for modeling the game. Since each button must change the state an odd number of times to end in the down state, this equation will be as follows:

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

Where button_1 through button_X are the states of the buttons that affect button_A. Some buttons may be enabled immediately if they are independent of others. For the rest, I try one configuration until I get a conflict and then back.

This algorithm is currently practical for small game configurations. I tested it from 3x3 games to 10x10 sizes. Where 6x6 is near the upper limit for a practical game.

Equations greatly reduce the search space from brute force, making it practical. There may be a purely mathematical way of solving a system of equations.

---

Example 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, click these: (0,0), (2,0), (1, 2), (0, 1), (1, 1), (2.1)

The equations for this game are:

 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 math functions to avoid the need for a module allows us to move the terms on the left side to the right, creating the neat matrix setting needed for the Gauss method. Thus, the first two equations are respectively converted 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 

Solution discussed here: Eliminating gausses with custom operators

Nearer. Almost ready to publish the complete solution: Invert Binary Networks

Answer 1

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

You can solve this like ordinary linear equations, but you need to do arithmetic modulo 2.

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

• Addition and subtraction become exceptional or, that is, 0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 0.

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

• Separation is possible with only one: 0/1 = 0, 1/1 = 1.

All coefficients in your equations and possible unknown values ​​are 0 or 1.

Thus, modulo the equations are not deleted outside, as you wrote, they are implicit in operations.

If your system of equations is not solvable, you will get the equation 0 = 1, which is obviously not solvable.

Answer 2

Instead of starting with a random state, why not generate an initial position by switching random switches, that is, work in the opposite direction from the allowed state to the initial state. This way you create solvable puzzles.

Answer 3

It looks almost like a system of linear equations (except for mod 2), so you can adapt one of the usual methods to solve them. abbreviation of the system string in matrix form (wikipedia) .

Answer 4

Since this is not a time limit problem (well, assuming it can be done in less than one day), I would probably go for a depth-limited breadth-first search, taking every possible move at a level, and then every step, which follows every move.

It will be slow, but there is almost guaranteed to be an answer, if any!

Answer 5

Suppose you have built a system of equations and solved them as best as possible, but some series turned out to have all 0 on the left side of the equation (I present the equations as an extended matrix) Suppose you tried to solve a system in the ring Z2 (which in the practical sense for this specific example means that the only change is that 1 + 1 = 0, otherwise everything remains unchanged ... ergo we only need the XOR operator) and as a result we get the following matrix:

 1001 1 0100 1 0011 0 0000 0 

As you can see in this example, the 4th line is all 0, which means that we have no answer. However, think of it this way: a line of only 0 means that this variable does not affect the decision. This is actually a poor choice of words ... it just means that they can be of any value (and we are lucky here, because all values ​​mean 1 or 0, unlike real numbers ... Thus, 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 the right solution for your game. For example, take the first row. It says that

 button_0 + button_3 = 1 

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

 button_0 + 0 = 1 

therefore, we know that button_0 is 1. Therefore, in this system, although we could not directly recognize button_3, we still have a valid solution.

The above matrix is ​​sufficient to verify solvability. If the string contains all 0s, then essentially they say that

 nothing = nothing 

or to better understand why this works,

 0x = 0 

which makes sense, the system remains valid. If, however, we encounter a string that is equal to all 0 except the rightmost bit, that is

 0000 1 

who will speak

 0x = 1 

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

Therefore, in a nutshell, try and solve the equation as best as possible, don’t worry if you can’t find out exactly what some of the variables, until you encounter, at any moment, the impossible line that I just mentioned, then the game is solvable.

But what if we want the shortest solution for the system? Here we look at all the possible solutions. We have button_3, which can be any value, so this means that any 1 in column 3 means that the row in which it is found depends on button_3. Therefore, suppose we want to check if the solution using button_3 is shorter. We create another matrix, but now set button_3 to 1 (since we previously determined that it could be anything, and we already had 0, so now we check 1). Now we get the following matrix:

 1001 1 0100 1 0011 0 0001 1 

We reduce this as much as we can, and now we get this matrix:

 1000 0 0100 1 0010 1 0001 1 

This is still a valid solution, however, we see that the solution is longer (it takes 3 instead of two button presses), so we discard it. We must do this for each permutation to set the lines we found, like all 0s to 1. Therefore, if we have x lines that were all 0s, then the system has x ^ 2 solutions, and we need to check them all.