Home > Archive > Prolog > September 2007 > Library CLP
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
|
|
| Trap D 2007-09-18, 7:15 pm |
| Hi everybody.
I tried to solve the problem SEND + MORE =3D MONEY using the SWI-PRLOG
library 'clp/bounds'
Here is my code :
:- use_module(library('clp/bounds')).
my_add(A, B, Carry, T, 0) :-
T is A + B + Carry,
T < 10, !.
my_add(A, B, Carry, T, 1) :-
T1 is A + B + Carry,
T is T1 - 10.
soluce1 :-
Vars1 =3D [S,E,N,D,O,R,Y],
Vars1 in 0..9,
M in 1..9,
all_different([M | Vars1]),
label(Vars1),
label([M]),
my_add(D, E, 0, Y, Carry),
my_add(N, R, Carry, E, Carry1),
my_add(E, O, Carry1, N, Carry2),
my_add(S, M, Carry2, O, Carry3),
M =3D Carry3,
format(' ~a~a~a~a~n', [S,E,N,D]),
format('+ ~a~a~a~a~n', [M,O,R,E]),
writeln('_______'),
format('=3D ~a~a~a~a~a~n', [M,O,N,E,Y]).
It works well but very slowly :
12 ?- time(soluce1).
9567
+ 1085
_______
=3D 10652
% 412,882,371 inferences, 73.30 CPU in 76.63 seconds (96% CPU, 5633015
Lips)
Yes
When I use this very simple code, it's faster :
soluce1:-
L =3D [0,1,2,3,4,5,6,7,8,9],
% premiere colonne
select(D, L, L1),
select(E, L1, L2),
select(Y, L2, L3),
my_add(D, E, 0, Y, Carry),
% Deuxi=E8me colonne
select(N, L3, L4),
select(R, L4, L5),
my_add(N, R, Carry, E, Carry1),
% troisi=E8me colonne
select(O, L5, L6),
my_add(E, O, Carry1, N, Carry2),
% quatri=E8me colonne
select(S, L6, L7),
select(M, L7, _), M \=3D 0,
my_add(S, M, Carry2, O, Carry3),
M =3D Carry3,
format(' ~a~a~a~a~n', [S,E,N,D]),
format('+ ~a~a~a~a~n', [M,O,R,E]),
writeln('_______'),
format('=3D ~a~a~a~a~a~n', [M,O,N,E,Y]).
11 ?- time(soluce2).
9567
+ 1085
_______
=3D 10652
% 29,506 inferences, 0.02 CPU in 0.02 seconds (98% CPU, 1888384 Lips)
Why is-it so different ?
Where did I make a fault ?
Thank you for your answers.
:
| |
| Markus Triska 2007-09-18, 7:15 pm |
| Trap D <joel.foutelet@free.fr> writes:
> :- use_module(library('clp/bounds')).
':- use_module(library(bounds)).' suffices.
> my_add(A, B, Carry, T, 0) :-
> T is A + B + Carry,
> T < 10, !.
Use constraints for this; for example:
my_add(A, B, Carry, T, 0) :-
T #= A + B + Carry,
T #< 10.
is/2 should not be necessary in your solution.
> It works well but very slowly :
You aren't using the solver to its full potential; first post ALL
constraints, THEN label the variables (otherwise, you are performing
generate and test, without propagation). No further checks should be
necessary after labeling has done its work. You will find that after
moving the label/1 goal towards the end of the predicate, the CLP(FD)
version is faster than your other version.
--
comp.lang.prolog FAQ: http://www.logic.at/prolog/faq/
| |
| Trap D 2007-09-18, 7:15 pm |
| On 18 sep, 19:51, Markus Triska <tri...@logic.at> wrote:
> Trap D <joel.foute...@free.fr> writes:
>
> ':- use_module(library(bounds)).' suffices.
>
>
> Use constraints for this; for example:
>
> my_add(A, B, Carry, T, 0) :-
> T #= A + B + Carry,
> T #< 10.
>
> is/2 should not be necessary in your solution.
>
>
> You aren't using the solver to its full potential; first post ALL
> constraints, THEN label the variables (otherwise, you are performing
> generate and test, without propagation). No further checks should be
> necessary after labeling has done its work. You will find that after
> moving the label/1 goal towards the end of the predicate, the CLP(FD)
> version is faster than your other version.
>
> --
> comp.lang.prolog FAQ:http://www.logic.at/prolog/faq/
I try what you said, but it doesn't work very well : it says very very
quickly that there is no solution !
I'll search to morrow.
Thank you.
| |
| Markus Triska 2007-09-19, 4:26 am |
| Trap D <joel.foutelet@free.fr> writes:
> I try what you said, but it doesn't work very well : it says very
> very quickly that there is no solution !
Remove the cut. By the way, the documentation of library(bounds)
contains exactly your example and models it in a better way: The model
in the documentation is deterministic; yours leaves choice-points that
the constraint solver doesn't "see" and can therefore not incorporate.
| |
| Trap D 2007-09-19, 8:06 am |
| On 19 sep, 07:26, Markus Triska <tri...@logic.at> wrote:
> Trap D <joel.foute...@free.fr> writes:
>
> Remove the cut. By the way, the documentation of library(bounds)
> contains exactly your example and models it in a better way: The model
> in the documentation is deterministic; yours leaves choice-points that
> the constraint solver doesn't "see" and can therefore not incorporate.
Thank you very much, it was exactly that. I remove the cut and it
works very well.
I'll read the solution in the documentation now, I didn't want to do
before my probleme was solved.
|
|
|
|
|