The N Queens problem: Main Page

 
In this site I will attempt to explain algorithms and the methods that I have implemented so far in C programming language, in order to solve the N-Queens problem. I also host the source code and the executables for some algorithms. If you are not familiar with the N-Queens problem I suggest reading about it in wikipedia.
 
 
 
  •  The N-Queens problem briefly explained:

 
In a few words the N-Queens problem (often refered as the N Queens puzzle) is to place on a NxN chesboard N queens so as none of them is able to capture another using the chess standard moves. It was derived from the old 8 queens puzzle (N = 8) on a standard chessboard. The problem may sound simple but requires a significant amount of effort to be solved. It was itroduced over 100 years ago and many distinguished mathematicians and programers came up with great solutions. This problem is often used as an exercise for students taking a cource in programming.
 
 
 
  • Algorithms:

The algorithms explained in this site can be found here. They are listed according to their speed and effectiveness. You can find the results of my programs and their speed, executed on a intel core 2 duo 2.13 GHz chip here.
Also I have to mention that there are heuristic methods / algorithms capable of solving the N Queens problem in a fraction of the time that the methods mentioned here require. While this is true they often produce a limited set of solutions or even just one. So they are a different approach to the problem.
 
 
  
  • Download:

 
Files available for download from this site are in the download section. You will find there executables and source codes in C. You may distribute them in any way you like but remember to mention this site.
 
 
 
  • Tools used to develop my applications:

 
I used the Dev C++ development environment to create my programs and the gcc compiler. Dev C++ is completely free and a very effective tool. Visual C++ Express Edition was not used because the executables compiled by it were somewhat slower. I am planning to use Ati Stream SDK 2 to run the N queens problem on a GPU using Opencl.
 
 
 
  • Relevant sites:

 
There are other sites similar to this one like Jeff Somers's N Queen solutions. Jeff Somer is the developer of one of the best algorithms for finding all the solutions on a chessboard. Another site is Takaken's N Queens problem. Takaken's algorithm may be slower than Jeff Somers's but is excellent for it's simplicity. Also you may find useful this implementation of the N Queens problem which has graphics.
 
 
 
  • Thougts and goals about the N Queens problem:

 
The N Queens problem is not very important in and of itself. But the methods used for its solution are usefull in other areas and can be very helpfull when learning about programming and algorithms. With the recent progress in GPGPU I am looking forward to develope parallel versions of my programs using Opencl, which should be several times faster than my previous implementations. Also all the modern cpus have multiple cores so the development of multithreaded programs is greatly encouraged. I am expecting at least a 32x speed up from my current faster implementation. You can read about my goals here. Now with the massive capabillities of a hi-end modern pc each person has the computing power of a supercomputer of the 90s.One may wonder: are there any limits?
 
 
 
  • Contact & Posting Comments:

 
You can contact me via e-mail. My e-mail adress is: fodgianm@gmail.com. Feel free to make any suggestions or criticize my page. You can post your comments on this website on the Comment section.
 
 
  • Notes:

 
  • I am not fully aware of the algorithms terminology so some algorithm names may sound strange or be wrong.
  • Also note that all the presented source codes have been developed by me and not "stolen" by other sites.
  • You can use them without permision as long as you mention this site.
  • I am not a professional programmer so except to find some minor "flaws" in the algorithms and the programs.
  • Also excuse me for any grammatical or syntactic mistakes as English is not my first language.