Mark Gritter (markgritter) wrote,
Mark Gritter
markgritter

Tubulo Falls Before the Might of Linear Algebra on Finite Fields

Another KadoKado game: Tubulo. You click on squares on a grid. The square you select and all the orthogonal neighbors cycle through the colors green->orange->blue->green. (So, basically, you "stamp" a cross onto the board.) Your goal is to get the board to an all-green state.

You can play around with the basic mechanics with this web implementation (which gives you the goal state as the start, so it's not all that interesting.) Or watch this YouTube video of somebody's high score (which I found a little surprising because he screwed up some fairly basic positions.)

The game as implemented in KadoKado has a rather sharp "knee" in its difficulty curve. Most positions can be solved by looking for the crosses, and learning a little bit about what overlapped crosses look like. But then comes a level in which you inevitably guess wrong about where to start, and end up with something like this:



This looks like you're close to a solution. But you're not. You can use the web toy linked above to try to get to this state--- it's not easy.

However, the structure of this game is mathematically pretty simple. The order of clicks doesn't matter--- any solution can be permuted at will. So this means we only need to solve for the number of clicks on a given square. Then the problem becomes one of linear algebra--- although on the finite field Z3, rather than the reals. (0=green, 1=orange, 2=blue.) The state of square (x,y) = the number of clicks on (x,y) added to the number of clicks on all of its neighbors. For N squares, we can represent this as a matrix M with NxN entries, where each entry is "1" if the squares are neighbors (or the same) and "0" if they are not. Then given a desired configuration G we solve M*C = G and each entry in the vector C tells us how many clicks to make. (Or, given a current state S we can solve M*C=-S to figure out how to get to the all-zeros state.)


Here's the matrix M for the 7x7 board used in the Flash game:

1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1


It's invertible, here's M':

0 2 2 2 0 2 0 2 2 0 2 2 1 1 2 0 0 0 1 0 1 2 2 0 0 0 0 1 0 2 1 0 2 2 1 2 1 0 0 2 1 2 0 1 1 1 1 2 2
2 2 1 2 1 0 2 2 2 1 2 0 0 1 0 2 0 1 0 2 0 2 2 2 0 0 1 0 2 1 2 0 2 0 2 1 2 1 2 1 1 1 1 1 2 2 0 0 2
2 1 2 0 2 1 0 0 1 1 2 0 0 2 0 0 0 0 2 0 1 0 2 2 2 1 0 0 1 2 0 1 1 2 2 0 1 1 2 1 1 2 1 2 2 1 1 0 1
2 2 0 2 0 2 2 2 2 2 2 2 2 2 0 1 0 1 0 1 0 0 0 2 0 2 0 0 0 0 1 1 1 0 0 0 2 2 0 2 2 0 1 2 1 1 1 2 1
0 1 2 0 2 1 2 2 0 0 2 1 1 0 1 0 2 0 0 0 0 0 0 1 2 2 2 0 2 2 1 1 0 2 1 2 1 1 2 1 1 0 1 0 1 1 2 2 1
2 0 1 2 1 2 2 1 0 0 2 1 2 2 0 2 0 1 0 2 0 0 1 0 0 2 2 2 2 0 2 0 2 1 2 1 1 1 2 1 2 1 2 0 0 2 2 1 1
0 2 0 2 2 2 0 1 1 2 2 0 2 2 1 0 1 0 0 0 2 1 0 0 0 0 2 2 1 2 2 0 1 2 0 2 1 2 0 0 1 2 2 2 1 1 1 1 0
2 2 0 2 2 1 1 2 2 2 2 1 2 1 1 1 0 2 2 1 2 2 2 1 0 0 2 2 1 0 0 0 2 1 0 0 0 2 1 0 1 0 2 1 0 0 2 1 2
2 2 1 2 0 0 1 2 1 1 0 1 2 2 1 1 0 2 0 1 1 2 0 2 1 2 2 2 0 1 0 2 1 2 1 0 2 1 2 2 0 1 1 2 1 2 1 1 1
0 1 1 2 0 0 2 2 1 2 0 1 1 1 0 0 0 1 1 0 2 1 2 0 1 0 2 0 0 0 0 1 2 1 2 2 1 2 2 2 2 0 0 1 1 2 1 1 2
2 2 2 2 2 2 2 2 0 0 0 0 0 2 2 2 1 2 1 2 2 0 1 1 2 1 1 0 0 2 1 0 1 2 0 1 2 2 2 2 2 1 0 2 2 0 2 2 0
2 0 0 2 1 1 0 1 1 1 0 2 1 2 2 0 1 1 0 0 0 0 2 0 1 0 2 1 2 1 2 1 0 0 0 0 2 2 2 2 1 2 2 1 1 2 1 1 0
1 0 0 2 1 2 2 2 2 1 0 1 1 2 1 1 0 2 0 1 1 2 2 2 1 2 0 2 1 2 1 2 0 1 0 1 0 2 2 1 2 0 1 1 1 2 1 2 1
1 1 2 2 0 2 2 1 2 1 2 2 2 2 2 1 2 2 0 1 1 2 2 0 0 1 2 2 0 1 2 0 0 0 1 0 1 0 1 2 0 0 2 1 2 0 0 1 2
2 0 0 0 1 0 1 1 1 0 2 2 1 2 2 1 0 2 0 1 2 0 2 0 2 1 2 1 2 0 2 1 1 1 1 1 0 0 0 2 1 0 0 2 1 0 2 2 1
0 2 0 1 0 2 0 1 1 0 2 0 1 1 1 2 0 0 0 2 1 2 0 1 1 1 2 2 0 1 1 0 2 2 1 0 1 0 2 1 2 1 2 1 2 0 2 0 2
0 0 0 0 2 0 1 0 0 0 1 1 0 2 0 0 2 1 2 0 0 0 1 1 0 2 1 1 2 1 2 2 1 2 1 0 0 0 1 2 1 2 1 2 0 1 1 2 2
0 1 0 1 0 1 0 2 2 1 2 1 2 2 2 0 1 1 1 0 2 2 1 0 2 0 1 2 1 0 2 0 2 0 1 0 2 1 0 1 2 0 0 0 1 1 1 0 0
1 0 2 0 0 0 0 2 0 1 1 0 0 0 0 0 2 1 2 0 0 1 1 2 0 1 1 0 1 2 1 2 2 1 2 2 1 2 1 0 0 0 2 2 1 1 0 2 1
0 2 0 1 0 2 0 1 1 0 2 0 1 1 1 2 0 0 0 2 1 2 2 1 1 1 0 2 1 2 2 0 1 1 0 1 2 1 2 0 1 0 2 0 2 0 2 1 2
1 0 1 0 0 0 2 2 1 2 2 0 1 1 2 1 0 2 0 1 2 1 2 1 2 0 2 0 1 1 1 1 2 0 2 0 1 2 0 0 0 1 1 2 2 0 1 2 0
2 2 0 0 0 0 1 2 2 1 0 0 2 2 0 2 0 2 1 2 1 2 2 1 0 1 0 1 0 2 0 2 1 2 1 2 2 1 0 0 2 2 2 2 0 0 0 0 1
2 2 2 0 0 1 0 2 0 2 1 2 2 2 2 0 1 1 1 2 2 2 0 2 2 0 2 0 2 0 1 1 1 2 2 2 0 2 1 2 2 2 2 2 2 0 0 1 0
0 2 2 2 1 0 0 1 2 0 1 0 2 0 0 1 1 0 2 1 1 1 2 1 2 0 0 1 0 1 1 0 2 1 1 1 2 0 1 0 2 0 0 2 2 2 1 0 0
0 0 2 0 2 0 0 0 1 1 2 1 1 0 2 1 0 2 0 1 2 0 2 2 2 2 2 0 2 1 0 2 0 1 2 0 1 1 2 1 1 0 0 0 2 0 2 0 0
0 0 1 2 2 2 0 0 2 0 1 0 2 1 1 1 2 0 1 1 0 1 0 0 2 1 2 1 1 1 2 0 1 1 0 0 2 0 1 0 2 1 0 0 1 2 2 2 0
0 1 0 0 2 2 2 2 2 2 1 2 0 2 2 2 1 1 1 0 2 0 2 0 2 2 0 2 2 2 1 1 1 0 2 2 2 2 1 2 0 2 0 1 0 0 2 2 2
1 0 0 0 0 2 2 2 2 0 0 1 2 2 1 2 1 2 0 2 0 1 0 1 0 1 2 2 1 2 1 2 0 2 0 2 2 0 0 1 2 2 1 0 0 0 0 2 2
0 2 1 0 2 2 1 1 0 0 0 2 1 0 2 0 2 1 1 1 1 0 2 0 2 1 2 1 2 1 0 2 0 1 2 1 1 0 2 2 1 2 2 0 0 0 1 0 1
2 1 2 0 2 0 2 0 1 0 2 1 2 1 0 1 1 0 2 2 1 2 0 1 1 1 2 2 1 2 0 0 0 2 1 1 1 0 2 0 1 1 0 2 0 1 0 2 0
1 2 0 1 1 2 2 0 0 0 1 2 1 2 2 1 2 2 1 2 1 0 1 1 0 2 1 1 0 0 2 1 2 0 0 0 0 0 1 1 0 2 0 0 0 0 2 0 1
0 0 1 1 1 0 0 0 2 1 0 1 2 0 1 0 2 0 2 0 1 2 1 0 2 0 1 2 2 0 1 1 1 0 2 2 2 1 2 1 2 2 0 1 0 1 0 1 0
2 2 1 1 0 2 1 2 1 2 1 0 0 0 1 2 1 2 2 1 2 1 1 2 0 1 1 0 0 0 2 1 2 0 0 2 0 1 1 0 0 0 1 0 2 0 0 0 0
2 0 2 0 2 1 2 1 2 1 2 0 1 0 1 2 2 0 1 1 0 2 2 1 1 1 0 2 1 2 0 0 0 2 1 1 1 0 2 0 1 1 0 2 0 1 0 2 0
1 2 2 0 1 2 0 0 1 2 0 0 0 1 1 1 1 1 2 0 2 1 2 1 2 0 2 0 2 1 0 2 0 1 2 2 1 2 2 0 1 1 1 0 1 0 0 0 2
2 1 0 0 2 1 2 0 0 2 1 0 1 0 1 0 0 0 2 1 0 2 2 1 0 0 2 2 1 1 0 2 2 1 2 2 2 2 2 1 2 1 2 2 0 2 2 1 1
1 2 1 2 1 1 1 0 2 1 2 2 0 1 0 1 0 2 1 2 1 2 0 2 1 2 2 2 1 1 0 2 0 1 1 2 1 1 0 1 2 2 2 2 1 2 0 0 1
0 1 1 2 1 1 2 2 1 2 2 2 2 0 0 0 0 1 2 1 2 1 2 0 1 0 2 0 0 0 0 1 1 0 2 2 1 2 0 1 1 1 0 1 1 2 0 0 2
0 2 2 0 2 2 0 1 2 2 2 2 2 1 0 2 1 0 1 2 0 0 1 1 2 1 1 0 2 2 1 2 1 2 2 2 0 0 0 0 0 2 2 2 2 2 2 2 2
2 1 1 2 1 1 0 0 2 2 2 2 1 2 2 1 2 1 0 0 0 0 2 0 1 0 2 1 2 0 1 1 0 0 0 1 1 1 0 2 1 2 2 0 0 2 1 1 0
1 1 1 2 1 2 1 1 0 2 2 1 2 0 1 2 1 2 0 1 0 2 2 2 1 2 0 2 1 1 0 2 0 1 1 2 2 1 0 1 1 2 1 0 0 2 1 2 2
2 1 2 0 0 1 2 0 1 0 1 2 0 0 0 1 2 0 0 0 1 2 2 0 0 1 2 2 2 1 2 2 0 1 1 1 2 1 2 2 2 2 1 1 2 2 0 2 2
0 1 1 1 1 2 2 2 1 0 0 2 1 2 0 2 1 0 2 2 1 2 2 0 0 0 0 1 2 0 0 0 1 0 1 2 2 0 2 2 1 1 0 2 2 2 0 2 0
1 1 2 2 0 0 2 1 2 1 2 1 1 1 2 1 2 0 2 0 2 2 2 2 0 0 1 0 0 2 0 1 0 2 0 2 2 1 2 0 0 1 2 2 1 2 1 0 2
1 2 2 1 1 0 1 0 1 1 2 1 1 2 1 2 0 1 1 2 2 0 2 2 2 1 0 0 0 0 0 0 2 0 1 0 1 1 2 0 0 2 2 1 2 0 2 1 0
1 2 1 1 1 2 1 0 2 2 0 2 2 0 0 0 1 1 1 0 0 0 0 2 0 2 0 0 0 1 0 1 0 1 0 2 2 2 2 2 2 2 2 2 0 2 0 2 2
1 0 1 1 2 2 1 2 1 1 2 1 1 0 2 2 1 1 0 2 1 0 0 1 2 2 2 0 1 0 2 0 0 0 0 2 0 0 2 1 1 0 0 1 2 0 2 1 2
2 0 0 2 2 1 1 1 1 1 2 1 2 1 2 0 2 0 2 1 2 0 1 0 0 2 2 2 0 2 0 1 0 2 0 1 0 0 2 1 2 2 2 0 1 2 1 2 2
2 2 1 1 1 1 0 2 1 2 0 0 1 2 1 2 2 0 1 2 0 1 0 0 0 0 2 2 1 0 1 0 0 0 2 1 1 2 2 0 2 2 0 2 0 2 2 2 0



So--- armed with this model we can quickly solve individual instances using Gaussian elimination, or use the inverted matrix above. Starting from a blank (all-green) grid the position above requires 50 clicks:

2 0 0 1 1 2 1
1 1 2 1 2 2 0
2 2 2 0 0 0 0
1 2 0 0 1 0 1
1 1 2 2 2 2 2
0 0 1 0 2 0 1
2 1 0 1 2 1 0


The inverse (swap 1<->2) gets back to the goal state, taking 49 steps. The Gauss-Jordan code I found craps out on 2x2 boards, N=4--- I'm still not entirely sure why. But this solution was verified by hand so I'm pretty confident the code works as expected. The solver is pretty fast, it only takes a couple of seconds for the 7x7 board--- fast enough to use in real time if I cared enough to create a graphical front end.

Because the matrix is invertible, we know that every possible pattern is reachable. (Dually, no position is unsolvable.)

Obviously the same approach will work for all games with a prime number of colors. But Z4 isn't a field so a four-color game probably doesn't generate an invertible matrix. However, individual positions might well be feasibly solved using a modification to the Gaussian elimination algorithm.

The approach can also handle different geometries (even irregular ones) because it depends only on being able to generate an adjacency matrix. Are there geometries that don't produce an invertible matrix?
Tags: games, geek, linear algebra, math
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 8 comments