Algorithm Speed - Results

  • Overview

 
Here I present the results of my programs in a table executed on a core 2 duo 2.13GHz chip. Execution times may greatly vary on other machines (for example an Atom netbook is about 3 times slower). You can read about those algorithms here and also download the executables and source codes. 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.
 
 

  •  Analytical results

 

Type of algorithm

 Number of queens handled (larger N requires too much time)

Time needed for a number of queens

Times faster aproximatelly than the previus implementation

Algorithm time complexity for table size N, C : constant

 Download links

Brute force

 N/A but probably less than 12

N/A

N/A

C*NN to C*N!

N/A

Novice Backtracking

 From 4 to 32 queens

For N = 28: 14 sec

100x faster at least

Exponential 

ExecutableSource

Optimised Backtracking 

 From 4 to 40 queens

For N = 30: 9 sec

20x faster at least

Exponential 

ExecutableSource

Systematic & greedy search

 From 30 to 20.000 queens

For N = 800: 9 sec

1000x faster at least

C*N3 to C*N2

Executable, Source

Systematic & greedy search multithreaded version

From 100 to 30.000 queens

For N = 1000: 4 sec

Depends on the available CPUs, almost linear scaling

C*N3 to C*N2 

Executable, Source

Systematic Random permutations (see blue notes)

From 8 to 200.000 queens

 For N = 10.000: 12 sec

1000x faster at least

C*N2

Executable, Source

Systematic Random permutations optimised (see blue notes)

From 16 to 8.000.000 queens

For N = 200.000: 6 sec 

100x faster at least

C*N1.5 (estimate)

Executable, Source

 Smart random permutations

From 40 to 20.000.000 queens

For N = 800.000: 5 sec 

5x - 10x faster at least 

C*N1.2 (estimate) 

Executable, Source

PLANNED:Optimised Smart random permutations  

From 40 to 100.000.000 queens

?????????? 

 5x - 10x faster at least 

 C*N (estimate) 

 Executable, Source

 
This presented board is real. There are even faster algorithms (maybe even 10x times faster) from what I have heard so far but you wont find them very easily.
 

 
  • Notes:

  • Some of the algorithms time complexities are estimated rather than calculated.
  • 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 and programs have been developed by me and not "stolen" by other sites.
  • You can use them without permision as long as you mention this site.
  • The algorithm name "Systematic random permutations" means that all queens are systematically chosen to "exchange positions" with a random one.

Comments