Cautarea unei solutii in spatiul starilor poate fi inteleasa cel mai simplu ca si o cautare a unui drum intr-un graf. Astfel, daca putem trece din starea S1 in starea S2, este ca si cum ar exista un arc directionat intre S1 si S2. In continuare consideram aceste arce reprezentate printr-un predicat s(S1,S2). De exemplu pentru un careu de 10x10 acest predicat poate fi:

    s((X,Y), (X1,Y1)) :-
            X < 10, X1 is X+1, Y1 is Y; X > 1, X1 is X-1, Y1 is Y;
            Y < 10, Y1 is Y+1, X1 is X; Y > 1, Y1 is Y-1, X1 is X.

unde starea consta in coordonatele X si Y la un moment dat.

Exista doua metode de cautare: in adancime (depthfirst search) si in latime (breadthfirst search).

Principiul cautarii in adancime implementeaza ideea ca "daca exista un arc de la nodul A la nodul B si exista un drum de la nodul B la nodul Z, atunci exista un drum intre nodul A si Z". Pentru a evita ciclurile se retine si drumul pina la nodul curent.

    depthfirst(Path, Node, Target, [Node|Path]) :-
        Node = Target.
    depthfirst(Path, Node, Target, Sol) :-
        s(Node,Node1),
        \+ member(Node1, Path),
        depthfirst([Node|Path], Node1, Target, Sol).

    solve(StartNode, TargetNode, Solution) :-
        depthfirst([], StartNode, TargetNode, Solution).
 

Daca algoritmul de cautare in adancime continua procesul de cautare cu cel mai recent nod intalnit, atunci cautarea in latime expandeaza drumul pentru nodul cel mai devreme intalnit. Pentru a putea realiza aceasta, in procesul de cautare fiecare nod intilnit si inca neexpandat se retine intr-o coada (implementata printr-o
lista). Ca si in cazul cautarii in adancime, pentru fiecare nod trebuie sa retinem drumul pina la acel nod, in coada avand deci o lista de drumuri.

    breadthfirst([[Node|Path]|_], Target, [Node|Path]) :-
        Node = Target.
    breadthfirst([[Node|Path]| RestPaths], Target, Sol) :-
        findall( [ Node1, Node|Path ],
                    ( s(Node,Node1), \+ member(Node1,Path)),
                    NewPaths),
        append(RestPaths, NewPaths, Paths1),
        breadthfirst(Paths1, Target, Sol).

    solve(StartNode, TargetNode, Solution) :-
        breadthfirst([[StartNode]], TargetNode, Solution).

Aceste proceduri de cautare pot fi utilizate pentru rezolvarea unor probleme foarte diverse (probleme pentru care are sens tranzitia de la o stare a alta).
De exemplu, pentru problema celor opt regine (prin cautare in latime) avem:

    attack(Q, [Q1|R], N) :-
        Q == Q1; abs(Q-Q1) =:= N;
        N1 is N+1, attack(Q,R,N1).
    noattack(Queen, Queens) :- \+ attack(Queen, Queens, 1).

    s(Queens,[Queen| Queens]) :-
        between(1,8,Queen),
        noattack(Queen, Queens).

    ?- length(S,8), solve([],S,_).
 

Probleme:

1. Consideram un numar de 3 cuburi a,b,c puse pe o masa sau unul peste altul. Se cere determinarea secventei de miscari elementare care sa asigure trecerea de la o configuratie initiala data la una finala.

        a
      a b c    =>     b
        c
2. Pe malul unui rau ajung trei misionari si trei canibali. Ei dispun de o barca in care incap cel mult doua persoane. Cum trebuie organizata traversarea a.i. niciodata sa nu ajunga pe unul dintre maluri canibalii in majoritate (exceptand situatia in care pe acel mal nu se afla nici un misionar).
3. Sa se gaseasca o secventa de mutari prin care un cal pe o tabla de sah poate sa ajunga dintr-un camp initial in unul final.