What is the fewest number of moves it takes to solve a sort puzzle? For puzzles of ★1 size (4 colors, 2 spare tubes) in the app Sort Puzzle, you can check every deal. I counted the fewest moves for all the deals, using Pour moves.
How I Checked
- I looked only at “fair deals,” which have no tube with a run of three or more of one color (these are the only deals the app shows).
- Deals that differ only by the order of the tubes, or only by the colors being repainted, count as the same. That gives 89,675 kinds (see How Many Starting Puzzles Are There?).
- For each deal, I expand every position reachable in 1 move, then in 2 moves, and so on, and find the number of moves at which a sorted position first appears (breadth-first search).
Distribution of the Fewest Moves
| Fewest moves | Kinds of deals |
|---|---|
| 5 moves | 3 |
| 6 moves | 8 |
| 7 moves | 124 |
| 8 moves | 741 |
| 9 moves | 3,523 |
| 10 moves | 11,070 |
| 11 moves | 21,321 |
| 12 moves | 26,778 |
| 13 moves | 19,271 |
| 14 moves | 6,635 |
| 15 moves | 197 |
| 16 moves | 4 |
The most common is 12 moves, and 10 to 13 moves make up more than 80% of all deals. Only 3 kinds of deals can be solved in 5 moves, and only 4 kinds take 16 moves.
(The numbers here are “kinds.” The chance of actually being dealt each one in the app differs slightly from kind to kind.)
The Shortest Puzzle (5 Moves)
In every tube, two of the same color are stacked together. Using the two empty tubes, it’s sorted in 5 moves.
The Puzzle That Takes the Most Moves (16 Moves)
Tubes 1 and 2 are exactly the same, and so are tubes 3 and 4. In every tube, all the colors next to each other are different, and red and lime each sit at the bottom of two tubes.
See the 16 moves
Finding a Lower Bound on Moves
You don’t have to try everything to find a lower bound on the fewest moves (a number it can’t go below). You can get it just by looking at the puzzle.
- Count the number of color breaks inside the tubes.
- If one color sits at the bottom of several tubes, add “that number minus 1.”
Each pour reduces this total by at most 1, so it can’t be larger than the fewest moves (see Solving It by Computer).
- The 5-move puzzle: There are 4 breaks, and red is at the bottom of 2 tubes, so add 1, giving a lower bound of 5. That is exactly the fewest moves.
- The 16-move puzzle: There are 12 breaks, and red and lime are each at the bottom of 2 tubes, so add 2, giving a lower bound of 14. It actually takes 16 moves.
Of the 89,675 kinds, the lower bound matched the fewest moves exactly in 38,571 kinds (about 43%). In the rest, it takes more than the lower bound.
For Bigger Puzzles
With more colors, there are too many deals to check them all. The average of the fewest moves for 20 puzzles each, made the same way the app does, was 11.8 moves for ★1 and 18.1 moves for ★2 (6 colors). For ★3 and up, even finding the fewest moves for one puzzle takes a long time.
The app’s “Hint” shows you a solution that is found quickly, not the fewest moves. If you want to go for the fewest moves, use the lower bound as a guide and work out the steps yourself (see How to Use Hints).
