Beat Strata

Strata is a beautiful award-winning game with mesmerizing sound and unique puzzle concept. It contains hundreds of levels with common rules and final goal. Below I present you these rules and ask you to find a universal algorithm, which will allow you to solve easily every single level of the game.

The rules are simple – you begin with an nxn board, some squares of which are colored in arbitrary colors. Then you start placing stripes of whatever color you choose over entire rows and columns of the board. Your task is after placing all available 2n stripes, the color of every (colored) square to match the color of the stripe which has been placed second over it (on top).

Can you find a simple algorithm, which results in solving any level of the game, no matter the starting position? You can watch AppSpy’s video below for better understanding of the rules.

SOLUTION

Imagine the reverse Strata puzzle – the color of every square must match the color of the first stripe which is placed upon it. Clearly, there must be a line in the grid such that all colored squares in it have the same color. Take all such lines in the grid and place on them stripes of appropriate colors. Then erase the colors from all squares covered by the stripes and repeat the procedure until you place all 2n stripes. It is easy to see that if the reverse Strata puzzle has a solution, then we will find it using this strategy. Finally, in order to solve the original Strata puzzle, just place the stripes in reverse order.