Re: [eclipse-clp-users] Symmetry breaking for N-Queens

Am 03.07.2013 08:55, schrieb Sergii Dymchenko:
> Also I've implemented simulated annealing using 'tentative' and 
> 'tentative_constraints' libraries pointed to by Joachim (I didn't 
> really look at 'repair' library because 'tentative' "is intended as a 
> successor for library(repair)."). After some tweaking N = 4000 took 
> 1m15s on my laptop, and N = 33000 took about 2.5 hours (which is 
> acceptable) with very little memory consumption.
>
> I reimplemented the same simulated annealing algorithm in C++ from 
> scratch and got about 8 seconds for N = 4000 and about 12 minutes for 
> N = 33000.


It often helps a lot if you can initialize the variables in a way that 
gives your local search algorithm a head start. (though sometimes you 
may find yourself in a local optimum straight away)

I tweaked Joachim's code a bit, changing the initialization such that 
the first queen is on position 1, the second on 3 etc. This gives an 
almost valid placement:

         % initialize
         N2 is integer(round(N/2)),
         (
             foreacharg(X, Board), count(I, 1, _), param(N2)
         do
             ( I =< N2 -> V is (I*2 - 1) ; V is (I - N2)*2 ),
             X tent_set V
         ),


I also changed the code so that the neighbourhood size increases when no 
improving move was found in the last iteration. If the neighbourhood 
becomes too large, a random move is made.

         (
             fromto(V0,V1,V2,0),
             fromto(-1,LD,D,_),
             fromto(SampleSize,LS,S,_),
             param(Vars,N,N0,SampleSize,Violations)
         do
             vs_random_worst(Vars, X),    % get a most violated variable
             (
                 (
                     LD < 0,       % if last move was improvement
                     S = SampleSize
                 ;
                     S0 is LS*10,  % or larger neighbourhood
                     S0 =< N0,     % is not too large
                     S = S0
                  )
             ->
                 % then find a best neighbour
                 tent_minimize_random(   (
random_sample(1..N,S,I),
                                             X tent_set I
                                         ),
                                         Violations,
                                         I
                                     )
             ;
                 % else make some random move
                 random(R),
                 I is (R mod N) + 1,
                 S = SampleSize
             ),
             X tent_set I,
             Violations tent_get V2,
             D is V2-V1
         ).


Here are the times for a couple of runs on my laptop:

?- queens(30000, B).
B = [](1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, ...
Yes (0.49s cpu)
?- queens(30000, B).
B = [](15306, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, ...
Yes (4.31s cpu)
?- queens(30000, B).
B = [](1, 3, 5, 7, 9, 11, 13, 15, 17, 15351, 21, 23, ...
Yes (3.29s cpu)
?- queens(30000, B).
B = [](1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, ...
Yes (6.64s cpu)


With a random initialization, the runtime was about 1.5 hours.

Cheers,
Thorsten