| Status: |
|
| Board: |
|
| Elapsed Time: |
|
*For best results, do NOT
have your browser check for a newer version of this page
with every visit. If you don't, it will check to see if each "queen" image has been updated,
causing the application to run slower. |
 |
The problem of the 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; |
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. |
|
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. |