Is this chromatic puzzle always solvable?

Question

I've created a new puzzle from an Alexey Nigin's idea. It consists of a 8x8 board where each square is randomly assigned one of three colors. A movement is defined by picking any two orthogonal adjacent squares (forming a domino shape) with different color. Then they both turn to the third color. The objective is to reach a board with only one color.

An example picking two adjacent squares (domino shape).

You can play a test version here.

For each initial board state, there are three final possible states (one of each color), but only one can be achieved.

The question is: Is one final color always achievable?

It would be also interesting to know the hardest configuration (or one of them) and how many steps are required to solve it.

Answer 1

Yes, it's possible.

Start with the various 2x2 squares. Ignoring symmetries of rotation and color swapping, there are 1 combination of 1 color, 3 combinations of 2 colors, and 2 combinations of 3 colors. It is simple to brute-force these 6 combinations to show that each can be changed to a 2x2 square of 1 color. For example:

$$ {12 \choose 31} \to {2 2 \choose 21 } \to {22 \choose 33} \to {12 \choose 13} \to {11 \choose 11}$$

So, to start, convert each of the 2x2 squares to 1 color, each.

If one has two adjacent 2x2 squares of different colors, the first step is to swap the touching colors:

$$ {1122 \choose 1122} \to {1332 \choose 1122} \to {1232 \choose 1222} \to {1212 \choose 1212}$$

For simplicity, call this process "swap", and denote it with $\implies$.

To make two 2x2 squares of different colors into one 2x4 block of one color:

$${1122 \choose 1122} \implies {1212 \choose 1212} \to {3312 \choose 1212} \to {3312 \choose 3312} \to {3333 \choose 3312} \to {3333 \choose 3333} $$

Do this with all adjacent pairs of 2x2 blocks (that are not the same color already). You now have 8 2x4 blocks.

To combine two 2x4 blocks of different colors, repeat the swap procedure until all the columns alternate, then apply dominoes horizontally to make all the colors the same.

$$ {11112222 \choose 11112222} \implies {11121222 \choose 11121222} \implies {11211222 \choose 11211222} \implies {12111222 \choose 12111222} \\ \implies {12112122 \choose 12112122} \implies {12121122 \choose 12121122} \implies {12121212 \choose 12121212} \\ \to {33121212 \choose 12121212} \to {33331212 \choose 12121212}... {33333333 \choose 33333333}$$

Do this to each row, yielding 4 blocks of 2x8.

Next, perform the same process using columns of 2 blocks instead of rows. Since all the squares in each row are already the same color, the process will yield an entire 8x8 square all one color.

This process can be extended to any rectangle where the number of rows and columns are powers of 2 (>=2).

Update It is possible to solve for any $m\times n$ rectangle, so long a $m$ and $n$ are each not divisible by 3.

Solution: make all the squares in each row a single color, using only horizontal dominoes. Repeat process vertically to make all the squares in each column a single color, using only vertical dominoes.

Proof that this is possible: Assign each color a value in ${1,2,3}$. Applying a domino does not change the sum of the values, modulo 3, for example $1 + 3 \equiv 2 + 2 \mod 3$. Since $m$ is not divisible by 3, we know that $m$, $2m$, and $3m$ have distinct values modulo 3. For each row, determine the sum of the color values, $S$, and find the color $i$ such that $S \equiv m i\mod 3$. That's the target color for the row.

Obviously, if $m = 2$, then either the colors are the same and we are done, or they are different, and a single domino will make them the same. So we focus on $m \geq 4$. Take the first $4$ squares, which have values $a, b, c,$ & $d$. It is possible to apply dominoes such to reach $XXXY$, where $X$ is the target color, and $Y = a+b+c+d\mod 3$ (unless $a = b= c= d = Y$).

Proof of this by brute force is tedious, but there are only 81 cases to consider. By way of example:

$$ aabb \to accb \to bbcb \to baab \to bacc \to bbbc \\ \to bbaa \to bcca \to aaca \to abba \to abcc \to aaac \\ \to aabb \to accb \to bbcb \to baab \to bacc \to cccc $$

That path covers 14 of the 81 cases (with some duplicates). No matter what the target color, each of those cases can reach it, except $cccc$.

For each row, determine your target color, $X$. Use this process to set the first three squares to your target color, possibly also changing the value of the fourth square (see caveat below for when this is not possible). Repeat for each group of 3 squares until you have only 1 or 2 left.

If you have 1 left, then that square must now be your target color.

If you have 2 left, then either they are both your target color, or neither is. If neither is, apply a domino to make them both your target color.

