When I created this game, I was generating random configurations of 3 by 3 square with 3 colors. I immediately asked myself "How can I be sure that these initials configurations are solvable ?"
As a former Computer Science student, I tried to describe the game with Mathematical concepts in order to investigate on the question. The more I was digging in, the more questions were coming to my mind. What happen if I change the number of colors ? Is it still solvable if I change the size of the square ? What if I remove certain tiles of the squares ?
This is the result of my investigations, do not hesitate to comment or share if you find mistakes or if you can help me understanding the Game!
The first thing I did to prove solvability was to write a linear system which was representing the game. I assign a number to each tile of the square. See below an example with 3 by 3 square:
We know that the game must be solve by clicking on specific tiles, let's call the number of times we need to click on the tile number . We are then looking to find the vector:
We remark that if we click on the same tile 3 times, then the game goes back to the previous configuration and nothing as changed. This means that all are between 0 and 2 included. Clicking 3 times on a tile is the same as not clicking on it.
This is because we have 3 colors, if we had n colors, then we would need to click n times on a tile to go back to the initial configuration.
Assuming we want to turn all tiles in red and starting with the initial configuration above, we have the following linear system:
Which can be described with matrices like this:
From this equation we can say that if the matrix A is inversible in the all initial configurations B are solvable!
We can use the same process for an arbitrary length of the square and any number of colors . Where is prime. Because when is prime, is a field.
This is part is to be continued, I have created a repository with python code implementing the Gaussian elimination for 3, 5 and 7 colors. You can find it herePlay