### N-Queens

 home  Bib  Algorithms  Bioinfo  FP  Logic  MML  Prog.Lang and the  mmlist

Algorithms
glossary
Recursion
Linear
Binary
Permutations
Partition
N-Queens
N-Queens 3D
Necklaces
Self-Ref

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 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.
You will find some references in the [bibliography].
• Also solutions by [continuations] in SML, and a [circular program].

© L.A., Dept. Computer Sci., U.W.A., 1984-1986,
and (HTML) School of Computer Sci. & Software Engineering, Monash University, 1999.
 Coding Ockham's Razor, L. Allison, Springer A Practical Introduction to Denotational Semantics, L. Allison, CUP

 Linux  Ubuntu free op. sys. OpenOffice free office suite The GIMP ~ free photoshop Firefox web browser

 © L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated), Faculty of Information Technology (Clayton), Monash University, Australia 3800 (6/'05 was School of Computer Science and Software Engineering, Fac. Info. Tech., Monash University, was Department of Computer Science, Fac. Comp. & Info. Tech., '89 was Department of Computer Science, Fac. Sci., '68-'71 was Department of Information Science, Fac. Sci.) Created with "vi (Linux + Solaris)",  charset=iso-8859-1,  fetched Monday, 25-Oct-2021 11:15:29 AEDT.