# Prolog/Search techniques

Prolog's default search algorithm is depth-first search (DFS), which is sometimes not convenient: DFS doesn't always find the solution for all problems, and when it does, it might not find the *optimal* solution.

Let's say we want to find the shortest path through a directed graph with nodes represented by symbols and arc by the predicate `arc/2`

. Then we can easily implement iterative deepening search to find the shortest path:

```
path(X, Z, Path) :-
length(Path, _),
path_r(X, Z, Path).
path_r(Z, Z, []).
path_r(X, Z, [X|Path]) :-
arc(X, Y),
path(Y, Z, Path).
```

`path/3`

backtracks over paths, ordered by length, if at least one path exists. Let's try it out:

```
?- path(a, g, P).
P = [a] ;
P = [a, b, f] ;
P = [a, c, d, f] ;
P = [a, b, c, d, f]
```

How this works: when `length/2`

is called with a variable first argument, it generates a list of the desired length containing fresh variables. When, in addition, the second argument is a variable, it backtracks over all possible lengths starting at zero and stepping by one. The helper predicate `path_r`

is called each time with a fixed path length.