Proving the tour is already lost

The question nobody asks while winning

The game has a button that says "where did I go wrong". Nobody presses it while things are going well. You get to it already stuck, with squares on the board that can no longer be reached. So the search is always asked the most expensive question it knows how to answer.

And the answer has to be exact — not "somewhere back there" but the move after which the tour became impossible. That is a binary search over the path already played: "is a tour still possible from here" flips from yes to no exactly once, so a handful of probes find the edge. Every probe is a search of its own, and half of them ask about a lost position.

Easy to find, hard to rule out

A tour is found by backtracking with the moves ordered by Warnsdorff's rule: try first the square that leaves the fewest onward moves. It sounds like superstition and it works — on an ordinary board a full tour turns up within a few hundred nodes, almost without backing up.

That is how it behaves while a tour exists. When none does there is nothing to stumble into: to earn the word "impossible" the search has to exhaust the tree. The ceiling was two million nodes, which is a second or three on a laptop and rather more on a phone, several times over per answer.

Three things a lost position shows on its face

A lost position almost always carries a mark you can see without searching at all. The game checks three of them, at every node.

First, a square nobody can enter any more. If an unvisited square has no unvisited neighbours left, it can only be entered now, from where the knight stands, and never left again. So it has to be the last one. If more than one move remains, there is no tour.

Second, too many forced endings. A square with exactly one unvisited neighbour is entered through that neighbour and not left: it is either the end of the route or where the knight goes right now. A tour has one end, and "right now" is also one. Two such squares out of reach is one more than a tour can carry.

Third, a board that has fallen apart. From here the tour runs through unvisited squares only — the past does not come back. Walk outwards from the current square through what is unvisited, and if you cannot reach all of it, the rest is unreachable forever, however many moves are left.

Why the answers did not change

All three are necessary conditions: not one of them fires on a position that still has a tour. So the search never refuses a live position, it only refuses a dead one sooner. What went away is the wait, not the accuracy.

It did not make the game cleverer, it made it less stubborn. It used to prove hopelessness by exhausting every alternative; most hopeless positions now give themselves away on the first check.

What it bought

A knight that has walked itself into a corner, and a board cut in two, are both refuted in under ten nodes. Both sit in the engine's tests and are asserted against exactly that number.

The ceiling for "where did I go wrong" is fifteen thousand nodes now rather than two million. The binary search asks for it half a dozen times, which puts the whole answer inside a tenth of a second on a laptop.

The honest price: once in a while a tour hidden too deep is not found within the ceiling, and the game calls a position lost a few moves before it truly is. That is the same mistake the two-million budget could make, arriving sooner. The opposite mistake — calling a lost position live — it cannot make: "live" is only ever said when a tour has actually been found.