Re: [eclipse-clp-users] 7.11 puzzle

From: Marco Gavanelli <marco.gavanelli_at_unife.it>
Date: Tue, 13 Sep 2011 11:15:22 +0200
Hi all,

well, now there is no need to improve further, however another lesson in 
CP is try to use the available global constraints. ECLiPSe has the 
interesting ordered_sum constraint, so one can join the symmetry 
breaking with the sum constraint.

I checked this model with the old labeling (as with the smart search 
suggested by Thorsten I could not even measure the computing time), and 
it went from 9.22 seconds to 2.78 on my machine.

Cheers,
Marco

On 13/09/11 08:42, Thorsten Winterer wrote:
> 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
>
>
> ------------------------------------------------------------------------------
> 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
>
>


-- 
Marco Gavanelli, Ph.D. in Computer Science
Dept of Engineering
University of Ferrara
Tel/Fax  +39-0532-97-4833
http://www.ing.unife.it/docenti/MarcoGavanelli/
Received on Tue Sep 13 2011 - 09:45:28 CEST

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