Note: This is an article from my old dev blog. External links have been updated, but the text is otherwise reposted verbatim.
A long while ago, I found a nice little mobile puzzle game called Strata by Graveck. The premise of the game is simple, you are presented with a grid of colored tiles, and you must create a lattice of colored ribbons on top of each other such that the topmost ribbon at each tile matches the color beneath. Empty tiles can have any color ribbon placed over them. Here’s the trailer to help make more sense of that:
I recently discovered that the game had made its way onto Steam, and became hooked once more. After playing through a few levels, I found myself thinking “I wonder if this can be solved programmatically?”, as I often do with puzzles. Turns out it can be, so let’s have a look at how.
First things first, let’s rotate the board 45° counter-clockwise to get a more obvious set of rows and columns.
I found the easiest way to approach the puzzle was to consider the state of the ribbon stack backwards. The game forces you to place ribbons on top of each other, but it’s easier to conceptualize solving it if you place ribbons under each other. So we consider the topmost ribbon first, and work our way down. When writing a programmatical solver, we can push each ribbon from this approach onto a stack, and then the solution in bottom-up order is given by popping ribbons off the stack in order.
We’ll use the puzzle above as an example. Since the topmost ribbon color for a tile has to match the tile’s color, the topmost ribbon in this puzzle has to be the middle row, and the ribbon must be blue.
Now that we’ve placed the topmost ribbon, we can consider the ribbons below it. Since we’re looking to match colors with the topmost ribbons, placing a ribbon underneath an existing one will only affect tiles that are not already covered. So we’re looking for rows/columns where the exposed tiles are all the same color. In this instance, the middle column’s exposed tiles are all red, so we can place our next ribbon there.
We can then repeat this process of looking for rows/columns where the exposed tiles are all the same color. In the case of a row/column having empty tiles, only the colored tiles are considered. So in this case, the top row contains only one color of colored tile, so we can put a ribbon there. The same goes for the leftmost column.
Continuing on the same path, we find the bottom row’s exposed tiles are all the same color (or rather, the row only has one exposed tile, so let’s put a ribbon there.
Now there’s only one more ribbon left to place! You’ll notice there are no exposed tiles, which means that we can place any color of ribbon since it won’t affect the outcome. Let’s throw a blue ribbon in there.
With this approach in mind, I cranked out a programmatical solver that supports M×N grids. You can feed in a grid layout and it’ll generate the solution for you using the approach above.
There are a couple of interesting points worth noting about the game. As pointed out before, the first ribbon played can be any color since every tile in it will be covered up. Further, we can keep placing ribbons parallel to the first one and their color won’t matter either. The first ribbon placed perpendicular to the first ribbon will contribute color to the final layout. Additionally, any ribbons placed parallel and consecutive to each other can be placed in any order, as they won’t cross over and affect the order of the stack. Similarly, any consecutive ribbons of the same color can be placed in any order, regardless of which direction they face, since their order will not affect which color ends up on top.