New multithreaded CPU benchmark: "Eight queens puzzle"

[BAGZZlash]

Today I accidentally stumbled over the "Eight queens puzzle". It's a game of placing n chess queens on an n×n chessboard so that no two queens threaten each other. Computationally, the challenge is to find the total number of solutions to that problem for differently sized (n) chessboards. The larger the board, the more solutions and the longer the computation time, of course. For n = 18, the number of solutions is 666,090,624. Solutions are known for n's of up to 26. For n >= 27, the number of solutions is yet unknown.

Back in 2011, takaken wrote a neat algorithm to compute the number of solutions based on multithreaded C code. I figured to turn this into a multithreaded CPU benchmark. The code computes the number of solutions for n = 18. This is because for n = 17, computation would be too fast on modern CPUs and for n = 19, users would have to wait for too long for the result.

Please download the attached file to obtain the binary package, including the source code.

I compiled the code for Windows using GCC: gcc -fopenmp Q.c -o Q.exe.

Usage is simple: Type Q [number of threads to use]. For example, run Q 8 for eight threads. If no number, a non-valid number or a number greater that the maximum hardware capability is provided, the program sets the maximum possible number of threads.

Have fun!

Spoiler: Here are some results on an Intel Core i7-4790 @ 3.6 GHz:

Using 1 thread(s).
Elapsed time (hh:mm:ss:cs): 21.01

Using 2 thread(s).
Elapsed time (hh:mm:ss:cs): 15.55

Using 3 thread(s).
Elapsed time (hh:mm:ss:cs): 10.38

Using 4 thread(s).
Elapsed time (hh:mm:ss:cs):  9.53

Using 5 thread(s).
Elapsed time (hh:mm:ss:cs):  9.23

Using 6 thread(s).
Elapsed time (hh:mm:ss:cs):  8.59

Using 7 thread(s).
Elapsed time (hh:mm:ss:cs):  8.27

Using 8 thread(s).
Elapsed time (hh:mm:ss:cs):  7.69

 

[Disparia]

i5-6600 stock with turbo on (between 3.6Ghz and 3.9Ghz)

Adding: FX-8120 Stock

Adding: A8-5500 Stock

 

[Solaris17]

This is cool.

 

[uuuaaaaaa]

AMD PII x6 1100T @ 3.8GHz /NB @ 2800MHz/ 4X4Gb 6 - 7 - 6 - 16 - 1T @1333MHz

Using 1 thread(s).
Elapsed time (hh:mm:ss:cs): 19.31

Using 2 thread(s).
Elapsed time (hh:mm:ss:cs): 14.08

Using 3 thread(s).
Elapsed time (hh:mm:ss:cs): 9.00

Using 4 thread(s).
Elapsed time (hh:mm:ss:cs): 8.54

Using 5 thread(s).
Elapsed time (hh:mm:ss:cs): 8.14

Using 6 thread(s).
Elapsed time (hh:mm:ss:cs): 6.83

 

[Vayra86]

This is fucking beautiful in all its simplicity.

 

[FordGT90Concept]

If it is not using a random seed, it's inefficient at finding a unique solution.

Core i7-6700K @ 4.0 GHz, 10 runs:

Using 8 thread(s).
Elapsed time (hh:mm:ss:cs): 7.07
Using 8 thread(s).
Elapsed time (hh:mm:ss:cs): 7.55
Using 8 thread(s).
Elapsed time (hh:mm:ss:cs): 7.13
Using 8 thread(s).
Elapsed time (hh:mm:ss:cs): 7.08
Using 8 thread(s).
Elapsed time (hh:mm:ss:cs): 7.13
Using 8 thread(s).
Elapsed time (hh:mm:ss:cs): 7.10
Using 8 thread(s).
Elapsed time (hh:mm:ss:cs): 7.15
Using 8 thread(s).
Elapsed time (hh:mm:ss:cs): 7.08
Using 8 thread(s).
Elapsed time (hh:mm:ss:cs): 7.12
Using 8 thread(s).
Elapsed time (hh:mm:ss:cs): 7.16

