### N-Queens

 LA home Computing Algorithms  glossary  Recursion   Linear   Binary   Permutations   Partition   N-Queens   N-Queens 3D   Necklaces   Subgraphs   Brackets   Self-Ref   N-queens

The n-queens problem is a classic combinatorial problem. It is required to place n queens on an n×n chess board so that no two queens threaten each other. Therefore no two queens can be on the same row, column or diagonal. There must be a queen on each column and all their row numbers must differ so a solution can be represented as a permutation of the rows. (Not all permutations are solutions.)

 Q Q Q Q Q 1 3 5 2 4

 Q Q Q Q Q 2 5 3 1 4
N-Queens Examples (N=5).

Note that not every permutation is a solution. A permutation generator can be turned into an n-queens solver by adding tests to check diagonals.

```procedure Queens(unused, board, col, N)
if col > N then
print board
else{ col <= N }
for each row in unused do
var safe := true;
for c in 1..col-1 do             -- safety check of
if row = board[c]+col-c        -- diag...
or row = board[c]-col+c then   -- ...onals
safe := false; break
end if
end for;
if safe then
board[col] := row;
Queens(unused-{row}, board, col+1, N) <--recursion
end if
end for
end if
end Queens

-- Queens({1..n}, board, 1, n)   <---initial call --
```
 NB. Needs Netscape's JavaScript on!

This program has been modified in a simple way from the permutation generator. The identifiers have been changed to reflect chess terminology. It is assumed that a partial solution, board[1..col-1], is safe and an attempt is made to place a queen in column col. If this is impossible the routine returns. If it is possible and the new queen threatens no previous queen then the extended solution is safe and a recursive call is made to place the remaining queens. The process succeeds when all queens are placed. For all n greater than or equal to four there are solutions and in fact more than one solution for each value of n.

A search for solutions to a combinatorial problem carried out in this way is known as back-tracking. This comes from the way that partial solutions are extended, backing up at blind alleys where the constraints cannot be satisfied, until one or more complete solutions are found.

### Notes

• Although the n-queens problem might seem like just a toy puzzle, it is often used as an example of a Constraint Satisfaction problem because it is easy to state, and...
• ...it is related to Latin Squares and to Knut Vik Designs, which are definitely not toy problems, and have applications in statistics.
• There are variations on the n-queens problems, e.g.
• make the board wrap-around (be a torus),
• super-queens -- can move on generalised diagonals.
• Also see solutions by continuations [All88] and by circular programs [All89, All93].

### References

[All88] L. Allison, 'Some Applications of Continuations', Computer Journal, 31(1), pp.9-11, doi:10.1093/comjnl/31.1.9, February 1988.

All89] L. Allison, 'Circular Programs and Self-Referential Structures', Software Practice and Experience, 19(2), pp.99-109, doi:10.1002/spe.4380190202, February 1989.

[All93] L. Allison, 'Applications of Recursively Defined Data Structures', Australian Computer Jurnal, 25(1), pp.14-20, [arxiv:2206.12795, February 1993.