Ball sort — water sort, colour sort, whatever your app store calls it — is usually shipped as a bank. Someone generates ten thousand boards offline, checks they are solvable, and ships them as data. The game loads level 4,312 from a file.
The reason is not laziness. It is that solving these boards is genuinely hard, and a solver that takes a second per board cannot run while a person is waiting.
We wanted Prism Sort to deal from a seed instead — infinite boards, no asset, no build step, and a daily puzzle that is the same everywhere without shipping anything. That needs a solver fast enough to run at deal time. Here is the one we found, and the more interesting thing it turned into.
The heuristic
For a ball sort position, define:
h = Σ_c (segments of colour c − 1) + |{c : no tube has c on its floor}|
In words: for every colour, count how many separate runs of it exist and subtract one — that is how many merges are still owed. Then add one for every colour that is not currently sitting on the floor of some tube.
The second term is the part that makes this work. A finished tube is one colour from the floor up. So a colour with no floor position anywhere needs at least one pour into an empty tube before any of its merges can start — a move that reduces no segment count at all, and which a segment-counting heuristic alone cannot see coming.
Why it is admissible, and better than that: every legal move relocates
exactly one run of one colour, and can merge at most two segments of it. So no
move can drop h by more than one. That makes the heuristic consistent, not
merely admissible — which means A* never has to reopen a node it has already
settled. That property is the whole performance story.
The measured jump
Naive IDA* on the same boards, same machine:
- 8 colours: about 1.2 seconds per deal, and only 45 per cent proved within a 4-million-node budget
- 10 colours: 10 per cent proved
With the heuristic above plus a transposition table keyed on tube-sorted canonical positions:
- 100 per cent proved, sub-millisecond typical
- worst case around 8ms at ten colours, 26ms at twelve
- fewer than 500 nodes expanded on a typical start
That is not a tuning win. It is a different algorithm's worth of difference from one better lower bound.
Consequence one: the bank disappears
Unjam, our Rush Hour game, still ships a pre-built puzzle file and a build script that produces it, because its search is far too slow to run at play time. That is the normal arrangement and there is nothing wrong with it.
Prism Sort ships nothing. It takes a seed, deals, proves par, and starts. Every
board is generated on the device. There is no puzzles.js, no generation step in
CI, no asset to version, and no ceiling on how many levels exist.
One trap worth naming, because we designed around it deliberately: the generator's rejection loop is bounded by node count, never by wall-clock time. A time budget there would hand a slow phone a different daily puzzle from a fast laptop — the deal would silently depend on the hardware. Wall-clock budgets are fine on the hint path, which does not affect what was dealt.
Consequence two: the solver becomes a feature
This is the part we did not anticipate, and it is the reason this post exists.
Once the solver runs in under a millisecond, you can afford to run it after every single move. And once you do that, you can show the player something no other game in this genre shows:
Fewest — the shortest finish still available from where you now stand.
It equals par while you are playing a perfect line. It rises by one each time you waste a move. It reads as a dash when you have made the board unsortable. It is a live, honest measure of how you are doing, and it is only possible because the solver got cheap enough to be a UI element rather than a build tool.
The generalisable version: when a solver gets fast enough to run per move, stop asking what it saves you at build time and start asking what it can now tell the player. We suspect that shape exists in a lot of puzzle games where the solver is currently locked away in a script.
And what the measurement said about the game itself
While the solver was there, we used it to ask how deep the genre actually is — the same method we used on the arrow-tap family: walk an optimal line, and at each step ask what fraction of legal moves keep the board solvable.
With two spare tubes: branching factor about 3.8. 96 to 99 per cent of legal moves keep the board solvable, and 62 to 70 per cent sit on an optimal line. So single moves are almost never traps. Losing a ball sort board is death by accumulation — a player choosing at random dies about 64 per cent of the time at eight colours, because thirty moves at 99 per cent each is not 99 per cent.
With one spare tube: branching collapses to 2.0 and 97 per cent of deals are unsolvable — more than thirty rejections per usable board. Tightening the board narrows it rather than deepening it. That is the same lesson the exit-gate experiment taught us in the arrow family, arrived at from a completely different direction.
A rule-of-thumb player who survives lands at 1.08 to 1.19× par. So even though the deadlock game is shallow, the move economy game has real headroom — which is exactly what the Fewest counter turns into something to chase.
Verdict: another calm game with a genuine efficiency chase, and we have written the copy to say so rather than pretending it is a brainteaser.
Play it free, no account, no install: Prism Sort · how to play
