Re: [eclipse-clp-users] 7.11 puzzle

Hi,

another improvement is adding explicit symmetry breaking:

    A #< B,
    B #< C,
    C #< D,

as well as using another labeling 

    search(Prices ,0,largest,indomain_split,complete,[]),

This solves the problem in 0.22 seconds instead of the original 
about 45 seconds on my machine.

In larger problems I would probably also have used the 
explicit domain declaration 

   Prices :: [1..711]

though in this case it doesn't improve times or the number of 
backtracks.

Here's the full model:

%%%%%%%%
   :- lib(ic).

   solve :-
       Sum = 711,
       Product = 711,
       Prices = [A, B, C, D],
       % A #> 0, B #> 0, C #> 0, D #> 0,
       Prices :: [1..711],
       A + B + C + D #= Sum,
       A * B * C * D #= Product * 1000000,

       A #< B,
       B #< C,
       C #< D,
       search(Prices ,0,largest,indomain_split,complete,[backtrack(Backtracks)]),

       % labeling(Prices),

       writeln(Prices),
       writeln(backtracks:Backtracks).

%%%%%%%%%


Best,

Hakan


On Tue, Sep 13, 2011 at 02:00:28AM +0200, Joachim Schimpf wrote:
> Sergey Dymchenko wrote:
> > Hi!
> > 
> > I'm trying to solve this puzzle: http://programmingpraxis.com/2009/11/27/7-11/
> > 
> > Here is my very straightforward code:
> > 
> > :- lib(ic).
> > solve :-
> >     Sum = 711,
> >     Product = 711,
> >     Prices = [A, B, C, D],
> >     A #> 0, B #> 0, C #> 0, D #> 0,
> >     A + B + C + D #= Sum,
> >     A * B * C * D #= Product * 1000000,
> >     labeling(Prices),
> >     writeln(Prices).
> > 
> > It works, but it's too slow.
> > Is there any way to speed it up without being too clever and
> > explicitly say to ECLiPSe that the prices of the four items must come
> > from the list of divisors of 711?
> 
> It is much faster (1.8 instead of 63 seconds on my machine) if you use
> domain splitting during search, i.e. replace labeling(Prices) with
> 
>     search(Prices, 0, input_order, indomain_split, complete, [])
> 
> This is probably always a good idea with relatively large domains
> and convex constraints.
> 
> Other improvements?
> 
> 
> Cheers,
> Joachim
> 
> ------------------------------------------------------------------------------
> BlackBerry&reg; DevCon Americas, Oct. 18-20, San Francisco, CA
> Learn about the latest advances in developing for the 
> BlackBerry&reg; mobile platform with sessions, labs & more.
> See new tools and technologies. Register for BlackBerry&reg; DevCon today!
> http://p.sf.net/sfu/rim-devcon-copy1 
> _______________________________________________
> ECLiPSe-CLP-Users mailing list
> ECLiPSe-CLP-Users_at_lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users

-- 
Hakan Kjellerstrand
http://www.hakank.org/index_eng.html
http://www.hakank.org/webblogg/
http://www.hakank.org/constraint_programming_blog/
http://www.hakank.org/arrays_in_flux/
http://twitter.com/hakankj