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.)
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
References
© L.A.
|
|
↑ © L. Allison, www.allisons.org/ll/ (or as otherwise indicated). Created with "vi (Linux)", charset=iso-8859-1, fetched Friday, 19-Apr-2024 21:45:00 UTC. Free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop, Firefox web-browser, FlashBlock flash on/off. |