How to implement a solve predicate for this "moving blocks" Prolog exercise?

Question

I am studying Prolog using Ivan Bratko book: Programming for Artificial Intelligence and I am finding some difficulties to implement the final part of an exercise proposed

The exercise is a program that use graphs to decide how to move blocks and to arrange them in an order.

This is an image related to what the program have to do:

enter image description here

As you can see in the previous immage the blocks A,B,C can be moved using a number of admissible moves that are:

A block can be moved only if it is at the top of the stack
A block can be moved on the ground (on a void stack)
A block can be moved over another block (at the top of another stack that contains some others blocks)

So these admissible moves induce a graph of the possible transitions between one state and another state in the graph, something like this:

enter image description here

So, as you can se in the previous graph I can rappresent a situation using a list of 3 sublist.

Each sublist rappresent a stack where I can put the blocks according to the previous constraints

So for example the situation of the central node of the previous graph can be represented by:

[[A], [B], [C]]

Because each stack contains a single block.

The situation represented by the node at the top left where I stacked one below the other blocks C,A,B can be represented by:

[[C,A,B], [], []]

Ok, so my program is the following one:

del(X, [X|Tail], Tail).

del(X, [Y|Tail], [Y|Tail1]) :- del(X, Tail, Tail1).

/* s(CurrentState, SuccessorState): Predicate that calculate a legal move from
                                    the CurrentState to the SuccessorState:
*/
s(Stacks, [Stack1, [Top1|Stack2] | OtherStacks]) :- 
                                     del( [Top1|Stack1], Stacks, Stacks1),
                                     del( Stack2, Stacks1, OtherStacks).

goal(Situation) :- member([a,b,c], Situation).

In these last days I have deeply studied it and I understand how it works.

Substantially the s/3 predicate is my successor function s(CurrentState, SuccessorState) that calculates a legal move from the CurrentState to the SuccessorState.

This predicate works well, in fact if I launch the following query:

[debug]  ?- s([[a,b,c],[],[]],R).
R = [[b, c], [a], []]

I obtain that [[b,c],[a],[]] is a successor state for the state [[a,b,c],[],[]] and this is good because I have moved the a block from the top of the first stack on the top of the second stack (that was void) and this is a perfectly legal move.

Ok, going on I have the goal/1 predicate that says when I have reached a final state (when the computation have to stop):

goal(Situation) :- member([a,b,c], Situation).

It says that a situation (a specific stacks list configuration) is a goal situation if in the related stacks list there is a stack that is the [a,b,c] list.

So the following situations are goal situations:

[[a,b,c],[],[]]
[[], [a,b,c],[]]
[[],[], [a,b,c]]

Ok now my problem is the following one: I have to implement the solve/2 predicate like this:

solve([[c,a,b],[],[]], Situation)

that starts from a passed situation (in this case the list of stacks that have all the blocks in the first stack with c on the ground, b in the middle and a on the top) and arrives to a goal situation.

I don't know exactly what I have to do and how I have to solve it (unfortunately I have no teacher)

I was trying to inspire myself looking at this version of 8 queen problem that uses a similar programming technique (in which I have a goal to satisfy and the solve predicate):

s(Queens, [Queen|Queens]) :- member(Queen, [1,2,3,4,5,6,7,8]),
                             noattack(Queen, Queens, 1).

goal([_,_,_,_,_,_,_,_]).

noattack(_,[],_) :- !.
noattack(Y,[Y1|Ylist],Xdist) :-   Y =\= Y1,
                                  Y1-Y =\= Xdist,
                                  Y-Y1 =\= Xdist,
                                  Dist1 is Xdist + 1,
                                  noattack(Y,Ylist,Dist1).

solve(N,[N]) :- goal(N).      % sample call: solve([], X).

solve(N, [N|Sol1]) :- s(N,N1),
                      solve(N1,Sol1).

CapelliC CapelliC · Accepted Answer · 2013-05-09T17:30:47

There will be loops in space search graph, then you can switch to some form of bound search. The easier I know it's bounded depth search:

?- length(Situation,_), solve([[c,a,b],[],[]], Situation).
Situation = [[[c, a, b], [], []], [[a, b], [c], []], [[b], [a], [c]], [[], [b, c], [a]], [[], [a, b|...], []]] .

length/2 enumerates unbound lists of growing length. So we get a result.

Note that this will still loop if there are no solutions from initial state to goal/1. If this is bad, I think solve/2 will need a service solve2/2 predicate, that will get the path, to enable the usual \+ memberchk(NewState, Visited) after the nondeterministic s/2 call. Then it will be (untested)

solve(N, SearchPath) :- solve2([N], SearchPath).

solve2([N|Visited], [N|Visited]) :- goal(N).
solve2([N|Visited], Path) :-
   s(N,N1),
   \+ memberchk(N1, Visited),
   solve2([N1,N|Visited], Path).

How to implement a solve predicate for this "moving blocks" Prolog exercise?

1 Answers