我不明白Prolog中的标签是做什么的

Question

我查看了手册和文档,但仍然不明白.我正在尝试实现一个数独解决方案,在写出游戏的所有其他规则后,我根据老师的指示添加了标签(Board).

但是我仍然没有得到它的工作原理或它正在做什么.不应该有其他约束(我有检查说数字必须是1..9,行必须全部不同,等等)给我自己的答案？

Answer 1

如果你想快速学习Prolog和CLP(FD),可以使用Prolog的顶级shell来玩,直到你熟悉它.事实上,您需要了解有关CLP(FD)和Prolog的所有信息; 或差不多.不需要写(他们的名字是什么？)文件,一切都符合要求.是的,我知道,我们的父母警告我们:我的孩子,答应我,永远不要做一个班轮.但是你会学得更快.

所以你有?-等待吗？

在传统的Prolog(没有约束)中,从查询中获得的是所谓的答案替换.在许多情况下,这种答案替代已经描述了一种解决方案 如果对于每个变量,则找到变量空闲项.让我们看一个具体的例子,并描述一个包含5个元素的列表,其中每个元素都是1到5之间的值.在这种情况下,找到不同值的解决方案L.

?- N = 5, length(L,N),maplist(between(1,N),L).
   N = 5, L = [1, 1, 1, 1, 1] ;
   N = 5, L = [1, 1, 1, 1, 2] ;
   N = 5, L = [1, 1, 1, 1, 3] ...

Prolog只会告诉你一个解决方案(暗地里希望你会对它感到满意,它有点懒,不严格).你得到所有人打字SPACE或;.尝试一下,看看他们有多少......

总共有5^5解决方案.如果您只想从众多解决方案中挑选一些解决方案,那就不太实际了.以这种方式表示大量解决方案非常无效.然后,想想无限集!Prolog或任何有限的存在如何枚举无限集？我们只能开始这样做,因为我们是有限的.

为了克服这个问题,Prolog并不总是被迫显示具体的价值观,即解决方案,但可以通过显示答案来代替它们:

?- N = 5, length(L,N).
   N = 5, L = [_A, _B, _C, _D, _E].

这个答案(-substitution)包含5^5上面的所有答案,还有更多答案L = [stack,over,flow,dot,com].事实上,它描述了一组无限的解决方案!我不是说我们有限的生物不能这样做吗？只要我们坚持具体的解决方案我们就不能,但如果我们对答案感到满意,我们就可以做到不可能.

这个想法可以扩展到描述更具体的集合.所有人都有一个答案.关于整数的集合,我们有library(clpfd).像这样使用它:

?- use_module(library(clpfd)).

?- asserta(clpfd:full_answer).  % only necessary for SICStus

我们现在可以重申我们的原始查询(在SWI中,你可以做到Cursor up ↑这一点):

?- N = 5, length(L,N),L ins 1..N.
   N = 5, L = [_A, _B, _C, _D, _E],
   _A in 1..5, _B in 1..5, _C in 1..5, _D in 1..5,_E in 1..5.

现在所有3125解决方案都只用一个答案进行了简洁描述.(3125？那是5^5).我们可以继续说明进一步的要求,例如它们都是不同的:

?- N = 5, length(L,N),L ins 1..N, all_different(L).
   N = 5, L = [_A, _B, _C, _D, _E],
   _A in 1..5,_B in 1..5,_C in 1..5,_D in 1..5,_E in 1..5,
   all_different([_A, _B, _C, _D, _E]).

(实际上)所有约束的共同点是它们不枚举解决方案,而是试图保持一致性.让我们试试这个,说明第一个元素应该是1:

?- N = 5, length(L,N),L ins 1..N, all_different(L), L = [1|_].
   N = 5, L = [1, _A, _B, _C, _D],
   _A in 2..5,_B in 2..5,_C in 2..5,_D in 2..5,
   all_different([1, _A, _B, _C, _D]).

你看到效果了吗？他们迅速改变了他们的域名!现在他们都在2..5.

他们都应该在1..4:

?- N = 5, length(L,N),L ins 1..N, all_different(L), L = [1|_], L ins 1..4.
   N = 5, L = [1, _A, _B, _C, _D],
   _A in 2..4,_B in 2..4,_C in 2..4,_D in 2..4,
   all_different([1, _A, _B, _C, _D]).

同样,它们也会更新.但是......想一想:剩下4个变量,它们应该都是不同的,但它们只有3个不同的值.

所以我们发现Prolog有点太懒了.实际上有被称为是一个更好的约束all_distinct/1,现在会失败,但无论多聪明的约束系统是如何拥有,会有总是这样的不一致性.问哥德尔教授.拯救的唯一方法是错误或无限循环.

所以我们需要另一种方法来确保答案确实描述了真正的解决方案.输入标签!有了label/1或者labeling/2我们可以消除所有那些奇怪的约束和破坏不一致:

?- N = 5, length(L,N),L ins 1..N, all_different(L), L = [1|_], L ins 1..4, labeling([], L).
   false.

?- N = 5, length(L,N),L ins 1..N, all_different(L), L = [1|_], labeling([], L).
   N = 5, L = [1, 2, 3, 4, 5] ;
   N = 5, L = [1, 2, 3, 5, 4] ;
   N = 5, L = [1, 2, 4, 3, 5] ...

我们怎样才能确定这些是真正的解决方案？容易:除了答案替换之外,它们不包含任何额外的目标¹.如果我们忘了一些:

?- N = 5, length(L,N),L ins 1..N, all_different(L), L = [1,B,C|_], labeling([],[B,C]).
   N = 5, L = [1, 2, 3, _A, _B], B = 2, C = 3,
   _A in 4..5, _B in 4..5,
   all_different([1, 2, 3, _A, _B]),

他们会表现出来.

SWI labeling/2有一个非常有用的保证:

标签始终完整,始终终止,并且不会产生冗余解决方案.

1由于SWI顶层未显示所有约束,因此您需要call_residue_vars(Goal, Vs)环绕它.但对于简单的顶级查询,上面就足够了.