Search Algorithms in Prolog
Prolog’s backtracking mechanism is, at its core, a search engine. In this chapter we build on that foundation to implement classic AI search algorithms, taking advantage of Prolog’s natural representation of graphs, states, and goals.
Loading Graph Data from a File
Rather than hard-coding edges inside the search modules, we keep the graph in a separate data file, graph_search/sample_graph.txt, using standard Prolog term syntax:
1 edge(albany, boston).
2 edge(albany, chicago).
3 edge(albany, detroit).
4 edge(boston, chicago).
5 edge(boston, eton).
6 edge(chicago, detroit).
7 edge(chicago, fresno).
8 %% ... 30 more edges spanning 20 cities ...
9 edge(portland, reno).
10 edge(quincy, reno).
The utility module graph_search/prolog/read_graph.pl reads this file and asserts each edge as a dynamic fact:
1 :- module(read_graph, [
2 load_graph/0,
3 load_graph/1,
4 clear_graph/0,
5 edge/2
6 ]).
7
8 :- dynamic edge/2.
9
10 %% clear_graph/0 - Remove all loaded edge/2 facts.
11 clear_graph :-
12 retractall(edge(_, _)).
13
14 %% load_graph/0 - Load graph from default file (sample_graph.txt
15 %% located next to this pack's prolog/ directory).
16 load_graph :-
17 source_file(read_graph:edge(_, _), SrcFile),
18 file_directory_name(SrcFile, PrologDir),
19 file_directory_name(PrologDir, ProjectDir),
20 atomic_list_concat([ProjectDir, '/sample_graph.txt'], DefaultFile),
21 load_graph(DefaultFile).
22
23 %% load_graph/1 - Load graph from a specified file
24 %% Reads lines of the form: edge(Source, Destination).
25 %% Clears any previously loaded edges first. Malformed terms
26 %% are counted and reported as a warning when reading finishes.
27 load_graph(File) :-
28 clear_graph,
29 setup_call_cleanup(
30 open(File, read, Stream),
31 read_edges(Stream, 0, Skipped),
32 close(Stream)
33 ),
34 ( Skipped > 0
35 -> print_message(warning, read_graph_skipped(Skipped))
36 ; true
37 ).
38
39 read_edges(Stream, Skip0, Skip) :-
40 read_term(Stream, Term, []),
41 ( Term == end_of_file
42 -> Skip = Skip0
43 ; ( Term = edge(From, To)
44 -> assertz(edge(From, To)),
45 Skip1 = Skip0
46 ; Skip1 is Skip0 + 1
47 ),
48 read_edges(Stream, Skip1, Skip)
49 ).
clear_graph/0 removes all loaded edge/2 facts. load_graph/1 calls it first, then reports a warning if any malformed terms were skipped.
This design makes it easy to swap in different graphs without touching the search algorithms.
Depth-First and Breadth-First Search
With the graph loaded dynamically, the search modules simply import edge/2 from read_graph. Depth-first search explores as deep as possible along each branch before backtracking, using a visited list for cycle detection. Here is graph_search/prolog/dfs.pl:
1 :- use_module(read_graph, [edge/2]).
2
3 %% dfs(+Start, +Goal, -Path)
4 dfs(Start, Goal, Path) :-
5 dfs(Start, Goal, [Start], Path).
6
7 dfs(Goal, Goal, Visited, Path) :-
8 reverse(Visited, Path).
9 dfs(Current, Goal, Visited, Path) :-
10 edge(Current, Next),
11 \+ member(Next, Visited),
12 dfs(Next, Goal, [Next|Visited], Path).
Breadth-first search instead explores all neighbors at the current depth before moving deeper, using an explicit queue of partial paths. Here is graph_search/prolog/bfs.pl:
1 :- use_module(read_graph, [edge/2]).
2
3 %% bfs(+Start, +Goal, -Path)
4 bfs(Start, Goal, Path) :-
5 bfs_queue([[Start]], Goal, Path).
6
7 bfs_queue([[Goal|Visited]|_], Goal, Path) :-
8 reverse([Goal|Visited], Path).
9 bfs_queue([[Current|Visited]|Rest], Goal, Path) :-
10 findall(
11 [Next, Current|Visited],
12 (edge(Current, Next), \+ member(Next, [Current|Visited])),
13 Children
14 ),
15 append(Rest, Children, NewQueue),
16 bfs_queue(NewQueue, Goal, Path).
Running these on our 20-node city graph:
1 ?- dfs(albany, reno, Path).
2 Path = [albany, boston, chicago, detroit, gary, houston, irving, ...]
3
4 ?- bfs(albany, reno, Path).
5 Path = [albany, boston, eton, kent, naples, portland, reno]
Notice that BFS finds the shortest path (7 nodes), while DFS may explore a longer route through the interior of the graph.
Iterative Deepening
Depth-First Search (DFS) has a major space advantage: it only needs to store the path it is currently exploring, meaning its memory consumption is linear with the maximum depth of the search tree, 
. However, DFS is not complete on infinite graphs and is not guaranteed to find the shortest path (as we saw on our city graph). Breadth-First Search (BFS) is complete and guarantees the shortest path, but its memory consumption is exponential, 
(where 
is the branching factor), because it must store all active paths in its queue.
Iterative Deepening Search (IDS) combines the best of both worlds: the space efficiency of DFS with the completeness and optimality of BFS.
IDS operates by repeatedly running a depth-limited DFS, starting with a depth limit of 1, and incrementing the limit on each iteration. Although it seems wasteful to re-explore the top parts of the search tree multiple times, the number of nodes at depth 
grows exponentially, so the overhead of re-exploring the shallower levels is minimal (usually under 11% for binary trees).
Custom Pure Prolog Implementation
In Prolog, we can implement IDS very elegantly. We use the built-in predicate between/3 to generate depth limits starting from 1, and then call a custom depth-limited DFS predicate:
1 %% ids(+Start, +Goal, -Path)
2 %% Iterative Deepening Search: increases depth limit incrementally.
3 ids(Start, Goal, Path) :-
4 between(1, 100, DepthLimit),
5 depth_limited_dfs(Start, Goal, [Start], DepthLimit, Path).
6
7 %% depth_limited_dfs(+Current, +Goal, +Visited, +Limit, -Path)
8 depth_limited_dfs(Goal, Goal, Visited, _, Path) :-
9 !,
10 reverse(Visited, Path).
11 depth_limited_dfs(Current, Goal, Visited, Limit, Path) :-
12 Limit > 0,
13 edge(Current, Next),
14 \+ member(Next, Visited),
15 NextLimit is Limit - 1,
16 depth_limited_dfs(Next, Goal, [Next|Visited], NextLimit, Path).
Because of Prolog’s backtracking, if depth_limited_dfs/5 fails to find the goal within the current DepthLimit, Prolog backtracks to between/3, which increments DepthLimit to the next integer, and the search starts again with the larger limit. Like BFS, this guarantees that the first path found is the shortest path.
Built-in Support: call_with_depth_limit/3
SWI-Prolog also provides a built-in meta-predicate called call_with_depth_limit(:Goal, +Limit, -Result). This limits the depth of execution of any arbitrary Prolog goal (measured by the depth of the call stack).
If the goal succeeds within the limit, Result is unified with the number of stack frames used. If the limit is reached, Result unifies with the atom depth_limit_exceeded. We can use this to build a general-purpose iterative deepening search wrapper over our standard, unbounded dfs/3 predicate:
1 %% ids_builtin(+Start, +Goal, -Path)
2 ids_builtin(Start, Goal, Path) :-
3 between(1, 100, Limit),
4 call_with_depth_limit(dfs(Start, Goal, Path), Limit, Result),
5 Result \= depth_limit_exceeded.
This built-in approach is useful when you want to impose depth limits on complex reasoning rules or when wrapping existing code, though writing a custom depth_limited_dfs/5 predicate (as shown above) is usually preferred for finer search control.
A* Heuristic Search
A* combines the actual path cost with a heuristic estimate of the remaining distance to the goal. By maintaining an open list sorted by f-cost (g + h), it explores the most promising paths first. Here is graph_search/prolog/astar.pl:
1 :- module(astar, [
2 astar/4,
3 distance_heuristic/2,
4 zero_heuristic/2
5 ]).
6
7 :- use_module(read_graph, [edge/2]).
8
9 %% A* search with a closed set holding best-known g values.
10 %% When a popped node's recorded g is worse than the closed g for
11 %% that node, it is skipped (lazy re-opening); otherwise it is
12 %% closed and expanded. Heuristic may be a callable term.
13 astar(Start, Goal, Heuristic, Path) :-
14 safe_call(Heuristic, Start, H0),
15 astar_loop([node(H0, 0, [Start])], Goal, Heuristic, [], Path).
16
17 astar_loop([node(_, _, [Goal|Rest])|_], Goal, _, _Closed, Path) :-
18 !,
19 reverse([Goal|Rest], Path).
20 astar_loop([node(_, G, [Current|_])|Open], Goal, Heuristic, Closed, Path) :-
21 best_g(Current, Closed, GBest),
22 G >= GBest,
23 !, % stale entry: skip it
24 astar_loop(Open, Goal, Heuristic, Closed, Path).
25 astar_loop([node(_, G, [Current|Rest])|Open], Goal, Heuristic, Closed, Path) :-
26 \+ best_g(Current, Closed, _),
27 findall(
28 node(F1, G1, [Next, Current|Rest]),
29 ( edge(Current, Next),
30 \+ member(Next, [Current|Rest]),
31 G1 is G + 1,
32 safe_call(Heuristic, Next, H),
33 F1 is G1 + H
34 ),
35 Children
36 ),
37 append(Open, Children, Unsorted),
38 sort(1, @=<, Unsorted, Sorted),
39 astar_loop(Sorted, Goal, Heuristic, [best_g(Current, G)|Closed], Path).
40
41 %% best_g(+Node, +Closed, -G), G is the best g recorded for Node.
42 best_g(Node, [best_g(Node, G)|_], G) :- !.
43 best_g(Node, [_|Closed], G) :- best_g(Node, Closed, G).
44
45 %% Safe call: evaluate Heuristic(Node, Value). Only an undefined
46 %% heuristic predicate (existence error) falls back to 0; any
47 %% other exception propagates to the caller.
48 safe_call(Callable, Node, Value) :-
49 catch(call(Callable, Node, Value),
50 error(existence_error(_, _), _),
51 Value = 0).
52
53 %% Zero heuristic: admissible for uniform-weight graphs (all edge
54 %% weights = 1).
55 %% Useful as a baseline for testing A* correctness.
56 zero_heuristic(_, 0).
57
58 %% Example heuristic: estimated remaining distance to goal (reno).
59 %% Rough estimates for the sample_graph cities, admissible for
60 %% uniform-weight graph.
61 distance_heuristic(reno, 0).
62 distance_heuristic(portland, 1).
63 distance_heuristic(quincy, 1).
64 distance_heuristic(omaha, 2).
65 distance_heuristic(naples, 2).
66 distance_heuristic(memphis, 3).
67 distance_heuristic(lansing, 3).
68 distance_heuristic(kent, 3).
69 distance_heuristic(jackson, 4).
70 distance_heuristic(irving, 4).
71 distance_heuristic(houston, 4).
72 distance_heuristic(gary, 5).
73 distance_heuristic(fresno, 5).
74 distance_heuristic(eton, 5).
75 distance_heuristic(detroit, 5).
76 distance_heuristic(chicago, 6).
77 distance_heuristic(boston, 6).
78 distance_heuristic(albany, 7).
1 ?- astar(albany, reno, distance_heuristic, Path).
2 Path = [albany, detroit, houston, lansing, omaha, portland, reno]
The heuristic guides A* directly toward the goal, avoiding the unnecessary exploration of interior nodes that DFS would visit.
State-Space Search and Puzzle Solving
Many classic AI problems can be modeled as State-Space Search. In this paradigm, we define:
- State representation: A data structure representing the current configuration of the world (typically a Prolog compound term).
- Initial state: The starting configuration.
- Goal state: The target configuration we want to reach.
- State transitions (moves): Legal actions that transform one state into another.
- Constraints: Conditions that states must satisfy to be considered valid or safe.
Prolog is uniquely suited for state-space search because of its built-in backtracking and pattern matching. We can implement search algorithms (like DFS) to traverse the states automatically, and use unification to check if our current state matches the goal state.
The Farmer, Fox, Chicken, and Grain Puzzle
To illustrate, we solve the classic river crossing puzzle: a farmer must transport a fox, a chicken, and a sack of grain from the left bank of a river to the right bank. The constraints are:
- The farmer’s boat can only carry the farmer and at most one other item.
- If the farmer leaves the fox and chicken alone on a bank, the fox eats the chicken.
- If the farmer leaves the chicken and grain alone on a bank, the chicken eats the grain.
We represent the state as a compound term: state(Farmer, Fox, Chicken, Grain), where each argument can be either left or right to indicate which bank the item is currently on.
The puzzle_solver project implements this solver. Here is the complete file puzzle_solver/prolog/farmer.pl:
1 %% farmer.pl - Farmer, Fox, Chicken, Grain river crossing puzzle
2 %% Demonstrates state-space search with Prolog backtracking
3 :- module(farmer, [
4 solve_farmer/1
5 ]).
6
7 %% State: state(Farmer, Fox, Chicken, Grain) where each is 'left' or
8 %% 'right'
9 %% Goal: all on the right bank
10
11 solve_farmer(Moves) :-
12 InitState = state(left, left, left, left),
13 GoalState = state(right, right, right, right),
14 solve(InitState, GoalState, [InitState], RevMoves),
15 reverse(RevMoves, Moves).
16
17 solve(Goal, Goal, _Visited, []).
18 solve(State, Goal, Visited, [Description|Moves]) :-
19 move(State, NextState, Description),
20 safe(NextState),
21 \+ member(NextState, Visited),
22 solve(NextState, Goal, [NextState|Visited], Moves).
23
24 %% Moves: farmer always crosses, optionally carrying one item.
25 %% Each move is expressed once; opposite/2 supplies the two
26 %% directions, so only 4 rules are needed instead of 8.
27 move(state(From,F,C,G), state(To,F,C,G), farmer_alone) :-
28 opposite(From, To).
29 move(state(From,From,C,G), state(To,To,C,G), farmer_fox) :-
30 opposite(From, To).
31 move(state(From,F,From,G), state(To,F,To,G), farmer_chicken) :-
32 opposite(From, To).
33 move(state(From,F,C,From), state(To,F,C,To), farmer_grain) :-
34 opposite(From, To).
35
36 %% opposite(+Bank, -OtherBank), the two river banks.
37 opposite(left, right).
38 opposite(right, left).
39
40 %% Safety: a state is unsafe when the fox and chicken (or chicken
41 %% and grain) share a bank while the farmer is on the opposite
42 %% bank. Pure head-pattern matching via opposite/2, no ==/2.
43 safe(State) :-
44 \+ unsafe(State).
45
46 unsafe(state(Farmer, Bank, Bank, _)) :-
47 opposite(Farmer, Bank). % fox left with chicken
48 unsafe(state(Farmer, _, Bank, Bank)) :-
49 opposite(Farmer, Bank). % chicken left with grain
Constraint-Based Search: The N-Queens Problem
A third powerful paradigm for search in Prolog is Constraint Logic Programming, specifically Constraint Logic Programming over Finite Domains (CLP(FD)). Instead of manually coding depth-first search or backtracking state transitions, you define variables, their domains, and the relationships (constraints) that must hold true. Prolog’s constraint solver then automatically propagates these constraints to prune the search space and find valid assignments.
To illustrate this, we can look at the classic N-Queens problem, which asks how to place 
queens on an 
chessboard such that no two queens can attack each other. This means no two queens can share the same row, column, or diagonal.
The companion project n_queens implements this solver. Here is the complete file n_queens/prolog/queens.pl:
1 :- module(queens, [
2 n_queens/2,
3 n_queens/3
4 ]).
5
6 :- use_module(library(clpfd)).
7
8 %% n_queens(+N:int, -Queens:list) is nondet
9 %% Queens is a list of column positions for queens in each row.
10 n_queens(N, Queens) :-
11 n_queens(N, [], Queens).
12
13 %% n_queens(+N:int, +Options:list, -Queens:list) is nondet
14 %% Options:
15 %% ff_opt(true) label with labeling([ff], Queens)
16 %% (first-fail heuristic); otherwise label/1 is used.
17 n_queens(N, Options, Queens) :-
18 length(Queens, N),
19 Queens ins 1..N,
20 safe_queens(Queens),
21 ( member(ff_opt(true), Options)
22 -> labeling([ff], Queens)
23 ; label(Queens)
24 ).
25
26 safe_queens([]).
27 safe_queens([Q|Qs]) :-
28 safe_queen(Q, Qs, 1),
29 safe_queens(Qs).
30
31 safe_queen(_, [], _).
32 safe_queen(Q, [Q1|Qs], D) :-
33 Q #\= Q1,
34 Q #\= Q1 + D,
35 Q #\= Q1 - D,
36 D1 #= D + 1,
37 safe_queen(Q, Qs, D1).
n_queens/3 takes an options list. ff_opt(true) selects the first-fail labelling heuristic labeling([ff], Queens), which is much faster for large N.
How the CLP(FD) Search Works
- Representation: We represent the board as a list of length called
Queens. The index of an element in the list represents the row number (1 to), and the value at that index represents the column number of the queen in that row.
- Domain:
Queens ins 1..Nestablishes that each variable in theQueenslist must be an integer between
and .
- Column Constraints: Since each row has exactly one queen, we only need to ensure no two queens share a column. By using the list representation, the index ensures row uniqueness. The column constraint
Q #\= Q1(insafe_queen/3) ensures that no two queens share the same column. -
Diagonal Constraints: Two queens at columns
and 
separated by 
rows are on the same diagonal if 
. This is elegantly modeled using two inequality constraints:
Q #\= Q1 + D(upper-diagonal check)Q #\= Q1 - D(lower-diagonal check)
- Labeling:
label(Queens)tells the constraint solver to perform the backtracking search to assign concrete values to the variables in theQueenslist that satisfy all constraints.
Running the Solver
You can run queries in the REPL to solve for a specific size :
1 ?- n_queens(8, Queens).
2 Queens = [1, 5, 8, 6, 3, 7, 2, 4] .
To count the total number of solutions for an 8x8 board:
1 ?- aggregate_all(count, n_queens(8, _), Count).
2 Count = 92.
CLP(FD) propagation dramatically prunes the search space relative to a naive backtracking search, and the first-fail labelling option keeps larger boards tractable.
Optional Practice Problems
- Weighted Graph Search: In the
graph_searchproject, modify the graph definition to include edge weights. Then implement a uniform-cost search (or Dijkstra’s algorithm) to find the shortest path between two nodes in terms of cumulative edge weights. - Farmer Puzzle Variation: In the
puzzle_solverproject, adapt thefarmer.plrules to allow the boat to hold the farmer and up to two items, but add a new constraint that the wolf and the goat cannot be left alone on either bank, nor can the goat and the cabbage.