users-prolog
[Top][All Lists]

## 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...

Archive: http://www.cs.unh.edu/ccc/archive/
There are some interesting references in 'Publications'...

> 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