On: Overkilling the 8-queens Problem

As an asm tutorial / case study, I found this neat. In terms of a conclusion, I found it potentially neat, but found myself wondering: cool, but how much of a win is all this special-cased effort, versus some kind of off-the-shelf constraint solver written in portable code? It'd be interesting to see a benchmark so we could have an idea if we're talking about a 50% win, orders of magnitude win, etc.

To get a rough baseline for what a generic solution could take, I took nqueens in Answer-Set Programming [1], set n=8, and ran it through clingo [2] on an Amazon micro instance, which gets me 15ms.

Another interesting question might be whether the two solutions have different scaling properties as n increases. The ASP solution scales like this (averaging a few runs and rounding):

   n   time
   8     15ms
  10     19
  15     50
  20    130
  25    290
  30    600
  35   1050ms [1.05s]

[1] http://www.hakank.org/answer_set_programming/nqueens.lp. This encoding can be optimized a bit as well, but is a decent starting point.

[2] http://potassco.sourceforge.net, a menagerie of logic-programming tools, written in C++. 'gringo' takes a high-level encoding and turns it into something more SAT-like, 'clasp' solves the SAT-like (variable-free) programs, and 'clingo' staples the two steps together into one binary. I used the version in Debian stable package 'gringo', which reports itself as "clingo 3.0.4 (clasp 1.3.10)"

N-queens, while quite a cute problem, is typically not that interesting as a constraint programming benchmark. The way to make it fast is to have a bit-set representation of the domains, which is not the best representation for many other important cases.

I tested the standard Gecode (http://www.gecode.org) implementation from version 4.2.1 without any special options on a MacBook Pro with a 2.6GHz Intel Core i7. Note that Gecode does not have bit-set representations for domains, so it is not optimized for this special case. Tests were run for 500 iterations and repeated 5 times to get deviations below 2.5%. I get the following timings for your sizes plus 50 and 100:

    n   time
    8     0.0368 ms
   10     0.0243 ms
   15     0.0221 ms
   20     0.1263 ms 
   25     0.2677 ms
   30     0.1621 ms 
   35     0.2433 ms 
   50     2.3234 ms 
  100     0.5509 ms

The timings are of course all strongly dependent on the heuristic used for finding the solution which is shown by the varying times above.

Constraint programming is typically also very dependent on the the pruning power of the constraints. Adding the option "-icl dom" which makes the pruning for the all-different constraints domain consistent, gives the following timings.

    n   time
    8     0.1138 ms
   10     0.0603 ms
   15     0.0879 ms
   20     0.2801 ms 
   25     0.6612 ms
   30     0.4657 ms 
   35     0.7553 ms  
   50     2.7687 ms 
  100     8.7687 ms

As can be seen, domain consistency did not actually help us in this case time-wise. The number of search-nodes visited range between 17 and 1066 for the normal consistency level, while the number of nodes visited for the domain consistent version range between 14 and 286. The reduction in search tree size was however offset by the increased complexity of the propagator.

As an update I saw that the original post was about finding all the solutions to the problem, compared to the single first solution searched for above. Running for finding all solutions, I got the following timings (same computer as above, same settings, default consistency).

    n   time           search tree  solutions
    8      0.8752 ms       767          92
   10     14.2759 ms     11431         724
   12    306.7616 ms    232163       14200
   14   8782.4620 ms   6391931      365596

Downloading the c-versions from https://github.com/davidad/8queens/tree/%2Bc_comparison gives a reference-time using the time built-in command of around 750 ms for 10k iterations. This means that the C solver takes around 0.075 ms per iteration which is a factor of ten faster than the Gecode version. That is not unreasonable given that the Gecode version is a high-level model in a general framework.

I did not manage to build the assembly-version unfortunately.

EDIT: Updated the timings and comments of the C-solver to represent that it actually solved the problem 10k times. Lesson, never do benchmarks quickly :-)

See [1]; it is about a factor of 7 win vs. a reasonable C implementation.

[1] https://github.com/davidad/8queens/tree/%2Bc_comparison

How do those numbers compare to the usual backtracking approach from the OP?I'm curious, specially with how the backtracking scales as N increases (this would be when all the heuristics from the sat solvers would really kick in)