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.

Answer 1

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:

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

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