The boards a knight can tour

Half the neighbours forces a tour found one simple condition that guarantees a closed tour through every point of a graph: every point joined to at least half the others. The graph of knight’s moves on a chessboard is nowhere near that dense. Each of its sixty-four squares is a knight’s move from at most eight others, and a corner square from only two. Dirac’s theorem says nothing about it, and neither does any other density condition.

Yet the knight’s tour is the oldest Hamiltonian-cycle problem there is, studied centuries before the name. Arab chess manuscripts give tours, Euler devoted a paper of 1759 to them, and H. C. von Warnsdorff proposed in 1823 the rule of thumb still used to find them. The question this essay answers is which rectangular boards have a closed tour — a route visiting every square once by knight’s moves and ending a move from its start. The answer, completed by Allen Schwenk in 1991, is a short list of exceptions, and each exception has a reason one can draw.

A tour is a cycle in a sparse graph #

Draw a point for each square and join two points when a knight can move between them. A closed tour is then a Hamiltonian cycle of this graph, exactly the object of the essays before this one; an open tour is a Hamiltonian path, the analogue for points of the walk through every edge that seven bridges began with. The graph is sparse and very regular: interior squares have eight neighbours, squares near the edge fewer, and every square’s neighbours lie on the opposite colour of the chessboard pattern — a knight’s move changes the sum of the row and column numbers by an odd amount, either $1 + 2$ or $2 + 1$.

That last fact makes the knight’s graph bipartite, with the light and dark squares as its two sides, and it is the source of the first exception. It also means that the dense-graph methods are useless here and that each board must be dealt with by structure. Euler’s paper already did what every later treatment does: it built tours on large boards by joining tours of smaller pieces at their ends, so that a few small boards, handled by hand, give tours on every larger one of the same shape. Schwenk’s theorem is the systematic version of that idea, together with proofs that the exceptions really are exceptions.

The tour in the opening figure was found by backtracking: at each step try the squares with the fewest onward moves first, which is Warnsdorff’s order, and abandon any branch that leaves some unvisited square with fewer than two ways in and out, since every square on a closed tour needs two. That second rule only ever discards branches that cannot finish, so the search is exact — it finds a tour if one exists and reports exhaustion if not — and on boards of this size it finds one almost immediately.

Odd boards: thirteen against twelve #

The first exception is every board with an odd number of squares.

A closed tour alternates light, dark, light, dark, and returns to its start, so it has as many squares of each colour, and its length is even. A board with an odd number of squares has unequal colours and odd area, and no closed tour. This is the same parity argument that the essay on the Petersen graph used in its unbalanced bipartite examples, and the same one that kills Dirac’s lower example of three against four: a bipartite graph with unequal sides has no Hamiltonian cycle.

The figure also shows what parity permits. An open tour, which need not return, can exist on an odd board, but it must start and end on the commoner colour: a path of twenty-five squares alternating colours has thirteen of one and twelve of the other, so both ends are on the side with thirteen. On the $5 \times 5$ board a tour can start from 13 of the 25 squares at most, and the light square in the corner is one of them.

Four rows: two colourings that cannot agree #

The second exception is subtler, and it is the one that makes the list interesting. No board with exactly four rows has a closed tour, however long it is — although four rows give the knight room to move freely, and a $4 \times n$ board has an even number of squares. Its proof, due to Louis Pósa and published by Solomon Golomb, uses two colourings at once.

Colour the top and bottom rows as outer and the middle two as inner. A knight on an outer row moves two rows or one row vertically; two rows from the top lands on the third row, which is inner, and one row from the top lands on the second, also inner; the bottom is the same. So every move from an outer square goes to an inner square. On a closed tour, the outer squares are half of all squares, and each is followed by an inner one; that uses up all the inner squares as successors of outer ones, so the tour runs outer, inner, outer, inner, without exception.

The tour also alternates light and dark. So the squares at the odd positions of the tour are all outer and all one colour, and the squares at even positions are all inner and all the other colour. That would make the outer squares exactly the light squares, or exactly the dark ones. They are not — each outer row is half light and half dark — and so no closed tour exists. The figure’s caption adds an independent check: an exhaustive search of every path on the $4 \times 6$ board, from one corner, finds no closed tour. The argument covers every length at once, which no search can.

