N-Queens

N-Queens is an extension of the 8-Queens puzzle, both of which make use of trial-and-error methods and backtracking algorithms. Carl F. Gauss introduced the problem in 1850, but he was unable to completely solve it. The 8-Queens problem is stated as follows: Eight queens are to be placed on a chess board in such a way that no queen checks against any other queen. In other words, there can only be one queen per row, column, and diagonal.

 
Status: 
 
Board: 
 
Elapsed Time: 
 
 


I have chosen Niklaus Wirth's algorithm as the basis for my implementation. The data representation is as follows:
var x : array [1..n] of integer;
a : array [1..n] of boolean;
b : array [2..2n] of boolean;
c : array [1-n..n-1] of boolean;
where
  • x[i] denotes the position of the queen in the ith column;
  • a[j] means no queen lies in the jth row;
  • b[k] means no queen occupies the kth minor diagonal;
  • c[k] means no queen occupies the kth major diagonal.

The algorithm for placing queens on the chess board is contained in the JavaScript function tryConfig(i) in NQueens.js. The following pseudocode explains how it works: function tryConfig(i: integer) {
   for j <- 1 to n do {
      if safe then {
         select jth candidate;
         set queen;
         if i < n then
            tryConfig(i+1);
         else
            record solution;
         remove queen;
      }
   }
} For a more thorough analysis of the 8-Queens problem, please read Niklaus Wirth's Algorithms + Data Structures = Programs, Englewood Cliffs: Prentice Hall, Inc., 1976, pp. 143-7.
Note: This implementation uses a JavaScript object for the computation and DHTML for the user interface. It is not a Java applet and, therefore, may not work as intended on older browsers.