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

i studying prolog using ivan bratko book: programming artificial intelligence , finding difficulties implement final part of exercise proposed

the exercise program use graphs decide how move blocks , arrange them in order.

this image related program have do:

as can see in previous immage blocks a,b,c can moved using number of admissible moves are:

• a block can moved if @ top of stack

• a block can moved on ground (on void stack)

• a block can moved on block (at top of stack contains others blocks)

so these admissible moves induce graph of possible transitions between 1 state , state in graph, this:

so, can se in previous graph can rappresent situation using list of 3 sublist.

each sublist rappresent stack can put blocks according previous constraints

so example situation of central node of previous graph can represented by:

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

because each stack contains single block.

the situation represented node @ top left stacked 1 below other blocks c,a,b can represented by:

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

ok, program following one:

del(x, [x|tail], tail).  del(x, [y|tail], [y|tail1]) :- del(x, tail, tail1).  /* s(currentstate, successorstate): predicate calculate legal move                                     currentstate 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 have studied , understand how works.

substantially s/3 predicate successor function s(currentstate, successorstate) calculates legal move currentstate successorstate.

this predicate works well, in fact if launch following query:

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

i obtain [[b,c],[a],[]] successor state state [[a,b,c],[],[]] , because have moved a block top of first stack on top of second stack (that void) , legal move.

ok, going on have goal/1 predicate says when have reached final state (when computation have stop):

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

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

so following situations goal situations:

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

ok problem following one: have implement solve/2 predicate this:

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

that starts passed situation (in case list of stacks have blocks in first stack c on ground, b in middle , a on top) , arrives goal situation.

i don't know have , how have solve (unfortunately have no teacher)

i trying inspire myself looking @ version of 8 queen problem uses similar programming technique (in have goal satisfy , 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 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). 

there loops in space search graph, can switch form of bound search. easier 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. result.

note still loop if there no solutions initial state goal/1. if bad, think solve/2 need service solve2/2 predicate, path, enable usual \+ memberchk(newstate, visited) after nondeterministic s/2 call. (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).