N-Queen Solver for OpenCL

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

  1. pcchen

    pcchen Moderator
    Moderator Veteran Subscriber

    Joined:
    Feb 6, 2002
    Messages:
    2,781
    Likes Received:
    166
    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

    Veteran Subscriber

    Joined:
    Jun 9, 2008
    Messages:
    1,805
    Likes Received:
    477
    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

    pcchen Moderator
    Moderator Veteran Subscriber

    Joined:
    Feb 6, 2002
    Messages:
    2,781
    Likes Received:
    166
    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
    Likes Received:
    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

    pcchen Moderator
    Moderator Veteran Subscriber

    Joined:
    Feb 6, 2002
    Messages:
    2,781
    Likes Received:
    166
    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
    Likes Received:
    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 Triskaine, Sep 12, 2011
    Last edited by a moderator: Sep 12, 2011
  7. OpenGL guy

    Veteran

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

Share This Page

  • About Us

    Beyond3D has been around for over a decade and prides itself on being the best place on the web for in-depth, technically-driven discussion and analysis of 3D graphics hardware. If you love pixels and transistors, you've come to the right place!

    Beyond3D is proudly published by GPU Tools Ltd.
Loading...