Eight queens, Euler's knight's tour, the mutilated chessboard: the great mathematical puzzles of the chessboard

These puzzles are played with the pieces or the grid of the chessboard, but they have nothing to do with a game: they are genuine mathematical problems, accessible from secondary school, and some of them have occupied great names in the discipline. They are perfect for a maths club, a presentation or a topic for the grand oral (the French baccalauréat oral exam).

Summary table

The eight queens problem

Eight queens problem

Placing eight queens on an 8 × 8 chessboard so that none can capture another: never two queens on the same rank, the same file or the same diagonal.

The problem was published in 1848 by Max Bezzel, a chess problem composer. Franz Nauck published the first solutions in 1850 and generalised it to n queens on an n × n chessboard. Carl Friedrich Gauss is among the mathematicians who took an interest in it.

The aim of the problem: find one arrangement, then all of them. There are 92. Many can be deduced from one another by rotating or reflecting the chessboard; if they are grouped together, 12 fundamental solutions remain. Here is one, with the queens on d8, g7, c6, h5, b4, e3, a2 and f1:

It is easy to check that there is one queen on each rank and each file. For the diagonals, it is enough to check that, for any two queens, the gap between files is never equal to the gap between ranks.

How do you solve it?

The classic method is backtracking: place a queen in the first file, then a queen in the second file on an unattacked square, and so on; when no square is possible, go back and move the previous queen. It is a much-loved exercise in computer science lessons at sixth-form level. The n-queens version has solutions for every n except 2 and 3: for example 2 solutions for n = 4, 10 for n = 5, 4 for n = 6, 40 for n = 7.

Euler's knight's tour problem

Knight's tour problem

Finding a sequence of knight moves that visits each of the 64 squares once and only once. The tour is called closed if the last square is one knight's jump from the first, which makes it possible to start the loop again.

The problem is very old: a knight's tour on half a chessboard already appears in a ninth-century Sanskrit treatise on poetics, Rudrata's Kavyalankara. Leonhard Euler devoted a paper to it, “Solution d'une question curieuse qui ne paroit soumise à aucune analyse” (“Solution of a curious question that does not seem to be subject to any analysis”), presented in 1759 and published in 1766 in the memoirs of the Berlin Academy of Sciences. In 1823, H. C. von Warnsdorff proposed a simple rule for finding a tour: always go to the square from which the knight will have the fewest possible exits.

There is a gigantic number of closed tours on the ordinary chessboard: 26,534,728,821,064 counting the direction of travel, or half of that, 13,267,364,410,532, if a tour and its reverse are considered the same.

A tour to check on a 5 × 5 chessboard

For practice, you can start smaller. Here is an open tour that visits the 25 squares of a 5 × 5 chessboard: follow the numbers from 1 to 25; each number is one knight's jump from the previous one.

This tour was obtained with Warnsdorff's rule, and every jump has been checked. Challenge: find another that starts in the centre.

The knight's tour at the grand oral

The subject suits the oral exam of the French baccalauréat, in the mathematics or NSI (digital and computer science) specialisms: modelling with a graph (the squares are the vertices, the possible jumps are the edges), searching for a path through all the vertices, the backtracking algorithm, Warnsdorff's rule and its efficiency. You can also explain why no closed tour exists on a 5 × 5 chessboard: the knight changes colour at every jump, so a loop necessarily has an even number of squares, and 25 is odd.

The mutilated chessboard

The philosopher Max Black posed the problem in 1946 in his book Critical Thinking. Two opposite corners of a chessboard are removed (for example a1 and h8). Can the 62 remaining squares be covered with 31 dominoes, each domino covering two neighbouring squares?

Answer: no. Each domino necessarily covers one white square and one black square. 31 dominoes would therefore cover 31 white squares and 31 black squares. But the two opposite corners are the same colour: 32 squares of one colour remain and 30 of the other. The tiling is impossible, without needing to try a single arrangement. Martin Gardner brought this problem to the general public in 1957 in his Scientific American column.

And if you remove one white square and one black square? Ralph Gomory proved (a result published in 1973) that the tiling is then always possible, whichever two squares are removed.

Polyominoes and pentominoes

A polyomino is a shape made of identical squares joined along their sides; the domino has two, the pentomino five. The mathematician Solomon Golomb introduced and studied these shapes from 1953. There are 12 different pentominoes (counting a flipped or rotated piece as the same), which together cover 60 squares.

Now a chessboard has 64 squares, which is 60 + 4: so you can try to lay the 12 pentominoes on the chessboard leaving a 2 × 2 square free in the centre. In 1958, Dana Scott had a computer solve this problem, one of the first uses of the backtracking method: there are 65 solutions. Another famous challenge: the 6 × 10 rectangle can be tiled in 2,339 different ways with the 12 pentominoes.

How many squares on a chessboard?

The answer “64” is wrong, or rather incomplete: it counts only the small squares. You must also count the 2 × 2 squares, the 3 × 3 squares… up to the big 8 × 8 square.

The total is the sum of the squares of the integers from 1 to 8: 1 + 4 + 9 + … + 64 = 204. To go further: a chessboard contains 1,296 rectangles (squares included), because a rectangle is determined by choosing 2 lines out of the 9 lines of the grid and 2 columns out of 9, that is 36 × 36.

Where to next

These problems call on precise notions: parity, colouring, counting, graphs. We go through them, with exercises for primary and secondary school, on the page the notions involved on the chessboard. For other very large numbers, see Sissa's chessboard. And for those who like puzzles, the Palais des Échecs blog offers the Palais des Échecs logic challenges, renewed regularly.