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.

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

- The topmost ribbon in a solved puzzle crosses only squares of its color or no color. This fact follows immediately from the rules of the game, as no other ribbon can override the topmost ribbon’s color. This also implies that puzzles lacking a row or column whose squares have at most one color have no solution.
- Removing the row or column of the topmost ribbon in a solved puzzle produces an independent puzzle with the same solution except for the topmost ribbon. Removing that row or column removes any colored squares that were satisfied only by the topmost ribbon; as ribbons only satisfy squares in their row or column, the remaining ribbons must cover the remaining squares. Thus a solution to the reduced puzzle provides a solution to the larger puzzle if the removed row or column contains squares of at most one color (required by the previous property).

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

- If the puzzle being solved is empty, return an empty solution.
- Search for a row containing squares of at most one color.
- If no such row is found, the puzzle has no solution (by the first property). Return null.
- If such a row is found, remove that row and recurse on the reduced puzzle.
- If the returned solution is null, return null.
- Otherwise append to the returned solution an assignment of the removed row’s ribbon to the single color of the squares in that row (or to an arbitrary color if there are no colored squares in the row) and return this modified solution.

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.

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.