Estou estudando o Prolog usando o livro de Ivan Bratko: Programação para Inteligência Artificial e estou encontrando algumas dificuldades para implementar a parte final de um exercício proposto.

O exercício é um programa que usa gráficos para decidir como mover blocos e organizá-los em um pedido.

Esta é uma imagem relacionada ao que o programa precisa fazer:

Como você pode ver na imagem anterior, os blocos A, B, C podem ser movidos usando um número de movimentos admissíveis que são:

Um bloco só pode ser movido se estiver no topo da pilha

Um bloco pode ser movido no chão (em uma pilha vazia)

Um bloco pode ser movido sobre outro bloco (no topo de outra pilha que contém alguns outros blocos)

Então, esses movimentos admissíveis induzem um gráfico das possíveis transições entre um estado e outro estado no gráfico, algo assim:

Então, como você pode ver no gráfico anterior, posso representar uma situação usando uma lista de 3 sub-listas.

Cada sublista representa uma pilha onde posso colocar os blocos de acordo com as restrições anteriores

Assim, por exemplo, a situação do nó central do gráfico anterior pode ser representada por:

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

Porque cada pilha contém um único bloco.

A situação representada pelo nó no canto superior esquerdo onde eu empilhei um abaixo dos outros blocos C, A, B pode ser representada por:

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

Ok, então meu programa é o seguinte:

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).

Nestes últimos dias eu estudei profundamente e entendi como funciona.

Substancialmente os / 3 predicado é meufunção sucessoras(CurrentState, SuccessorState) que calcula um movimento legal doCurrentState aoSuccessorState.

Este predicado funciona bem, na verdade, se eu lançar a seguinte consulta:

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

Eu obtenho isso[[b, c], [a], []] é umestado sucessor para o estado[[abc],[],[]] e isso é bom porque eu mudei oa bloco do topo da primeira pilha no topo da segunda pilha (que foi anulada) e este é um movimento perfeitamente legal.

Ok, acontecendo eu tenho ogoal/1 predicado que diz quando eu cheguei a um estado final (quando o cálculo tem que parar):

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

Ele diz que uma situação (uma configuração de lista de pilhas específica) é uma situação de meta, se na lista de pilhas relacionadas houver uma pilha que é a lista [a, b, c].

Portanto, as situações a seguir são situações de objetivo:

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

Ok, agora meu problema é o seguinte: eu tenho que implementar osolve/2 predicado assim:

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

que começa de uma situação passada (neste caso a lista de pilhas que tem todos os blocos na primeira pilha comc no chão,b no meio ea no topo) e chega a uma situação de meta.

Eu não sei exatamente o que tenho que fazer e como tenho que resolver (infelizmente não tenho professor)

Eu estava tentando me inspirar olhando para esta versão do problema de 8 rainhas que usa uma técnica de programação similar (na qual tenho um objetivo de satisfazer e resolver o predicado):

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).