Mathematics on a chessboard

A chessboard is a small world of 8 × 8 squares. Yet place queens on it, or send a knight walking, and you meet problems that kept mathematicians busy for centuries.

Eight Queens (the site’s “Eight Queens”)

A queen moves any distance along a row, a column or a diagonal. Can you put eight queens on the 8 × 8 board so that none of them attacks another? The answer is 92 ways. If you count placements that match after turning or flipping the board as the same, there are 12. This site’s program checked both numbers by going through the board exhaustively.

If you change the size of the board, the number of solutions grows unevenly. Here are the counts this site’s program has checked.

Board side	Solutions
4	2
5	10
6	4
7	40
8	92
9	352
10	724

At side 6 there are only 4 solutions, fewer than at side 5. The count does not simply rise with the board.

Who posed it, and the Gauss story

The puzzle is said to have been posed in 1848 by Max Bezzel in a Berlin chess magazine. In 1850 Franz Nauck gave the 92 solutions and extended the problem to n queens, though he did not add a proof that the list was complete.

The mathematician Gauss also worked on it and discussed it in a letter to a friend. But Gauss neither posed the problem nor solved it completely. Books repeated this mistake many times, until a researcher named Campbell sorted it out in 1977. It is a good example of how a story that “a famous person solved it” can spread wrongly.

Around 1972, Dijkstra is said to have used the puzzle to explain the technique of backtracking carefully: try a path to the end, and step back if it fails. It is still a standard programming exercise.

Knight’s Tour (the site’s “Knight’s Tour”)

A knight jumps in an L shape. A path that visits every square exactly once is called a knight’s tour. This site’s program has been checked to build complete tours from a corner on 5 × 5, 6 × 6 and 8 × 8 boards.

An old pastime

Records of knight’s tours are old. A tour by a master of the Arabic chess of the 9th century is said to be preserved in a 14th-century manuscript. In India, the 9th-century poet Rudrata is said to have woven a half-board tour into a poetic form, so the tour was hiding inside a poem. Who was first cannot be said for sure, so these are simply some of the earliest recorded examples.

Euler is said to have discussed the problem in detail at the Berlin Academy in 1759, with publication in 1766. He studied it seriously as mathematics, but he did not discover it.

Warnsdorff’s rule

A rule of thumb, “move to the square with the fewest onward moves,” is said to have been written down in 1823 (Warnsdorff’s rule). It often builds a tour, but it does not always work, and on large boards it can fail. It is a handy habit, not a proven method. The helper numbers on the board give you what you need to use this rule.

How to count more than 13 trillion tours

On the 8 × 8 board, “closed” tours, which end one move away from where they started, number 13,267,364,410,532 when direction is not distinguished: more than 13 trillion. If you also tell clockwise from anticlockwise, the number is double, 26,534,728,821,064, as reported. The first published figure was wrong, and Brendan McKay gave the correct value in 1997.

The number depends on how you count, so a count of tours always needs its conditions: closed tours only? direction distinguished? By the way, a closed tour cannot exist on a board with an odd number of squares along both sides.

Can a tour be a magic square?

Number the squares in the order the knight visits them. Tours whose rows and columns all add up to the same total have been found, but no tour on the 8 × 8 board also has equal diagonals, which would make it a true magic square. An exhaustive computer search finished in 2003 and confirmed it. On larger boards, fully magic tours are reported to exist. A tour made in 1848 is said to be a “semi-magic” one, with equal row and column sums.

How to think about them

• Eight Queens: Place one queen per row and the search shrinks a lot. When a row has no safe square left, step back and change an earlier choice.
• Knight’s Tour: Corners and edges are easy to get stuck in, so visit them early.
• Both: When counting “how many ways,” first settle the conditions for counting.

In Eight Queens you can collect the 12 solutions that remain after turning and flipping are treated as the same. In Knight’s Tour, use the helper numbers shown on the board (how many unvisited squares you could go on to from each destination) as your clue.