Given N columns of capacity N, each initially containing one ball of every color
[0, 1, 2, ..., N-1], plus one empty buffer column of the same capacity,
sort the balls so that each column contains N balls of a single color.
Only the top ball of each column can be moved. This is essentially a matrix transposition problem using stacks with a single buffer.
We believe the minimum number of moves (par) for a grid of size N follows:
This was derived from computing the exact optimal solution for small values of N using BFS (breadth-first search) and fitting a degree-2 polynomial to the results.
| N | Par | Status |
|---|---|---|
| 2 | 3 | Verified (BFS) |
| 3 | 10 | Verified (BFS) |
| 4 | 21 | Verified (BFS) |
| 5 | 36 | Verified (IDA*+TT) |
| 6 | 55 | Conjecture |
| 7 | 78 | Conjecture |
The state space grows exponentially with N. For N=4, a BFS solver explores 11 million states in 8 seconds. For N=5, BFS exceeds 9 GB of RAM and crashes before finding the answer.
N=5 was finally cracked using IDA* with an improved admissible heuristic (optimal color-to-column assignment + blocking penalty) and an 8 GB transposition table. It confirmed par = 36 in 38 seconds and 4 million nodes. N=6 (conjecture: 55) remains out of reach — limit 50 alone takes 16+ hours.
A complete proof requires two things:
1. Upper bound — An explicit algorithm that solves any N in exactly (2N−1)(N−1) moves.
2. Lower bound — A proof that no algorithm can do better.
Can you prove or disprove this conjecture? If you find a proof, a counterexample, or a better algorithm, we want to hear from you.