Caveat: it may be the case that for a given group of four squares, they are already all the same color, and that color is not your target color. In that case, skip the first three and work on the next set of squares. When you reach the end, then work your way backward. The last set you skipped must now be $YYYX$, which you can convert to $XXXX$. Continue until you are done.

This process will convert a single row to all the same color, using only horizontal dominoes.

When you have converted each row to a single color, you can then proceed to do the same with each column, using vertical dominoes. Since each column now contains the same pattern, the result must be at the end that all squares are the same color.

Answer 2

If the colors are assigned values of 0, 1, and 2, the indicated move will not alter the mod-3 sum of all the squares: (0+1=2+2; 0+2=1+1; 1+2=0+0).

.

If one labels the squares in a row or column A-H, then hitting AB CD EF GH will leave the row or column with four pairs of colors. Then BC AB BC AB CD will make the first four colors match, and FG GH FG EF GH will make the last four colors match. DE CD EF will swap the color of CD and EF, whereupon repeating BC AB BC AB CD and FG GH FG EF GH will make all eight colors match. Note that there is no need to even look at any of the colors one is touching, if hitting two matching colors simply leaves them as they were.

.

Using the indicated procedure once for each row will mean that all eight columns of the board are identical. Using it once fore each column would then cause all columns to end up with the same solid color.

Answer 3

EDIT: Started writing this yesterday and saw there were a couple of answers today. My answer is basically the same, but uses squares instead of rows. Meh. Leaving it here for people to look at if they are interested, but give your votes to others who answered first, and in some cases, more completely.

Yes, the puzzle is always solvable for an 8x8 board with 3 colours.

Lets assign numbers to all the colours. Then the moves become:

• $0+1 \implies 2\times 2$
• $1+2 \implies 2\times 0$
• $2+0 \implies 2\times 1$

Now, lets create a value $S$ which is the score of the board. This value is simply the sum of all the squares modulo 3.

Notice that each move will never affect the score. For example, if your score is $S$ and you make the first move, then you replace a $0$ and a $1$ with two $2$s. The new score is $$\left(S-(1+0)+(2+2)\right) \text{ mod } 3 =S+3 \text{ mod } 3 = S$$

Thus, none of the moves will ever change the score.

So, to solve, simply calculate the score $S$ of the board. Notice that

• $(64 \times 0) \text{ mod } 3 = 0$
• $(64 \times 1) \text{ mod } 3 = 1$
• $(64 \times 2) \text{ mod } 3 = 2$

Thus, the score $S$ tells you which colour can be used to achieve the result.

How to Solve

To solve, you don't even need to know the final colour - it will be made for you. However, this isn't terribly efficient in that it converts regions to colours and then converts the entire region to a different colour. In any event, it works.

This solution only works for boards of size $2^n$. It works by creating larger and larger squares which are homogeneous. At the end, you have an 8x8 square. It can probably be generalized to larger boards.

Phase 1

At the end of this phase, you will have 16 2x2 squares arranged in a 4x4 pattern.

Phase 1.1

First, lets partition the board into 32 2x1 horizontal rectangles starting at the upper left. If the two squares within this rectangle are different, then make a move involving both. You will now have 32 coloured 2x1 dominoes arranged 4x8.

For example:

1200...     0000...
0111... --> 2211...
...         ...

Phase 1.2

Now repeat the phase 1.1 vertically.

1200...     0000...     1122...
0111... --> 2211...     1122...
...         ...         ...

Phase 2

At the end, you will have four 4x4 squares arranged 2x2.

Phase 2.1

Consider two adjacent 2x2 squares made in the previous phase. We will now make 1 horizontal move at their boundary. We will then make 2 vertical moves on either side of the boundary.

Then, repeat phase 1.1 on the region.

Like so:

horizontal move       Repeat phase 1
       |                  |
0011  --> 0221  --> 0101 --> 2222
0011      0011   |  0101     2222
                 |
            Two vertical
             moves

Phase 2.2

Now rotate the board 90 degrees and repeat phase 2.2.

Phase 3 - Final phase

Phase 3.1

Lets look at a single 1x8 row. Start by making a move in the middle (the only valid move, 4th and 5th colums). Now repeat phase 1.1 on the row. This will only have the effect on the 3rd and 4th columns and on the 5th and 6th columns. At the end, we will have effectively reversed the middle section.

....         ....         ...
00001111 --> 00022111 --> 00110011
....         ....         ...

So, now run through phase 2.1 on the entire board. This will recombine 2x2 squares back into 4x4 squares.

Phase 3.2

