Re: CLP(FD)vJust Prolog

[Daniel Diaz]

Hello Carlos,

Constraint Programming is a powerful extension to Logic Programming. The 
basic idea is to use a constraint solver to solve a set of constraints. There 
are several constraint domains: reals, finite domains (FD), booleans, sets, 
lists,... GNU Prolog offers a FD solver. FD is well-suited to solve 
combinatorial problems, puzzles, scheduling problems,...

You are right when you tell that a same problem stated with constraints is 
much more efficient since the FD solver can avoid to try some trivial 
impossible values for variables.

E.G. in the crypto-arithmetic puzzle: SEND+MORE=MONEY since M is >= 1 (this 
is stated in the problem) a FD solver can immediately deduce that M=1 (since 
it is a carry resulting from S+M). On the other hand a naive pure-prolog 
version will try all possible values for M...

You can find more information on Constraint Programming at the Constraints 
Archive: http://www.cs.unh.edu/ccc/archive/
There are some interesting references in 'Publications'...


address@hidden said:
> Hi all,   Last week while doing just test examples of the things that
> struck me the most was that with a fairly complex combinatorial
> problem -a cryptarithmetic puzzle-. When coded without using FD it
> took 450 ms but when I used FD the thing went down to 10 ms.
> Unfortunately, I deleted the tests so I cannot confirm this (I
> remembered the figures because I thought wow..cool.what a
> difference!!).However, I was also playing with the order of the
> clauses and the cut predicate to improve efficiency ...and I could be
> mistaken.. Has anybody had any experience on this? or I am just
> talking rubbish.   Many thanks,


-- 
===============================================
                 Daniel Diaz
University of Paris 1      INRIA Rocquencourt
75013 Paris FRANCE      78153 Le Chesnay FRANCE
        web: http://pauillac.inria.fr/~diaz
        email: address@hidden
===============================================