Practical Lab

19 experiments, each set out as 1. Question, 2. Aim, 3. Steps, 4. Programme, 5. Execution and Results. The syllabus names SWI-Prolog and adds "environment for practice without installation" — meaning swish.swi-prolog.org, which runs in a browser.

Code lives in labs/course-13a-ai/.

Read this before you read anything else

Every Prolog file here runs, in SWI-Prolog 9.0.4. Each experiment has two halves:

(Updated October 2026: SWI-Prolog could not be installed where these labs are checked, and every .pl file said NOT EXECUTED. It now installs from the Ubuntu archive. Running the files found five faults, each corrected in its file and noted below: a warning on loading 07_cut_fail.pl, another on loading 15_logic.pl under a non-UTF-8 locale, compare_searches/2 printing four comparisons, the expert system's explanation calling every fact a rule, and forward chaining that existed only as a comment.)

The .pl file is the deliverable. It is what you paste into SWISH and what the examiner marks. Under 5. Execution and Results is what SWI-Prolog answered: the toplevel waits for a key between answers, so the queries were asked by prolog_lab.py, which prints every answer as the toplevel does — X = asha ; for each and a full stop after the last — and, past eight answers, the first and how many there are.

bash tools/data-science/setup_prolog.sh          # SWI-Prolog, from the Ubuntu archive
pip install -r tools/requirements.txt
python3 tools/data-science/run_ai_labs.py

Output ends:

  16 Prolog programs run
  they cover experiments: [1, 2, 3, 4, 5, 6, 7, 8, 12, 13, 14, 15, 16, 17, 18, 19]
  (08_graph_search.pl covers experiments 8-11, which are one graph)

==============================================================
7 lab programs executed and asserted, 0 failed
covering all 19 prescribed experiments

Nineteen experiments, sixteen files because experiments 8–11 are one graph asked four ways — represent it, DFS it, BFS it, compare the path lengths — so they share 08_graph_search.pl, and one section below.

Experiment 1 — A family tree

1. Question

Represent a family tree in Prolog, with rules for father, mother, grandparent, ancestor, sibling and cousin.

2. Aim

State the facts, write the rules — one of them recursive — and query them.

3. Steps

In SWI-Prolog, 01_family_tree.pl:

1. State the facts.
2. Write the rules.
3. Ask the queries.

The Python check, 01_family_tree.py, through pytholog's resolution:

1. State the facts and simple rules.
2. Resolve the recursive ancestor/2.
3. Put the base case first.
4. Guard sibling/2 against X = Y.
5. Count one solution per proof.
6. Find cousins, and pytholog's limit.

4. Programme

In SWI-Prolog, 01_family_tree.pl:

% Experiment 1 -- A family tree in Prolog: ancestor/2, sibling/2, cousin/2.
%
% Run it: swipl 01_family_tree.pl, then type a query at the ?- prompt -- or paste the
% file into https://swish.swi-prolog.org/. Each "% ?-" query below was asked of
% SWI-Prolog 9.0.4 by tools/data-science/prolog_lab.py, and the lab page shows
% what it answered. 01_family_tree.py checks the same logic in Python.
% [Changed: this said the file had never been run, as SWI-Prolog could not be
% installed where these labs are checked. It now installs from the Ubuntu archive.]

% Step 1: State the facts
parent(ram,   asha).
parent(ram,   ravi).
parent(sita,  asha).
parent(sita,  ravi).
parent(asha,  kiran).
parent(asha,  meena).
parent(ravi,  bhanu).

male(ram).    male(ravi).   male(kiran).  male(bhanu).
female(sita). female(asha). female(meena).

% Step 2: Write the rules
father(X, Y) :- parent(X, Y), male(X).
mother(X, Y) :- parent(X, Y), female(X).

grandparent(X, Y) :- parent(X, Z), parent(Z, Y).

% ancestor/2 -- the recursive one, and the point of the experiment.
% BASE CASE FIRST. Prolog tries clauses top to bottom, so putting the
% recursive clause first makes it recurse before it can ever succeed.
ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

descendant(X, Y) :- ancestor(Y, X).

% sibling/2 -- share a parent, and are not the same person.
% Without the X \= Y guard, everyone is their own sibling.
sibling(X, Y) :- parent(P, X), parent(P, Y), X \= Y.

% cousin/2 -- their parents are siblings.
cousin(X, Y) :- parent(A, X), parent(B, Y), sibling(A, B).

% Step 3: Ask the queries
% ?- ancestor(ram, X).            % asha, ravi, kiran, meena, bhanu
% ?- descendant(kiran, X).        % asha, ram, sita
% ?- sibling(asha, X).            % ravi  (twice -- once per shared parent)
% ?- cousin(kiran, X).            % bhanu  (twice -- through each shared parent of
%                                 %  asha and ravi; setof/3 gives it once)
% ?- father(X, kiran).            % no -- kiran's parent asha is female
% ?- findall(X, ancestor(ram, X), L).   % L = [asha, ravi, kiran, meena, bhanu]

% --- WHY sibling(asha, X) GIVES ravi TWICE -----------------------------------
% asha and ravi share BOTH ram and sita, and Prolog reports one solution per
% way of proving the goal. Use setof/3 to get distinct answers:
%   ?- setof(X, sibling(asha, X), L).
% This is a real property of resolution, not a bug, and it is examinable.

The Python check, 01_family_tree.py, through pytholog's resolution:

"""Experiment 1 — A family tree, executed as a logic program.

This is NOT a simulation. pytholog implements SLD resolution over Horn
clauses, so the recursive ancestor/2 rule below is genuinely resolved the way
Prolog would resolve it -- including finding kiran, who is three levels down
and reachable only by recursion.
"""
import pytholog as pl

from fixtures import FAMILY_FACTS, FAMILY_RULES


def build():
    kb = pl.KnowledgeBase("family")
    kb(FAMILY_FACTS + FAMILY_RULES)
    return kb


def answers(kb, goal, var="X"):
    """Sorted distinct bindings for one variable -- Prolog's setof/3."""
    result = kb.query(pl.Expr(goal))
    if result in (["No"], []):
        return []
    return sorted({r[var] for r in result if isinstance(r, dict) and var in r})


def facts_and_simple_rules():
    kb = build()

    assert answers(kb, "parent(ram, X)") == ["asha", "ravi"]
    assert answers(kb, "father(X, asha)", "X") == ["ram"]
    assert answers(kb, "mother(X, asha)", "X") == ["sita"]
    assert answers(kb, "grandparent(ram, X)") == ["bhanu", "kiran", "meena"]

    print(f"  parent(ram, X)        -> {answers(kb, 'parent(ram, X)')}")
    print(f"  father(X, asha)       -> {answers(kb, 'father(X, asha)', 'X')}")
    print(f"  mother(X, asha)       -> {answers(kb, 'mother(X, asha)', 'X')}")
    print(f"  grandparent(ram, X)   -> {answers(kb, 'grandparent(ram, X)')}")
    print("       father/2 and mother/2 are the SAME rule with a different")
    print("       guard. That is what makes logic programming compact")


def recursion_is_what_makes_ancestor_work():
    """The point of the experiment: kiran is reachable only by recursing."""
    kb = build()

    descendants = answers(kb, "ancestor(ram, X)")
    assert descendants == ["asha", "bhanu", "kiran", "meena", "ravi"], descendants

    # One level down is the base case; two and three need the recursive clause.
    direct = answers(kb, "parent(ram, X)")
    assert set(direct) == {"asha", "ravi"}
    assert {"kiran", "meena", "bhanu"} <= set(descendants)
    assert {"kiran", "meena", "bhanu"} & set(direct) == set()

    print(f"  parent(ram, X)   -> {direct}                (1 level)")
    print(f"  ancestor(ram, X) -> {descendants}")
    print("       kiran, meena and bhanu are TWO levels down and appear only")
    print("       through the recursive clause. Delete it and they vanish.")
    print("       This is genuine SLD resolution, not a table lookup")


def base_case_must_come_first():
    """Clause ORDER matters in Prolog, and does not matter in logic."""
    good = pl.KnowledgeBase("good")
    good(FAMILY_FACTS + [
        "anc(X, Y) :- parent(X, Y)",                   # base case FIRST
        "anc(X, Y) :- parent(X, Z), anc(Z, Y)",
    ])
    result = good.query(pl.Expr("anc(ram, X)"))
    found = sorted({r["X"] for r in result if isinstance(r, dict)})
    assert found == ["asha", "bhanu", "kiran", "meena", "ravi"], found

    print(f"  base case first -> {found}")
    print("       with the RECURSIVE clause first, SWI-Prolog recurses before")
    print("       it can ever reach a fact, and a left-recursive rule such as")
    print("       'anc(X,Y) :- anc(X,Z), parent(Z,Y)' loops for ever.")
    print("       Clause order matters in Prolog and does NOT matter in logic --")
    print("       because Prolog is backward chaining with DEPTH-FIRST search")


def sibling_needs_the_inequality_guard():
    kb = build()
    siblings = answers(kb, "sibling(asha, X)")
    assert siblings == ["ravi"], siblings
    assert "asha" not in siblings, "the neq guard stops asha being her own sibling"

    # Without the guard, everyone is their own sibling.
    loose = pl.KnowledgeBase("loose")
    loose(FAMILY_FACTS + ["sib(X, Y) :- parent(P, X), parent(P, Y)"])
    bad = sorted({r["X"] for r in loose.query(pl.Expr("sib(asha, X)"))
                  if isinstance(r, dict)})
    assert "asha" in bad, bad

    print(f"  sibling(asha, X)  with the guard -> {siblings}")
    print(f"  without the guard                -> {bad}   <- asha is her own sibling")
    print("       every parent(P,X), parent(P,Y) pair unifies with X = Y unless")
    print("       you forbid it. In SWI-Prolog the guard is X \\\\= Y")


def duplicate_solutions_are_real():
    """asha and ravi share TWO parents, so Prolog proves sibling twice."""
    kb = build()
    raw = kb.query(pl.Expr("sibling(asha, X)"))
    bindings = [r["X"] for r in raw if isinstance(r, dict) and "X" in r]
    distinct = sorted(set(bindings))

    assert distinct == ["ravi"]
    assert len(bindings) >= 1

    print(f"  raw solutions for sibling(asha, X): {bindings}")
    print(f"  distinct                          : {distinct}")
    print("       asha and ravi share BOTH ram and sita, so in SWI-Prolog the")
    print("       goal succeeds once per shared parent -- one solution per PROOF,")
    print("       not per answer. setof/3 collapses them, and this is a property")
    print("       of resolution rather than a bug")


def cousins_expose_an_engine_limitation():
    """Two encodings of the same logic. One of them breaks pytholog.

    This is worth seeing rather than hiding: the .pl file uses the idiomatic
    nested form, which SWI-Prolog handles correctly. pytholog does not
    propagate neq/2 correctly through a nested derived predicate, so the same
    rule returns wrong answers here -- and the FLAT formulation, which asks
    the same question without an intermediate rule, gets it right.
    """
    # (a) The flat form: kiran and Y have different parents who share a parent.
    flat = pl.KnowledgeBase("flat")
    flat(FAMILY_FACTS + [
        "cousin(X, Y) :- parent(A, X), parent(B, Y), "
        "parent(G, A), parent(G, B), neq(A, B)"])
    flat_answers = sorted({r["X"] for r in flat.query(pl.Expr("cousin(kiran, X)"))
                           if isinstance(r, dict)})
    assert flat_answers == ["bhanu"], flat_answers

    # (b) The nested form, which is what the .pl file uses.
    nested = pl.KnowledgeBase("nested")
    nested(FAMILY_FACTS + [
        "sib(X, Y) :- parent(P, X), parent(P, Y), neq(X, Y)",
        "cousin(X, Y) :- parent(A, X), parent(B, Y), sib(A, B)"])
    nested_answers = sorted({r["X"] for r in nested.query(pl.Expr("cousin(kiran, X)"))
                             if isinstance(r, dict)})
    assert nested_answers == ["bhanu", "kiran", "meena"], nested_answers
    assert "kiran" in nested_answers, "kiran is returned as his OWN cousin"

    print(f"  flat rule   (no intermediate predicate) -> {flat_answers}   CORRECT")
    print(f"  nested rule (calls sib/2)               -> {nested_answers}")
    print("       the nested answer is WRONG: kiran is not his own cousin, and")
    print("       meena is his SISTER. pytholog does not propagate neq/2")
    print("       correctly through a nested derived predicate.")
    print("       SWI-Prolog handles the nested form correctly, and the .pl file")
    print("       uses it because it is the idiomatic encoding. This is an")
    print("       ENGINE limitation, not a flaw in the logic -- and it is why")
    print("       the .pl file is the deliverable and this file is the check")


def main():
    print("Experiment 1 -- A family tree as a logic program")
    # Step 1: State the facts and simple rules
    facts_and_simple_rules()
    # Step 2: Resolve the recursive ancestor/2
    recursion_is_what_makes_ancestor_work()
    # Step 3: Put the base case first
    base_case_must_come_first()
    # Step 4: Guard sibling/2 against X = Y
    sibling_needs_the_inequality_guard()
    # Step 5: Count one solution per proof
    duplicate_solutions_are_real()
    # Step 6: Find cousins, and pytholog's limit
    cousins_expose_an_engine_limitation()


if __name__ == "__main__":
    main()

5. Execution and Results

In SWI-Prolog, 01_family_tree.pl:

?- ancestor(ram, X).
X = asha ;
X = ravi ;
X = kiran ;
X = meena ;
X = bhanu.

?- descendant(kiran, X).
X = asha ;
X = ram ;
X = sita.

?- sibling(asha, X).
X = ravi ;
X = ravi.

?- cousin(kiran, X).
X = bhanu ;
X = bhanu.

?- father(X, kiran).
false.

?- findall(X, ancestor(ram, X), L).
L = [asha, ravi, kiran, meena, bhanu].

?- setof(X, sibling(asha, X), L).
L = [ravi].

The Python check, 01_family_tree.py, through pytholog's resolution:

Experiment 1 -- A family tree as a logic program
  parent(ram, X)        -> ['asha', 'ravi']
  father(X, asha)       -> ['ram']
  mother(X, asha)       -> ['sita']
  grandparent(ram, X)   -> ['bhanu', 'kiran', 'meena']
       father/2 and mother/2 are the SAME rule with a different
       guard. That is what makes logic programming compact
  parent(ram, X)   -> ['asha', 'ravi']                (1 level)
  ancestor(ram, X) -> ['asha', 'bhanu', 'kiran', 'meena', 'ravi']
       kiran, meena and bhanu are TWO levels down and appear only
       through the recursive clause. Delete it and they vanish.
       This is genuine SLD resolution, not a table lookup
  base case first -> ['asha', 'bhanu', 'kiran', 'meena', 'ravi']
       with the RECURSIVE clause first, SWI-Prolog recurses before
       it can ever reach a fact, and a left-recursive rule such as
       'anc(X,Y) :- anc(X,Z), parent(Z,Y)' loops for ever.
       Clause order matters in Prolog and does NOT matter in logic --
       because Prolog is backward chaining with DEPTH-FIRST search
  sibling(asha, X)  with the guard -> ['ravi']
  without the guard                -> ['asha', 'ravi']   <- asha is her own sibling
       every parent(P,X), parent(P,Y) pair unifies with X = Y unless
       you forbid it. In SWI-Prolog the guard is X \\= Y
  raw solutions for sibling(asha, X): ['ravi', 'ravi']
  distinct                          : ['ravi']
       asha and ravi share BOTH ram and sita, so in SWI-Prolog the
       goal succeeds once per shared parent -- one solution per PROOF,
       not per answer. setof/3 collapses them, and this is a property
       of resolution rather than a bug
  flat rule   (no intermediate predicate) -> ['bhanu']   CORRECT
  nested rule (calls sib/2)               -> ['bhanu', 'kiran', 'meena']
       the nested answer is WRONG: kiran is not his own cousin, and
       meena is his SISTER. pytholog does not propagate neq/2
       correctly through a nested derived predicate.
       SWI-Prolog handles the nested form correctly, and the .pl file
       uses it because it is the idiomatic encoding. This is an
       ENGINE limitation, not a flaw in the logic -- and it is why
       the .pl file is the deliverable and this file is the check

ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

sibling(asha, X)  with the guard -> ['ravi']
without the guard                -> ['asha', 'ravi']   <- asha is her own sibling

Experiment 2 — member, append, reverse and length

1. Question

Write list predicates in Prolog: member, append, reverse and length.

2. Aim

Define the four predicates recursively, and run append/3 backwards.

3. Steps

In SWI-Prolog, 02_lists.pl:

1. Define member/2.
2. Define append/3.
3. Define reverse/2, with an accumulator.
4. Define length/2.
5. Ask the queries.
6. Run append/3 backwards.

The Python check, 02_lists_and_arithmetic.py, for experiments 2–7:

1. Prove pytholog's limits first.
2. Experiment 2: the list predicates.
3. Experiment 3: the maximum.
4. Experiment 4: flatten.
5. Experiments 5 and 6: factorial, Fibonacci and GCD.
6. Experiment 7: cut, fail and negation.

4. Programme

In SWI-Prolog, 02_lists.pl:

% Experiment 2 -- member/2, append/3, reverse/2, length/2.
%
% Run it: swipl 02_lists.pl, then type a query at the ?- prompt -- or paste the
% file into https://swish.swi-prolog.org/. Each "% ?-" query below was asked of
% SWI-Prolog 9.0.4 by tools/data-science/prolog_lab.py, and the lab page shows
% what it answered. 02_lists_and_arithmetic.py checks the same logic in Python.
% [Changed: this said the file had never been run, as SWI-Prolog could not be
% installed where these labs are checked. It now installs from the Ubuntu archive.]
%
% pytholog has NO LIST TERMS, so none of this can run there. The .py file
% checks what these predicates COMPUTE, in Python.

% Step 1: Define member/2
mem(X, [X|_]).
mem(X, [_|T]) :- mem(X, T).

% Step 2: Define append/3
app([], L, L).
app([H|T], L, [H|R]) :- app(T, L, R).

% Step 3: Define reverse/2, with an accumulator
rev(L, R) :- rev_acc(L, [], R).
rev_acc([], Acc, Acc).
rev_acc([H|T], Acc, R) :- rev_acc(T, [H|Acc], R).

% Step 4: Define length/2
len([], 0).
len([_|T], N) :- len(T, N1), N is N1 + 1.

% Step 5: Ask the queries
% ?- mem(b, [a,b,c]).            % true
% ?- app([a,b], [c,d], X).       % X = [a,b,c,d]
% ?- rev([a,b,c], X).            % X = [c,b,a]
% ?- len([a,b,c], N).            % N = 3

% Step 6: Run append/3 backwards
% app/3 RUNS BACKWARDS. It is a RELATION, not a function:
%   ?- app(X, Y, [a,b,c]).
%   X = [],      Y = [a,b,c] ;
%   X = [a],     Y = [b,c]   ;
%   X = [a,b],   Y = [c]     ;
%   X = [a,b,c], Y = []      .
% FOUR solutions from ONE definition. No functional language does this, and it
% is the single best demonstration of what declarative programming means.

The Python check, 02_lists_and_arithmetic.py, for experiments 2–7:

"""Experiments 2-7 — List predicates, arithmetic, and the cut.

pytholog has NO LIST TERMS, NO ARITHMETIC EVALUATION and NO CUT, so these six
experiments cannot be run as logic programs here. That limitation is ASSERTED
below rather than described, and the same computations are then performed in
Python so the expected answers in the .pl files are checked.

The .pl files carry the real Prolog, and they are the lab deliverable.
"""
import pytholog as pl


def pytholog_has_no_lists():
    """Asserted, so this file can never quietly start claiming to test lists."""
    kb = pl.KnowledgeBase("lists")
    kb(["mem(X, [X|_])", "mem(X, [_|T]) :- mem(X, T)"])
    result = kb.query(pl.Expr("mem(b, [a,b,c])"))

    assert result == ["No"], result
    print("  pytholog: mem(b, [a,b,c]) -> ['No']  (SWI-Prolog answers 'true')")
    print("       there are no list TERMS, so [X|T] never unifies. Experiments")
    print("       2, 3 and 4 are executed in Python below; the .pl files carry")
    print("       the real Prolog")


def pytholog_has_no_arithmetic():
    kb = pl.KnowledgeBase("arith")
    kb(["fact(0, 1)", "fact(N, F) :- N1 is N-1, fact(N1, F1), F is N*F1"])
    result = kb.query(pl.Expr("fact(5, X)"))

    assert result == ["No"], result
    print("  pytholog: fact(5, X) -> ['No']  (SWI-Prolog answers X = 120)")
    print("       'is/2' does not evaluate, so experiments 5 and 6 are executed")
    print("       in Python too")


# --- experiment 2: member, append, reverse, length --------------------------

def list_predicates():
    """What the Prolog definitions compute, checked in Python."""
    xs = ["a", "b", "c"]
    ys = ["d", "e"]

    assert "b" in xs and "z" not in xs                     # member/2
    assert xs + ys == ["a", "b", "c", "d", "e"]            # append/3
    assert list(reversed(xs)) == ["c", "b", "a"]           # reverse/2
    assert len(xs) == 3                                    # length/2

    # append/3 is RELATIONAL: it can also split a list, which is the property
    # that makes Prolog different from a functional language.
    splits = [(xs[:i], xs[i:]) for i in range(len(xs) + 1)]
    assert len(splits) == 4
    assert splits[0] == ([], ["a", "b", "c"])
    assert splits[-1] == (["a", "b", "c"], [])

    print(f"  member(b, {xs})      -> true")
    print(f"  append({xs}, {ys}, X) -> {xs + ys}")
    print(f"  reverse({xs}, X)     -> {list(reversed(xs))}")
    print(f"  length({xs}, N)      -> {len(xs)}")
    print(f"  append(X, Y, {xs})   -> {len(splits)} solutions: {splits}")
    print("       that last one is the point of Prolog: append/3 RUNS BACKWARDS.")
    print("       One definition both concatenates and splits, because a rule")
    print("       states a RELATION rather than a function")


def maximum_of_a_list():
    """Experiment 3."""
    def maximum(xs):
        best = xs[0]
        for x in xs[1:]:
            if x > best:
                best = x
        return best

    assert maximum([3, 7, 2, 9, 4]) == 9
    assert maximum([5]) == 5
    assert maximum([-3, -7, -2]) == -2

    print(f"  max([3,7,2,9,4]) -> {maximum([3, 7, 2, 9, 4])}")
    print("       the Prolog version recurses on the tail and compares against")
    print("       the maximum of the rest. The base case is the ONE-element")
    print("       list, not the empty one -- max([]) has no answer")


def flatten_a_nested_list():
    """Experiment 4."""
    def flatten(x):
        if not isinstance(x, list):
            return [x]
        out = []
        for item in x:
            out.extend(flatten(item))
        return out

    nested = [1, [2, [3, 4], 5], [[6]], 7]
    assert flatten(nested) == [1, 2, 3, 4, 5, 6, 7]
    assert flatten([]) == []
    assert flatten([[], [[]], 1]) == [1], "empty lists vanish"

    print(f"  flatten({nested}) -> {flatten(nested)}")
    print(f"  flatten([[], [[]], 1]) -> {flatten([[], [[]], 1])}")
    print("       three clauses in Prolog: the empty list, a list head (recurse")
    print("       into it and append), and an atom head (keep it). Empty")
    print("       sublists disappear, which is the case people forget")


# --- experiments 5 and 6: arithmetic ----------------------------------------

def factorial_and_fibonacci():
    def fact(n):
        return 1 if n == 0 else n * fact(n - 1)

    def fib(n):
        return n if n < 2 else fib(n - 1) + fib(n - 2)

    assert [fact(n) for n in range(6)] == [1, 1, 2, 6, 24, 120]
    assert [fib(n) for n in range(10)] == [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
    assert fact(10) == 3628800

    # Naive fib is exponential -- 177 calls for fib(10).
    calls = {"n": 0}

    def counted(n):
        calls["n"] += 1
        return n if n < 2 else counted(n - 1) + counted(n - 2)

    counted(10)
    assert calls["n"] == 177, calls["n"]

    print(f"  factorial 0..5 -> {[fact(n) for n in range(6)]}")
    print(f"  fibonacci 0..9 -> {[fib(n) for n in range(10)]}")
    print(f"  naive fib(10) makes {calls['n']} recursive calls")
    print("       the naive Prolog definition is exponential for the same")
    print("       reason. Add an accumulator, or use assertz/1 to memoise --")
    print("       which is Prolog's version of dynamic programming")


def gcd_by_recursion():
    """Experiment 6 -- Euclid's algorithm."""
    def gcd(a, b):
        return a if b == 0 else gcd(b, a % b)

    assert gcd(48, 18) == 6
    assert gcd(17, 5) == 1
    assert gcd(0, 7) == 7
    assert gcd(100, 75) == 25

    steps = []
    a, b = 48, 18
    while b:
        steps.append((a, b))
        a, b = b, a % b
    assert steps == [(48, 18), (18, 12), (12, 6)]

    print(f"  gcd(48, 18) = {gcd(48, 18)}   trace: {steps} -> 6")
    print(f"  gcd(17, 5)  = {gcd(17, 5)}    (coprime)")
    print("       two clauses in Prolog: gcd(A,0,A) is the base case, and")
    print("       gcd(A,B,G) :- B > 0, R is A mod B, gcd(B,R,G)")


# --- experiment 7: cut and fail ---------------------------------------------

def cut_and_fail_are_documented_only():
    """No cut in pytholog, so this is stated as semantics, not tested."""
    behaviours = [
        ("!", "commits to the current clause AND to the bindings made "
              "before it; discards remaining choice points"),
        ("fail", "always fails, forcing backtracking"),
        ("!, fail", "the CUT-FAIL idiom: commit, then fail, so the whole "
                    "goal fails with no alternatives tried"),
        ("\\\\+ G", "negation as failure -- succeeds if G cannot be proved"),
    ]
    assert len(behaviours) == 4

    print("  the cut and fail, as semantics (pytholog has no cut):")
    for op, meaning in behaviours:
        print(f"    {op:10} {meaning}")
    print()
    print("  the classic cut-fail example -- 'penguins do not fly':")
    print("      fly(X) :- penguin(X), !, fail.")
    print("      fly(X) :- bird(X).")
    print("    for a penguin the first clause commits and fails, so the second")
    print("    is NEVER tried. Remove the cut and every penguin flies.")
    print()
    print("  GREEN CUT   -- removes only redundant choice points; deleting it")
    print("                 changes nothing but speed")
    print("  RED CUT     -- changes the MEANING; deleting it changes answers")
    print("       the cut is the point where Prolog stops being pure logic:")
    print("       clause order and cut placement become semantically load")
    print("       bearing, which is why it is the hardest thing to debug")


def negation_as_failure_is_not_logical_negation():
    """The examinable subtlety, demonstrated with a closed world."""
    known_birds = {"tweety", "polly"}
    known_penguins = {"pingu"}

    # \+ penguin(tweety) succeeds because tweety is not KNOWN to be a penguin
    assert "tweety" not in known_penguins
    # ... but the database simply may not know. That is the CLOSED WORLD
    # ASSUMPTION: anything not derivable is taken to be false.
    unknown_bird = "kiwi"
    assert unknown_bird not in known_birds and unknown_bird not in known_penguins

    print(f"  known birds: {sorted(known_birds)}, known penguins: "
          f"{sorted(known_penguins)}")
    print(f"  \\\\+ penguin(tweety)  succeeds -- tweety is not known to be one")
    print(f"  \\\\+ bird({unknown_bird})       succeeds -- but we simply do not know")
    print("       Prolog's \\\\+ is NEGATION AS FAILURE, not logical negation.")
    print("       It assumes a CLOSED WORLD: anything not derivable is false.")
    print("       Logical negation would require proving the fact untrue")


def main():
    print("Experiments 2-7 -- Lists, arithmetic, and the cut")
    # Step 1: Prove pytholog's limits first
    print("  engine limits, asserted:")
    pytholog_has_no_lists()
    pytholog_has_no_arithmetic()
    # Step 2: Experiment 2: the list predicates
    print("  experiment 2 -- list predicates:")
    list_predicates()
    # Step 3: Experiment 3: the maximum
    print("  experiment 3 -- maximum of a list:")
    maximum_of_a_list()
    # Step 4: Experiment 4: flatten
    print("  experiment 4 -- flatten:")
    flatten_a_nested_list()
    # Step 5: Experiments 5 and 6: factorial, Fibonacci and GCD
    print("  experiments 5 and 6 -- factorial, Fibonacci, GCD:")
    factorial_and_fibonacci()
    gcd_by_recursion()
    # Step 6: Experiment 7: cut, fail and negation
    print("  experiment 7 -- cut and fail:")
    cut_and_fail_are_documented_only()
    negation_as_failure_is_not_logical_negation()


if __name__ == "__main__":
    main()

5. Execution and Results

In SWI-Prolog, 02_lists.pl:

?- mem(b, [a,b,c]).
true.

?- app([a,b], [c,d], X).
X = [a, b, c, d].

?- rev([a,b,c], X).
X = [c, b, a].

?- len([a,b,c], N).
N = 3.

?- app(X, Y, [a,b,c]).
X = [],
Y = [a, b, c] ;
X = [a],
Y = [b, c] ;
X = [a, b],
Y = [c] ;
X = [a, b, c],
Y = [].

The Python check, 02_lists_and_arithmetic.py, for experiments 2–7:

Experiments 2-7 -- Lists, arithmetic, and the cut
  engine limits, asserted:
  pytholog: mem(b, [a,b,c]) -> ['No']  (SWI-Prolog answers 'true')
       there are no list TERMS, so [X|T] never unifies. Experiments
       2, 3 and 4 are executed in Python below; the .pl files carry
       the real Prolog
  pytholog: fact(5, X) -> ['No']  (SWI-Prolog answers X = 120)
       'is/2' does not evaluate, so experiments 5 and 6 are executed
       in Python too
  experiment 2 -- list predicates:
  member(b, ['a', 'b', 'c'])      -> true
  append(['a', 'b', 'c'], ['d', 'e'], X) -> ['a', 'b', 'c', 'd', 'e']
  reverse(['a', 'b', 'c'], X)     -> ['c', 'b', 'a']
  length(['a', 'b', 'c'], N)      -> 3
  append(X, Y, ['a', 'b', 'c'])   -> 4 solutions: [([], ['a', 'b', 'c']), (['a'], ['b', 'c']), (['a', 'b'], ['c']), (['a', 'b', 'c'], [])]
       that last one is the point of Prolog: append/3 RUNS BACKWARDS.
       One definition both concatenates and splits, because a rule
       states a RELATION rather than a function
  experiment 3 -- maximum of a list:
  max([3,7,2,9,4]) -> 9
       the Prolog version recurses on the tail and compares against
       the maximum of the rest. The base case is the ONE-element
       list, not the empty one -- max([]) has no answer
  experiment 4 -- flatten:
  flatten([1, [2, [3, 4], 5], [[6]], 7]) -> [1, 2, 3, 4, 5, 6, 7]
  flatten([[], [[]], 1]) -> [1]
       three clauses in Prolog: the empty list, a list head (recurse
       into it and append), and an atom head (keep it). Empty
       sublists disappear, which is the case people forget
  experiments 5 and 6 -- factorial, Fibonacci, GCD:
  factorial 0..5 -> [1, 1, 2, 6, 24, 120]
  fibonacci 0..9 -> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
  naive fib(10) makes 177 recursive calls
       the naive Prolog definition is exponential for the same
       reason. Add an accumulator, or use assertz/1 to memoise --
       which is Prolog's version of dynamic programming
  gcd(48, 18) = 6   trace: [(48, 18), (18, 12), (12, 6)] -> 6
  gcd(17, 5)  = 1    (coprime)
       two clauses in Prolog: gcd(A,0,A) is the base case, and
       gcd(A,B,G) :- B > 0, R is A mod B, gcd(B,R,G)
  experiment 7 -- cut and fail:
  the cut and fail, as semantics (pytholog has no cut):
    !          commits to the current clause AND to the bindings made before it; discards remaining choice points
    fail       always fails, forcing backtracking
    !, fail    the CUT-FAIL idiom: commit, then fail, so the whole goal fails with no alternatives tried
    \\+ G      negation as failure -- succeeds if G cannot be proved

  the classic cut-fail example -- 'penguins do not fly':
      fly(X) :- penguin(X), !, fail.
      fly(X) :- bird(X).
    for a penguin the first clause commits and fails, so the second
    is NEVER tried. Remove the cut and every penguin flies.

  GREEN CUT   -- removes only redundant choice points; deleting it
                 changes nothing but speed
  RED CUT     -- changes the MEANING; deleting it changes answers
       the cut is the point where Prolog stops being pure logic:
       clause order and cut placement become semantically load
       bearing, which is why it is the hardest thing to debug
  known birds: ['polly', 'tweety'], known penguins: ['pingu']
  \\+ penguin(tweety)  succeeds -- tweety is not known to be one
  \\+ bird(kiwi)       succeeds -- but we simply do not know
       Prolog's \\+ is NEGATION AS FAILURE, not logical negation.
       It assumes a CLOSED WORLD: anything not derivable is false.
       Logical negation would require proving the fact untrue

Experiment 3 — The maximum of a list

1. Question

Find the maximum element of a list.

2. Aim

Define max_list/2 recursively, from the right base case.

3. Steps

1. Define max_list/2, from a one-element base case.
2. Ask the query.

4. Programme

% Experiment 3 -- the maximum element of a list.
%
% Run it: swipl 03_maximum.pl, then type a query at the ?- prompt -- or paste the
% file into https://swish.swi-prolog.org/. Each "% ?-" query below was asked of
% SWI-Prolog 9.0.4 by tools/data-science/prolog_lab.py, and the lab page shows
% what it answered. 02_lists_and_arithmetic.py checks the same logic in Python.
% [Changed: this said the file had never been run, as SWI-Prolog could not be
% installed where these labs are checked. It now installs from the Ubuntu archive.]

% Step 1: Define max_list/2, from a one-element base case
max_list([X], X).
max_list([H|T], M) :- max_list(T, M1), (H > M1 -> M = H ; M = M1).

% Step 2: Ask the query
% ?- max_list([3,7,2,9,4], M).   % M = 9

% NOTE the base case: a ONE-element list, not the empty one. max_list([], M)
% has no answer, because the maximum of nothing is undefined -- and writing
% max_list([], 0) would be wrong for a list of negative numbers.

5. Execution and Results

?- max_list([3,7,2,9,4], M).
M = 9.

The Python check for this experiment, 02_lists_and_arithmetic.py, is shown in full under Experiment 2, with what it printed.

Experiment 4 — Flatten a nested list

1. Question

Flatten a nested list into a single-level list.

2. Aim

Define flatten/2 in three clauses: the empty list, a list head and an atom.

3. Steps

1. Define flatten/2 in three clauses.
2. Ask the query.

4. Programme

% Experiment 4 -- flatten a nested list into a single-level list.
%
% Run it: swipl 04_flatten.pl, then type a query at the ?- prompt -- or paste the
% file into https://swish.swi-prolog.org/. Each "% ?-" query below was asked of
% SWI-Prolog 9.0.4 by tools/data-science/prolog_lab.py, and the lab page shows
% what it answered. 02_lists_and_arithmetic.py checks the same logic in Python.
% [Changed: this said the file had never been run, as SWI-Prolog could not be
% installed where these labs are checked. It now installs from the Ubuntu archive.]

% Step 1: Define flatten/2 in three clauses
flatten([], []) :- !.
flatten([H|T], R) :- !, flatten(H, FH), flatten(T, FT), append(FH, FT, R).
flatten(X, [X]).

% Step 2: Ask the query
% ?- flatten([1,[2,[3,4],5],[[6]],7], X).   % X = [1,2,3,4,5,6,7]

% THREE clauses: the empty list, a list head (recurse into it and append), and
% an atom (wrap it). The cuts make the clauses mutually exclusive -- without
% them, flatten([], X) would also match the third clause and give X = [[]].
% These are RED CUTS: removing them changes the answers, not just the speed.

5. Execution and Results

?- flatten([1,[2,[3,4],5],[[6]],7], X).
X = [1, 2, 3, 4, 5, 6, 7].

The Python check for this experiment, 02_lists_and_arithmetic.py, is shown in full under Experiment 2, with what it printed.

Experiment 5 — Factorial and Fibonacci

1. Question

Compute factorial and Fibonacci numbers by recursion.

2. Aim

Define fact/2 and fib/2 with is/2, see why the naive fib/2 is slow, and make it linear.

3. Steps

1. Define factorial.
2. Define Fibonacci.
3. Ask the queries.
4. Make Fibonacci linear with an accumulator.

factorial 0..5 -> [1, 1, 2, 6, 24, 120]
fibonacci 0..9 -> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
naive fib(10) makes 177 recursive calls

4. Programme

% Experiment 5 -- factorial and Fibonacci.
%
% Run it: swipl 05_factorial_fib.pl, then type a query at the ?- prompt -- or paste the
% file into https://swish.swi-prolog.org/. Each "% ?-" query below was asked of
% SWI-Prolog 9.0.4 by tools/data-science/prolog_lab.py, and the lab page shows
% what it answered. 02_lists_and_arithmetic.py checks the same logic in Python.
% [Changed: this said the file had never been run, as SWI-Prolog could not be
% installed where these labs are checked. It now installs from the Ubuntu archive.]
%
% pytholog does not evaluate is/2, so this cannot run there either.

% Step 1: Define factorial
fact(0, 1).
fact(N, F) :- N > 0, N1 is N - 1, fact(N1, F1), F is N * F1.

% Step 2: Define Fibonacci
fib(0, 0).
fib(1, 1).
fib(N, F) :- N > 1, N1 is N-1, N2 is N-2, fib(N1, F1), fib(N2, F2), F is F1+F2.

% Step 3: Ask the queries
% ?- fact(5, F).   % F = 120
% ?- fib(10, F).   % F = 55

% Step 4: Make Fibonacci linear with an accumulator
% fib(10, F) makes 177 recursive calls, because fib(8) is recomputed inside
% both fib(9) and fib(8). It is exponential. Two fixes:
%
% 1. An accumulator pair, which makes it linear:
fib_fast(N, F) :- fib_acc(N, 0, 1, F).
fib_acc(0, A, _, A).
fib_acc(N, A, B, F) :- N > 0, N1 is N-1, C is A+B, fib_acc(N1, B, C, F).
% ?- fib_fast(30, F).   % F = 832040, at once -- fib(30, F) makes 2,692,537 calls
% [Added: nothing asked for fib_fast/2, so it had never been tried.]
%
% 2. assertz/1 to memoise -- Prolog's dynamic programming:
%      :- dynamic fibm/2.
%      fibm(N, F) :- fib(N, F), assertz(fibm(N, F)).

5. Execution and Results

?- fact(5, F).
F = 120.

?- fib(10, F).
F = 55.

?- fib_fast(30, F).
F = 832040.

Added: nothing in the file asked for its accumulator version, fib_fast/2; the query above runs it. fib_fast(30, F) answers at once, where the naive fib(30, F) makes 2,692,537 calls.

The Python check for this experiment, 02_lists_and_arithmetic.py, is shown in full under Experiment 2, with what it printed.

Experiment 6 — GCD by recursion

1. Question

Find the greatest common divisor of two numbers by recursion.

2. Aim

Define gcd/3 by Euclid's algorithm, and see why it terminates.

3. Steps

1. Define gcd/3, by Euclid.
2. Ask the queries.

gcd(48, 18) = 6   trace: (48,18) -> (18,12) -> (12,6) -> 6
gcd(17, 5)  = 1   (coprime)

4. Programme

% Experiment 6 -- greatest common divisor by recursion (Euclid).
%
% Run it: swipl 06_gcd.pl, then type a query at the ?- prompt -- or paste the
% file into https://swish.swi-prolog.org/. Each "% ?-" query below was asked of
% SWI-Prolog 9.0.4 by tools/data-science/prolog_lab.py, and the lab page shows
% what it answered. 02_lists_and_arithmetic.py checks the same logic in Python.
% [Changed: this said the file had never been run, as SWI-Prolog could not be
% installed where these labs are checked. It now installs from the Ubuntu archive.]

% Step 1: Define gcd/3, by Euclid
gcd(A, 0, A) :- A > 0.
gcd(A, B, G) :- B > 0, R is A mod B, gcd(B, R, G).

% Step 2: Ask the queries
% ?- gcd(48, 18, G).   % G = 6
% ?- gcd(17, 5, G).    % G = 1   (coprime)

% The trace for gcd(48, 18):
%   gcd(48, 18) -> gcd(18, 12) -> gcd(12, 6) -> gcd(6, 0) -> 6
% Each step replaces (A, B) with (B, A mod B), and B strictly decreases, so
% termination is guaranteed. That decreasing measure is the recursion's
% variant, and it is what you point at when asked why it halts.

5. Execution and Results

?- gcd(48, 18, G).
G = 6.

?- gcd(17, 5, G).
G = 1.

The Python check for this experiment, 02_lists_and_arithmetic.py, is shown in full under Experiment 2, with what it printed.

Experiment 7 — Cut and fail

1. Question

Demonstrate the cut (!) and fail.

2. Aim

Write the cut-fail idiom, tell a green cut from a red one, and negate by failure.

3. Steps

1. State the facts.
2. Write the cut-fail rule.
3. Tell a green cut from a red one.
4. Negate by failure.

fly(X) :- penguin(X), !, fail.
fly(X) :- bird(X).

4. Programme

% Experiment 7 -- the cut (!) and fail.
%
% Run it: swipl 07_cut_fail.pl, then type a query at the ?- prompt -- or paste the
% file into https://swish.swi-prolog.org/. Each "% ?-" query below was asked of
% SWI-Prolog 9.0.4 by tools/data-science/prolog_lab.py, and the lab page shows
% what it answered. 02_lists_and_arithmetic.py checks the same logic in Python.
% [Changed: this said the file had never been run, as SWI-Prolog could not be
% installed where these labs are checked. It now installs from the Ubuntu archive.]
%
% pytholog has NO CUT, so the .py file sets out the semantics and asserts the
% engine limitation; the cut itself runs here, in SWI-Prolog.

% Step 1: State the facts
bird(tweety).
bird(polly).
bird(pingu).
penguin(pingu).
% [Corrected: bird(pingu) came after penguin(pingu), so bird/1's clauses were not
% together, and SWI-Prolog warned "Clauses of bird/1 are not together" on loading.]

% Step 2: Write the cut-fail rule
fly(X) :- penguin(X), !, fail.
fly(X) :- bird(X).

% ?- fly(tweety).   % true
% ?- fly(pingu).    % false  -- the first clause commits and fails, so the
%                   %           second is NEVER tried
%
% REMOVE THE CUT and fly(pingu) succeeds via the second clause. That is a
% RED CUT: it changes the meaning of the program.

% Step 3: Tell a green cut from a red one
% GREEN CUT: removes only redundant choice points. Deleting it changes speed
%            and nothing else.
% RED CUT:   changes which answers are produced. Deleting it changes meaning.
%
% max_green(X, Y, X) :- X >= Y, !.     % green -- the guard already excludes
% max_green(X, Y, Y) :- X < Y.         %          the other case
%
% max_red(X, Y, X) :- X >= Y, !.       % red -- without the cut, max_red(3,2,2)
% max_red(_, Y, Y).                    %        would also succeed

% Step 4: Negate by failure
not_penguin(X) :- \+ penguin(X).
% ?- not_penguin(tweety).   % true -- tweety is not KNOWN to be a penguin
%
% \+ is NEGATION AS FAILURE under the CLOSED WORLD ASSUMPTION: anything not
% derivable is taken to be false. It is NOT logical negation, which would
% require proving the fact untrue. For an unknown bird, \+ penguin(kiwi)
% succeeds simply because the database has never heard of it.

5. Execution and Results

?- fly(tweety).
true.

?- fly(pingu).
false.

?- not_penguin(tweety).
true.

Corrected: bird(pingu) came after penguin(pingu), so the clauses of bird/1 were not together, and SWI-Prolog warned "Clauses of bird/1 are not together in the source-file" on loading. They are together now, and the file loads silently.

known birds: ['polly', 'tweety'], known penguins: ['pingu']
\+ penguin(tweety)  succeeds  -- tweety is not known to be one
\+ bird(kiwi)       succeeds  -- but we simply do not know

The Python check for this experiment, 02_lists_and_arithmetic.py, is shown in full under Experiment 2, with what it printed.

Experiments 8–11 — A graph, DFS, BFS, and the comparison

1. Question

Experiment 8: represent a graph as facts. Experiment 9: search it depth-first. Experiment 10: search it breadth-first. Experiment 11: compare the paths they find.

2. Aim

State one graph, search it both ways, and see that DFS finds the long way round and BFS the short one.

3. Steps

In SWI-Prolog, 08_graph_search.pl:

1. Experiment 8: state the graph as edge/2 facts.
2. Experiment 9: search depth-first.
3. Experiment 10: search breadth-first, with a queue.
4. Experiment 11: compare the paths.

The Python check, 03_uninformed_search.py, for experiments 8–11:

1. Compare BFS, DFS and uniform cost on the Romania map.
2. See uniform cost as Dijkstra.
3. Run DFS and BFS on the six-node graph.
4. Make one step cost more.
5. Count iterative deepening's extra nodes.

4. Programme

In SWI-Prolog, 08_graph_search.pl:

% Experiments 8-11 -- a graph, DFS, BFS, and comparing path lengths.
%
% Run it: swipl 08_graph_search.pl, then type a query at the ?- prompt -- or paste the
% file into https://swish.swi-prolog.org/. Each "% ?-" query below was asked of
% SWI-Prolog 9.0.4 by tools/data-science/prolog_lab.py, and the lab page shows
% what it answered. 03_uninformed_search.py checks the same logic in Python.
% [Changed: this said the file had never been run, as SWI-Prolog could not be
% installed where these labs are checked. It now installs from the Ubuntu archive.]

% Step 1: Experiment 8: state the graph as edge/2 facts
edge(a, b).  edge(a, c).
edge(b, d).
edge(c, g).
edge(d, e).
edge(e, g).

% Step 2: Experiment 9: search depth-first
% The Visited list is what stops it looping. Without it, a cycle is fatal.
dfs(Start, Goal, Path) :- dfs_helper(Start, Goal, [Start], P), reverse(P, Path).

dfs_helper(Goal, Goal, Visited, Visited).
dfs_helper(Node, Goal, Visited, Path) :-
    edge(Node, Next),
    \+ member(Next, Visited),
    dfs_helper(Next, Goal, [Next|Visited], Path).

% ?- dfs(a, g, P).   % P = [a,b,d,e,g]  -- the LONG way, found first; ; gives [a,c,g]

% Step 3: Experiment 10: search breadth-first, with a queue
bfs(Start, Goal, Path) :- bfs_queue([[Start]], Goal, R), reverse(R, Path).

bfs_queue([[Goal|Rest]|_], Goal, [Goal|Rest]).
bfs_queue([[N|Rest]|Others], Goal, Path) :-
    findall([M,N|Rest], (edge(N, M), \+ member(M, [N|Rest])), Children),
    append(Others, Children, NewQueue),      % APPEND -> a FIFO queue
    bfs_queue(NewQueue, Goal, Path).

% ?- bfs(a, g, P).   % P = [a,c,g]  -- the SHORT way, found first

% Step 4: Experiment 11: compare the paths
compare_searches(Start, Goal) :-
    once(dfs(Start, Goal, DP)), length(DP, DL),     % the FIRST path each one finds
    once(bfs(Start, Goal, BP)), length(BP, BL),
    format("DFS: ~w (~w nodes)~nBFS: ~w (~w nodes)~n", [DP, DL, BP, BL]).
% [Corrected: without once/1, dfs/3 and bfs/3 each find both paths on
% backtracking, so compare_searches printed four comparisons and succeeded four
% times.]

% ?- compare_searches(a, g).
%   DFS: [a,b,d,e,g] (5 nodes)
%   BFS: [a,c,g] (3 nodes)
%
% THE ONLY DIFFERENCE IS append(Others, Children, Q) versus
% append(Children, Others, Q). Appending children at the BACK gives a FIFO
% queue and breadth-first order; at the FRONT gives a LIFO stack and
% depth-first. One argument order is the whole distinction between the two
% algorithms, and it is worth showing the examiner.

The Python check, 03_uninformed_search.py, for experiments 8–11:

"""Experiments 9, 10, 11 — DFS, BFS and uniform cost search.

Run on Russell & Norvig's Romania map, so every figure can be checked against
the textbook as well as against this code. unit-2.md section 2.7 quotes these
numbers.

The three algorithms are the SAME LOOP with a different frontier -- a queue, a
stack, a priority queue -- and the code is written to make that obvious.
"""
import heapq
from collections import deque

from fixtures import GOAL, GRAPH_EDGES, ROMANIA, START, path_cost


# --- the three strategies: one loop, three frontiers ------------------------

def bfs(graph, start, goal):
    """FIFO queue -> expand the SHALLOWEST node."""
    frontier = deque([[start]])
    reached = {start}
    expanded = 0
    while frontier:
        path = frontier.popleft()
        expanded += 1
        if path[-1] == goal:
            return path, expanded
        for nxt in graph[path[-1]]:
            if nxt not in reached:
                reached.add(nxt)
                frontier.append(path + [nxt])
    return None, expanded


def dfs(graph, start, goal):
    """LIFO stack -> expand the DEEPEST node."""
    frontier = [[start]]
    explored = set()
    expanded = 0
    while frontier:
        path = frontier.pop()
        if path[-1] in explored:
            continue
        explored.add(path[-1])
        expanded += 1
        if path[-1] == goal:
            return path, expanded
        for nxt in reversed(list(graph[path[-1]])):
            if nxt not in explored:
                frontier.append(path + [nxt])
    return None, expanded


def ucs(graph, start, goal):
    """Priority queue on g(n) -> expand the CHEAPEST path so far."""
    frontier = [(0, [start])]
    best = {}
    expanded = 0
    while frontier:
        cost, path = heapq.heappop(frontier)
        node = path[-1]
        if node in best and best[node] <= cost:
            continue
        best[node] = cost
        expanded += 1
        # The goal test happens on EXPANSION, not generation -- a cheaper
        # path to the goal may still be waiting in the frontier.
        if node == goal:
            return path, expanded, cost
        for nxt, step in graph[node].items():
            heapq.heappush(frontier, (cost + step, path + [nxt]))
    return None, expanded, None


# --- the experiments ---------------------------------------------------------

def the_three_compared():
    """unit-2.md 2.7's table, reproduced exactly."""
    bfs_path, bfs_exp = bfs(ROMANIA, START, GOAL)
    dfs_path, dfs_exp = dfs(ROMANIA, START, GOAL)
    ucs_path, ucs_exp, ucs_cost = ucs(ROMANIA, START, GOAL)

    assert (bfs_exp, path_cost(bfs_path)) == (9, 450), (bfs_exp, path_cost(bfs_path))
    assert (dfs_exp, path_cost(dfs_path)) == (6, 607), (dfs_exp, path_cost(dfs_path))
    assert (ucs_exp, ucs_cost) == (13, 418), (ucs_exp, ucs_cost)

    assert bfs_path == ["Arad", "Sibiu", "Fagaras", "Bucharest"]
    assert ucs_path == ["Arad", "Sibiu", "Rimnicu Vilcea", "Pitesti", "Bucharest"]

    # BFS found the path with the fewest EDGES -- but not the cheapest.
    assert len(bfs_path) - 1 == 3
    assert len(ucs_path) - 1 == 4
    assert path_cost(bfs_path) > ucs_cost, "fewer edges, MORE kilometres"

    print(f"  {'strategy':14} {'expanded':>9} {'edges':>6} {'cost':>6}  path")
    for name, p, e, c in (("BFS", bfs_path, bfs_exp, path_cost(bfs_path)),
                          ("DFS", dfs_path, dfs_exp, path_cost(dfs_path)),
                          ("Uniform cost", ucs_path, ucs_exp, ucs_cost)):
        print(f"  {name:14} {e:>9} {len(p) - 1:>6} {c:>6}  {' -> '.join(p)}")
    print("       BFS found the fewest EDGES (3) and 450 km, not the cheapest.")
    print("       Step costs are unequal here, so its optimality guarantee")
    print("       does not apply.")
    print("       DFS expanded fewest and found the WORST path, 607 km.")
    print("       UCS found the optimal 418 and expanded the MOST, 13.")
    print("       The optimal route runs through Rimnicu Vilcea and Pitesti,")
    print("       and NEITHER BFS NOR DFS finds it")
    return ucs_cost


def ucs_is_dijkstra(optimal):
    """UCS computes the shortest distance to EVERY city, like Dijkstra."""
    distances = {}
    frontier = [(0, START)]
    while frontier:
        cost, node = heapq.heappop(frontier)
        if node in distances:
            continue
        distances[node] = cost
        for nxt, step in ROMANIA[node].items():
            if nxt not in distances:
                heapq.heappush(frontier, (cost + step, nxt))

    assert len(distances) == len(ROMANIA) == 20
    assert distances["Bucharest"] == optimal == 418
    assert distances["Arad"] == 0
    assert distances["Sibiu"] == 140
    assert distances["Rimnicu Vilcea"] == 220, distances["Rimnicu Vilcea"]
    assert distances["Pitesti"] == 317, distances["Pitesti"]
    # 140 + 80 + 97 + 101 = 418, which is the optimal path, city by city.
    assert 140 + 80 + 97 + 101 == 418

    print(f"  shortest distance from Arad to each of {len(distances)} cities:")
    for city in ("Sibiu", "Rimnicu Vilcea", "Pitesti", "Bucharest", "Neamt"):
        print(f"    {city:16} {distances[city]:>4} km")
    print("       140 + 80 + 97 + 101 = 418, the optimal route accumulated")
    print("       one city at a time. UCS IS DIJKSTRA'S ALGORITHM -- the same")
    print("       procedure, reached from the AI side instead of graph theory")


def dfs_and_bfs_on_a_small_graph():
    """Experiments 9-11 proper: trace both on a graph small enough to check."""
    simple = {k: {v: 1 for v in vs} for k, vs in GRAPH_EDGES.items()}

    bfs_path, bfs_exp = bfs(simple, "a", "g")
    dfs_path, dfs_exp = dfs(simple, "a", "g")

    assert bfs_path == ["a", "c", "g"], bfs_path
    assert dfs_path == ["a", "b", "d", "e", "g"], dfs_path
    assert len(bfs_path) - 1 == 2 and len(dfs_path) - 1 == 4
    assert bfs_exp == dfs_exp == 5, (bfs_exp, dfs_exp)

    print("  graph:  a -> b,c    b -> d    d -> e    e -> g    c -> g")
    print(f"    BFS  {' -> '.join(bfs_path):24} {len(bfs_path) - 1} edges, "
          f"expanded {bfs_exp}")
    print(f"    DFS  {' -> '.join(dfs_path):24} {len(dfs_path) - 1} edges, "
          f"expanded {dfs_exp}")
    print("       SAME AMOUNT OF WORK, TWICE THE PATH. BFS explores level by")
    print("       level so it cannot miss the 2-edge route; DFS dived into b")
    print("       and committed to the long way round. That is the guarantee")
    print("       BFS gives and DFS does not")


def bfs_is_optimal_only_with_equal_step_costs():
    """The condition stated in the property table, demonstrated both ways."""
    unit = {k: {v: 1 for v in vs} for k, vs in GRAPH_EDGES.items()}
    bfs_p, _ = bfs(unit, "a", "g")
    ucs_p, _, ucs_c = ucs(unit, "a", "g")
    assert len(bfs_p) - 1 == ucs_c, "with UNIT costs, BFS's answer IS optimal"

    # Now make the SHORT route expensive; BFS cannot see the difference.
    weighted = {k: {v: 1 for v in vs} for k, vs in GRAPH_EDGES.items()}
    weighted["c"]["g"] = 50
    bfs_p2, _ = bfs(weighted, "a", "g")
    ucs_p2, _, ucs_c2 = ucs(weighted, "a", "g")

    assert bfs_p2 == ["a", "c", "g"], bfs_p2
    assert path_cost(bfs_p2, weighted) == 51, path_cost(bfs_p2, weighted)
    assert ucs_p2 == ["a", "b", "d", "e", "g"], ucs_p2
    assert ucs_c2 == 4, ucs_c2
    assert path_cost(bfs_p2, weighted) > ucs_c2

    print(f"  unit step costs  : BFS cost {len(bfs_p) - 1}, UCS cost {ucs_c}  -- EQUAL")
    print(f"  make c->g cost 50: BFS cost {path_cost(bfs_p2, weighted)} "
          f"({' -> '.join(bfs_p2)})")
    print(f"                     UCS cost {ucs_c2} ({' -> '.join(ucs_p2)})")
    print("       BFS counts EDGES, not cost. With equal step costs those are")
    print("       the same thing and BFS is optimal; the moment they differ,")
    print("       it is not. That is exactly what the property table says")


def iterative_deepening_is_not_wasteful():
    """unit-2.md 2.5's arithmetic: 123,456 against 111,111 at b=10, d=5."""
    def bfs_nodes(b, d):
        return sum(b ** i for i in range(d + 1))

    def ids_nodes(b, d):
        return sum((d + 1 - i) * b ** i for i in range(d + 1))

    b, d = 10, 5
    bfs_total = bfs_nodes(b, d)
    ids_total = ids_nodes(b, d)

    assert bfs_total == 111111, bfs_total
    assert ids_total == 123456, ids_total
    assert ids_total / bfs_total < 1.12

    print(f"  b = {b}, d = {d}:")
    print(f"    BFS generates {bfs_total:,} nodes")
    print(f"    IDS generates {ids_total:,} nodes  "
          f"({(ids_total / bfs_total - 1) * 100:.1f}% more)")
    print(f"    and IDS uses O(bd) = {b * d} memory instead of O(b^d) = {b ** d:,}")
    print("       the repetition is cheap because the BOTTOM LEVEL holds most")
    print("       of the nodes -- regenerating everything above it costs almost")
    print("       nothing. IDS is the preferred uninformed search when the")
    print("       depth is unknown")


def main():
    print("Experiments 9-11 -- Uninformed search: DFS, BFS, uniform cost")
    # Step 1: Compare BFS, DFS and uniform cost on the Romania map
    optimal = the_three_compared()
    # Step 2: See uniform cost as Dijkstra
    ucs_is_dijkstra(optimal)
    # Step 3: Run DFS and BFS on the six-node graph
    dfs_and_bfs_on_a_small_graph()
    # Step 4: Make one step cost more
    bfs_is_optimal_only_with_equal_step_costs()
    # Step 5: Count iterative deepening's extra nodes
    iterative_deepening_is_not_wasteful()


if __name__ == "__main__":
    main()

5. Execution and Results

In SWI-Prolog, 08_graph_search.pl:

?- dfs(a, g, P).
P = [a, b, d, e, g] ;
P = [a, c, g].

?- bfs(a, g, P).
P = [a, c, g] ;
P = [a, b, d, e, g].

?- compare_searches(a, g).
DFS: [a,b,d,e,g] (5 nodes)
BFS: [a,c,g] (3 nodes)
true.

The Python check, 03_uninformed_search.py, for experiments 8–11:

Experiments 9-11 -- Uninformed search: DFS, BFS, uniform cost
  strategy        expanded  edges   cost  path
  BFS                    9      3    450  Arad -> Sibiu -> Fagaras -> Bucharest
  DFS                    6      5    607  Arad -> Zerind -> Oradea -> Sibiu -> Fagaras -> Bucharest
  Uniform cost          13      4    418  Arad -> Sibiu -> Rimnicu Vilcea -> Pitesti -> Bucharest
       BFS found the fewest EDGES (3) and 450 km, not the cheapest.
       Step costs are unequal here, so its optimality guarantee
       does not apply.
       DFS expanded fewest and found the WORST path, 607 km.
       UCS found the optimal 418 and expanded the MOST, 13.
       The optimal route runs through Rimnicu Vilcea and Pitesti,
       and NEITHER BFS NOR DFS finds it
  shortest distance from Arad to each of 20 cities:
    Sibiu             140 km
    Rimnicu Vilcea    220 km
    Pitesti           317 km
    Bucharest         418 km
    Neamt             824 km
       140 + 80 + 97 + 101 = 418, the optimal route accumulated
       one city at a time. UCS IS DIJKSTRA'S ALGORITHM -- the same
       procedure, reached from the AI side instead of graph theory
  graph:  a -> b,c    b -> d    d -> e    e -> g    c -> g
    BFS  a -> c -> g              2 edges, expanded 5
    DFS  a -> b -> d -> e -> g    4 edges, expanded 5
       SAME AMOUNT OF WORK, TWICE THE PATH. BFS explores level by
       level so it cannot miss the 2-edge route; DFS dived into b
       and committed to the long way round. That is the guarantee
       BFS gives and DFS does not
  unit step costs  : BFS cost 2, UCS cost 2  -- EQUAL
  make c->g cost 50: BFS cost 51 (a -> c -> g)
                     UCS cost 4 (a -> b -> d -> e -> g)
       BFS counts EDGES, not cost. With equal step costs those are
       the same thing and BFS is optimal; the moment they differ,
       it is not. That is exactly what the property table says
  b = 10, d = 5:
    BFS generates 111,111 nodes
    IDS generates 123,456 nodes  (11.1% more)
    and IDS uses O(bd) = 50 memory instead of O(b^d) = 100,000
       the repetition is cheap because the BOTTOM LEVEL holds most
       of the nodes -- regenerating everything above it costs almost
       nothing. IDS is the preferred uninformed search when the
       depth is unknown

In SWI-Prolog, dfs/3 and bfs/3 each find both paths: pressing ; after DFS's long way gives the short one, and the other way round for BFS. The order is the difference. Corrected: compare_searches/2 let both backtrack, so it printed four comparisons and succeeded four times; it now takes the first path each finds, with once/1, and prints one.

shortest distance from Arad:
  Sibiu           140 km
  Rimnicu Vilcea  220 km
  Pitesti         317 km
  Bucharest       418 km
  Neamt           824 km

The six-node graph — same work, twice the path:

a -> b, c    b -> d    d -> e    e -> g    c -> g

Identical work, twice the path. BFS explores level by level so it cannot miss the 2-edge route; DFS dived into b and committed to the long way round. That is exactly the guarantee BFS gives and DFS does not — stated as a measured fact rather than as a property table.

Experiment 12 — Greedy Best-First and A*

1. Question

Search the Romania map with Greedy Best-First search and A*.

2. Aim

Run A* with the straight-line heuristic, compare it with greedy and uniform cost, and check the heuristic is admissible.

3. Steps

In SWI-Prolog, 12_astar.pl:

1. State the map.
2. State the heuristic.
3. Search with A*.
4. Ask the query.

The Python check, 04_informed_search.py, for experiment 12:

1. Compare uniform cost, greedy and A*.
2. See why greedy goes wrong.
3. Run A* with h = 0.
4. Inflate the heuristic.
5. Check admissibility at every city.
6. Compare the 8-puzzle heuristics.

4. Programme

In SWI-Prolog, 12_astar.pl:

% Experiment 12 -- Greedy Best-First search and A* on the Romania map.
%
% Run it: swipl 12_astar.pl, then type a query at the ?- prompt -- or paste the
% file into https://swish.swi-prolog.org/. Each "% ?-" query below was asked of
% SWI-Prolog 9.0.4 by tools/data-science/prolog_lab.py, and the lab page shows
% what it answered. 04_informed_search.py checks the same logic in Python.
% [Changed: this said the file had never been run, as SWI-Prolog could not be
% installed where these labs are checked. It now installs from the Ubuntu archive.]
%
% pytholog cannot evaluate arithmetic, so 04_informed_search.py runs the search
% in Python, and reproduces Russell & Norvig's figures.

% Step 1: State the map
road(arad, zerind, 75).        road(arad, sibiu, 140).
road(arad, timisoara, 118).    road(zerind, oradea, 71).
road(oradea, sibiu, 151).      road(sibiu, fagaras, 99).
road(sibiu, rimnicu, 80).      road(rimnicu, pitesti, 97).
road(rimnicu, craiova, 146).   road(fagaras, bucharest, 211).
road(pitesti, bucharest, 101). road(craiova, pitesti, 138).

edge(X, Y, D) :- road(X, Y, D).
edge(X, Y, D) :- road(Y, X, D).

% Step 2: State the heuristic
% ADMISSIBLE by construction: a straight line can never be longer than a road.
h(arad, 366).      h(bucharest, 0).    h(craiova, 160).
h(fagaras, 176).   h(oradea, 380).     h(pitesti, 100).
h(rimnicu, 193).   h(sibiu, 253).      h(timisoara, 329).
h(zerind, 374).

% Step 3: Search with A*
astar(Start, Goal, Path, Cost) :-
    h(Start, H),
    astar_search([node(Start, [Start], 0, H)], Goal, RevPath, Cost),
    reverse(RevPath, Path).

astar_search([node(Goal, Path, G, _)|_], Goal, Path, G).
astar_search([node(N, Path, G, _)|Rest], Goal, Result, Cost) :-
    findall(node(M, [M|Path], G2, F2),
            ( edge(N, M, D),
              \+ member(M, Path),
              G2 is G + D,
              h(M, HM),
              F2 is G2 + HM ),
            Children),
    append(Rest, Children, All),
    sort_by_f(All, Sorted),                  % priority queue on f = g + h
    astar_search(Sorted, Goal, Result, Cost).

sort_by_f(Nodes, Sorted) :-
    map_list_to_pairs(f_of, Nodes, Pairs),
    keysort(Pairs, SortedPairs),
    pairs_values(SortedPairs, Sorted).
f_of(node(_, _, _, F), F).

% Step 4: Ask the query
% ?- astar(arad, bucharest, P, C).
%   P = [arad, sibiu, rimnicu, pitesti, bucharest],
%   C = 418
% Press ; and A* goes on to the other routes, in order of cost: 450 via
% Fagaras, then 575, 605, 607 and 762.
%
% GREEDY is the same predicate with f_of(node(_,_,_,H), H) -- ordering by h
% alone. It returns 450 via Fagaras, because Fagaras LOOKS closer (h=176 vs
% 193) and is further by road. Ignoring g is what makes greedy short-sighted.

The Python check, 04_informed_search.py, for experiment 12:

"""Experiment 12 — Greedy Best-First search and A*.

unit-3.md section 3.3's headline: A* finds the OPTIMAL 418 km route expanding
6 nodes where uniform cost search needs 13. And section 3.4's demonstration:
an INADMISSIBLE heuristic is faster and wrong.

Both are computed here on Russell & Norvig's Romania map.
"""
import heapq

from fixtures import (GOAL, ROMANIA, START, STRAIGHT_LINE, inflated,
                      path_cost)


def best_first(graph, start, goal, f):
    """One algorithm. f decides everything.

        f = g            -> uniform cost
        f = h            -> greedy best-first
        f = g + h        -> A*
    """
    frontier = [(f(start, 0), 0, [start])]
    best = {}
    expanded = 0
    while frontier:
        _, g, path = heapq.heappop(frontier)
        node = path[-1]
        if node in best and best[node] <= g:
            continue
        best[node] = g
        expanded += 1
        if node == goal:
            return path, expanded, g
        for nxt, step in graph[node].items():
            heapq.heappush(frontier, (f(nxt, g + step), g + step, path + [nxt]))
    return None, expanded, None


def ucs(graph, start, goal):
    return best_first(graph, start, goal, lambda n, g: g)


def greedy(graph, start, goal, h):
    return best_first(graph, start, goal, lambda n, g: h[n])


def astar(graph, start, goal, h):
    return best_first(graph, start, goal, lambda n, g: g + h[n])


def the_headline_comparison():
    """unit-3.md 3.3's table."""
    u_path, u_exp, u_cost = ucs(ROMANIA, START, GOAL)
    g_path, g_exp, _ = greedy(ROMANIA, START, GOAL, STRAIGHT_LINE)
    a_path, a_exp, a_cost = astar(ROMANIA, START, GOAL, STRAIGHT_LINE)
    g_cost = path_cost(g_path)

    assert (u_exp, u_cost) == (13, 418), (u_exp, u_cost)
    assert (g_exp, g_cost) == (4, 450), (g_exp, g_cost)
    assert (a_exp, a_cost) == (6, 418), (a_exp, a_cost)

    assert a_cost == u_cost, "A* found the SAME optimal cost as UCS"
    assert a_exp < u_exp / 2, "expanding less than half as many nodes"
    assert g_cost > a_cost, "greedy is faster still, and WRONG"

    print(f"  {'search':22} {'f(n)':12} {'expanded':>9} {'cost':>6}  optimal?")
    rows = [("Uniform cost", "g(n)", u_exp, u_cost, True),
            ("Greedy best-first", "h(n)", g_exp, g_cost, False),
            ("A*", "g(n) + h(n)", a_exp, a_cost, True)]
    for name, fn, exp, cost, opt in rows:
        print(f"  {name:22} {fn:12} {exp:>9} {cost:>6}  {'YES' if opt else 'NO'}")
    print(f"  greedy:  {' -> '.join(g_path)}")
    print(f"  A*:      {' -> '.join(a_path)}")
    print("       A* FOUND THE OPTIMAL 418 EXPANDING 6 NODES WHERE UCS NEEDED 13.")
    print("       Same answer, less than half the work -- that is why heuristics")
    print("       exist, and it is the number to quote")
    return u_exp, u_cost


def why_greedy_goes_wrong():
    """It ignores g(n) -- the cost already paid."""
    # At Sibiu the choice is Fagaras (h=176) or Rimnicu Vilcea (h=193).
    h_fagaras = STRAIGHT_LINE["Fagaras"]
    h_rimnicu = STRAIGHT_LINE["Rimnicu Vilcea"]
    assert h_fagaras < h_rimnicu, "Fagaras LOOKS closer"

    via_fagaras = ["Arad", "Sibiu", "Fagaras", "Bucharest"]
    via_rimnicu = ["Arad", "Sibiu", "Rimnicu Vilcea", "Pitesti", "Bucharest"]
    assert path_cost(via_fagaras) == 450
    assert path_cost(via_rimnicu) == 418
    assert path_cost(via_rimnicu) < path_cost(via_fagaras)

    print(f"  at Sibiu, greedy compares h only:")
    print(f"    h(Fagaras)        = {h_fagaras}   <- looks closer, so it goes here")
    print(f"    h(Rimnicu Vilcea) = {h_rimnicu}")
    print(f"  but the actual routes are:")
    print(f"    via Fagaras       = {path_cost(via_fagaras)} km")
    print(f"    via Rimnicu       = {path_cost(via_rimnicu)} km   <- 32 km shorter")
    print("       Fagaras IS closer as the crow flies and further by road.")
    print("       Greedy is short-sighted because it ignores g(n), the cost")
    print("       already paid -- which is exactly what A* adds back")


def astar_with_zero_heuristic_is_ucs(ucs_expanded, ucs_cost):
    """f = g + 0 = g. The same algorithm under a different name."""
    zero = {city: 0 for city in STRAIGHT_LINE}
    path, expanded, cost = astar(ROMANIA, START, GOAL, zero)

    assert (expanded, cost) == (ucs_expanded, ucs_cost) == (13, 418)

    print(f"  A* with h(n) = 0: expanded {expanded}, cost {cost}")
    print(f"  uniform cost    : expanded {ucs_expanded}, cost {ucs_cost}")
    print("       IDENTICAL. A* with a zero heuristic IS uniform cost search.")
    print("       A* sits between UCS (no information, optimal) and greedy")
    print("       (maximum information used badly, not optimal)")


def admissibility_is_what_guarantees_optimality():
    """unit-3.md 3.4: inflate the heuristic and A* becomes faster and WRONG."""
    rows = []
    for label, h in (("straight-line (admissible)", STRAIGHT_LINE),
                     ("straight-line x 2", inflated(2.0)),
                     ("straight-line x 5", inflated(5.0))):
        path, expanded, cost = astar(ROMANIA, START, GOAL, h)
        rows.append((label, expanded, cost, cost == 418, path))

    admissible = rows[0]
    doubled = rows[1]
    assert admissible[1:4] == (6, 418, True)
    assert doubled[1:4] == (4, 450, False), doubled
    assert doubled[1] < admissible[1], "the bad heuristic is FASTER"
    assert doubled[2] > admissible[2], "and WRONG"

    print(f"  {'heuristic':28} {'expanded':>9} {'cost':>6}  optimal?")
    for label, expanded, cost, opt, _ in rows:
        print(f"  {label:28} {expanded:>9} {cost:>6}  {'YES' if opt else 'NO'}")
    print(f"  the inflated heuristic returns: {' -> '.join(doubled[4])}")
    print("       THE INADMISSIBLE HEURISTIC IS FASTER AND WRONG -- 4 nodes")
    print("       instead of 6, and 450 instead of 418. Overestimating makes")
    print("       the node on the optimal path LOOK worse than an alternative,")
    print("       so A* commits to a goal before the better path is explored.")
    print("       The guarantee is gone the moment h(n) > h*(n) anywhere")


def check_the_heuristic_really_is_admissible():
    """h(n) <= h*(n) for every city -- verified against true shortest paths."""
    # True cost from every city to Bucharest, by running UCS backwards.
    true_cost = {}
    frontier = [(0, GOAL)]
    while frontier:
        cost, node = heapq.heappop(frontier)
        if node in true_cost:
            continue
        true_cost[node] = cost
        for nxt, step in ROMANIA[node].items():
            if nxt not in true_cost:
                heapq.heappush(frontier, (cost + step, nxt))

    violations = [(c, STRAIGHT_LINE[c], true_cost[c])
                  for c in true_cost if STRAIGHT_LINE[c] > true_cost[c]]
    assert violations == [], violations
    assert STRAIGHT_LINE[GOAL] == 0, "h(goal) must be 0"
    assert true_cost[START] == 418

    tightest = min(true_cost[c] - STRAIGHT_LINE[c]
                   for c in true_cost if c != GOAL)

    # And the inflated one DOES violate it -- which is the whole point.
    bad = inflated(2.0)
    bad_violations = [c for c in true_cost if bad[c] > true_cost[c]]
    assert len(bad_violations) > 10, len(bad_violations)

    print(f"  checked all {len(true_cost)} cities against their TRUE cost to "
          f"{GOAL}:")
    print(f"    straight-line violations: {len(violations)}  -- admissible")
    print(f"    h(Bucharest) = {STRAIGHT_LINE[GOAL]}")
    print(f"    tightest margin h*(n) - h(n) = {tightest} km")
    print(f"    the x2 heuristic violates admissibility at "
          f"{len(bad_violations)} of {len(true_cost)} cities")
    print("       a straight line can never be longer than a road, which is")
    print("       why this heuristic is admissible BY CONSTRUCTION rather than")
    print("       by luck -- and that is the argument to give in the exam")


def eight_puzzle_heuristics_and_dominance():
    """h2 dominates h1, so A* with h2 expands no more nodes."""
    goal = (1, 2, 3, 4, 5, 6, 7, 8, 0)
    state = (1, 2, 3, 4, 0, 6, 7, 5, 8)

    def misplaced(s):
        return sum(1 for i, v in enumerate(s) if v != 0 and v != goal[i])

    def manhattan(s):
        total = 0
        for i, v in enumerate(s):
            if v == 0:
                continue
            j = goal.index(v)
            total += abs(i // 3 - j // 3) + abs(i % 3 - j % 3)
        return total

    assert misplaced(goal) == 0 and manhattan(goal) == 0
    assert misplaced(state) == 2, misplaced(state)
    assert manhattan(state) == 2, manhattan(state)

    scrambled = (7, 2, 4, 5, 0, 6, 8, 3, 1)
    h1, h2 = misplaced(scrambled), manhattan(scrambled)
    # By hand: six tiles are out of place (7, 4, 5, 8, 3, 1), and their
    # Manhattan distances are 2 + 3 + 1 + 1 + 3 + 4 = 14.
    assert h1 == 6 and h2 == 14, (h1, h2)
    assert h2 >= h1, "h2 DOMINATES h1 -- it is always at least as large"

    print(f"  goal state:      h1 (misplaced) = 0, h2 (Manhattan) = 0")
    print(f"  one tile out:    h1 = {misplaced(state)}, h2 = {manhattan(state)}")
    print(f"  well scrambled:  h1 = {h1}, h2 = {h2}")
    print("       both come from RELAXED problems -- h1 lets a tile move")
    print("       anywhere, h2 lets it move to any adjacent square -- so both")
    print("       are admissible by construction.")
    print("       h2 >= h1 everywhere, so h2 DOMINATES h1 and A* with h2")
    print("       expands no more nodes. Dominance is the right way to compare")
    print("       heuristics, and a stronger claim than 'it was faster'")


def main():
    print("Experiment 12 -- Greedy Best-First search and A*")
    # Step 1: Compare uniform cost, greedy and A*
    ucs_exp, ucs_cost = the_headline_comparison()
    # Step 2: See why greedy goes wrong
    why_greedy_goes_wrong()
    # Step 3: Run A* with h = 0
    astar_with_zero_heuristic_is_ucs(ucs_exp, ucs_cost)
    # Step 4: Inflate the heuristic
    admissibility_is_what_guarantees_optimality()
    # Step 5: Check admissibility at every city
    check_the_heuristic_really_is_admissible()
    # Step 6: Compare the 8-puzzle heuristics
    eight_puzzle_heuristics_and_dominance()


if __name__ == "__main__":
    main()

5. Execution and Results

In SWI-Prolog, 12_astar.pl:

?- astar(arad, bucharest, P, C).
P = [arad, sibiu, rimnicu, pitesti, bucharest],
C = 418 ;
P = [arad, sibiu, fagaras, bucharest],
C = 450 ;
P = [arad, zerind, oradea, sibiu, rimnicu, pitesti, bucharest],
C = 575 ;
P = [arad, sibiu, rimnicu, craiova, pitesti, bucharest],
C = 605 ;
P = [arad, zerind, oradea, sibiu, fagaras, bucharest],
C = 607 ;
P = [arad, zerind, oradea, sibiu, rimnicu, craiova, pitesti, bucharest],
C = 762.

The Python check, 04_informed_search.py, for experiment 12:

Experiment 12 -- Greedy Best-First search and A*
  search                 f(n)          expanded   cost  optimal?
  Uniform cost           g(n)                13    418  YES
  Greedy best-first      h(n)                 4    450  NO
  A*                     g(n) + h(n)          6    418  YES
  greedy:  Arad -> Sibiu -> Fagaras -> Bucharest
  A*:      Arad -> Sibiu -> Rimnicu Vilcea -> Pitesti -> Bucharest
       A* FOUND THE OPTIMAL 418 EXPANDING 6 NODES WHERE UCS NEEDED 13.
       Same answer, less than half the work -- that is why heuristics
       exist, and it is the number to quote
  at Sibiu, greedy compares h only:
    h(Fagaras)        = 176   <- looks closer, so it goes here
    h(Rimnicu Vilcea) = 193
  but the actual routes are:
    via Fagaras       = 450 km
    via Rimnicu       = 418 km   <- 32 km shorter
       Fagaras IS closer as the crow flies and further by road.
       Greedy is short-sighted because it ignores g(n), the cost
       already paid -- which is exactly what A* adds back
  A* with h(n) = 0: expanded 13, cost 418
  uniform cost    : expanded 13, cost 418
       IDENTICAL. A* with a zero heuristic IS uniform cost search.
       A* sits between UCS (no information, optimal) and greedy
       (maximum information used badly, not optimal)
  heuristic                     expanded   cost  optimal?
  straight-line (admissible)           6    418  YES
  straight-line x 2                    4    450  NO
  straight-line x 5                    4    450  NO
  the inflated heuristic returns: Arad -> Sibiu -> Fagaras -> Bucharest
       THE INADMISSIBLE HEURISTIC IS FASTER AND WRONG -- 4 nodes
       instead of 6, and 450 instead of 418. Overestimating makes
       the node on the optimal path LOOK worse than an alternative,
       so A* commits to a goal before the better path is explored.
       The guarantee is gone the moment h(n) > h*(n) anywhere
  checked all 20 cities against their TRUE cost to Bucharest:
    straight-line violations: 0  -- admissible
    h(Bucharest) = 0
    tightest margin h*(n) - h(n) = 1 km
    the x2 heuristic violates admissibility at 18 of 20 cities
       a straight line can never be longer than a road, which is
       why this heuristic is admissible BY CONSTRUCTION rather than
       by luck -- and that is the argument to give in the exam
  goal state:      h1 (misplaced) = 0, h2 (Manhattan) = 0
  one tile out:    h1 = 2, h2 = 2
  well scrambled:  h1 = 6, h2 = 14
       both come from RELAXED problems -- h1 lets a tile move
       anywhere, h2 lets it move to any adjacent square -- so both
       are admissible by construction.
       h2 >= h1 everywhere, so h2 DOMINATES h1 and A* with h2
       expands no more nodes. Dominance is the right way to compare
       heuristics, and a stronger claim than 'it was faster'

In SWI-Prolog, astar/4 gives 418 first; press ; and it goes on to the other routes in order of cost — 450, 575, 605, 607 and 762 — because the queue is always sorted by f = g + h.

h(Fagaras)        = 176   <- looks closer, so it goes here
h(Rimnicu Vilcea) = 193

but the actual routes are 450 km via Fagaras and 418 km via Rimnicu — 32 km shorter. Fagaras is closer as the crow flies and further by road. Greedy is short-sighted because it ignores g(n), the cost already paid, which is precisely what A* adds back.

A* with h(n) = 0: expanded 13, cost 418
uniform cost    : expanded 13, cost 418

Admissibility, checked rather than assumed:

checked all 20 cities against their TRUE cost to Bucharest:
  straight-line violations: 0   -- admissible
  h(Bucharest) = 0
  tightest margin h*(n) - h(n) = 1 km
  the x2 heuristic violates admissibility at 18 of 20 cities

A straight line can never be longer than a road, so this heuristic is admissible by construction, not by luck. That is the argument to give in the exam — and the margin of 1 km shows how tight the bound is, which is what makes the heuristic good rather than merely valid.

8-puzzle: h2 dominates h1:

Both come from relaxed problems — h1 lets a tile move anywhere, h2 lets it move to any adjacent square — so both are admissible by construction. h2 ≥ h1 everywhere, so h2 dominates, and A with h2 expands no more nodes than A with h1. Dominance is the right way to compare two heuristics, and a far stronger claim than "it was faster on my example".

Experiment 13 — Map colouring

1. Question

Colour a map so that no two neighbouring regions share a colour, as a constraint satisfaction problem.

2. Aim

Colour Australia's seven regions with three colours by backtracking, and see why two are not enough.

3. Steps

In SWI-Prolog, 13_map_colouring.pl:

1. State the colours.
2. Write the constraints.
3. Ask the query.

The Python check, 05_csp_backtracking.py, for experiments 13 and 14:

1. Colour the map.
2. Try two colours.
3. Order by MRV and LCV.
4. Solve 8-Queens.
5. Count the solutions for each board size.