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    
13524
  n=5
permutation of rows
 Q   
    Q
  Q  
Q    
   Q 
25314
  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


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 solutions by continuations and by circular programs.
© L.A.
www:

↑ © L. Allison, www.allisons.org/ll/   (or as otherwise indicated).
Created with "vi (Linux)",  charset=iso-8859-1,   fetched Saturday, 15-Dec-2018 16:34:40 EST.

Free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop, Firefox web-browser, FlashBlock flash on/off.