Before it shows you a puzzle, the app Sort Puzzle uses the computer to confirm that it can be solved. The next move shown by “Hint” is also the first move of the steps found by the same solver. Here is how that solver works.
Following Positions and Moves
The state of a sort puzzle board (which colors are in which tubes) is called a position. When you make one move, you get a different position. If you follow moves from the starting position and arrive at a sorted position, the path you followed is the answer.
The most straightforward way to search is breadth-first search, which expands every position reachable in 1 move, then every position reachable in 2 moves, and so on. It always finds an answer with the fewest moves, but with many colors the number of positions to check becomes enormous.
A Measure of “Distance” to Sorted
So the app counts a measure of the distance to a sorted position for each position, and checks the positions that look closer first. The measure is the sum of these two:
- The number of color breaks inside the tubes: The number of places where the color changes, looking from the bottom.
- Overlapping bottoms: If one color sits at the bottom of several tubes, that number minus 1.
In this puzzle, the color breaks are 2 in tube 1, 2 in tube 2, 3 in tube 3, and 3 in tube 4, for 10 in all. Sky blue is at the bottom of tubes 3 and 4, so the overlapping bottoms are 1. The measure is 11. In a sorted position, there are no breaks and no overlaps, so the measure is 0.
The Measure Never Exceeds the Fewest Moves
This measure has a nice property: in one move, the measure never drops by more than 1.
- In one pour, the number of breaks in the tube you move from drops by at most 1. The tube you move to is either on top of the same color or empty, so its breaks neither rise nor fall.
- The overlapping bottoms drop by one only when a tube becomes empty, and that happens only when you move the last run of that tube, and then the breaks don’t drop.
So a puzzle with a measure of 11 takes at least 11 moves. Even after checking a little over 120,000 moves in all kinds of puzzles, no move dropped the measure by 2 or more. The fewest moves for the puzzle above is exactly 11.
Weighted A* Search
The app gives each position a score of “moves so far + 3 × the measure” and checks the positions with the smallest scores first. This is called weighted A* (A-star) search.
- With a weight of 1 (ordinary A* search), the measure is a lower bound on the fewest moves, so it always finds an answer with the fewest moves.
- With a weight of 3, it keeps checking positions with a small measure first, so it finds an answer much faster. In exchange, the answer can be a bit longer than the fewest moves.
For 20 puzzles each, made the same way the app does, I compared the number of positions checked before reaching a sorted position and the number of moves in the answer found (I didn’t count breadth-first search for ★3, because there are too many positions).
| ★1 (4 colors, 2 spare) | Positions checked | Moves in the answer |
|---|---|---|
| Breadth-first search | 537 | 11.8 |
| A* (weight 1) | 203 | 11.8 |
| A* (weight 3) | 39 | 11.9 |
| ★2 (6 colors, 2 spare) | Positions checked | Moves in the answer |
|---|---|---|
| Breadth-first search | 2934 | 18.1 |
| A* (weight 1) | 622 | 18.1 |
| A* (weight 3) | 64 | 18.8 |
Both are averages over 20 puzzles. A weight of 3 found an answer by checking a few tens of times fewer positions than breadth-first search, and the number of moves rose only slightly.
Ways to Check Fewer Moves
The app’s solver also cuts down the positions it checks in these ways.
- Don’t tell the order of the tubes apart: If the contents of the tubes are the same, it treats positions as the same even if the order differs.
- Don’t check pointless moves: It leaves out moves that put a one-color tube into an empty tube (the shape doesn’t change) and moves into a second or later empty tube (it gives the same position as the first).
- Search only with Pour moves: Even for Stack puzzles, it checks whether they can be solved with Pour moves (see Pour vs. Stack).
- Set a limit: If it hasn’t found anything after checking 60,000 positions, it treats the answer as “unknown” and doesn’t use that deal.
This one solver covers both the “check that it can be solved” step in making puzzles (see How Solvable Puzzles Are Made) and “Hint” (see How to Use Hints). The idea of bottom colors is also covered in Which Color Should You Gather First?.
