Constraint solving remains a niche art, which is in part why it’s so refreshing to find instances were it can be put to good use. Recently came across the Adrift puzzle game and thought it would be fun to create a puzzle solver and generator. Although it has been shown that the game is NP-complete that doesn’t necessarily mean we can’t write a speedy solver.
The goal in the Adrift game is to connect each of the color end point pairs by a string of blocks of the same color. From constraints extrapolated from this goal we can solve and even create new puzzles. A key insight that can be gleaned from this puzzle is that each color must be surrounded by exactly two of its color, unless it is on an end, in which case it is surrounded by exactly one of its color. Using this observation, we can write a simple solver for the first puzzle using SABR and extend this solver to even larger puzzles.
First we need to state that the allowed symbols are R (red), B (blue) and X (stone).
Now we can set the board, this is simply stating all the blocks that exist in the puzzle which we can later constrain.
.... b0 b1;
... c0 c1 c2;
.... d0 d1;
..... e0;
x3 x4 x5 . y3 y4 y5;
x6 x7 x8 . y6 y7 y8;
}
Below is our first constraint. We tell the board the starting positions of R, B, and X and what we want to fill in via !X (not X) meaning it must be a color. We will do this with a requirement (Req) on the Board object.
!X X;
B !X X;
!X !X;
!X;
X X !X X !X X;
B !X !X X !X R;
}
Below we have the meat of our solver were we express block links. For a block to be a link it must be surrounded by exactly two of its color. The first represents the link block and the subsequents represent the blocks it is surrounded by.
This construct uses option (Opt) groups for each of the objects: link2, link3, link4. An option group is like a requirement, only that at least one, but not necessarily all of the requirements in the option group must be met. For example, in link3 we express that for whatever symbol occupies the first place, exactly two of the next three places must match this symbol.
Opt link3 { v !v v v }
Opt link3 { v v !v v }
Opt link3 { v v v !v }
Opt link4 { v v v !v !v }
Opt link4 { v v !v v !v }
Opt link4 { v v !v !v v }
Opt link4 { v !v v v !v }
Opt link4 { v !v v !v v }
Opt link4 { v !v !v v v }
Now we simply describe all of the objects that match up to our Opt groups using DesObj. Note that while Req and Opt can only contain symbols and temporary variables representing symbols, DesObj can only contain Board cells.
DesObj link4 { c1 b0 b1 d1 d0 }
DesObj link4 { d0 c0 c1 e0 x1 }
DesObj link4 { d1 e0 c1 c2 y1 }
DesObj link4 { e0 d0 d1 y0 x2 }
DesObj link4 { x2 e0 y0 x5 x1 }
DesObj link4 { x5 x2 y3 x8 x4 }
DesObj link3 { x7 x4 x8 x6 }
DesObj link3 { x8 x5 y6 x7 }
DesObj link4 { y1 d1 y2 y4 y0 }
DesObj link4 { y4 y1 y5 y7 y3 }
DesObj link3 { y7 y4 y8 y6 }
Running our source code with “./sabr 1 source” we get the only valid solution. This is quite a simple example, but we can easily extend this reasoning to create a more expressive solver and solve more complex puzzles.
You can try out the generator posted here. It works by picking five random location pairs for the five colors, solving it to make sure it can be solved, then trying to solve it again another way to make sure there is only one valid solution. It is fairly fast, generating a new 5x5 with five color puzzle every couple of minutes on a laptop. Here’s a little visualization that shows some of the puzzles it created. To complete the puzzle, click and drag the colored blocks.
They are not curated, so the difficulty curve is all over the map. Writing a program to automatically determine puzzle difficulty would be quite a challenge and likely delve into psychology, so it would probably be faster just to take a sample of solving times and use ascending order. As with many computing problems, it’s surprising how far can be reached just by counting.