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

From: Joachim Schimpf <jschimpf_at_coninfer.com>
Date: Tue, 02 Jul 2013 07:18:46 -0700
On 29/06/2013 16:04, Helmut Simonis wrote:
> For large n-queens problems, a repair based method typically works very
> well. I seem to recall a library in ECLiPSe for this.
>
> Regards
>
> Helmut
>
>> Hi,
>>
>> In the online course https://class.coursera.org/optimization-001 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.

You can find Local Search based code for queens in the example for library(tentative):
http://www.eclipseclp.org/doc/bips/lib/tentative_constraints/index.html

This works well for a few thousand queens, and 10000 take a few minutes
to solve, without any memory problems.  To do 30000 in a reasonable time,
it may need some work on the (rather naive) heuristic.  Let us know if
you manage to improve it!

Cheers,
Joachim
Received on Tue Jul 02 2013 - 14:19:03 CEST

This archive was generated by hypermail 2.2.0 : Wed Jul 03 2013 - 18:13:15 CEST