Three rows: too narrow until ten #

The third exception is three special boards. A board with three rows and even length has an even number of squares and no two-colouring obstruction, and still the boards $3 \times 4$, $3 \times 6$ and $3 \times 8$ have no closed tour.

There is no slick colouring proof for these; the reason is that a three-row board is too narrow for a knight to turn round in, until it is long enough. The search makes the point concretely: following every path from a corner finds nothing at lengths 4, 6 and 8, then sixteen closed tours at length 10 and 176 at length 12. Schwenk’s proof handles these boards by exhausting cases, as the figure does, and then shows that every three-row board of even length from ten on has a tour, by splicing a tour of a $3 \times 10$ or $3 \times 12$ piece onto tours of shorter pieces built for joining.

The counts grow quickly once tours exist, and the same is true of wider boards. The $5 \times 6$ board has 8 closed tours, which the search also finds by exhaustion; the $6 \times 6$ board has 9,862 and the ordinary chessboard about $1.3 \times 10^{13}$, a number found by Brendan McKay in 1997 by a computation far beyond these figures. The interest of the small boards is that the answer goes from none to some abruptly, at a length that nothing in the geometry predicts in advance.

Euler’s method: build small, then splice #

Euler’s paper did not search; it constructed. Its central trick was to divide a board into pieces, find a tour or an open path on each piece with its ends placed so that a knight’s move joins the end of one to the start of the next, and splice the pieces into one route. A closed tour of a large board then needs only a supply of small tours with ends in the right places, and the work of finding them is done once, by hand.

That is the same move that builds a Gray code, the tour of the cube in a walk that changes one thing at a time: a tour of a large object is two tours of smaller ones, joined at their ends. It is also how Schwenk’s proof covers every allowed board: tours of a handful of small boards — boards such as $5 \times 6$, $5 \times 8$, $6 \times 6$, $6 \times 8$, $3 \times 10$, $3 \times 12$ and a few more — each with a pair of adjacent squares on its boundary through which it can be cut open, are laid side by side and stitched, and every larger rectangle allowed by the theorem decomposes into such pieces. The exceptions are exactly the boards too small or too narrow to be cut into pieces of the right shapes, plus the boards the colourings forbid outright.

The method also explains why the counts explode. Each piece has many tours and many ways of being cut open, and the choices multiply across the pieces, so a board made of $k$ pieces has at least the product of their counts. A procedure that builds tours by gluing finds a vast number of them, and still says nothing exact about how many there are.

Every board up to eight by twelve #

Put together, the exceptions are: boards with an odd number of squares; boards with one, two or four rows; and the three-row boards of length 4, 6 and 8. Schwenk’s theorem says that every other rectangular board has a closed tour. The census below checks this on every board from $3 \times 3$ to $8 \times 12$.

The table reads as a picture of the theorem. The odd boards form a chequerboard of their own, the four-row line runs straight across, and the three special boards sit at the start of the three-row line. Everything else is filled. Boards with one or two rows are not drawn: a knight on a single row cannot move at all, and on two rows each square has at most two neighbours arranged so that the graph falls into disconnected paths.

The census also shows how unequal the two kinds of obstruction are. The odd boards fail for a reason about the whole board’s size, visible before any move is made. The four-row boards fail for a reason about the shape of the knight’s move, which is why four rows is the one width that is wide enough to move in and still too narrow to come back: every move from the edge must go inward, and the tour has no room to make up the difference.

Colouring arguments elsewhere #

The two colourings used here are instances of one of the most reliable tools in combinatorics: find a quantity that every step changes in a predictable way, and compare what the steps must accumulate with what the whole configuration has. The chessboard colouring is the one that settles the domino problem in which two opposite corners of a board are removed — every domino covers one light and one dark square, and the two removed corners are the same colour — and dominoes that no algorithm can match took the tiling side of that story much further. A sum that forbids half the pairings used a parity count to rule out Langford arrangements for half of all sizes before any arrangement was tried, and the crossings that will not come out even used the parity of a permutation to show that some rearrangements cannot be reached by swaps.

