Suppose you need to make change for $26$ cents using standard United States coins:
Quarters: $25$¢
Dimes: $10$¢
Nickels: $5$¢
Pennies: $1$¢
In how many different ways can you do it?
In standard procedural programming languages (like Lua, Python, or Java), finding all combinations requires writing complex nested loops, recursion trees, or dynamic programming lookup tables.
In Prolog, we solve this using generate-and-test with automatic backtracking:
Base Case: Making change for $0$ cents requires an empty list of coins: [].
Recursive Step: Pick a coin $C \le \text{Amount}$. Deduct $C$ from the amount: $\text{Remaining} = \text{Amount} - C$. Then recursively find change for the remainder!
When Prolog finds a valid combination, you can ask for the next solution; Prolog will automatically backtrack, undo its previous choices, and explore alternative coin selections!
coin(25). coin(10). coin(5). coin(1). change(0, []). change(Amount, [C | Rest]) :- coin(C), Amount >= C, % Remaining balance after choosing coin C: Replace ???? with C
Rem is Amount - ???? , change(Rem, Rest). goal: change(26, Coins).
Move the mouse over a dotted box for more information.
Preventing Duplicate Permutations: To avoid counting $[10, 5, 1]$ and $[5, 10, 1]$ as distinct solutions, we enforce that coins must be picked in descending order ($C \le \text{MaxCoin}$).
Combinatorics: The number of ways to make change for $N$ is connected to the mathematical theory of Integer Partitions studied by Euler and Ramanujan!
Now you try. Change the goal to make_change(15, Coins). and hit Run.
Type your code here:
See your results here:
The code has ???? for subtracting the chosen coin. Replace ???? with C, then click Run to find the coin combinations!
Coins = [25, 1] (one quarter and one penny).
Other combinations that make 26 cents include:
$[10, 10, 5, 1]$ (two dimes, one nickel, one penny)