[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
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
===============================================