[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: CLP(FD)vJust Prolog

From: Daniel Diaz
Subject: Re: CLP(FD)vJust Prolog
Date: Wed, 23 May 2001 13:55:45 +0200

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 
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 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
        email: address@hidden

reply via email to

[Prev in Thread] Current Thread [Next in Thread]