How to Read This

This guide is a progressive tutorial. Every section uses only concepts you've already seen. Don't skip ahead — the order matters. By the end, you'll be able to write anything the exam can throw at you.

1. Facts & Queries — Your First 5 Minutes

In C++ you write instructions. In Prolog, you state what is true, and Prolog figures out the rest. That's the entire paradigm shift.

Facts — things that are true

A fact is just a name followed by some values in parentheses, ending with a period. Think of it as a row in a database table.

parent(tom, bob).       % "tom is a parent of bob" — that's it, done
parent(bob, ann).
parent(bob, pat).
likes(mary, food).
likes(mary, wine).

You can also use facts as a lookup table — this is extremely common:

% A fact for each digit → word mapping
means(0, zero).
means(1, one).
means(2, two).
means(3, three).
% ... and so on up to 9

Queries — asking Prolog questions

At the ?- prompt, you ask questions. Prolog searches through all facts to find an answer.

?- parent(tom, bob).
true.                       % "Yes, that's a fact I know"

?- parent(tom, ann).
false.                      % "I don't have that fact"

Variables — "find me a value that works"

Anything starting with an uppercase letter is a variable. When you put a variable in a query, Prolog finds values that make it true.

?- parent(tom, Who).
Who = bob.                  % Prolog found: parent(tom, bob) matches!

?- parent(bob, Child).
Child = ann ;               % First answer. Press ; for more...
Child = pat.               % Second answer. No more.

?- means(3, What).
What = three.              % Looked up 3 in our "table"

The ; means "show me another answer." Press . or Enter to stop asking.

Unification — how Prolog answers questions

When you ask ?- means(3, What)., Prolog goes through its facts one by one:

This "match and bind" process is called unification. That's the engine that powers everything in Prolog.

2. Rules — Teaching Prolog to Reason

Facts are what Prolog knows. Rules tell it how to figure things out from what it knows.

% "X is a grandparent of Z  IF  X is a parent of Y  AND  Y is a parent of Z"
grandparent(X, Z) :- parent(X, Y), parent(Y, Z).

Read :- as "if" and , as "and". The left side is the head (what we're defining). The right side is the body (the conditions).

?- grandparent(tom, Who).
Who = ann ;
Who = pat.

Your first recursive rule: translate

Let's combine a rule with the means/2 lookup table from section 1. We want to translate a list of digits into words: [3,5,1] → [three,five,one].

Don't worry about list syntax yet (that's section 4). Just see the pattern:

% Base case: empty list translates to empty list
translate([], []).

% Recursive case: translate the first element, then do the rest
translate([Num | RestNums], [Word | RestWords]) :-
    means(Num, Word),                  % look up Num in our fact table
    translate(RestNums, RestWords).     % translate the rest the same way

Two things to notice: (1) means(Num, Word) in the body is a query against our facts — Prolog unifies Num with a digit and Word with the corresponding word. (2) The rule calls itself. That's recursion. We'll formalize this pattern properly in section 5.

