The Strata Solver

This is a naive implementation of a solver for the Strata game. It's currently only implemented in Prolog and is tailored for the YAP Prolog System. There is a Git repository at GitLab and a simple web page at the Ringlet development site.

The algorithm for solving Strata puzzles is as follows:

1. Take as input a representation of the puzzle as a two-dimensional array of non-negative small integers; non-colored fields are represented by zeroes, colored fields are represented by 1, 2, 3, etc.

2. Create a set of the fields in all the verticals (marked "A", "B", "C", ...) and all the horizontals (marked "1", "2", "3", ...) on the board.

3. "Explode" the board into a list of triples representing colored fields; each triple consists of two coordinates and a color code. Non-colored fields are left out of the "exploded" board representation.

4. Check if there are any colored fields left on the board; if none, mark all the rest of the horizontal/vertical sets as filled with color 1 and go to step 9.

5. Find a set that satisfies both the following conditions:

   • there is at least one colored field left in it
   • all the colored fields left in it are of the same color

   If there is no such set to be found, backtrack (restore the last chosen set's colored fields, then choose a next candidate for it).

6. Add the chosen set and the color of its fields to the end of the list of sets representing the solution.

7. Remove all the colored fields in this set from the board.

8. Go to step 4.

9. Reverse the list of sets representing the solution and return it.

For any comments or suggestions please do not hesitate to contact Peter Pentchev.