#### 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.

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; |

*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.