State propagation during bactracking in Prolog

Question

Let's assume, that I have a simple program in Prolog, which is searching through a certain state space:

search(State, State) :-
    is_solution(State).

search(State, Solution) :-
    generate(State, NewState),
    search(NewState, Solution).

And I know that:

• generate(State, NewState) is producing at least one NewState for any given State
• the whole states space is finite

I want to modify the search predicate to ensure that it always manages to check in a finite time. So I write something like:

search(State, Solution) :-
    empty_memory(EmptyMem),
    add(State, EmptyMem, Memory),
    search(State, Memory, Solution).

search(State, _, State) :-
    is_solution(State).

search(State, Memory, Solution) :-
    generate(State, NewState),
    \+ exist(NewState, Memory),
    add(NewState, Memory, NewMemory),
    search(NewState, NewMemory, Solution).

which is working, but it's losing computed states during backtracking, so now I have a search tree with maximum height of space size.

Is it any way to propagate a state during the backtracking without losing any computed information? I want to have a whole search tree with O(space_size) nodes. Is it possible?

EDIT: It seems that I should use assert/[1,2] in order to dynamically create new clauses which will serve as a global memory.

Answer 1

In SICStus Prolog, you can use the blackboard to store information across backtracks: see Blackboard Primitives in the manual. Use bb_put(Key, Value) to store something on the blackboard, and bb_get(Key, Value) to retrieve it. Note that the bloackboard is defined per module.

Answer 2

The most clean solution will likely be to use a Prolog compiler that supports tabling like B-Prolog, Ciao, XSB, or YAP. In this case, you would simply declare the generate/2 predicate as tabled.

Answer 3

Instead of using assert, why not generate all possible states with findall(N, generate(S,N),ALL). This will eliminate the need for backtracking and will explicate the search space tree, which then could be preorder-traversed while passing along the visited-so-far states as additional argument.