The Knight's Tour solver bug that called solvable boards impossible

I built a small iOS app for the Knight's Tour — the puzzle where a knight has to visit every square of a board exactly once. One of its modes just watches a solver find a tour for any board and start square you pick. Simple enough.

Except the solver kept lying to me.

On a 7×7 board starting from (3,1) — a position that definitelyhas a tour — it would report “no solution” about 40% of the time. Not always. Just often enough that I couldn't reproduce it on demand and nearly shipped it.

The solver

It's Warnsdorff's heuristic with backtracking: at each step move to the square with the fewest onward moves, breaking ties randomly, and backtrack if you hit a dead end. The random tie-break matters — it's what lets a fresh run escape a layout the previous run got stuck in.

To keep the UI responsive I capped the search at 500k iterations. And here's the bug, in one line of intent:

if iterations > CAP { return .noSolution }   // WRONG

I treated the cap as a proof of unsolvability. It isn't. The cap is a timeout, not a proof. When a run happened to make unlucky tie-break choices, it blew the iteration budget before exhausting the tree — and I reported that as “this board has no tour,” which for most boards is mathematically false.

The measured false-negative rate: ~40% on 7×7 from that corner, ~5% on 9×9 and 10×10. Big boards have more tours, so a single run is likelier to stumble into one before the cap. Small-but-not-tiny boards are the danger zone.

The fix

Almost embarrassingly small: separate “I ran out of time” from “I proved there's no tour.”

// backtrack now reports whether it aborted on the cap
func backtrack(..., hitCap: inout Bool) -> Bool { ... }

// solve() retries with a fresh shuffle on a cap-abort,
// and only returns nil on genuine exhaustion of the tree
for _ in 0..<maxRestarts {          // maxRestarts = 15
    var hitCap = false
    if backtrack(..., hitCap: &hitCap) { return path }
    if !hitCap { return nil }       // real exhaustion → truly no tour
    reshuffle()                     // hit the cap → unlucky, try again
}

Each restart re-randomizes the tie-breaking, so a run that got unlucky gets a fresh roll instead of a false verdict. Verified across the danger-zone boards: 40% → 0%.

The lesson

The one I keep relearning: a resource limit is not a mathematical result. “I gave up” and “it's impossible” are different answers, and conflating them is how you confidently tell someone a solvable puzzle can't be solved.