[eclipse-clp-users] Programming challenge (Re: constraint on indexed elements)

From: Joachim Schimpf <joachim.schimpf_at_infotech.monash.edu.au>
Date: Sun, 21 Mar 2010 23:57:51 +1100
I have set up a page on the web site to turn this into
a little programming competition:
http://eclipse-clp.org/examples/challenge.html
The deadline is in 3 weeks, lets see how good we can get!

Benoit's solution solves 12 of the 40 problem instances
within a minute, but times out for the others.  The largest
problem it solves has 15 boxes, so there is plenty of room
for improvement: different models, other constraints, other
solvers, heuristics, maybe there is even an efficient
algorithm for the problem?

Riyadh's solution looks correct, but is a generate-and-test
approach. This can only work for very small instances or
lucky data sets like the one he used.  A list of length N
has N! permutations, or 265252859812191058636308480000000 for
N=30, which is about the age of the universe in femtoseconds.
What a constraint programming solution does is to use the
constraints to cut the search space to a manageable size.

Good luck ;-)
Joachim
Received on Sun Mar 21 2010 - 12:58:01 CET

This archive was generated by hypermail 2.2.0 : Thu Feb 02 2012 - 02:31:58 CET