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
n=5
permutation of rows
Q
Q
Q
Q
Q
2
5
3
1
4
n=5
permutation of rows
N-Queens Examples.
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 dovar 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 ifend for;
if safe then
board[col] := row;
Queens(unused-{row}, board, col+1, N) <--recursionend ifend forend ifend Queens
Queens({1..n}, board, 1, n) <---initial call
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.
You will find some references in the
[bibliography].