[Prolog] State space search method

This is not an introductory article into state space search method in general. Rather, it will show you how to implement state space search method in Prolog.

Backtracking is in the nature of Prolog’s interpreter so the idea here is: We will utilize its backtracking nature to implement depth-first search. If you are not sure about how backtracking works in Prolog, please take a quick look at part Orientation: Prolog Search Trees by Epistemological Engineering or just google more about it for your self.

  • S stands for Starting state.
  • E stands for Ending state (or goal state).
  • R stands for Running path. It can be initialized as an empty list or a list with one member being the starting state, then collects the searching path through recursive process. Its first element in a recursion may not be the ending state but soon it will be, if not the program will return false.
  • P stands for Path. It is the running path with first element being the ending state. We use it to get the running path when the search is done. You can imagine the path is a list looks like this: [E,Mn,…,M1,S], with M1…Mn are the medium states.

f(S, X) is a state transfer predicate that you will have to implement it yourself based on the specific problem:

  • S is the current state.
  • X is the next possible state of S.

For example, if you have implemented a series of predicate f, the list [0,0] is the starting state and the [1,1] is the goal state and you want to search the path that goes from [0,0] to [1,1], you run:

Your program will return a list like this: [[1,1],…[some medium states]…,[0,0]].

As you have seen, you will have to repeat the starting state in the input and the returning path seems unnatural. You may want to add the below code line:

Hence when you run the program:

Your program will return a list like this: [[0,0],…[some medium states]…,[1,1]].

Full path search code:

If you want something concrete to play with, you may want to see the full program in Prolog that solves The Three Jealous Men and Their Wives puzzle.


Sometime, you may want to view all the possible states can be reached from a specific state, here is a way to do that:

  • S is the specific state in consideration.
  • gm is a global variable in Prolog that saves all the considered state (so we will not consider or print the same state twice or more).

You can add the above code lines to The Three Jealous Men and Their Wives program to run this:

Global variable gm (in g predicate) versus local variable R (in s predicate):

  • In s predicate, you want to search all possible paths between starting state and ending state. So the program may return you this solution path:

    [1]: [S, M1, M2, M3, E]

    But then if you press ; button, you may receive the second solution path looks like this:

    [2]: [S, M1, M2, M5, M7, E]

    The explanation here is: First the program has done it work with solution [1] and the local variable R has M3 in it. But then when you press ; for other solution, the program has to backtrack to M2 point and removes M3 from local variable R simultaneously and finally M3 is not in the list R in the solution [2] anymore.

  • In g predicate, if we want to traverse all the possible states that can be reached from a specific state, we will have to do a process that is recursive and backtrackable. However, we do not want backtracking process to affect on what we have gotten: Global variable gm comes into play. Global variable’s value is not affected by the backtracking so we will use it as a collection of all considered state so that we do not reconsider or reprint a considered state anymore (reconsidering a considered state will definitely lead you to an endless loop).

And maybe you want to count all the possible solution paths:

The idea of series of c predicate is similar to the idea of series of s predicate.

The differences:

  • c2 will always return “false” result to trigger the backtracking process automatically (in s predicate, we have to do this manually by pressing ; button). count is a global variable so its value is not affected through backtracking.
  • By c predicate, we want to return the value of count automatically. Here, we consider another not-working version of it:

    Here we do not negate c2 so the c predicate will always fail at the bold part. If c predicate fails at that, it will not run the following part nb_getval(count, C), writeln(C). That is why we have to negate c2 result in c predicate.

Facebooktwittergoogle_plusredditpinterestlinkedinmail

3 comments on “[Prolog] State space search method”

Leave a Reply

Your email address will not be published. Required fields are marked *