# Eight Queens

 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.

### Give it a go …

Click the board to place pieces.

#### Current queens

This applet was based on code originally written by Patricio Moline.

### Solutions

Did you find a solution? There are 92 solutions to the 8 x 8 problem. Many of these are reflections and rotations of some of the others, and if we de-duplicate against this, purists state that there are only 12 distinct solutions (92 does not divide equally by 12 because many of the reflections and rotations of a pure solutions are not unique).

Here are thumbnails for the 92 full solutions:

# Algorithms

There are many possible algorithms that can be used to find solutions to the eight queen’s problem, and a smaller subset of algorithms that can be used to enumerate all possible solutions.

The first possible mechanism is pure brute force; blindly trying the eight queens in every possible location. This is a really dumb idea, but would calculate all possible solutions (We’d have to examine 64!/56! = 178,462,987,637,760 possible placements, ouch!)

 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.

Here is an interesting page that provides code to solve in many dozens of programming languages.

If you’re only interested in one solution there are plenty of interesting iterative algorithms to select from. Many are not particularly efficient, but they are fun to code and experiment with. (I’ve even seen a genetic programming implementation, which reminded me of some code I wrote a few years ago to paint my picture).

A basic iterative algorithm starts by initially place the eight queens at random on the board subject to the constraint that there is only one queen on each row and column (see the rook comment above).

The simplest mechanism to find a solution from this starting condition is to randomly select two columns and swap them. This will eventually find a solution, but there is no measure of how long you might need to wait!

 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.

Go ahead, write some code to solve the eight queens problem. You'll have fun!

# Different size boards

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.

BoardTotal SolutionsUnique Solutions
1 x 1  1  1
2 x 2  0  0
3 x 3  0  0
4 x 4  2  1
5 x 5  10  2
6 x 6  4  1
7 x 7  40  6
8 x 8  92  12
9 x 9  352  46
10 x 10  724  92
11 x 11  2,680  341
12 x 12  14,200  1,787
13 x 13  73,712  9,233
14 x 14  365,596  45,752
15 x 15  2,279,184  285,053
16 x 16  14,772,512  1,846,955
17 x 17  95,815,104  11,977,939
18 x 18  666,090,624  83,263,591
19 x 19  4,968,057,848  621,012,754
20 x 20  39,029,188,884  4,878,666,808
21 x 21  314,666,222,712  39,333,324,973
22 x 22  2,691,008,701,644  336,376,244,042
23 x 23  24,233,937,684,440  3,029,242,658,210
24 x 24  227,514,171,973,736  28,439,272,956,934
25 x 25  2,207,893,435,808,350  275,986,683,743,434
26 x 26  22,317,699,616,364,000  2,789,712,466,510,280

Below is a historgram plot of the number of solutions based on board size.

Note the log-scale for the y-axis (each line representing a factor or 10x).

# Extra Credit

 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 … ?

Here's an example solution below:

Can you find the 44 11 x 11 solutions?