Collecting solutions: findall, setof, and minimum-cost paths

Backtracking finds one solution at a time

A bare Prolog query yields solutions one at a time on backtracking. To reason about *all* solutions at once — count them, sort them, pick the cheapest — you need a meta-predicate that collects them into a list. The two you must know:

- findall(Template, Goal, List) — runs Goal exhaustively and collects every instantiation of Template into List. Keeps duplicates, preserves solution order, and returns [] if Goal never succeeds. - setof(Template, Goal, List) — like findall but the result is sorted and duplicate-free (it is a *set*). Crucially, sorting on a compound term like [Cost, Path] sorts by Cost first — which is how you find a minimum.

The collect-all-then-pick-best pattern

Optimisation in Prolog is usually two moves: (1) enumerate every candidate with findall/setof, then (2) pick the best. For a minimum-cost path (the A1 min_path task), weight the edges and collect [Cost, Path] pairs; because setof sorts ascending, the head of the sorted list is the cheapest.

Worked example — minimum-cost path (A1)

edge(a, b, 3). edge(b, c, 1). edge(c, d, 2). edge(b, d, 5).

path(G, G, _, [G], 0).
path(N, G, V, [N | P], Cost) :-
    edge(N, Nx, W), \+ member(Nx, V),
    path(Nx, G, [Nx | V], P, C1), Cost is W + C1.

min_path(S, G, Path, Cost) :-
    setof([C, P], path(S, G, [S], P, C), [[Cost, Path] | _]).

The path/5 predicate is the acyclic finder from the previous lesson, now also threading a running cost (each step adds its edge weight W). min_path calls setof to gather every [Cost, Path] pair; setof sorts them ascending by cost, and the pattern [[Cost, Path] | _] peels off the head — the minimum.

For this graph the candidate paths from a to d are a→b→c→d (cost 3+1+2 = 6) and a→b→d (cost 3+5 = 8). setof sorts to [[6, [a,b,c,d]], [8, [a,b,d]]], so min_path returns the cost-6 route. The Python exercise enumerates the same paths and takes the minimum by cost.