Re: [eclipse-clp-users] 7.11 puzzle

Hi,

just for completeness I would use #=</2 instead of #</2 for the symmetry 
breaking (although #</2 of course gives the same solution).

But for search/6, I think there are better choices than 'largest' and 
'indomain_split' available.

With  'largest' and 'indomain_split', I need 0.52 sec to find the 
solution on my machine instead of 67.81 sec.

With 'first_fail' and 'indomain_reverse_split', I need only 0.04 sec.


Cheers,
Thorsten


Am 13.09.2011 06:56, schrieb Hakan Kjellerstrand:
> 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