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

From: Thorsten Winterer <thorsten_winterer_at_...126...>
Date: Fri, 05 Jul 2013 11:36:29 +0200
```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
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
```
Received on Fri Jul 05 2013 - 09:36:38 CEST

This archive was generated by hypermail 2.3.0 : Tue May 14 2019 - 03:13:24 CEST