Solving the N-Queens Problem
Finding a solution to the N-Queens problem for any N
greater than or equal to 4 can be done without searching.
Determining where each queen should go can be done in
constant time per queen, or O(N) altogether. Thus, drawing
the board (which is O(N^2)) is the rate limiting step.
This is demonstrated by the Java applet below, which lets you
select an N from 4 to 60.
The algorithm used here is taken from the ACM SIGART Bulletin,
2(2), page 7.
The original version of this page is at
http://www.apl.jhu.edu/~hall/java/NQueens.html. Source code for the
applet is at
http://www.apl.jhu.edu/~hall/java/NQueens.java.
Questions, Comments, More Info: