# N-Queen Solver for OpenCL

Discussion in 'GPGPU Technology & Programming' started by pcchen, Jan 10, 2010.

1. ### pcchen Moderator ModeratorVeteranSubscriber

Joined:
Feb 6, 2002
Messages:
2,888
374
Location:
Taiwan
nolocal is faster? Maybe the L1 cache of Cayman is very good
It looks like that I need to get hold of one of these beasts... I am still stuck with that 5850, unfortunately.

2. ### Lightman VeteranSubscriber

Joined:
Jun 9, 2008
Messages:
1,918
859
Location:
Torquay, UK
Tested again to verify and the result is bugged. Gives different amounts of solutions each time I run it.

Vec2 score is OK though - 95815104 solutions

3. ### pcchen Moderator ModeratorVeteranSubscriber

Joined:
Feb 6, 2002
Messages:
2,888
374
Location:
Taiwan
Ok. I think maybe a solution check should be in place now to avoid confusion. I'll add it later when I have some time

4. ### prunedtree Newcomer

Joined:
Aug 8, 2009
Messages:
27
0
One might wonder if there's some way to solve this problem approximately (and thus much faster).

I found one interesting paper on the topic: `Counting Solutions for the N-queens and Latin Square Problems by Efficient Monte Carlo Simulations' by Zhang and Ma.

While the paper is quite cryptic on the details, it turns out the basic idea is pretty simple (consider the problem as a thermodynamic simulation).

I implemented something similar, using the Wang-Landau algorithm to compute the density of states of the boards (define energy by the number of conflicts). The result is then found by looking at the zero-energy state. This method is essentially a markov chain monte carlo algorithm, and thus variance depends on the amount of sampling.

Here's one run of this implementation:
(the same parameters are used for all n, set to achieve ~5% relative error)

Code:
```[   0] Q_1  ~        1.0
[   1] Q_2  ~        0.0
[   1] Q_3  ~        0.0
[   2] Q_4  ~        2.0
[   2] Q_5  ~       10.1
[   4] Q_6  ~        4.0
[   8] Q_7  ~       41.0
[   9] Q_8  ~       91.1
[  14] Q_9  ~      358.9
[  85] Q_10 ~      707.4
[  40] Q_11 ~     2746.0
[  76] Q_12 ~    14239.4
[  43] Q_13 ~    74638.6
[ 187] Q_14 ~   365537.6
[ 458] Q_15 ~ 2.284e+006
[ 248] Q_16 ~ 1.471e+007
[ 165] Q_17 ~ 9.684e+007
[ 285] Q_18 ~ 6.571e+008
[ 236] Q_19 ~ 4.908e+009
[ 971] Q_20 ~ 3.897e+010
[ 421] Q_21 ~ 3.034e+011
[1736] Q_22 ~ 2.675e+012
[2389] Q_23 ~ 2.412e+013
[2322] Q_24 ~ 2.253e+014
[4633] Q_25 ~ 2.212e+015
[2173] Q_26 ~ 2.194e+016
[ 974] Q_27 ~ 2.394e+017
[3863] Q_28 ~ 2.521e+018
[1730] Q_29 ~ 2.935e+019
[7324] Q_30 ~ 3.390e+020
[3289] Q_31 ~ 4.033e+021
[5312] Q_32 ~ 4.985e+022
[8782] Q_33 ~ 6.530e+023```
The first number between brackets is the number of sweeps (in millions) to convergence. The pace is about 10 million sweeps per second. To compare, here is a list of the known values: http://oeis.org/A000170/list

Obviously it's quite inefficient for small sizes (it takes about 16 seconds to get an approximate answer for N=17, and the solver presented in this thread can find the exact result significantly faster). However it scales extremely well for higher dimensions, as long as one is satisfied with approximate solutions.

Can current GPUs run this `more clever' approach as efficiently as they can do the bruteforce search ? Given that most of the work is essentially sampling (the monte carlo method is a form of `brute force' approach as well, after all), it might not be that bad.

5. ### pcchen Moderator ModeratorVeteranSubscriber

Joined:
Feb 6, 2002
Messages:
2,888
374
Location:
Taiwan
This is interesting. I think GPU is good for doing Monte Carlo style random algorithms, but a good source for random numbers may take some effort to do efficiently.

6. ### Triskaine Newcomer

Joined:
Mar 28, 2010
Messages:
59
57
[strike] Why are you using such an old version of the SDK? The most up to date one is 2.4 . [/strike]

God that was stupid of me.

#146
Last edited by a moderator: Sep 12, 2011
7. ### OpenGL guy Veteran

Joined:
Feb 6, 2002
Messages:
2,357
28
That was a bot. Notice how they took the text from pcchen's original posting.

Similar Threads - Queen Solver OpenCL

Replies:
43
Views:
3,937

Replies:
119
Views:
834

Replies:
12
Views:
5,695
4. ### Dragon Quest Swords: The Masked Queen - Wii Launch title!

Titanio, in forum: Console Gaming
Replies:
4
Views:
1,121

Replies:
4
Views:
166

Replies:
25
Views:
2,154