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*N^{N} to C*N! |
N/A |
Novice Backtracking |
From 4 to 32 queens |
For N = 28: 14 sec |
100x faster at least |
Exponential |
Executable, Source |
Optimised Backtracking |
From 4 to 40 queens |
For N = 30: 9 sec |
20x faster at least |
Exponential |
Executable, Source |
Systematic & greedy search |
From 30 to 20.000 queens |
For N = 800: 9 sec |
1000x faster at least |
C*N^{3} to C*N^{2} |
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*N^{3} to C*N^{2} |
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*N^{2} |
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*N^{1.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*N^{1.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 |