Rotate the board 90 degrees and repeat phase 3.1.

Example

Lets start with a random board. Phase 1 is easy.

             Phase 1.1    Phase 1.2 
12001020     00002211     11002211
01122202     22002211     11002211
01002010     22001122     00111100 
20102020 --> 11221111 --> 00111100 
11111010     11112222     11002200
02010102     11222211     11002200 
10201020     22112211     11221100
12211201     00000022     11221100

For phase 2, we need to break it into steps. First, we will make all the horizontal moves. These occur in the 2nd and 3rd column, and the 6th and 7th column. We will do them in the odd numbered rows.

Then, we will make the vertical moves in the 2nd, 3rd, 6th, and 7th columns. Lastly, we run Phase 1.1 on the lot.

             Horizontal   Vertical     Phase 1.1
               Moves        Moves 
11002211     12202001     10102121     22220000
11002211     11002211     10102121     22220000
00111100     02211220     01011010     22222222
00111100 --> 00111100 --> 01011010 --> 22222222
11002200     12202110     10102020     22221111
11002200     11002200     10102020     22221111
11221100     10021220     12121010     00002222
11221100     11221100     12121010     00002222

Then we rotate and repeat.

             Vertical    Horizontal    Phase 1.2
              Moves        Moves   (since board is rotated)
22220000     22220000     22220000     22221111
22220000     22221010     22222222     22221111
22222222     22221212     22220000     22221111
22222222 --> 22222222 --> 22222222     22221111
22221111     22221111     22221111     11110000
22221111     21210101     00002222     11110000
00002222     01010202     22221111     11110000
00002222     00002222     00002222     11110000

Phase 3 starts by making horizontal moves down the middle and then on either side. Then we run Phase 2.1.

                                          Phase 2.1
                                   Horizontal   Vertical  
             Middle      Side        Moves       Moves      Phase 1.1
22221111    22200111    22112211    20012001    21212121    00000000
22221111    22200111    22112211    22112211    21212121    00000000
22221111    22200111    22112211    20012001    21212121    00000000
22221111 -> 22200111 -> 22112211 -> 22112211    21212121    00000000
11110000    11122000    11001100    12201220    10101010    22222222
11110000    11122000    11001100    11001100    10101010    22222222
11110000    11122000    11001100    12201220    10101010    22222222
11110000    11122000    11001100    11001100    10101010    22222222

Now rotate and repeat.

                                         Phase 2.2 (due to rotation)
                                   Horizontal   Vertical
              Middle     Side         Moves       Moves     Phase 1.2
00000000    00000000    00000000    00000000    00000000    22222222
00000000    00000000    00000000    20202020    11111111    22222222
00000000    00000000    11111111    21212121    00000000    22222222
00000000 -> 22222222 -> 11111111 -> 11111111 -> 11111111 -> 22222222
11111111    22222222    00000000    00000000    00000000    22222222
11111111    11111111    00000000    20202020    11111111    22222222
11111111    11111111    11111111    21212121    00000000    22222222
11111111    11111111    11111111    11111111    11111111    22222222

General Solution

Note that if the number of squares is a multiple of 3 (e.g. in a 6x8 board, or in a 9x9 board), then only boards with scores $S=0$ would be solvable, in any colour. All other boards would be intractable. The method above would not work as it is since it is only for boards of size $2^n$.

Answer 4

This is a simplification of @user3294068's answer, and can serve as a detailed explanation of @supercat's answer. Points should go to them.

Strategies:

1. Make 4 squares in a row (A-D) the same color (if they aren't already):
   • Hit AB and CD to create two color pairs (colors X and Y):
     X X Y Y
   • Swap BC to color Z:
     X Z Z Y
   • Swap AB to color Y (which is the same color as D):
     Y Y Z Y
   • Swap BC to color X. Now we have two pairs of color X+Y:
     Y X X Y
   • Swap AB and CD, and all squares now have the color Z:
     Z Z Z Z
2. Make 8 squares in a row (A-H) the same color (if they aren't already):
   • Make A-D the same color, and E-H the same color using strategy 1:
     X X X X Y Y Y Y
   • Swap DE to color Z:
     X X X Z Z Y Y Y
   • Swap CD to color Y and EF to color X. Now A-D and E-H look the same:
     X X Y Y X X Y Y
   • Using strategy 1 again, change A-D and E-H to color Z:
     Z Z Z Z Z Z Z Z

Solve the board:

• Use strategy 2 on each row to make a board with horizontal stripes, meaning all columns are identical.
• Use strategy 2 on each column to make each column (and thus the whole board) the same color.