One of the oldest chess based puzzles is known, affectionately, as The Eight Queens Problem.

Using a regular chess board, the challenge is to place eight queens on the board such that no queen is attacking any of the others. (For those not familiar with chess pieces, the queen is able to attack any square on the same row, any square on the same column, and also any square on either of the diagonals).

It’s a great little puzzle because it’s not too hard to solve manually, and it’s a fun programming exercise to write code to enumerate all the solutions. Using an 8 x 8 regular size chess board, the number of permutations to examine is small enough that, even an ugly algorithm can brute force out solutions in a sensible time.

Want to give it ago? Below is a small interactive application allowing you experiment.

It does not take much imagination to realize that only one queen can be placed on each row, and this massively reduces the solutions set to be searched. Similarly, there can be only one queen per column, and this reduces the solutions even further (trimming the problem, at this stage, to the analogous problem of placing eight rooks on a chess board, which is a much more manageable 8! = 40,320 combinations). All we need to do now is eliminate from this set all solutions where queens share a common diagonal.

A more efficient algorithm (which can be implemented recursively or not) is to start in the first column in the top left, then it then places a queen in the second column and moves it until it finds a place where it cannot be hit by the queen in the first column.

It then places a queen in the third column and moves it until it cannot be hit by either of the first two queens. Then it continues this process with the remaining columns. If there is no place for a queen in the current column the program goes back to the preceding column and moves the queen in that column. If the queen there is at the end of the column it removes that queen as well and goes to the preceding column. If the current column is the last column and a safe place has been found for the last queen, then a solution of the puzzle has been found. If the current column is the first column and its queen is being moved off the board then all possible configurations have been examined, all solutions have been found, and the algorithm terminates.

This basic algorithm can be improved by adoption of a greedy clause which selects the columns to switch that reduce the number of queens in jeopardy on the board (with the additional constraint of not moving the pairs of columns just moved last to stop oscillations between two states).

Other possible algorithms don’t just switch columns, but select a queen in jeopardy, and move the queen to the row position in that column minimizes the number of attacks it receives (or a random selection if there are more than one with the same score).

Using a technique called simulated annealing, the random switching algorithms can be enhanced. Here, most of the time, the switch which betters the problem is taken, but there is a random chance that the switch is made even if it does not. This helps the algorithm break out of optimizing its way to a local minimum and move towards a global minimum. The probability that a bad switch is made initially starts out high, and gradually reduces with each iteration. This probability is often referred to as the “temperature”, as a reference to the analogy of a liquid cooling down to form crystals.

It's very easy to expand (and contract) this puzzle to other sized chess boards.

To the right is a table of the number of solutions for different sized n x n boards.

For each size board I've shown the number of total solutions, and also the number of distinct types of solutions (unique before rotations and reflections).

Trivially, there is only one solution for a 1 x 1 board, and it's not hard to see that there are no possible solutions for a 2 x 2 or 3 x 3 sized board.

It's interesting that, whilst there are 10 solutions to a 5 x 5 board, the number of solutions drops to just 4 solutions on a 6 x 6 board.

There is (currently) no known formula for determining the number possible solutions for an n x n board, and an internet search reveals that the highest calculated board size to-date is 26 x 26.

Want more of a challenge? Consider writing code to solve the n x n Superqueens problem!

A Superqueen is the same as a regular queen, but is also able to attack like a knight.

There is a trivial solution for 1 x 1, but the first 'honest' superqueen solution occurs at board size 10 x 10. Are you going to create an algorithm that checks for knight collisions as you go along, or calculate the regular queen solutions and just filter those … ?