About Pixelea puzzle
Pixelea is a combinatorial brain teaser, a kind of puzzle with a fixed set of pieces or elements that you must be combined or arranged somehow in order to reach a goal state. Pixelea is also a chromatic puzzle because it uses colors as its primary elements: colors determine the state of the game.
Alexey Nigin invented this formidable game: it is simple and clean, not difficult but not trivial. Anyone can solve it given enough time. But the best part of the puzzle lies within its combinatorial problem.
A general version of the puzzle consists of an m x n grid of squares, randomly assigned one of three colors. A valid movement consists in placing a domino on the grid covering two different colors, and switching them to the third color. The goal of the puzzle is to reach a board with only one color.
This is the front-face of the puzzle. But for the keen mind, this game has also a back-face. First, once we have our random board, there is only one color that we can reach with our movements. Second, how do we know that the puzzle is even solvable? It could happen that we never reach an uniformly coloured board!
For those interested, I initiated a discussion about the existence of the solution, where it was proven that it always exists provided that the board size is not divisible by 3.
This is a solution from a constructive proof, not the optimal solution, but it always works. Shortly, the algorithm consists of solving each row to one color and then solving for all columns to the final color. It is rather a time consuming task, but it has the advantage that you don't need to know the final color in advance.
Solving for rows: each row can be switched to a concrete color. One way to do this is to switch the first 4 elements of the row to a single color. There are 81 possible combinations (3⁴), but they basically reduce to ten patterns (subscripts are the identifiers of unique patterns):
Once you have half row in one color, repeat this on the last four colors of the row. Now you will have a row with two groups of four colors. If the colors are the same, row solved! Else, you can switch to a unique color:
Now you can repeat on each row and end up with all rows being its own color and all columns being identical. Just repeat the algorithm, this time vertically. You can repeat the same steps on each column since they are all the same color pattern, and they all will change to the same color, solving the puzzle.
Some of you have asked what happens when the board has size divisible by three. The answer is that you can find configurations that are unsolvable: however much you switch colors, you cannot reach a single color board.
The final color
For those wondering to know how to know the final color in advance, the read the Pixelea Challenge about for an nice application of invariants.
Edit - July 1, 2016
Here you have an example of the algorithm solving one instance of the puzzle. As you can see, it starts solving by columns first, then solves each row (all the same) to the final color.
- Name Pixelea
- Version 1.0
- Credits Pixelea is a fun combinatorial puzzle where you switch colors until there is only one color.
- 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.