The N Queens Problem
Library Home || Full Table of Contents || Suggest a Link || Library Help
|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 a Java applet that lets you select an N from 4 to 60, using an algorithm from the ACM SIGART Bulletin.|
|Resource Types:||Problems/Puzzles, Web Interactive/Java|
© 1994- The Math Forum at NCTM. All rights reserved.