I wrote two similar programs (one stresses CPU, the other stresses RAM). Depending on the seed, it can find a solution in a fraction of a second or several minutes.

Chess.exe = Knight's Tour (CPU intensive, very fast)
NumberMazeWpf.exe = number maze (RAM intensive, extremely variable)

Be very, very, very careful with NumberMaze. If the grid is too big and sufficiently connected, it can eat all your memories....and your virtual memories too.

 

[the54thvoid]

i7 3930k @ 4.2 GHz

12 threads - 3.96
6 threads - 5.68

8 threads - 5.68
4 threads - 6.91

Somebody run a skylake at 4.2 GHz so I can see how much I need to upgrade

 

[FordGT90Concept]

Your 4 thread is faster than my 8 thread...

 

[Liquid Cool]

Jizzler...

I ran my AMD A10-5750m to compare to your A8-5550m...Wanna trade? . Kidding of course....but I actually liked my laptop better with the original A8-5550m. I recently "upgraded" to the A10. My laptop seems a little slower.....

Best,

Liquid Cool

 

[BAGZZlash]

If it is not using a random seed, it's inefficient at finding a unique solution.

It doesn't use anything random at all. Look at the source code, it uses deterministic backtracking.

Contributin':

Spoiler: Intel Core 2 Quad Q6600 @ Stock (2.4 GHz) - Wow, this is slow

Using 1 thread(s).
Elapsed time (hh:mm:ss:cs): 32.35

Using 2 thread(s).
Elapsed time (hh:mm:ss:cs): 27.29

Using 3 thread(s).
Elapsed time (hh:mm:ss:cs): 15.09

Using 4 thread(s).
Elapsed time (hh:mm:ss:cs): 14.20

Spoiler: Intel Core 2 Duo E6750 @ Stock (2.66 GHz)

Using 1 thread(s).
Elapsed time (hh:mm:ss:cs): 29.44

Using 2 thread(s).
Elapsed time (hh:mm:ss:cs): 21.69

 

[Dippyskoodlez]

 

[PHaS3]

3570K @ 4.5

 

[FordGT90Concept]

It doesn't use anything random at all. Look at the source code, it uses deterministic backtracking.

I edited since I said that. I'm half tempted to code Knight's Corner-like solution that involves a random seed. I suspect it can find a solution much, much faster but performance is at the mercy of the random seed. My methodology would simulate the board (like Knight's Corner and Number Maze) where it throws up one queen (random position), updating the board with viable positions for the next, so on and so forth until it solves or gets stuck. That doesn't work well as a benchmark though.

 

[Drone]

Asus X555LD ultrabook

 

[BAGZZlash]

I'm half tempted to code Knight's Corner-like solution that involves a random seed.

That would be great. The so-far known number of solutions for n = 26 has been computed back in 2009. Time to crack the n = 27!

That doesn't work well as a benchmark though.

Does not matter much. Do you have this nice piece of hardware?

 

[FordGT90Concept]

That would be great. The so-far known number of solutions for n = 26 has been computed back in 2009. Time to crack the n = 27!

That's the problem with the random approach. It finds a solution rather than all solutions.

 

[truth teller]

pentium 4 670

wut?

 

[uuuaaaaaa]

pentium 4 670

wut?

I have to try my 478 3.4EE Gallatin on this! hahaha

 

[Frick]

pentium 4 670

wut?

Yeah the results I see are all over the place, it's hard to tell anything.

 

[biffzinker]

Core i7-4790K @ 4.8 GHz/Uncore @ 4.5 GHz

 

[natr0n]

 

[uuuaaaaaa]

That vcore is it safe? My 1100T did 4.0Ghz at 1.42 on my CHIII formula...

 

[natr0n]

That vcore is it safe? My 1100T did 4.0Ghz at 1.42 on my CHIII formula...

It was really 1.5125 in bios. I just loaded last saved oc profile and it was a bit high while testing. I have a shitty board. Its safe tho for little tests i have heatsinks on vrms and fans and such

 

[ERazer]

i need to try this when i get home, sub

 

[broken pixel]

Program foes not work for me? Says its testing 12 threads then the window clothes after a few seconds. ;*(