What the four-row argument adds to that tradition is the use of two invariants at once. Neither colouring alone forbids a tour of a $4 \times n$ board: the board has as many light squares as dark and as many outer squares as inner. The contradiction comes only from asking that a single route alternate in both, which forces the two colourings to coincide. Arguments of that kind are rarer and more delicate than single parity counts, and the knight’s tour is one of the cleanest examples of the form.

A rule of thumb from 1823 #

Warnsdorff’s rule says: from wherever the knight stands, move to the unvisited square with the fewest unvisited squares beyond it. The idea is to visit awkward squares — corners, edges — while they can still be reached, and leave the well-connected middle for later. It needs no backtracking, and it often completes a tour.

On the chessboard the rule completes a tour from 62 of the 64 starting squares, and on boards up to thirty-two squares wide it succeeds from all but a few per cent. On the odd boards it does worse, for a reason the colour count explains: a tour of an odd board must start on the commoner colour, so on $5 \times 5$ at most 13 of the 25 starts can succeed, and the rule manages 11. Its failures elsewhere depend on how ties are broken; with ties broken badly it can strand a corner, which is why every search in this essay keeps Warnsdorff’s order as a preference and backs up when it fails.

The rule is a good example of a heuristic that is almost always right and provably not always right. Nobody has proved for which boards a suitably refined version always succeeds, and the success rates in the figure are measurements, not theorems.

What the census cannot prove #

Every “tour” in the census is a checked construction: the tour is found, each move is verified to be a knight’s move, and every square is verified to be visited once. Those entries are certain. The “search” entries are exhaustive searches, which are proofs for those three boards. The “odd” and “4 rows” entries are applications of the two colouring arguments, which are proofs for every board of those shapes, not only the ones in the table.

What the census cannot do is reach beyond $8 \times 12$. That every larger board allowed by the theorem has a tour is Schwenk’s inductive construction — tours of small boards spliced together along their edges — and the figure illustrates the conclusion on the boards small enough to search, without re-deriving the construction. The counts of tours on the three-row boards are exact; the counts quoted for the $6 \times 6$ board and the chessboard are not computed here.

Still open: the knight on other boards #

Rectangles are settled. Other boards are not. On a three-dimensional board of $m \times n \times p$ cells, with a knight moving two steps along one axis and one along another, the existence of closed tours was worked out only in the 2000s and 2010s, and the exceptions are again a mixture of parity arguments and small cases. On boards drawn on a torus, where the knight wraps round the edges, tours exist far more often, because the edge obstructions vanish.

The counting questions are more open. Exactly how many closed tours an $n \times n$ board has is known only for small $n$ — the chessboard’s count required large computations in the 1990s — and the growth rate of the count with $n$, which ought to be roughly exponential in the number of squares with some constant base, has no proved value. The knight’s graph is regular enough that its tours ought to be countable by a structured method, and no such method is known. The situation resembles the one the walk through the middle levels described for a much more symmetric graph, where even the existence of a single tour resisted proof for decades and counting them is out of reach.

Two colourings and a narrow strip #

The knight’s tour problem shows the two great sources of impossibility for Hamiltonian cycles in miniature. One is counting: an invariant, here the colour of a square, that every step alternates, so that a closed tour must balance it — and an odd board cannot. The other is a second invariant that the first must agree with: on four rows, a tour would have to alternate both colours and rows at once, and the board’s geometry makes those two alternations incompatible. A third source, plain lack of room, shows up on the three-row boards and has no slick proof at all.

Everything else in the rectangle has a tour, and the construction of them is a matter of building small tours and splicing them, the method Euler used. That is the shape of most good answers about Hamiltonian cycles: a few clean obstructions, a few stubborn small cases checked by exhaustion, and a construction for everything left over. The density that Dirac’s theorem relied on plays no part, and the regular structure of the knight’s move plays every part.