Knight's Tour and N-Queens Lab

Put a knight on a chessboard and ask it to visit every square exactly once. Then clear the board and place eight queens so that none attacks another. Neither task helps anyone win a game.

Both have outlived almost every opening ever analysed. They are small enough to try on a kitchen table and deep enough that parts of them are still open. They are also the two problems on which generations of programmers first met an idea that runs through modern computing: a search does not have to look at everything, as long as it knows when to turn back.

A problem older than the queen

The knight’s tour is much the older of the two. The earliest known reference dates to the ninth century, in a Sanskrit work on poetics by Rudrata. He set a verse on half a board so that it reads the same from left to right as it does when the syllables are taken in the order of a knight’s path.

Chess players took it up soon after. Among the books credited to al-Suli, the great player of the early tenth century who beat the reigning champion at the caliph’s court between 902 and 908, is one said to hold the first known description of the knight’s tour as a problem. The puzzle, in other words, was already old when the mathematicians found it.

Mathematicians arrived in the eighteenth century. An early solution on the full board is credited to De Moivre. Leonhard Euler was one of the first mathematicians to investigate the question properly, in work dated 1759. In 1771 Alexandre-Theophile Vandermonde wrote a paper on it that studied how the curve traced by the moving knight winds through itself, a paper now read as an early step toward topology.

Then came a recipe. In 1823 H. C. von Warnsdorff described a rule simple enough to follow with a pencil: always move the knight to the square from which it will have the fewest onward moves, never counting squares already visited. The rule looks backwards at first. It sends the knight into corners and along edges while it still can get out, and saves the roomy centre for later, when room is what the knight needs.

Which boards can be toured at all

A tour that ends one knight move from where it began is called closed, because the knight could go round again. Any other tour is open. Whether a board has either kind is not a matter of opinion or of trying hard enough. It is settled.

For closed tours the answer is a theorem of Allen Schwenk. On a rectangular board, with the shorter side called m and the longer n, a closed tour exists unless one of three things is true: both sides are odd; m is 1, 2 or 4; or m is 3 and n is 4, 6 or 8. The first case has a reason anyone can check. A knight changes square color with every move, so a closed tour needs equal numbers of light and dark squares, and a board with an odd number of squares cannot supply them.

Open tours are more forgiving. Every rectangular board whose shorter side is at least 5 has one. The boards without any tour are those with a side of 1 or 2, the 3 by 3, 3 by 5 and 3 by 6 boards, and the 4 by 4 board. That is the whole list. The same color argument reaches further than the theorem. A 5 by 5 board has 25 squares, 13 of one color and 12 of the other, so a tour must both start and finish on the color of the corners. Start the knight on the square beside a corner and no tour exists, however long anyone searches.

The size of the haystack

How many tours are there? On the 5 by 5 board, counting each direction of travel separately, 1,728. On 6 by 6 there are 6,637,920. On the ordinary board the figure is 19,591,828,170,979,904. Closed tours alone number 13,267,364,410,532 on the ordinary board when a tour and its reverse count once, and only 9,862 on 6 by 6.

Those numbers sound like good news for a searcher, and they are not. The tours are a vanishing fraction of all the ways a knight can wander for 63 moves. A search that picks moves blindly spends nearly all its time in dead ends, with a few squares stranded that the knight can no longer reach.

The standard remedy has a plain name. Backtracking means trying one of several choices and, if the choice proves wrong, returning to the point of choice and trying another. A reference dictionary of algorithms describes it as a depth-first walk through a tree of partial solutions and quotes an early paper on it: the method was named backtrack by Professor D. H. Lehmer of the University of California at Berkeley. The same dictionary lists the knight’s tour as a classic problem that may be solved this way.

Backtracking alone is still slow on a tour, because the mistake that dooms a path may have been made forty moves earlier. Warnsdorff’s rule is what makes it practical. Use the rule to order the choices and the first path tried is usually a complete tour, with no turning back at all.

Here is a case to reproduce. On the ordinary board, start the knight in the top left corner, a8, and follow the rule, breaking ties toward the square farthest from the centre. The knight finishes all 64 squares having tried exactly 64, without one retreat. Add up the step numbers along each row of that tour and the sums run from 186 to 330. A tour can be semi-magic, with every row and column adding to 260 while the diagonals do not. This one is not.

The rule is a rule of thumb, though, not a theorem. It can strand the knight, and on some boards it does so from particular squares. An honest program therefore keeps the complete search underneath, lets it take over when the rule fails, and admits it when a limit is reached before an answer is.

Eight queens and a very small tree

The queens puzzle is young by comparison. The chess composer Max Bezzel published it in 1848, and Franz Nauck published the first solutions in 1850 and widened the question to n queens on a board n squares wide. Carl Friedrich Gauss was among the mathematicians who worked on it. In 1874 Siegmund Gunther proposed attacking it with determinants.

The numbers explain the appeal. Eight queens can be set on 64 squares in 4,426,165,368 ways. Insist on one queen in each row and 16,777,216 remain. Insist as well on one per column and there are 40,320. Exactly 92 of them are solutions.

Even 92 overstates the variety. Turn the board a quarter turn or reflect it in a mirror and a solution becomes another solution. Counted up to those eight symmetries there are 12 fundamental solutions. Eleven of them yield eight variants each and one, which looks the same after a half turn, yields only four: 88 and 4 make 92.

Backtracking finds them all with almost no work. Fill the board row by row, testing each square against the queens already placed, and step back a row whenever no square is safe. In 1972 Edsger Dijkstra used exactly this problem to show what he called structured programming. The search for all 92 solutions tests only 15,720 squares. Its tree has 2,056 placements below the root, and it reaches the first solution after 113 placements and 105 retreats.

Why counting is harder than finding

Finding one arrangement for a large board needs no search whatever. For any board of side 4 or more, list the even row numbers, then the odd ones, adjust the list slightly when the side leaves a remainder of 2 or 3 on division by 6, and place the queens column by column. For eight queens the list reads 2, 4, 6, 8, 3, 1, 7, 5. The same staircase works for a thousand queens as readily as for eight.

Counting is another matter. There is no known formula for the number of solutions. The counts begin 1, 0, 0, 2, 10, 4, 40, 92, 352, 724 and are known exactly only as far as the board of side 27, which has 234,907,967,154,122,528 solutions. Each further size multiplies the count roughly tenfold at that scale, and a search that counts by finding must still pass through every solution.

So mathematicians estimate instead. For years the proven bounds on the count were far apart. In 2021 Michael Simkin showed that for large n the number of solutions is roughly (0.143n) raised to the power n, pinning the constant in the exponent to 1.942 give or take 0.003.

Related questions stay hard. Wrap the diagonals around the edges, as on a torus, and solutions exist only when n is divisible by neither 2 nor 3. Ask whether a board with some queens already placed can be completed, a question that also goes back to Nauck in 1850, and the general problem is NP-complete, the class for which no fast general method is known. Yet any placement of at most one sixtieth of n queens can always be completed.

None of this makes the puzzles useful in the way a sorting routine is useful. No real schedule is a chessboard, and a method tuned to knights or queens does not carry over unchanged. What does carry over is the habit they teach: describe the choices as a tree, test early, abandon a branch the moment it cannot succeed, and be exact about which claims are proved, which are counted and which are only the result of a search that ran out of time.