prolog - 如何使用 Prolog CLP FD 进行路径限制？

Question

我正在尝试通过 Prolog CLP FD 使用限制编程来解决提出的难题。这个谜题包含以下简单规则:

现在，在我的代码中，我已经涵盖了 2x2 网格的限制，并且其中一件必须连接到至少一种相同的颜色。

问题是我找不到一种方法来构建限制，即一 block 必须有一个路径(连接)到所有其他相同颜色的 block ，而不通过相反颜色的 block ，所以我'得到这种输出:

0 0 0 0
0 1 0 1
0 1 0 1
0 1 0 0

0 0 0 0
0 1 0 1
0 1 0 1
0 1 0 1

其中 1 并不都相互连接。

如何在 CLP FD 中编写这种图形限制？

编辑:我正在使用 SICStus Prolog。

Answer 1

改写您的情况，以便我们可以更清楚地考虑它:

1. 你已经可以生成答案了
2. 但是目前的答案过于笼统。

为了使您的程序更具体，您必须在您生成的其中一个答案中找到当前违反但必须保持的条件strong> 在每个解决方案中，然后用约束表达这个条件。

例如，再次考虑你的情况:

0 0 0 00 1 0 10 1 0 10 1 0 1

这里违反了哪个条件？显然，1碎片不沿着路径。但是用 CLP(FD) 描述完整路径非常乏味，而且由于这显然是从考试或家庭作业中提取的，这个想法本身表明有一个简单的本地标准来表达所需的条件.

“本地”是指您只需考虑几个邻居而不是整个董事会。

因此，再次考虑 1件。显然，每个 1 piece 有一个邻居在这个答案中也是 1。还有什么？是否每个 1 piece 有 2 邻居？目前没有，没有。 应该每1 piece 有 2 个邻居也是 1 ？如果不是，有多少异常(exception)是可以接受的？

如果你按照这些条件来思考，你一定会得到一个很好的解决方案。

一个提示:有时具体化约束在此类任务中很有用。这意味着您可以说:B #<==> (X #= Y) , 让 B表示是否 X #= Y持有。请注意，在这种情况下您甚至可能不需要它。