Jeffrey Bosboom's Blog

[blog] [projects] [about]

Review and analysis: Strata

Strata is a constraint-satisfaction puzzle game played on small grids (up to 6x6), some squares of which are colored with one of up to six colors. The goal is to cover each row and column with a colored ribbon such that the top ribbon on each colored square matches the square’s color. Ribbons are placed one at a time, bottom-to-top, inducing a partial order; in other words, the ribbons cannot be interwoven.

Strata bills itself as “a challenging game of forethought and sequencing”, but the difficulty is fake. Below, I describe a simple algorithm for solving Strata puzzles. This algorithm orders the ribbons top-to-bottom, recursing on smaller puzzles until no constraints remain. If Strata’s user interface allowed placing the ribbons top-to-bottom, it would be clear which rows or columns remained with unsatisfied constraints, making the game trivial. Instead, Strata requires bottom-to-top ribbon replacement, so already-placed ribbons can’t be used to define the subpuzzles. Strata quickly stopped being fun.

So as with most puzzle games, I started thinking about algorithms.

Analysis of Strata

The algorithm is based on the following two properties of Strata puzzles.

These properties suggest a simple algorithm for solving Strata puzzles. For brevity, we use row generically to refer to both rows and columns.

This algorithm returns null if the puzzle has no solution and an ordering and color assignment for the ribbons otherwise. Note that some ribbons may not be present in the solution; consider, e.g., a puzzle with all rows having at most one color, for which the returned solution may omit all the columns. These omitted ribbons are not used to satisfy any colored squares, so they may be given an arbitrary order below all present ribbons and an arbitrary color.

By the first property, if a puzzle has a solution, the algorithm will find a row or column to remove. By the second property, if the reduced puzzle has a solution, the original puzzle also has a solution. The base case is the empty puzzle, which has no constraints (no colored squares) and is vacuously solvable. Thus the algorithm is correct.

The algorithm recurses at most r+c times for a puzzle with r rows and c columns, at each step performing O(rc) work searching for a row or column with at most one color of squares, so it runs in O((r+c)rc) time.

stratabot

I implemented the above algorithm in stratabot, a Java program that can play Strata by parsing its graphics and submitting mouse clicks. I spent more time on the automation than on the algorithm; Strata includes some nondeterministic “texture” (noise) in its graphics, making parsing difficult. In the end, I hardcoded pixel offsets to read colors and send clicks.

stratabot can play single puzzles or a “wave” (Strata’s word for a level set) at a time, provided a human tells it the puzzle size and number of colors. The wave and puzzle select screens could be automated with a bit more effort, but stratabot’s current state is enough to get all the cheevos, so I stopped there.