About Pixelea Challenge

About Pixelea Challenge

This puzzle is a special case of Pixelea game, the only difference being that the initial distribution is always the same. I've added it because it allows us to compare solutions: all users are solving the same puzzle so we can add a leaderboard (that is, more fun!).

As you can imagine, you can apply the Pixelea's solution algorithm to solve this particular case. But that algorithm is far from optimal, because you perform a lot of extra color switches. Here you have, then, an opportunity to find an optimal solution.

My initial idea was to create a two color version with the aim to solve the board to the third color. I also wanted to use one of the two colors only in one square. Sadly, this is not possible! To see why, we will use a color switch invariant. But first we are going to deal with a related problem: how to know the final color in advance.

Final color in advance

An invariant is a value associated to the state of our puzzle (or a general system) that is constant regardless of the state of the game. This is a powerful technique for solving problems otherwise difficult.

Let's create an invariant that will allow us to calculate the color of the winner board. If you assign integer values a, b, c to the three colors (for example a = 0, b = 1 and c = 2), then we can calculate the sum S of all color values of the board. It happens that the remainder of S divided by 3, name it R, is an invariant. This means that no matter how many color switches are performed on the board, that value remains the same.

0
1
2
We assign a numeric value to each color. They could be any integer as long as the remainders when divided by 3 are different (in order to be able to tell them apart). The easiest choice is to pick the residues themselves 0, 1 and 2.

We are using the invariant in conjunction with congruences: the arithmetic of remainders of divisions. It is also known as modular arithmetic, another easy but powerful technique for solving difficult problems. We won't dive into it, though. Only one thing to bear in mind from now on: all numbers with the same remainder when divided by three will be the same. So 42 = 0, 13 = 37 or 17 = 2.

A generic state of the Pixelea challenge puzzle.
Here we have 22 gray squares, 18 blue and 24 orange. Using the color numbers assigned previously, our invariant is R = 18·0 + 24·1 + 22·2, that is, R = 24 + 44 = 68. But remember, we are working with the remainders of 3. The remainder of 68/3 is 2, so the invariant for this concrete puzzle image is R = 2.

Why is R an invariant? Well we should demonstrate that any color switch leaves it intact. Let's see: a valid movement consists of picking two adjacent squares with different colors, let them be x and y, and replacing both of them with the third color, let it be w. So our invariant after this movement is R' = R - x - y + w + w. The simplest way to see that R' = R is to explore all possible cases. Remember that x, y and w are all different. It turns out that there are only three cases:

x y w 2·w - x - y Variation
0 1 2 2·2 - 0 - 1 0
0 2 1 2·1 - 0 - 2 0
1 2 0 2·0 - 1 - 2 0

Last row contains the variation value of -3, that has a remainder 0 when divided by 3, so it is equivalent to 0. Thus, R is an invariant.

We've seen that R is constant, so it will be the same for all the states of our puzzle instance. In particular, we can calculate it for the solved state that consists of all squares with the same color. If x is the final color, we can calculate R by adding the 64 color values as

R = 64·x

This can be expressed as

64·x = (63 + 1)·x = 63·x + x

But 63 is multiple of 3, so 63·x is multiple of three and therefore is has remainder 0, so when we work with the remainders,

64·x = 63·x + x = 0 + x = x

(In modular arithmetic, we would say that 64 is equal to 1 (the remainder of 64/3), so 64·x = 1·x = x)

That means that if x is the final color, then R = x. In the previous image example, R was 2, so the final color for that puzzle was gray.

Summarizing, the value of the invariant is the value of the final color. To know the final color we just need to calculate the sum of the colors and divide by 3 to see the remainder. Interestingly, the distribution of the colors over the board is irrelevant for the final color.

Pixelea Challenge has final color orange

Our configuration consists of 63 blue squares and one orange. No matter the values assigned to the colors, as 63 is multiple of 3, the blue squares are equivalent to 0 in our invariant for this puzzle and it only depends on the value of the orange square. And this means that the final color is orange, not gray as I wanted it to be.

Blue board with one orange square.
As we've seen, the final color here is orange.

Now if we had an initial configuration of 62 blue squares and two orange squares, then the final color would be different. With this configuration, the invariant is, using previous color values, R = 62·0 + 2·1 = 2, so final color is gray.

Blue board with two orange squares.
We also calculated that the final color here is gray.

Finally for a configuration of 61 blue squares and three orange squares, final color is blue. As we have three orange squares and 3 is multiple of 3 and hence the remainder is 0, they don't affect to the invariant, so it can be calulated with the other squares, which are all blue. There are 61 equal squares (blue), but as 61 = 1, the invariant is the value of one blue square, so the final color is blue.

Blue board with three orange squares.
The contribution of three equal color squares to the invariant is 0. Here final color is blue.

Credits

Team

Components:

Comments (6)
  • · 12 months ago

    Pixelea Challenge can be solved in 63 moves

    • · 12 months ago

      Mi solución no queda registrada Edgar, saludos!

      • · 12 months ago

        Hola Fali, sí, Alexey me ha comentado el mismo problema, trataré de resolverlo cuanto antes, saludos!

        • · 12 months ago

          He realizado unos cambios, creo que ahora ya funcionará para quien sepa cómo resolverlo con 63 pasos!

        • · 12 months ago

          Gracias Edgar!

          • · 12 months ago

            As Alexey detected, there is a bug in the leaderboard: when you solve the puzzle more than once, it should pick the best result sorted by date! I've added it to the large bug list! Sorry for the inconveniences.

            New comment

            Please login to comment.