So, imagine the game as this 3x3 grid of cells:

a b c

d e f

g h i

Here is how the different cells relate to each other. The number of times you need to press piece 'a' depends on the number of times you press piece 'b' and 'd', and it also depends on the initial state of 'a' as well. The relationship between them is that at the end of the game, you must have toggled the square's parity a number of times such that it's in the down state.

We can represent this by considering the variables a through i to be binary variables that count the number of times you click each grid cell (binary variables because adding 2 clicks to any cell is idempotent, so we can remove them), and also consider the initial states s[a] through s[i] to be binary variables - we could say that a, b, d, and s[a] must have an even parity all together, since after each of them is applied, the cell must be 'down', or 0.

We can represent these relationships with these equations, where the things on a line have their parity xor'ed:

0 = a b d s[a]

0 = b a e c s[b]

0 = c b f s[c]

0 = d a e g s[d]

0 = e d b f h s[e]

0 = f c e i s[f]

0 = g d h s[g]

0 = h g e i s[h]

0 = i h f s[i]

Those equations can be represented as a matrix A:

1 1 0 1 0 0 0 0 0

1 1 1 0 1 0 0 0 0

0 1 1 0 0 1 0 0 0

A= 1 0 0 1 1 0 1 0 0

0 1 0 1 1 1 0 1 0

0 0 1 0 1 1 0 0 1

0 0 0 1 0 0 1 1 0

0 0 0 0 1 0 1 1 1

0 0 0 0 0 1 0 1 1

Where if we take the vector

**s**of the initial game state, and the vector

**x**of how many times you click each cell (variables a-g in the equations above), then the solution to the game is Ax + s = 0. This is saying the same thing as the equations above - if we add together the initial state, along with each cell's influencing cells, it has to equal the zero vector because the game ends with a flat board.

Since I couldn't find any programs to do mod-2 matrix solving, it took some (python-assisted) work to solve for the pseudoinverse of the matrix A. Then modulo-2, that ends up being:

1 0 1 0 0 1 1 1 0

0 0 0 0 1 0 1 1 1

1 0 1 1 0 0 0 1 1

A-1= 0 0 1 0 1 1 0 0 1

0 1 0 1 1 1 0 1 0

1 0 0 1 1 0 1 0 0

1 1 0 0 0 1 1 0 1

1 1 1 0 1 0 0 0 0

0 1 1 1 0 0 1 0 1

Testing this matrix: if the input is [0 1 1 1 1 0 1 1 0] (which is a game I just got), multiplying by the "inverse" gives [3 3 3 2 4 3 2 3 4]. Since only the parity of number of clicks matters, we can take that vector mod 2, which is [1 1 1 0 0 1 0 1 0] - and clicking on those boxes yields a flat board.

## No comments:

Post a Comment