2.8 Change for a dollar

This simple Prolog program checks or generates change adding up to a dollar consisting of half-dollars, quarters, dimes, nickels, and pennies.

 
change([H,Q,D,N,P]) :- 
    member(H,[0,1,2]),                      /* Half-dollars */ 
    member(Q,[0,1,2,3,4]),                  /* quarters     */ 
    member(D,[0,1,2,3,4,5,6,7,8,9,10]) ,    /* dimes        */ 
    member(N,[0,1,2,3,4,5,6,7,8,9,10,       /* nickels      */ 
               11,12,13,14,15,16,17,18,19,20]),  
    S is 50*H + 25*Q +10*D + 5*N, 
    S =< 100, 
    P is 100-S. 

Several kinds of goals are possible; for example

 
?- change([H,Q,D,N,P]). 
...

will list all possible ways of giving change for a dollar (try it!), and

?- change([0,2,3,4,6]). 
no 

since 2 quarters, 3 dimes, 4 nickels, and 6 pennies does not make a dollar, and

?- change([0,2,3,2,P]). 
P=10 

The most important feature of this example is to show how member can be used to generate choices for values of some variable in order to satisfy some constraint !!! Prolog's backtracking mechanism then automatically pursues each of the alternatives. This methodology will be applied in the next section, and in many subsequent examples in later sections.


Prolog Code for this section.
Prolog Tutorial Contents

Valid HTML 4.01 Transitional