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.
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.
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.
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.
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.
- Name Pixelea Challenge
- Version 1.0
- Credits Pixelea Challenge is a fixed Pixelea case with only one square against the others.
- Game category Brain and Puzzle
- Price 0 (Free)
- Platforms Chrome, Internet Explorer 9+, Firefox, Safari, Opera
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License
- Original idea: Alexey Nigin, he enjoys difficult puzzles.
- Sound: Kenney Vleugels, wowsoundsg
- Translations: Catherine S.