I wrote an IDA* search to compute the optimal solution length for a puzzle, and eight
tests to cover it: three hand-built boards with optima I could count by hand, one
unsolvable case, one node-budget case, and two property tests sweeping thirty generated
levels. All green.
Then a reviewer replaced the implementation with a one-liner that returned the length of
any valid solution. All eight still passed.
TL;DR — a test suite for an optimiser has teeth only if at least one case pins a value
where the optimal answer and a merely-correct answer differ. Small hand-built cases
usually do not differ, and one-sided property tests never do.
What I expected
The suite looked thorough to me. It had exact values, it had invariants, it swept a range
of real inputs. In particular I thought the two property tests carried the weight:
// A lower bound the heuristic guarantees.
assertTrue(optimum >= blocks(board) - colours)
// An optimum cannot be longer than some valid solution we already have.
assertTrue(optimum <= anySolutionLength)
That reads like a squeeze. Lower bound below, upper bound above, so the value in between
must be right.
What actually happens
Both hold when optimum == anySolutionLength. The bracket is satisfied by the upper bound
being the answer. A solver that stopped searching at the first solution it found would
sail through.
The demonstration was mechanical. My project already had a depth-first solver that returns
a valid solution, not the shortest one. Swapping it in:
// Stub: returns the length of the FIRST solution found, not the shortest.
fun optimalMoves(board: Board, nodeBudget: Int = 3_000_000): Int? =
(solve(board, board.flipsLeft, nodeBudget) as? SolveResult.Solved)?.moves?.size
8 tests, 8 passing. The hand-built boards were small enough that depth-first search finds
the optimum by luck. The unsolvable and budget cases only check null. And the two
property tests degenerate exactly as above.
The two solvers were not close, either. On one generated level the depth-first answer was
50 moves against a true optimum of 39 — a 28% error that the suite could not see.
The fix
One test, pinning both numbers on an input where the two demonstrably disagree:
@Test fun `the optimum is strictly better than an arbitrary solution`() {
val board = generate(100)
val arbitrary = (solve(board, board.flipsLeft) as SolveResult.Solved).moves.size
assertEquals(39, optimalMoves(board))
assertEquals(50, arbitrary)
}
Pinning both is deliberate. assertTrue(optimum < arbitrary) would pass for a solver that
returned 1. And asserting the arbitrary length too means that if the generator or the rules
ever change, this test fails loudly instead of quietly comparing two numbers that both
moved.
The stub now fails on the first assertion: expected:<39> but was:<50>.
Why it works
An optimiser has two failure modes, and they need different tests. « Returns garbage » is
caught by ordinary correctness tests. « Returns a valid but suboptimal answer » is caught by
nothing unless a test names a case where optimal and valid diverge.
Hand-built test data is exactly where they do not diverge. You build small cases so you
can verify them by hand, and on small cases greedy, depth-first and optimal all agree. The
property that makes a case checkable by hand is the property that makes it useless for this.
The technique generalises past search. Substitute a deliberately weaker implementation —
first-fit instead of best-fit, greedy instead of dynamic programming, an unsorted scan
instead of the tuned index — and run the suite. Whatever still passes is not being tested.
It costs about two minutes and it is much more honest than reading your own assertions and
nodding.
This was the difference between a suite that guarded 500 precomputed constants shipped in
an app and one that only looked like it did. A wrong constant there is invisible at runtime:
the player is shown a target nobody can reach, and nothing crashes.
What I did not test
I did not check whether a mutation-testing tool would have caught this automatically —
plausibly yes for the exact-value assertions, and I doubt it for the one-sided property
tests, since flipping <= to < there is not the mutation that matters. The stub
substitution is a manual approximation of the same idea, and it took less time than
configuring a tool.
The numbers above are from one Kotlin project on JUnit 4. The reasoning is not
language-specific, but I have not repeated the exercise elsewhere.
Facts
context: An IDA* search computing optimal solution lengths, covered by 8 JUnit tests
problem: All 8 tests also passed a stub returning any valid solution, not the shortest
solution: Pin exact values on an input where optimal and merely-valid answers differ
verified_on: 2026-08-13
applies_to: [any optimiser, shortest-path, scheduler, packer, compressor test suite]
does_not_apply_to: [correctness-only code with no notion of a better answer]