3. Arithmetic & The "is" Trap (EXAM GOTCHA #1)

Prolog does NOT evaluate math automatically. 3 + 2 is just a structure called +(3,2), not the number 5. You must explicitly ask for evaluation.

Comparison operators

X =:= Y    % arithmetic equal (evaluates both sides)
X =\= Y    % arithmetic not-equal
X < Y      % less than
X > Y      % greater than
X =< Y     % less-or-equal (NOTE: NOT <=)
X >= Y     % greater-or-equal

4. Lists & Pattern Matching

Lists are the bread and butter of Prolog. Almost every exam problem involves them.

% A list is elements in square brackets
[1, 2, 3]           % a list of three numbers
[hello, world]      % a list of two atoms
[]                   % the empty list
[[1,2], [3,4]]      % a list of lists (nested)

The [Head | Tail] split

This is the most important syntax in all of Prolog. The | splits a list into its first element (Head) and everything else (Tail).

[H | T] = [1, 2, 3]         % H = 1,     T = [2, 3]
[H | T] = [hello]            % H = hello,  T = []      (tail of single-element list is empty!)
[A, B | T] = [x, y, z, w]   % A = x, B = y, T = [z, w]
[H | T] = []                 % FAILS — can't split an empty list

Built-in predicates you'll need

5. Recursion on Lists — THE Core Skill

Almost every Prolog problem is: process the first element, then recurse on the rest. Here's the universal template:

% Template:
predicate([], ...).                          % BASE CASE: empty list
predicate([Head | Tail], ...) :-             % RECURSIVE CASE:
    % ... do something with Head ...
    predicate(Tail, ...).                    % ... then handle the rest

Example 1: translate (from your A1)

We saw this in section 2. Now let's trace through it step by step to really understand what Prolog does.

% Facts (lookup table)
means(3, three). means(5, five). means(1, one).

% Rule
translate([], []).
translate([Num | RestNums], [Word | RestWords]) :-
    means(Num, Word),
    translate(RestNums, RestWords).

Example 2: my_between (from your A1)

This one doesn't process a list — it generates values. Two clauses, each a possible answer:

my_between(Low, High, Low) :-     % Option A: the answer IS Low
    Low =< High.
my_between(Low, High, X) :-       % Option B: the answer is somewhere after Low
    Low < High,
    Next is Low + 1,               % (using "is" for arithmetic!)
    my_between(Next, High, X).

% ?- my_between(1, 3, X).
% X = 1 ; X = 2 ; X = 3

This is a generator pattern — it produces values one at a time. We'll see why the ; works in the next section.

6. Backtracking — Prolog's Superpower

When a predicate has multiple clauses that could match, Prolog tries them in order. If one doesn't work out, it goes back and tries the next one. This is backtracking — and it's what makes Prolog special.

Choice points

Any time multiple clauses match, Prolog creates a choice point — a bookmark it can return to. Pressing ; tells Prolog to backtrack to the most recent choice point and try the next option.

This is why my_between(1, 3, X) gives three answers: at each call, clause 1 (yield Low) and clause 2 (try Next) both match, creating a choice point.

The "include or skip" pattern: subsum (from your A1)

Given a list of numbers and a target sum, find a subset that adds up to the target. The trick: for each element, Prolog can either include it or skip it.

subsum(_, 0, []).                             % Base: sum reached, take nothing more
subsum([Head | Tail], Sum, [Head | Part]) :-  % CHOICE A: Include Head
    Sum > 0,
    Remaining is Sum - Head,
    Remaining >= 0,
    subsum(Tail, Remaining, Part).
subsum([_ | Tail], Sum, Part) :-              % CHOICE B: Skip Head
    Sum > 0,
    subsum(Tail, Sum, Part).

Clauses 2 and 3 both match any non-empty list. That creates a choice point at every element. Prolog explores all 2^N subsets automatically — no loops, no recursion stack to manage. Backtracking IS the loop.

7. Cut (!) — "Commit to This Choice"

Sometimes backtracking wastes time trying alternatives you know are wrong. The cut (!) says: "I've found the right clause — don't try any others."

Once Prolog crosses a !, it will not backtrack to try other clauses for this predicate call.

Example: splitting a list (from your A2)

Split a list of numbers into positives and negatives.

Version 1: WITH cut

split_cut([], [], []).
split_cut([H | T], [H | Pos], Neg) :-
    H >= 0, !,                       % H is non-negative: COMMIT. Don't try clause 3.
    split_cut(T, Pos, Neg).
split_cut([H | T], Pos, [H | Neg]) :-% Only reached if H < 0
    split_cut(T, Pos, Neg).

Version 2: WITHOUT cut (explicit guards)

split_nocut([], [], []).
split_nocut([H | T], [H | Pos], Neg) :-
    H >= 0,                           % guard: only non-negative
    split_nocut(T, Pos, Neg).
split_nocut([H | T], Pos, [H | Neg]) :-
    H < 0,                            % guard: only negative
    split_nocut(T, Pos, Neg).

Both produce the same answers. The cut version is a bit more efficient (doesn't test H < 0 separately) but the no-cut version is easier to understand.

8. Negation (\+) — "I Can't Prove It"

\+ Goal succeeds if Prolog cannot prove Goal. It's not "Goal is false in the real world" — it's "I have no fact or rule that makes Goal true."

?- \+ member(99, [1, 2, 3]).
true.     % "I can't prove 99 is in [1,2,3]" → succeeds

?- \+ member(2, [1, 2, 3]).
false.    % "I CAN prove 2 is in [1,2,3]" → fails

Useful shorthand: \=

X \= Y is shorthand for \+ (X = Y) — succeeds if X and Y cannot be unified.

?- 3 \= 4.        true.     % 3 and 4 can't unify
?- 3 \= 3.        false.    % 3 and 3 CAN unify

Example: number_of_parents (from your A2)

% Adam and Eve have 0 parents. Everyone else has 2.
number_of_parents(adam, 0).
number_of_parents(eve, 0).
number_of_parents(X, 2) :-
    X \= adam,                 % X is NOT adam
    X \= eve.                  % X is NOT eve

?- number_of_parents(adam, N).
N = 0.                         % Clause 1 matches

?- number_of_parents(john, N).
N = 2.                         % Clause 3: john \= adam, john \= eve. Both pass.

9. Flatten — Putting It All Together (A1)

Now we can understand my_flatten, which uses almost everything we've learned: lists, recursion, is_list, cut, negation, and append.

The goal: [a, [b, [c]], d] → [a, b, c, d]. Flatten all nesting.

my_flatten([], []).                                % Base: nothing to flatten
my_flatten([Head | Tail], FlatList) :-
    is_list(Head), !,                               % Head IS a sublist?
    my_flatten(Head, FlatHead),                     %   flatten the sublist
    my_flatten(Tail, FlatTail),                     %   flatten the rest
    append(FlatHead, FlatTail, FlatList).            %   join them
my_flatten([Head | Tail], [Head | FlatTail]) :-
    \+ is_list(Head),                               % Head is an atom/number
    my_flatten(Tail, FlatTail).                     %   keep Head, recurse on rest

Three clauses, each handling one case:

1. Empty list: Done.
2. Head is a list: Flatten it separately, flatten the tail, append them. The ! commits: once we know Head is a list, don't try clause 3.
3. Head is an atom: Keep it in the result, recurse on tail.

10. Graph Traversal (HIGH Exam Probability)

This pattern combines everything: facts as a database, recursion, negation for cycle prevention, and an accumulator list.

Step 1: Define edges as facts

directTrain(guwahati, tezpur).
directTrain(nagaon, guwahati).
directTrain(lumding, nagaon).
directTrain(haflong, lumding).
directTrain(silchar, haflong).

Step 2: Make connections bidirectional

% If there's a direct train A→B, then they're connected both ways
connected(A, B) :- directTrain(A, B).
connected(A, B) :- directTrain(B, A).

Step 3: Find a route with cycle prevention

route(From, To, Route) :-
    route_helper(From, To, [From], RevRoute),
    reverse(RevRoute, Route).

% Base case: we've arrived!
route_helper(To, To, Visited, Visited).

% Recursive case: move to an unvisited neighbor
route_helper(From, To, Visited, Route) :-
    connected(From, Next),             % pick a neighbor
    \+ member(Next, Visited),          % that we haven't visited (CYCLE PREVENTION)
    route_helper(Next, To, [Next | Visited], Route).

This same pattern works for any graph: maze solving, social networks, dependency resolution. Change the edge facts, keep the traversal code.

11. N-Queens — Constraint Satisfaction (A3)

Board representation

The board is a list of column numbers. [2, 4, 1, 3] means: queen in row 1 at column 2, row 2 at column 4, row 3 at column 1, row 4 at column 3.

Since there's exactly one queen per row (by construction), we only need to check that no two queens share a column or diagonal.

The diagonal trick

Two queens at (R1,C1) and (R2,C2) are on the same diagonal when |R1-R2| = |C1-C2|. Equivalently:

• Rising diagonal (↗): all cells where Row + Col is the same
• Falling diagonal (↘): all cells where Row - Col is the same

The incremental approach (best one for the exam)

Place queens row by row. Track three "occupied" sets: used columns, used rising diagonals (R+C), used falling diagonals (R-C). A queen is safe if all three are free.

queens_inc(N, Board) :-
    numlist(1, N, Rows),
    place(Rows, N, [], [], [], RevBoard),
    reverse(RevBoard, Board).

place([], _, _, _, _, []).                    % No more rows
place([R | Rs], N, Cols, Ups, Downs, [C | More]) :-
    between(1, N, C),                         % try each column
    \+ member(C, Cols),                       % column must be free
    Up is R + C,
    \+ member(Up, Ups),                       % rising diagonal free
    Down is R - C,
    \+ member(Down, Downs),                   % falling diagonal free
    place(Rs, N, [C|Cols], [Up|Ups], [Down|Downs], More).

When between(1, N, C) picks a column that's already occupied (or has a diagonal conflict), the \+ member check fails, and Prolog backtracks to try the next column value. This prunes the search tree dramatically.

The safe-check approach (simpler, for testing a given board)

% Check each queen against all queens below it
safe([]).
safe([Q | Qs]) :-
    safe_against(Q, Qs, 1),                   % check Q vs all others
    safe(Qs).                                  % then check the rest

safe_against(_, [], _).                        % no more queens to check
safe_against(C, [C2 | Rest], Gap) :-
    C =\= C2,                                 % different column
    abs(C - C2) =\= Gap,                      % different diagonal
    Gap1 is Gap + 1,
    safe_against(C, Rest, Gap1).

Gap tracks the row distance. If |C - C2| = Gap, they're on the same diagonal. This works because we're comparing queen at position i against queen at position i+Gap.

12. DOMjudge I/O Template

The exam gives you a main predicate and test cases. Your code reads from stdin, processes, and writes to stdout.

% Template: read space-separated numbers, process, print
:- initialization(main).

main :-
    read_line_to_string(user_input, Line),
    split_string(Line, " ", " \t\r\n", Parts),
    maplist(number_string, Numbers, Parts),
    % --- Your logic here ---
    % solve(Numbers, Result),
    % writeln(Result),
    halt.

% Alternative: read a Prolog term (ending with a period on stdin)
main2 :-
    read(Term),
    process(Term, R),
    write(R), nl,
    halt.

% Print a list space-separated
print_list([]) :- nl.
print_list([X]) :- write(X), nl.
print_list([X|Xs]) :- write(X), write(' '), print_list(Xs).

13. Practice Problems

Problem 1: Path Finding

Given edge/2 facts, write path(Start, End, Path) that finds a path avoiding cycles. (Uses: facts, recursion, negation, accumulator — sections 1, 5, 8, 10)

% Test facts:
edge(a, b). edge(b, c). edge(c, d). edge(b, d). edge(d, a).
% ?- path(a, d, P).
% P = [a, b, c, d] ; P = [a, b, d]

path(Start, End, Path) :-
    path_helper(Start, End, [Start], RevPath),
    reverse(RevPath, Path).

path_helper(End, End, Visited, Visited).
path_helper(Current, End, Visited, Path) :-
    edge(Current, Next),
    \+ member(Next, Visited),
    path_helper(Next, End, [Next | Visited], Path).

Problem 2: Partition a List

Write partition(List, Pivot, Less, GreaterEq) that splits elements around a pivot. (Uses: recursion, cut or guards — sections 5, 7)

% ?- partition([3,1,4,1,5,9,2,6], 5, L, G).
% L = [3,1,4,1,2], G = [5,9,6]

partition([], _, [], []).
partition([H | T], Pivot, [H | Less], Greater) :-
    H < Pivot, !,
    partition(T, Pivot, Less, Greater).
partition([H | T], Pivot, Less, [H | Greater]) :-
    partition(T, Pivot, Less, Greater).

Problem 3: Safe Queens Check

Write safe(Board) that checks if a list of column positions represents a valid N-Queens board. (Uses: arithmetic, recursion, the diagonal trick — sections 3, 5, 11)

% ?- safe([2, 4, 1, 3]).   % true
% ?- safe([1, 2, 3]).       % false (diagonal conflict)

safe([]).
safe([Q | Qs]) :-
    no_attack(Q, Qs, 1),
    safe(Qs).

no_attack(_, [], _).
no_attack(C, [C2 | Rest], Gap) :-
    C =\= C2,                   % different column
    abs(C - C2) =\= Gap,        % different diagonal
    Gap1 is Gap + 1,
    no_attack(C, Rest, Gap1).

Problem 4: Remove Duplicates

Write remove_dups(List, Clean) that removes duplicate elements, keeping the first occurrence. (Uses: recursion, negation, member — sections 5, 8)

% ?- remove_dups([1,2,3,2,1,4], R).
% R = [1, 2, 3, 4]

remove_dups([], []).
remove_dups([H | T], Clean) :-
    member(H, T), !,             % H appears later: skip it
    remove_dups(T, Clean).
remove_dups([H | T], [H | Clean]) :-
    remove_dups(T, Clean).       % H is unique in tail: keep it