Skip to content
Tutorials Center
My learning

Topics

Lesson 40 of 40 ยท Projects and Practice

Prolog Practice Problems with Solutions

Sharpen your Prolog with sixteen graded exercises on lists, arithmetic, recursion, search, DCGs and constraints. Try each problem first, then compare with the worked solutions and runnable checks.

Reading about Prolog is not the same as writing it. This final lesson gives you sixteen problems in four tiers, from one-clause list predicates to constraint puzzles. Work on each in your own Prolog (SWI-Prolog is ideal) before you look at the solutions. Prolog is not available on this site, so the solutions are shown read-only, and most of them are also run for you on the stand-in interpreter, a Python program that supports facts, rules, the cut, negation, findall/3, between/3 and DCG rules.

How to practice: write the clauses, then test with the empty case, a one-element case, a typical case and a failing case. Try the predicate "backwards" (with an unbound first argument) and see what happens. Ask whether each query terminates and leaves choice points.

The problems

Tier 1: lists and recursion

  1. last_element(List, X): X is the last element of a list.
  2. my_length(List, N): the length of a list, using an accumulator.
  3. no_dups(List, Set): remove duplicates, keeping the first occurrence.
  4. flat(Nested, Flat): flatten arbitrarily nested lists, so [a,[b,[c]],d] becomes [a,b,c,d].

Tier 2: arithmetic

  1. gcd(X, Y, G): greatest common divisor by Euclid's algorithm.
  2. collatz(N, Steps): the number of steps for N to reach 1 (halve if even, otherwise triple and add one).
  3. prime(N): test for a prime by trial division.
  4. ways(Amount, Coins, W): the number of ways to make Amount from a list of coin values.

Tier 3: search and structure

  1. perm(List, Perm): all permutations of a list.
  2. subseq(List, Sub): all subsequences (the power set).
  3. qsort(List, Sorted): quicksort.
  4. hanoi(N, From, To, Via): print the moves that solve the Towers of Hanoi.

Tier 4: grammars and constraints

  1. balanced//0: a DCG that accepts balanced parentheses.
  2. palindrome//0: a DCG for palindromes over the letters a and b.
  3. Magic square: place 1 to 9 in a 3 by 3 grid so every row, column and diagonal adds up to 15 (CLP(FD)).
  4. Map colouring: colour a small map with three colours so that neighbours differ (CLP(FD)).

Solutions: tier 1 and 2

PROLOG
last_element([X], X).
last_element([_|T], X) :- last_element(T, X).

my_length(L, N) :- my_length(L, 0, N).
my_length([], N, N).
my_length([_|T], A, N) :- A1 is A + 1, my_length(T, A1, N).

no_dups([], []).
no_dups([H|T], [H|R]) :- delete_all(H, T, T1), no_dups(T1, R).
delete_all(_, [], []).
delete_all(X, [X|T], R) :- delete_all(X, T, R).
delete_all(X, [H|T], [H|R]) :- X \= H, delete_all(X, T, R).

flat([], []) :- !.
flat([H|T], F) :- !, flat(H, FH), flat(T, FT), append(FH, FT, F).
flat(X, [X]).

gcd(X, 0, X).
gcd(X, Y, G) :- Y > 0, Z is X mod Y, gcd(Y, Z, G).

