Rubis Square

Game Theory

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!

Mathematical Representation

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:

0
1
2
0
1
2
0
1
2

Assignment:

123456789\begin{matrix} 1 & 2 & 3\\ 4 & 5 & 6\\ 7 & 8 & 9\\ \end{matrix}

We know that the game must be solve by clicking on specific tiles, let's call xix_{i} the number of times we need to click on the tile number ii. We are then looking to find the vector:

(x1x2x3x4x5x6x7x8x9)\begin{pmatrix} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \\ x_{5} \\ x_{6} \\ x_{7} \\ x_{8} \\ x_{9} \\ \end{pmatrix}

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 xix_{i} are between 0 and 2 included. Clicking 3 times on a tile is the same as not clicking on it.

0
1
2
0
1
2
0
1
2

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:

{x1+x2+x4+0=0x1+x2+x3+x5+1=0x2+x3+x6+2=0x1+x4+x5+x7+0=0x2+x4+x5+x6+x8+1=0x3+x5+x6+x9+2=0x4+x7+x8+0=0x5+x7+x8+x9+1=0x6+x8+x9+2=0\begin{cases} x_1 + x_2 + x_4 + 0 = 0 \\ x_1 + x_2 + x_3 + x_5 + 1 = 0 \\ x_2 + x_3 + x_6 + 2 = 0 \\ x_1 + x_4 + x_5 + x_7 + 0 = 0 \\ x_2 + x_4 + x_5 + x_6 + x_8 + 1 = 0 \\ x_3 + x_5 + x_6 + x_9 + 2 = 0 \\ x_4 + x_7 + x_8 + 0 = 0 \\ x_5 + x_7 + x_8 + x_9 + 1 = 0 \\ x_6 + x_8 + x_9 + 2 = 0 \\ \end{cases}

Which can be described with matrices like this:

(110100000111010000011001000100110100010111010001011001000100110000010111000001011)×(x1x2x3x4x5x6x7x8x9)+(012012012)=(000000000)\begin{pmatrix} 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 \\ 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 \\ \end{pmatrix} \times \begin{pmatrix} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \\ x_{5} \\ x_{6} \\ x_{7} \\ x_{8} \\ x_{9} \\ \end{pmatrix} + \begin{pmatrix} 0 \\ 1 \\ 2 \\ 0 \\ 1 \\ 2 \\ 0 \\ 1 \\ 2 \\ \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \end{pmatrix}

Or:

AX+B=0AX + B = 0

From this equation we can say that if the matrix A is inversible in Z/3Z \mathbb{Z} / 3 \mathbb{Z} 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 pp. Where pp is prime. Because when pp is prime, Z/pZ\mathbb{Z} / p \mathbb{Z} is a field.

Solving

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 here

Play