A multitude of queens

Here’s a challenge which appeared in a German chess magazine in 1848: place eight white queens on an empty chessboard so that no two queens occupy the same file, rank or diagonal. In other words, none of the queens may defend each other.

Perhaps you start with a queen in the top left corner, on a8. The next might be placed on the adjacent file, nearby but not touching, on the b6 square, a knight’s move away from the first. Following the pattern, you put another on c4, and a fourth one on d2. For the e-file, we need to break the pattern, so let’s revert to near the top of the board, on e7. Flushed with success, you see that the ‘knight move’ pattern still works, and plonk two more queens on f5 and g3. Giddily, you add the last queen on h1, the only unused file and rank, and — bloody hell! — it conflicts with the first queen you placed on a8. This is, as Sherlock Holmes might say, a three-pipe problem.

The 8-queens problem: a failed attempt (Diagram above left)

It turns out that there are 92 different solutions, though only 12 of these are fundamentally distinct, once you take into account reflections and rotations. You might wonder how many solutions there are on boards of different sizes — 10×10, or 100×100. In fact, this ‘n queens’ problem (where n denotes a board of arbitrary size) has turned out to be a rich seam for mathematicians. Last year Michael Simkin, a Harvard academic, identified a formula which approximates the number of solutions on giant boards. He found that when n becomes large enough, there are roughly (0.143n)ⁿ solutions, which on a 1 million by 1 million board equates to 1 followed by more than 5 million zeros.