collatz(1, 0).
collatz(N, S) :-
    N > 1,
    (   N mod 2 =:= 0 -> M is N // 2 ; M is 3 * N + 1 ),
    collatz(M, S0),
    S is S0 + 1.

prime(N) :- N > 1, \+ has_factor(N, 2).
has_factor(N, F) :- F * F =< N, ( N mod F =:= 0 ; F1 is F + 1, has_factor(N, F1) ).

ways(0, _, 1).
ways(N, _, 0) :- N < 0.
ways(N, [], 0) :- N > 0.
ways(N, [C|Cs], W) :-
    N > 0, N1 is N - C,
    ways(N1, [C|Cs], W1),     % use coin C again
    ways(N, Cs, W2),          % never use C
    W is W1 + W2.

Notes: last_element/2 has two clauses with a clean first-argument split (a one-element list versus a longer one), so no cut is needed. no_dups/2 uses the guard X \= H instead of a cut, which keeps delete_all/3 logically clean when its arguments are ground. flat/2 needs cuts because its third clause matches anything, including lists; compare that with the cleaner is_list/1 guard in SWI-Prolog (flat(X, [X]) :- \+ is_list(X).). gcd/3 and collatz/2 use guards so that a failed arithmetic test, not a cut, selects the clause. ways/3 splits the solutions into those that use the first coin and those that never use it, which is the standard counting recursion; it takes exponential time for large amounts, which tabling would fix.

Python Tier 1 and 2 solutions, run (Python stand-in interpreter)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Solutions: tier 3

PROLOG
perm([], []).
perm(L, [H|T]) :- select(H, L, R), perm(R, T).

subseq([], []).
subseq([H|T], [H|S]) :- subseq(T, S).
subseq([_|T], S) :- subseq(T, S).

qsort([], []).
qsort([P|Xs], S) :-
    part(P, Xs, L, G),
    qsort(L, SL), qsort(G, SG),
    append(SL, [P|SG], S).

part(_, [], [], []).
part(P, [X|Xs], [X|L], G) :- X =< P, part(P, Xs, L, G).
part(P, [X|Xs], L, [X|G]) :- X > P,  part(P, Xs, L, G).

hanoi(0, _, _, _) :- !.
hanoi(N, From, To, Via) :-
    N1 is N - 1,
    hanoi(N1, From, Via, To),
    format("move ~w -> ~w~n", [From, To]),
    hanoi(N1, Via, To, From).

perm/2 picks any element with select/3 as the head, then permutes what remains. subseq/2 decides for each element whether it is in the subsequence (clause 2) or not (clause 3); with three elements it yields 8 answers. qsort/2 partitions around the first element; the two guards in part/4 are mutually exclusive, so no cuts are needed. hanoi/4 moves N-1 discs out of the way, moves the biggest, then moves the N-1 discs back on top: three lines that mirror the English description.

Python Tier 3 solutions, run (Python stand-in interpreter)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Solutions: tier 4

PROLOG
balanced --> [].
balanced --> ['('], balanced, [')'], balanced.

palindrome --> [].
palindrome --> [_].
palindrome --> [X], palindrome, [X].

balanced//0 says: a balanced string is empty, or an opening bracket, a balanced string, a closing bracket and another balanced string. palindrome//0 has the same shape: empty, a single letter, or the same letter on both ends around a palindrome. Check them with phrase(balanced, ['(', ')']) and phrase(palindrome, [a, b, a]). Used as generators, both enumerate their language.

Python DCG solutions, run (Python stand-in interpreter)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The constraint problems use CLP(FD) from the earlier lessons:

PROLOG
:- use_module(library(clpfd)).

magic([A,B,C,D,E,F,G,H,I]) :-
    Sq = [A,B,C,D,E,F,G,H,I],
    Sq ins 1..9,
    all_different(Sq),
    A + B + C #= 15,  D + E + F #= 15,  G + H + I #= 15,    % rows
    A + D + G #= 15,  B + E + H #= 15,  C + F + I #= 15,    % columns
    A + E + I #= 15,  C + E + G #= 15,                      % diagonals
    label(Sq).
PROLOG
?- magic(S).
S = [2, 7, 6, 9, 5, 1, 4, 3, 8] .

For map colouring, give each region a variable in 1..3 and add #\= between neighbours. For example, with regions WA, NT, SA, Q, NSW, V:

PROLOG
colour([WA, NT, SA, Q, NSW, V]) :-
    Cs = [WA, NT, SA, Q, NSW, V],
    Cs ins 1..3,
    WA #\= NT, WA #\= SA, NT #\= SA, NT #\= Q,
    SA #\= Q, SA #\= NSW, SA #\= V, Q #\= NSW, NSW #\= V,
    label(Cs).

The first query colour(Cs) gives Cs = [1, 2, 3, 1, 2, 1]. Changing the number of colours to 2 makes the query fail, because WA, NT and SA form a triangle.

Where to go next

  • Rewrite the tier 1 predicates so that they work in several directions, and test them with unbound arguments.
  • Add once/1-free determinism checks with :- det(Name/Arity). in SWI-Prolog 9.
  • Solve the problems in a second way: for example perm/2 with the built-in permutation/2, qsort/2 with msort/2, and prime/1 with a CLP(FD) formulation.
  • Take on the classic puzzles: Zebra puzzle, knights and knaves, cryptarithms, the eight queens without CLP(FD), and the farmer-wolf-goat-cabbage river crossing as a search problem.
  • Read other people's code: the SWI-Prolog library(lists) and library(apply) sources are short and excellent.
  • Build something real: a small expert system, a parser for a configuration format, a scheduler, a rule checker.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does gcd(X, Y, G) :- Y > 0, ... need the guard Y > 0?

    The guard makes the two clauses mutually exclusive, so there is no spurious second answer and no cut is needed.
  2. 2. How many answers does subseq([a, b, c], S) give?

    Each of the three elements is either in or out: 2 * 2 * 2 = 8 subsequences, including the empty one.
  3. 3. What does the DCG palindrome --> [X], palindrome, [X]. say?

    The shared variable X forces the first and last symbols to match.
  4. 4. In the colouring problem, why does using only 2 colours make the query fail?

    Three mutually adjacent regions form a triangle, which needs three colours.

Summary

  • Practice with the four-case test: empty, one element, typical, failing; then try the predicate backwards.
  • Guards in clause bodies (X \= H, N > 0) are cleaner than cuts for choosing between clauses.
  • Counting, permutations, subsequences, sorting and Hanoi are all one-paragraph recursions in Prolog.
  • DCGs describe languages directly, and constraints describe puzzles: state the rules, let the system search.

You have reached the end of the Prolog tutorial. Return to the track page to revisit any chapter.