如何为这个“移动块”Prolog练习实现一个求解谓词？

Question

我使用的伊万·布拉科书研究序言：人工智能编程，我发现了一些困难，实施工作的最后部分提出

演习是使用图形来决定如何移动块和程序按顺序排列它们。

这是有关程序必须做的图像：

正如你在前面的IMMAGE见块A，B，C可以使用多种受理举动感动是：

• 块可以仅当它是在该堆的顶部上移动

• 块可以在地面上被移动（上空隙栈）

• A嵌段可以在另一个块被移动（在另一个栈 的包含一些其它块顶部）

因此，这些可容许移动引起可能的转变的曲线图一个状态，并在图中的另一个状态时，事之间这样的：

因此，正如你可以在上图中看到的那样，我可以使用3个子列表来反驳一个情况。

每个子列表rappresent堆叠在哪里可以根据前述约束

因此，例如，先前的图的中心节点的情况可表示为把块：

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

因为每个堆栈都包含一个单独的块。

通过在左上角，其中我一个堆叠中的其它块C，A下方的节点所表示的情况，B可以表示为：

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

好了，我的程序是以下一个：

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

在这些最后的日子里，我深入地研究了它，并且我理解它是如何工作的。

基本上与S/3谓词是我后继函数s(CurrentState, SuccessorState)计算从CurrentState到SuccessorState一个合法的移动。

该断言效果很好，其实如果我启动以下查询：

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

我获得[B，C]，[A]，[]是后继状态对于状态[[a，b，c]，[]，[]]，这很好，因为我已经从第二个堆栈顶部的第一个堆栈顶部移除了a块（这是无效的）这是完全合法的举动。

好了，怎么回事我有goal/1谓词说，当我已经达到了一个最终状态（当计算必须停止）：

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

上面说的情况（具体的堆栈列表配置）是一个目标情况，如果在相关堆栈列表中有一个堆栈是[a，b，c]列表。

所以下面的情况是目标的情况：

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

好了我现在的问题是下面的一个：我要实现的solve/2谓词是这样的：

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

，从开始通过的情况（在这种情况下，第一个堆栈中的所有块的地址为c，中间为b，中间为a在顶部），并达到目标的情况。

我不知道到底是什么我必须做的，我怎么也得解决这个问题（可惜我没有老师）

我是想激励自己看这个版本的八皇后问题是使用类似的编程技术（其中我有一个目标，以满足和解决谓语）：

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

Answer 1

将有在空间搜索图的循环，那么你可以切换到某种形式的约束搜索。我知道它越容易越深入搜索：

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

长度/ 2列举出长度不变的未绑定列表。所以我们得到一个结果。

请注意，如果没有从初始状态到目标/ 1的解决方案，这仍将循环。 如果这是不好的，我认为解决/ 2将需要服务solve2/2谓词，这将得到的路径，以启用非确定性s/2调用后通常\+ memberchk(NewState, Visited)。然后它会（未经测试）

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