Search Strategies

8-puzzle, missionaries & cannibals, wolf-goat-cabbage, zebra puzzle (Einstein's riddle), map coloring — all natural in Prolog (try them with both search and CLP(FD)).

34.1 State-space search framework

% Water jugs: 4L and 3L; goal: exactly 2L in the 4L jug
move(s(A, B), s(4, B)) :- A < 4.                       % fill A
move(s(A, B), s(A, 3)) :- B < 3.                       % fill B
move(s(A, B), s(0, B)) :- A > 0.                       % empty A
move(s(A, B), s(A, 0)) :- B > 0.                       % empty B
move(s(A, B), s(A1, B1)) :- A > 0, B < 3, T is min(A, 3 - B), A1 is A - T, B1 is B + T.  % pour A→B
move(s(A, B), s(A1, B1)) :- B > 0, A < 4, T is min(B, 4 - A), A1 is A + T, B1 is B - T.  % pour B→A
goal(s(2, _)).

34.2 Depth-first search (with cycle check)

dfs(S, Path) :- dfs(S, [S], Rev), reverse(Rev, Path).
dfs(S, Visited, Visited) :- goal(S).
dfs(S, Visited, Path) :- move(S, S1), \+ memberchk(S1, Visited), dfs(S1, [S1|Visited], Path).

34.3 Iterative deepening (complete, memory-efficient)

id_search(S, Path) :- length(Path, _), path_from(S, Path).   % length/2 enumerates depths
path_from(S, [S]) :- goal(S).
path_from(S, [S|Ps]) :- move(S, S1), path_from(S1, Ps).

34.4 Breadth-first search (shortest path)

bfs(Start, Path) :- bfs_([[Start]], [Start], Rev), reverse(Rev, Path).
bfs_([[S|Ps]|_], _, [S|Ps]) :- goal(S), !.
bfs_([[S|Ps]|Queue], Seen, Sol) :-
    findall([S1, S|Ps], (move(S, S1), \+ memberchk(S1, Seen)), Next),
    findall(S1, member([S1|_], Next), New), append(Seen, New, Seen1),
    append(Queue, Next, Queue1),
    bfs_(Queue1, Seen1, Sol).

?- bfs(s(0, 0), P).

34.5 A* search

:- use_module(library(heaps)).

astar(Start, Path, Cost) :-
    h(Start, H0),
    singleton_heap(Heap, H0, n(Start, 0, [Start])),
    astar_(Heap, [], RevPath, Cost),
    reverse(RevPath, Path).

astar_(Heap, _, Path, G) :-
    get_from_heap(Heap, _, n(S, G, Path), _), goal(S), !.
astar_(Heap0, Closed, Path, Cost) :-
    get_from_heap(Heap0, _, n(S, G, P), Heap1),
    (   memberchk(S, Closed) -> astar_(Heap1, Closed, Path, Cost)
    ;   findall(F-n(S1, G1, [S1|P]),
                ( arc(S, S1, C), G1 is G + C, h(S1, H), F is G1 + H ), Children),
        foldl([K-V, H0, H1]>>add_to_heap(H0, K, V, H1), Children, Heap1, Heap2),
        astar_(Heap2, [S|Closed], Path, Cost)
    ).
% Provide arc/3 (successor with cost), h/2 (admissible heuristic), goal/1.

34.6 Game search: minimax with alpha-beta

minimax(Pos, BestMove, Val) :-
    findall(M, move(Pos, M), Moves), Moves \== [], !,
    best(Moves, BestMove, Val).
minimax(Pos, _, Val) :- static_value(Pos, Val).
% best/3 picks max for the maximizing player, min for the opponent; alpha-beta prunes branches.

34.7 Classic puzzles

8-puzzle, missionaries & cannibals, wolf-goat-cabbage, zebra puzzle (Einstein's riddle), map coloring — all natural in Prolog (try them with both search and CLP(FD)).

% Map coloring with CLP(FD)
color_map([WA, NT, SA, Q, NSW, V, T]) :-
    [WA, NT, SA, Q, NSW, V, T] ins 1..3,
    WA #\= NT, WA #\= SA, NT #\= SA, NT #\= Q, SA #\= Q,
    SA #\= NSW, SA #\= V, Q #\= NSW, NSW #\= V,
    label([WA, NT, SA, Q, NSW, V, T]).