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

Hi Thorsten,

I used "diagonal" initialization: first queen on position 1, second on
position 2 and so on. After that I used queen swap as local moves, that way
the first of alldifferent constraints can be removed.

I don't want to do complex initialization that gives almost a valid
placement because N-Queens is not really NP-hard and you can construct
explicit solutions very fast (
http://en.wikipedia.org/wiki/N-queens#Explicit_solutions ). Doing complex
initialization is like partially constructing explicit solution, and this
doesn't help to learn how techniques and algorithms work in general.

Sergii.


On Fri, Jul 5, 2013 at 2:36 AM, Thorsten Winterer
<thorsten_winterer_at_web.de>wrote:

> 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
>
>
>
>
> ------------------------------------------------------------------------------
> This SF.net email is sponsored by Windows:
>
> Build for Windows Store.
>
> http://p.sf.net/sfu/windows-dev2dev
> _______________________________________________
> ECLiPSe-CLP-Users mailing list
> ECLiPSe-CLP-Users_at_lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users
>