-1

我正在 Prolog 学习 SWI Prolog 实施的大学考试。

我对这个版本的 8 Queen 问题如何使用排列解决问题有一些疑问：

solution(Queens) :-
 permutation([1,2,3,4,5,6,7,8], Queens),
 safe(Queens).

permutation([],[]).

permutation([Head|Tail],PermList) :-
 permutation(Tail,PermTail),
 del(Head,PermList,PermTail).

del(Item,[Item|List],List).

del(Item,[First|List],[First|List1]) :-
 del(Item,List,List1).

safe([]).

safe([Queen|Others]) :-
 safe(Others),
 noattack(Queen,Others,1).

noattack(_,[],_).

noattack(Y,[Y1|Ylist],Xdist) :-
 Y1-Y=\=Xdist,
 Y-Y1=\=Xdist,
 Dist1 is Xdist + 1,
 noattack(Y,Ylist,Dist1).

在以前的解决方案中，我使用了这个解决方案模板： [1\Y1, 2\Y2, 3\Y3, 4\Y4, 5\Y5, 6\Y6, 7\Y7, 8\Y8] 简单地说每个女王都有要在不同的行上，X 值可能会受到限制。

这个版本的程序有很大的不同，因为我们可以观察到，为了防止垂直攻击，所有的皇后都必须在不同的行上，所以我每行都有一个皇后。

因此，在不丢失信息的情况下，我可以说解决方案将是列表的排列：[1,2,3,4,5,6,7,8]，其中每个元素都表示女王的 Y 坐标。

所以在这种情况下，我只通过它的 Y 坐标（它的行索引）来表示一个皇后位置

所以我有解决方案的关系，而不是说如果皇后是[1,2,3,4,5,6,7,8]原始列表的前排列并且如果这个排列是安全的（每个皇后在这个排列列表不攻击其他女王）。

好的，这很清楚......现在它定义了安全关系。

有一个基本情况说，如果列表为空，那么这是安全的，因为没有攻击。

并且有一个一般情况，列表不为空。如果列表不为空，我可以将其划分为[Queen|Others]，其中Queen是列表中的第一个皇后， Others是剩余的子列表......所以如果子列表 Others 它，原始列表[Queen|Others]是安全的本身就是一个解决方案（如果是安全的，如果Others中没有攻击的话）并且如果第一项Queen没有攻击其他子列表中的另一个Queen...

好的......直到现在我认为这对我来说很清楚......

现在我对noattack关系的定义有一些问题！

问题是我只通过它的 Y 坐标和 X 坐标来表示一个皇后位置，它没有明确存在。

我知道为了规避这种表示的限制，有以下概括（我希望能很好地理解......我不太确定......）：**我也知道每列必须有一个女王棋盘的，所以与列表中的第一个皇后（Queen）和子列表Others的X距离必须为1**

第一项Queen和子列表Others的距离是第一项Queen和最接近它的Queen的X距离，我的推理是否正确？

因此，如果女王在不同的列上，则noattack关系为 TRUE（对于构造总是正确的），我可以表示必须在不同的行上，说从女王和其他子列表中最近的女王的 X 距离为 1。

但是，如果我的推理是正确的，我会发现很多麻烦试图理解这部分代码中这个东西是多么的好：

noattack(Y,[Y1|Ylist],Xdist) :-
 Y1-Y=\=Xdist,
 Y-Y1=\=Xdist,
 Dist1 is Xdist + 1,
 noattack(Y,Ylist,Dist1).
4

2 回答 2

2

我认为你的问题只有这两条线：

Y-Y1=/=Xdist,
Y1-Y=/=Xdist,

它检查有 Y 的皇后是否以对角方式攻击距离 Xdist 的行中的皇后。( |Y - Y1| = Xdist --> diagonal attack )。

攻击其他皇后的另一种方法是将它们 qttack 在同一行中，这不会仅仅因为解决方案是 的排列而发生[1,2,3,4,5,6,7,8]。所以像[1,1,3,4,5,6,7,8]永远不会发生的事情，这足以检查对角线。

我希望它解决了这个问题。

ps注意是从规则Y1头部的Y坐标。所以它一开始是 a为 1 的皇后，然后它回溯到其他行。OthersSafe/1Xdist

澄清

我们正在谈论noattack/3。你给它三个论点：

第一个：Y 当前女王的坐标，

第二个：最右边的列表从列表 [Y1| Ylist] 中 where 之后的某处开始 Y ，并继续到主列表的末尾。（是的，这是解决方案的子列表），并且

第三：Xdist 是当前女王（有Y）和将与当前女王（有Y1并且是第二个参数的头）检查的女王之间的索引距离。

第三个参数是必要的，因为没有它我们无法检查当前女王与拥有 Y1 的女王之间的对角线交互。这真的是基础数学，坐标系中有 2 个点，只有自然数。假设当且仅当abs(x1 - x2) = abs(y1 - y2)时，这两个点以对角线方式相互攻击。

示例 #1 。如果您很好地理解了我的解释，请将其选中为已接受。

P1 = (3, 4) 和 P2 = (1, 2) -->这些点具有对角线攻击，因为abs(3-1) = abs(4-2) = 2

示例 #2

P1 = (3, 4) 和 P2 = (7, 0) -->这些点具有对角线攻击，因为abs(3-7) = abs(4-0) = 4

这就是我们同时检查 Y1-Y =\= Xdist 和的原因 Y-Y1 =\= Xdist 。因为每当有对角线攻击时，至少会有一个true。Y当它们都不是真的时，这意味着女王与女王之间没有对角线攻击Y1。所以我们可以继续检查下一个皇后，即Ylist.

我希望这足够。这是一个非常简单的问题，只要仔细阅读它，如果你不能再次理解，请尝试自己在一张纸上追踪算法。这是一种总是有效的方法。

于 2013-04-06T22:48:05.880 回答
0

在使用 C 递归解决相同问题时，我也有同样的困惑。对角线攻击有两种可能的方向。用 x,y 坐标为每个正方形编号，左上角为 0,0。然后你会看到这两个攻击对角线检测或计算满足条件：

  • x1 - y1 == x2 - y2
  • x1 + y1 == x2 + y2

我用 C 等式表示法而不是 Prolog 表示法对上面的比较进行了注释。在 (x1,y1) 和 (x2,y2) 两点之间，如果满足上述条件之一，则存在女王对角线攻击。

于 2016-01-19T21:45:45.620 回答