prolog - Prolog 中的公式化

Question

我目前有以下问题，我想用 Prolog 解决。这是一个简单的例子，很容易在 Java/C/whatever 中解决。我的问题是，我认为与 Java 的思想联系太紧密，无法以利用 Prolog 逻辑能力的方式实际表述问题。

问题是..

我有一组 6 个箭头，指向左或右。让我们假设它们处于以下起始配置中:

->
<-
->
<-
->
<-

现在，我可以切换两个箭头，只要它们彼此相邻即可。我的目标是发现哪个 Action 序列将使箭头的初始配置变成

<-
<-
<-
->
->
->

我在制定问题的最初尝试是..

right(arrow_a).
left(arrow_b).
right(arrow_c).
left(arrow_d).
right(arrow_e).
left(arrow_f).

atPosition(1, arrow_a).
atPosition(2, arrow_b).
atPosition(3, arrow_c).
atPosition(4, arrow_d).
atPosition(5, arrow_e).
atPosition(6, arrow_f).

这将告诉 Prolog 箭头的初始配置是什么。但是现在如何在其中插入附加逻辑？例如，如何实现 switchArrows(Index) ？在 Prolog 中说明这样的初始条件是否正确？例如，当我尝试设置 arrow_a 位于位置 6 atPosition(6, arrow_a) 时，它​​会不会干扰稍后？

Answer 1

您的问题可以表述为配置之间的一系列转换。首先考虑您希望如何表示单个配置。您可以使用列表来执行此操作，例如 [->,<-,->,<-,->,<-] 表示初始配置。一个单一的移动可以用一个关系 step/2 来描述，它被用作 step(State0, State) 并描述两个配置之间的关系，这些配置通过翻转两个相邻的箭头而彼此“可达”。它通常是不确定的。然后，您的主谓词描述了从初始状态到所需目标状态的一系列状态转换。由于您想描述一个(配置)列表，DCG 非常适合:

solution(State0, Target) -->
    (    { State0 == Target } -> []
    ;    { step(State0, State1) },
         [State1],
         solution(State1, Target)
    ). 

然后使用迭代深化来找到解决方案(如果存在)，如下所示:

?- length(Solution, _), phrase(solution([->,<-,->,<-,->,<-], [<-,<-,<-,->,->,->]), Solution).

好消息是，一旦给定长度的所有序列都已尝试并且尚未达到目标状态，Prolog 会自动回溯。您现在只需执行 step/2 即可完成。