The N Queens Problem
Library Home 
Full Table of Contents 
Library Help
http://www.apl.jhu.edu/~hall/java/NQueens.html  


Marty Hall  
Finding a solution to the NQueens 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.  


Levels:  College 
Languages:  English 
Resource Types:  Problems/Puzzles, Web Interactive/Java 
Math Topics:  Combinatorics 
[Privacy Policy] [Terms of Use]
© 1994 The Math Forum at NCTM. All rights reserved.
http://mathforum.org/