# Re: [eclipse-clp-users] 7.11 puzzle

From: Hakan Kjellerstrand <hakank_at_...314...>
Date: Tue, 13 Sep 2011 06:56:53 +0200
```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
> 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/