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

From: Helmut Simonis <h.simonis_at_...70...>
Date: Sun, 30 Jun 2013 00:04:51 +0100
For large n-queens problems, a repair based method typically works very
well. I seem to recall a library in ECLiPSe for this.



> Hi,
> In the online course I have an
> assignment to solve N-Queens problem of the size as large as possible.
> For now the max size I've solved is N=4000. To get maximum grade for the
> problem N ~ 30000 is needed.
> The best result I've got so far is with gfd library, alldifferent
> constraints, most_constrained, indomain_median and credit search, without
> any symmetry breaking. Memory, not the processor speed, is the problem in
> this case - for N=5000 is eats all my 4GB + 6GB swap very fast. The model
> is an integer for every column.
> I tried different libraries for symmetry breaking: ldsb with ic and gfd (I
> had to change ldsb library slightly to make it work with gfd), sbds with
> ic
> and gfd (from the very recent 6.1 #161 release) and ic_gap_sbds and
> ic_gap_sbdd. Every library has settings for N-Queens in its documentation,
> so I used those.
> I haven't had any success with any of the symmetry breaking libraries.
> Using any of them seems to worsen speed or memory consumption greatly. Are
> there any results that symmetry breaking works for N-Queens in practice?
> Middle first rearrangement also works pretty bad compared to
> most_constrained.
> Any suggestions how to get better results than N=4000 with ECLiPSe (no
> code
> or pseudo-code please, because that would violate the course collaboration
> policy)?
> Sergii.
> ------------------------------------------------------------------------------
> This email is sponsored by Windows:
> Build for Windows Store.
> ECLiPSe-CLP-Users mailing list

Helmut Simonis
4C, University College Cork
Tel: +353 21 420 5967
Received on Sat Jun 29 2013 - 23:20:20 CEST

This archive was generated by hypermail 2.2.0 : Mon Jul 09 2018 - 02:05:30 CEST