Prolog : coin change

Question

I am new to prolog, trying to solve this classic coin change problem.

change(M,P,N,D) with formula that M>=0 and M = P+5*N+10*D here is my approach

change(M,P,N,D) :-
     M is P+5*N+10*D,
     P is M - (5*N+10*10).

couple of test-cases

  change(100,10,8,5).
  True
  change(X,10,8,5).
  X = 100.

However, if I try

 change(100,P,8,5).

it gives me "Arguments are not sufficiently instantiated" instead of P = 10. what is casuing this ?

edit : fix my code by using between predicate between(0,M,P),between(0,M,N),between(0,M,D),M is P+5*N+10*D.

possible duplicate of [Prolog Break Money into Smaller Amounts](http://stackoverflow.com/questions/29338495/prolog-break-money-into-smaller-amounts) — , Apr 01 '15 at 06:20
The reason why you get the error is that `is/2` evaluates an _arithmetic expression_: it is **not** a purely "logical" predicate. You already seem to know at least one way to solve this; see the duplicate question and the answer for a better way. — , Apr 01 '15 at 06:42

repeat · Accepted Answer · 2015-10-01T06:33:40.237

Use clpfd!

:- use_module(library(clpfd)).

All we need to express change/4 is one equation:

change(Money,Pennies,Nickels,Dimes) :-
   Money #= Pennies + Nickels*5 + Dimes*10.

Let's run the ground query given by the OP!

?- change(100,10,8,5).
true.

Next up, four queries having exactly one variable:

?- change(Money,10,8,5).
Money = 100.

?- change(100,Pennies,8,5).
Pennies = 10.

?- change(100,10,Nickels,5).
Nickels = 8.

?- change(100,10,8,Dimes).
Dimes = 5.

As we are using clpfd, we can also ask more general queries, like this one with three variables:

?- change(100,Pennies,Nickels,Dimes).
100 #= Pennies + 5*Nickels + 10*Dimes.

Note that this does not (yet) enumerate all possible combinations... to do so takes two steps:

State that "all counts are non-negative" by using ins/2:

?- [Pennies,Nickels,Dimes] ins 0..sup,
   change(100,Pennies,Nickels,Dimes).
100 #= Pennies + 5*Nickels + 10*Dimes,
Pennies in 0..100,
Nickels in 0..20,
Dimes   in 0..10.

Use the enumeration predicate labeling/2:

?- Zs = [Pennies,Nickels,Dimes],
   Zs ins 0..sup,
   change(100,Pennies,Nickels,Dimes),
   labeling([],Zs).
  Pennies = 0  , Nickels = 0, Dimes = 10
; Pennies = 0  , Nickels = 2, Dimes = 9
; Pennies = 0  , Nickels = 4, Dimes = 8
% the next 115 answers were omitted for the sake of brevity
; Pennies = 90 , Nickels = 2, Dimes = 0
; Pennies = 95 , Nickels = 1, Dimes = 0
; Pennies = 100, Nickels = 0, Dimes = 0
; false.

Prolog : coin change

1 Answers1