CLP(FD)有限域上的约束逻辑式编程

1. 关于本教程
1.1. 谁应该用这个教程
本教程适用于要用clp(fd)、有一定经验的SWI-Prolog程序员。
此外，对于用其他版本Prolog且要用clp(fd)的Prolog程序员，本教程也是有用的。
本教程的重点不在理论。作者不是数学家，而且本文可能对那些能通过学术文献找到材料的称职的数学家也没多少用处。
本教程将帮助你理解有限域上的约束系统的基础知识。
它包涵了一定的实践经验。
这篇教程大多数情况下是对SWI-Prolog的clp(fd)谓词文档的转述，由简明扼要的数学文档变为更平易近人的语言。
1.2. clp(fd)有什么用？
clp(fd)是标准SWI-Prolog发行版中包含的库。它解决涉及变量集的问题，其中变量之间的关系需要得到满足。
clp(fd)还可用于替代面向对象语言中由getter和setter提供的许多保护函数。例如，如果我们尚不知道一个人的实际身高，我们仍然可以断言其超过21英寸且不到108英寸（已知的最矮/最高）。 当我们最终找到解决方案时，不合理的值将被丢弃。
clp(fd)用于通过减少搜索空间来优化搜索问题。约束可以削减整个搜索空间的子树。
clp(fd)对解决各种查找变量的问题非常有用。这是一些clp(fd)可以解决的问题的广泛类别：
安排问题，如应该在什么时候做什么工作来生产这些产品？
优化问题，如应该在工厂生产哪种产品以获得最大利润？
需求满足问题，如在医院中找到符合条件的房间，例如在康复室旁边的手术室，或是找到全家都赞成的度假方案。
顺序问题，如找到我们前往目的地的路线。
标识问题，如数独或密码算术问题。
相信与意图问题，比如侦探谜题和游戏中的非玩家角色。
分配问题，如分配飞机机组人员，使其满足工会的要求，并最大时间离家。
为相关联的变量集找可接受的解决方案，如在一群嫉妒的少女中，找出谁会去参加聚会，如果B去了，A才会去；如果C去了，B就不会去，等等。
为多个互相影响的变量创建可接受方案列表。如一个宴席筹备者可能希望看到宴席菜单满足宴席开销、厨师和侍者的日程、烤箱的安排等不同需求，然后自己选择采用哪种方案。
图形的几何约束条件，如CAD系统中，其中两条线必须垂直，另外两条必须平行，其他两条线相距30英尺，依此类推。
clp(fd)的使用练习
为上面每个类别再举一个例子。尽量扩展问题的范围。例如，给定一组火车车厢，将它们按合理的顺序排列，使其遵守一些规则（例如，没有油罐车靠近引擎，守车必须在后面）就是个顺序问题。
1.3. 前提
掌握SWI-Prolog的基础知识。
数学水平与计算机科学本科课程的高等水平相当。
SWI-Prolog已安装并运行正常。
本教程没有附带代码文件。你可以剪贴示例。
1.4.你可以从本教程中学到什么
如果你读完此教程，并完成所有练习，你可以期待：
了解约束编程的基本概念
能编写查找未知值解决方案的程序
能用clp(fd)库阐述现实世界的问题
能对约束系统问题选用适当的解决方案
了解如何在真正的SWI-Prolog的程序中使用clp(fd)
1.5. 完成时间
6－8小时，因人的数学水平而异。

2. clp(fd)库
SWI-Prolog的clp(fd)库是由Markus Triska为他的博士论文编写的。clp(fd)代表有限域上的约束逻辑式编程。
clp(fd)是SWI-Prolog中可用的几种约束求解器之一。其他的有：clp(b)，clp(qr)， clp(b)处理布尔值；clp(qr)处理有理数和实数。 CHR是用于创建自己的约束系统的工具（其他类型）。
clp(fd)库可以轻易地激活：
1 :- use_module(library(clpfd)).
这将安装个编译时的挂钩，可以优化一些clp(fd)约束，并加载运行时的库。
3. 变量
在计算机科学中，我们很宽松地使用“变量”这个术语。
3.1 替代变量
在命令式编程语言中，比如Java，变量是可变的。其值会随时间而改变。
在C语言中，像变量x：
int x;... what about here? ...x = 5;
3.2 逻辑变量
在逻辑式语言中，变量是不同的。它们更像高中代数中的变量或未知数。
在Prolog中，变量可以是绑定或非绑定的。非绑定的变量将与任何值结合。绑定的变量仅与一个模板统一。
实际上，我们要么知道，要么不知道变量的值。
当我们试图结合时，我们实际上是在问：“我们对左边和右边答案的理解是一致的吗？”鲍勃声称自己是主城市长的好友，如果鲍勃是《主城日报》的编辑，这很可能是可信的。如果鲍勃声称从未涉足主城，这就有些矛盾了。 在Prolog中，对于原子结果只有两种可能。完全不知道，或确切知道。显然，在列表或项中可能有非绑定的变量，但对于每个变量，只有这两种状态。
3.3. 约束变量
但在现实世界，我们可以讲出更多关于变量的内容。 我们可能不知道确切的值，但我们知道它是一组可能的值中之一。我们称之为域。
我们可能不知道具体值是什么，但可以说它其他一些我们同样不知道值的变量要大，我们说这个变量是受约束的。
随着我们开始积累约束条件，我们开始能对约束进行推理。假设我们有两个整数变量，X和Y。
现在我告诉你，X在0到10的范围内。
接着，Y在4到8的范围内。
最后，X大于Y。
你可以推断出，X在5到10这个更窄的范围内，因为Y可以具有的最小值是4，并且X必须比Y至少大1。
这便是clp(fd)的样子。如果你没完全理解这些，也不要担心。
:- use_module(library(clpfd)). 1
test(X, Y) :- X in 0..10, 2
Y in 4..8, 3
X #> Y. 4
14 ?- test(X, Y).X in 5..10, 5
Y#=<X+ -1, 6
Y in 4..8.
1 导入clp(fd)库
2 使用“in”运算符，约束X在0到10之间
3 使用“in”运算符，约束Y在4到8之间
4 使用“#>”运算符，约束X比Y大
5 现在X被约束为5到10之间
6 现在Y被约束为=< X - 1（同样是X>Y），且范围为4到8。
当我们将一个变量限制为单一值时，会发生一些神奇的事——我们现在已经知道了变量，因此可以绑定变量。在clp(fd)中，确实发生了这种情况！假设我将X约束在0到5的范围内，并且将Y约束在4到8的范围内，并且X> Y，那么突然X现在绑定到5了。ground（X）成功了，并且X是一个非常普通的绑定变量。
:- use_module(library(clpfd)).
test2(X, Y) :-
X in 0..5,
Y in 4..8,
X #> Y.
16 ?- test2(X,Y).
X = 5, 1
Y = 4. 2
1 X被绑定，就像在普通的Prolog中那样
2 注意，Y也被绑定了。此外，它失去了原先的约束。
编辑、运行练习
输入并尝试以上两个例子。使用调试器进入它们，以查看列出的约束。
回溯练习
:- use_module(library(clpfd)).foo(X) :- X in 1..3 .foo(X) :- X in 5..7 .foo(X) :- X in 8..12 .
如果查询foo(X)，并通过回溯得到所有解决方案，将会发生什么？预测会发生什么，并尝试它。你的预测正确吗？
3.4. 实现
SWI-Prolog能将属性添加到变量。这是附加到变量的附加元数据。如果你有兴趣，可以在SWI-Prolog网站上阅读有关属性变量的更多内容。
clp(fd)使用此属性数据修饰约束变量。然后clp(fd)实现了约束编程，并作为常规Prolog统一的扩展。
本教程结尾将对此作更多介绍。
属性练习
Extra credit -
考虑除了用于约束，变量属性的另一种用法。
3.5. 域
clp(fd)中的(fd)表示有限域。该域可以具有数百万个值，但它必须是一个有限列表。
我们只关心有限域的变量。就我们的目的而言，这意味我们要对整数集的域进行推理。
clp（fd）可用于[air, land, sea]这样的域，但优化效果不佳。映射air = 0，land = 1，sea = 2，然后说域是0..2，会更好。任何可能的有限列表都可以映射到整数的有限子集。
乍一看，这可能显得有些笨拙，但实际上与使用数组索引没什么不同。更大的问题可能是调试——整数列表可能毫无意义。编写一些调试代码以提取并输出数据，可能会有帮助。

4. 示例
我总是被那些毫无根据的讨论恼火。这是一个典型的约束程序，并包含各部分的简要说明。你可能还不了解所有部分。 “SEND + MORE = MONEY”密码算术问题是约束编程中的经典“hello world”。题目要求将0到9数字分配给字母，使它们拼出SEND MORE MONEY，当以10为底地读取数字时，将形成真正的算式。数字不允许有前导0。
:- use_module(library(clpfd)). 1
puzzle([S,E,N,D] + [M,O,R,E] = [M,O,N,E,Y]) :- 2
Vars = [S,E,N,D,M,O,R,Y], 3
Vars ins 0..9, 4
all_different(Vars), 5
S*1000 + E*100 + N*10 + D + 6
M*1000 + O*100 + R*10 + E #=
M*10000 + O*1000 + N*100 + E*10 + Y,
M #\= 0, S #\= 0, 7
label(Vars). 8
9 ?- puzzle(X).X = ([9, 5, 6, 7]+[1, 0, 8, 5]=[1, 0, 6, 5, 2]) ; 9
false.
1 导入clp(fd)库
2 注意，clp(fd)不像pce或准引用那样的嵌入式DSL。clp(fd)与Prolog一起使用，增加了主义。
3 为了方便起见，列出了我们要约束的所有变量
4 将Vars中的每个变量限制为0..9的范围（含）
5 添加约束条件，它们必须是不同的
6 添加定义问题的算术约束
7 单词以M和S打头，因此不能为0
8 尝试尽可能多地确定变量
9 注意，外面没有有趣的属性，只返回了解决方案
FortyTenTen练习
1）通过修改程序来解决密码算术FORTY + TEN + TEN = SIXTY 2）如果允许前导0，是否还有SEND+MORE=MONEY的解决方案？修改程序以找出答案。
5. 标签
附加约束很好，但在我们最终回到简单地绑定变量之前，它用处不大。有着所有固定变量的解称为固定解。
有一些次要的机制可以做到这一点。
如果将定义域缩减至单个值，则变量会被固定。
一般，你可以轻易地为变量赋值。通常，X = 3将变量限制为单个值。
谓词indomain/1会在回溯时，连续地将变量綁定到其可能的值。
通常，我们将找单个固定的解决方案称为label/1或labeling/2。label/1和labeling/2是不确定的，在每次回溯时，都绑定了一组不同的值。
当然，我们的约束系统可能不足以表达每个约束。如果是这样，我们必须依赖生成和测试搜索策略来熟悉所有Prolog程序员了。有了约束系统，生成和测试系统成为
1.约束
2.生成（通过labeling）
3.测试
实际上，大多数clp(fd)程序遵循约束后接标签的一般模式。
提示
设置模型，并在单独的谓词中执行标签和剩余的搜索是良好的做法。这使得在应用标签之前检查模型变得更加容易。
labeling/2有大量选项能影响变量选择策略。由于 clp(fd)程序花费的大部分时间通常是在labeling上，我们会在后面详细介绍这些内容。现在我们使用label/1，它有合理的默认值。
labeling/2的选项也用于最优化的问题。
6. 简单约束
clp(fd)提供一组基本、简单的约束。
请记住，clp(fd)与整数一起使用。
X #>= YX #=< YX #= YX #\= YX #> YX #< Y
提示
你可以使用#=作为is的声明性版本，否则不是clp(fd)。X is 3+Y使Y被固定，而X #= 3+Y，在X被固定、而Y不是的情况下起作用。
提示
X #< Y可以消除不必要的对称。比如，如果玩家1和3在锦标赛中已配对，再考虑3和1的配对是没意义的。请思考以下取自SWI-Prolog文档的示例，它找出了使四个配对的所有方法：
示例1 消除对称
?- Vs = [A,B,C,D], Vs ins 1..4,
all_different(Vs),
A #< B, C #< D, A #< C,
findall(pair(A,B)-pair(C,D), label(Vs), Ms).
Ms = [ pair(1, 2)-pair(3, 4), pair(1, 3)-pair(2, 4), pair(1, 4)-pair(2, 3)].
严格递增练习
编写谓词increase/1，它接收一个列表，约束它严格递增。
首先记录你预计每个查询的结果。然后测试你的谓词是否符合你的预期。

7. 约束域
变量的域是它可以取的一组值。
在clp(fd)中，每个变量必须被限制到有限域，以进行推理。在尝试标记它们之前，你需要给变量赋予域。如果不是，你将得到令人困惑的异常，错误：参数未被充分实例化。
X in 5..10, 1
Y in 1..10, 2
Y #> X 3
1 X的域设定为5到10
2 Y的域设定为-1到10
3 将Y约束为大于X，因此可以推断出域。Y必须为6、7、8、9、10其中之一。
奇怪的是，对于所有有关有限域的讨论，都可以像4..sup那样，将变约束到4至无穷大的域。inf是负无穷大。
7.1. In和Ins
你可以使用in和ins运算符来限制变量的域。
in和ins都设定右边的域。域是一个简单范围或几个简单范围用\/运算符形成的并集。
一个简单的域可以是单个数字或由双点相连的一对边界。边界可以是数字，或用于最小的inf，用于最大的sup。其中任何一个都可以是被固定的变量，比如N=3, X in 1..N .。
7.2. \/运算符
域可以和\/运算符并在一起。
并集
1..3 \/ 5..7
示例2 复杂域
V in inf.. -2 \/ 0 \/ 2..16 \/ 18..sup
in约束单个变量。
ins将一个变量列表约束为同样范围的值，相当于用in映射整个列表。
7.3. 来自数据的域
如果域来自输入数据呢？假设我们从某处得到一个数据结构，需要以某种方式对其约束。
将你的域组合为项MyDomain，并运用X in MyDomain。这有个例子
示例3 来自数据的域
% Bases是个整数列表。以B表示Var，约束为B..B+2
% Bases的一员
two_domains(Bases, Var) :-
make_two_domains(Bases, Term),
Var in Term.
make_two_domains([H], H..HT) :-
HT is H + 2.
make_two_domains([H | T], '\\/'(H .. HT, TDomain)) :-
HT is H + 2,
make_two_domains(T, TDomain).
25 ?- two_domains([1, 8, 16], V).
V in 1..3\/8..10\/16..18 ;
8. 算术运算符
你可以用算术约束来进行很多约束工作。
约束可以采用中缀算术表达式。
X + 2 #= Y * 3
可用的运算符有
unary -,
+,
-,
*,
/（截断整数除法）,
^（幂）,
min,
max,
mod,
rem,
abs

9. 逻辑运算符
9.1 #\ 否定
一元运算符。反转所包含的约束。
9.2 #/\ 与
同时约束两边。
9.3 #\/ 或
至少约束一边。
10. 具体化
具体化是通过约束来控制其他约束的过程。clp(fd)包括两个用于具体化的操作符。
10.1. #<==> 等价
每边是个布尔型变量或是个约束。调节约束，使它们都成立或都不成立。
10.2. #==> 蕴含
如果左边成立，则右边必须成立。如果左边不成立，则右边被忽略。
示例 一些具体化的约束
在化工厂有个反应容器。容器中的温度被限定为必须低于某个特定的值，并在不是启动模式的情况下，还要高于另一个值。
chem_tank(Temp, Startup) :-
Temp #< 800,
#\ Startup #==> Temp #> 300.
我们可以将启动模式定义在某个起始时间后的10分钟。
chem_demo(Temp, TimeNow, StartTime) :-
chem_tank(Temp, TimeNow - StartTime #< 10).
注意，StartTime是作为一个约束传入的。你可以构建一个谓词来应用约束和应用约束所适用的条件。
工作练习
编写一个人与工作相匹配的小系统。这些工作对教育水平、能举起的重量、年龄、离家距离都有要求。能够在个人记录中记录特殊约束条件，比如，鲍勃在假释期间，离家不能超过20英里。莎莉需要帮手，但她不喜欢那些不工作时到处闲逛的工人。她想找一个住在10英里以外的人帮忙。
人们都有些有趣的状况，所以尽量把它们一般化。
对于这个练习，你可以假设（不现实地）用户了解Prolog。

11.常用约束
现在我们来看clp（fd）库中提供的更方便的谓词。大多同时建立大量的简单约束。
除了引入了方便的谓词外，这也是用约束开发工具的好办法。
以下是在各种约束情况下有用的一些约束。
11.1.length(List, Length)
在length(-, +)模式下，生成未绑定变量列表很有用。
提示
length_(Length, List) :- length(List, Length).有时在调用＋1情况下列出未绑定变量列表很方便。像length(List, 9), maplist(length_(9), List)给出了未绑定变量的二维数组。
length练习
?- length(X, 5)
现在尝试
?- length(X, Y).
11.2. all_different(List)
该谓词经常使用。它将列表的成员限制为不同的值。
all_different示例
?- length(List, 4),List ins 1..4, all_different(List), List = [1,_,3,4].
List = [1, 2, 3, 4].
all_different/1与鸽巢原理（抽屉原理）结合起来很有用，该原理指，如果你有N个变量，每个元素在1..M范围内，且N>M，那么一定有两个变量具有相同的值。出于这个原因，在上面的例子中，List肯定始终是[1,2,3,4]的排列。
all_distinct的工作方式类似于all_different，但是会尽力检测何时所有内容都不相同。
例如，我们尝试将3个变量约束在1..2范围中，且值不同——这是不可能的。
24 ?- X in 1..2, Y in 1..2, Z in 1..2, all_different([X,Y,Z]).
X in 1..2,
all_different([X, Y, Z]),
Y in 1..2,
Z in 1..2.
25 ?- X in 1..2, Y in 1..2, Z in 1..2, all_distinct([X,Y,Z]).
false.
26 ?-
上述内容中，all_different没有检测X、Y和Z只有两个可能的值，因此其中两个必须相同。
all_distinct会做更多工作来分析其变量的域，并会检测到这种情况。但是，使用all_distinct时cpu占用较高——因此，这需要提前裁剪搜索树以与性能提升进行平衡。
如果你遇到性能问题，那么使用其中一种方法进行审查可能是值得的。
11.3. tuples_in(+ListOfVariableTuples, +ListOfAcceptedTuples)
列出一些变量的可选组合列表是很常见的。一种常见的情况是点美式餐，你点的是一份套餐，套餐的价格包括一份主菜和两个配菜；但是如果你点的是馅饼，你只有一个配菜，等等。你需要列出所有不同的组合。
SWI-Prolog文档有个很酷的为旅行选择火车的演示。
示例5 火车旅程
:- use_module(library(clpfd)).
trains([[1,2,0,1], % 出发站，到达站，departs at, arrives at
[2,3,4,5],
[2,3,0,1],
[3,4,5,6],
[3,4,2,3],
[3,4,8,9]]).
threepath(A, D, Ps) :-
Ps = [[A,B,_T0,T1],[B,C,T2,T3],[C,D,T4,_T5]],
T2 #> T1,
T4 #> T3,
trains(Ts),
tuples_in(Ps, Ts).
?- threepath(1, 4, Ps).
Ps = [[1, 2, 0, 1], [2, 3, 4, 5], [3, 4, 8, 9]].
除了将它作为一种很酷的寻路方法之外，还请注意，我们无需做任何标记。这里只有一种解决方案。
如果发现元组看起来像[[1,2], [2,7], [3,8]…]，请考虑使用element/3代替。
tuples_in练习
1.修改“火车旅程”程序，使它能查有着任意数量火车的路线，而不仅仅是3。
2.要求你提供一张有资格晋升的员工表。你有的此列表的列表，每个内部列表是单个员工的记录。这些字段有员工编号、上次考核分数、违反安全法规次数、任职时间、晋升所需时间
employees([
[1, 75, 0, 30, 1],
[2, 83, 0, 45, 1],
[3, 90, 1, 45, 2],
[4, 45, 3, 75, 1],
[5, 89, 0, 52, 2]
]).
time_in_grade([[1,25], [2,50]]).
员工的最后考核成绩必须在80分以上，不超过1次安全违规，任职时间需超过晋升要求的时间，方有资格晋升。
3.最后一列，提升所需的时间，没有标准化。员工要么是团队成员，要么是团队领导。团队成员需要25周的任职时间，团队领导需要50周。首席架构师决定将其抽取到第二张表中，以便可以轻松更改这些数字。
employees([
[1, 75, 0, 30, 1],
[2, 83, 0, 45, 1],
[3, 90, 1, 45, 2],
[4, 45, 3, 75, 1],
[5, 89, 0, 52, 2]
]).
time_in_grade([[1,25], [2,50]]).
更新练习2，使用新的数据格式。
11.4.数独
好吧，这实际不是真正的数独谓词，但当变量被自然地表示为一个2D网格时，transpose(+Matrix, ?Transpose) 很有用。
将网格表示为列表的列表。每个列表就是一行。
许多约束谓词都可以处理列表中元素的相邻关系。如果您需要对行进行操作，则可以用maplist。要对列进行操作，请转置矩阵，它们现在就是行了。
提示
不，你不需要将其转置回来。新的转置矩阵与原先的共享。对它的任何约束都是对原先的约束。
例如，这是个解决“孩子吵架”问题的程序。通过只处理行，它就大大简化了
孩子吵架
/*
孩子吵架概述
16个孩子要坐在一个4 x 4椅子。
孩子有8个女孩（编号1..8），8个男孩（编号9..16）。
1,3,5,8认为男孩很烂
9,10,11,14认为女孩恶心
这几对是冤家
[[1,2], [4,6], [4,7], [4, 9],[9,11], [12, 14], [14,16]]
*/
length_(Length, List) :- length(List, Length).
child_row(X) :- X ins 1..16 .
ww(X) :-
write(X),
write('/').
print_row(Row) :-
maplist(ww, Row),
nl.
children(Class) :-
length(Class, 4),
maplist(length_(4), Class),
maplist(child_row , Class),
maplist(row_compatible, Class),
transpose(Class, TransClass),
maplist(row_compatible, TransClass),
flatten(Class, FlatClass),
all_different(FlatClass),
maplist(label, Class),
maplist(print_row, Class).
row_compatible([A,B,C,D]) :-
compatible(A, B),
compatible(B, C),
compatible(C, D).
compatible(A, B) :-
not_enemy(A, B),
not_enemy(B, A),
sex_compatible(A, B),
sex_compatible(B, A).
not_enemy(A, B) :-
NotA #\= A #\/ NotB #\= B,
tuples_in([[NotA, NotB]],
[[1,2], [4,6], [4,7], [4, 9],[9,11], [12, 14], [14,16]]).
sex_compatible(A, B) :-
A in 1\/3\/5\/8 #==> B #=< 8,
A in 9..11\/14 #==> B #> 8.
transpose练习
编写成为roguelike游戏的一部分的谓词。
您的游戏板是二维数组（列表的列表）。 每格包含以下元素之一
0-地面
1-墙
2-怪物
3-玩家
写一个谓词，can_move(+Board, -Moves)。Board是如上定义的游戏板。SafeMoves是个列表的列表，玩家可以移动的地方为1，不能移动的地方为0。必须遵守以下规则：
玩家可以向水平、垂直但不是对角线方向移动0、1、2或3个空格。
玩家无法穿过或到达墙上
玩家不能穿过或与怪物相邻
玩家无法移开游戏盘
示例运行（出于可读性采取了一些措施）：
游戏板示例
board([
[1,1,1,1,1,1,1,1],
[1,0,2,0,0,0,0,0],
[0,1,0,0,0,2,0,0],
[0,0,1,0,0,0,0,3],
[0,0,0,1,0,0,2,0],
[0,0,0,0,1,0,0,0],
[0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,1,0],
[0,0,0,0,0,0,0,1]
]).
?- board(B), can_move(B, M), writeq(M).
M = [
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,1,1],
[0,0,0,0,0,0,0,1],
[0,0,0,0,0,0,0,1],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0]
]
11.5. zcompare(?Order, ?A, ?B)
当你需要了解两个未标记变量的域之间的关系时，zcompare很有用。
10 ?- X in 0..10, Y in 11..20,zcompare(C, X, Y).
C = (<),
X in 0..10,
Y in 11..20.
11 ?- X in 0..11, Y in 11..20,zcompare(C, X, Y).
X in 0..11,
zcompare(C, X, Y),
freeze(C, clpfd:zcompare_(C, X, Y)),
Y in 11..20.
245/5000
我承认，第二个让我有些困惑。事实证明，C仍然不受约束，因为当它们的域重叠时，我们无法真正分辨X和Y之间的关系。但是，如果C稍后绑定，它将返回并约束X和Y！
15 ?- X in 0..11, Y in 11..20,zcompare(C, X, Y),C = <, writeln(C).
<
C = (<),
X in 0..11,
X#=<Y+ -1,
zcompare(<, X, Y),
Y in 11..20.
提示
试着想像调试代码时使用了大量zcompare
zcompare练习
创建一个约束谓词same_side_of_line/4，其参数是词典形式
point{x:12.34, y:56.78}
前两个参数是直线上的点，后两个参数是两个要测试点。 如果两个测试点都在直线的同侧，或两个都在直线上，则谓词成功，约束成立

12. 资源
clp(fd)非常适合解决资源受限的问题。
调度问题通常是一系列资源受限问题的组合。
大多此类问题能用基本的约束来解决，但内置在clp(fd)中的约束很好用。sum/3和 scalar_product/4非常易懂。
scalar_product/4的使用可能不是很明显。它对于定义不同事物具有不同成本（时间、金钱或其他）的关系很有用。
便士糖
%
% 便士糖示例
% 蒂米有25美分
% 口香糖需要1便士
% 士力架需要10美分
% 太妃糖2美分
% 甘草需要5美分
%
% 蒂米有哪些可选方案？
% 假设蒂米花了整整25美分
scalar_test(Candy) :-
Candy = [_Gumball, _Snickers, _Toffee, _Licorice],
Candy ins 0..sup,
scalar_product([1, 10, 2, 5], Candy, #=, 25),
label(Candy).
6 ?- scalar_test([Gumball, Snickers, Toffee, Licorice]).
Gumball = Snickers, Snickers = Toffee, Toffee = 0,
Licorice = 5 ;
Gumball = Snickers, Snickers = 0,
Toffee = 5,
Licorice = 3 ;
Gumball = Snickers, Snickers = 0,
Toffee = 10,
Licorice = 1 ;
Gumball = Toffee, Toffee = 0,
Snickers = 1,
Licorice = 3 ;
Gumball = 0,
Snickers = Licorice, Licorice = 1,
Toffee = 5 ;
...
提示
尝试在便士糖示例中删去Candy ins 0..sup这行。会发生什么？
13. 序列
我们常要事物按特定顺序排列。这些约束有助于建立序列。
13.1. chain(+List, +Relation)
Chain会对列表中每对相邻元素间建立关系约束。
Chain示例
chain_example([A,B,C,D]) :-
chain([A,B,C,D], #>=).
?- chain_example(X).
X = [_G4676, _G4679, _G4682, _G4685],
_G4676#>=_G4679,
_G4679#>=_G4682,
_G4682#>=_G4685.
13.2. lex_chain(+Lists)
lex_chain/1 更有趣，它接受一个列表的列表。它将内部列表约束为非递减的词典顺序。这意味着它们应从左侧开始的列进行排序。这是我们通常对文本进行排序的方式
andy
babble <-- below andy because a is less than b
beef <-- below babble because a is less than e
been <-- below beef because f is less than n
除了排序文本这种明显用途外，lex_chain还具有其他排序方面的用途。
医院的病人
医院中的病人将一组编码了的信息作为项。
patient(ID, Name, YearAdmitted, MonthAdmitted, DayAdmitted, HourAdmitted, MinuteAdmitted, Status, Payment)
状态为0（正常）或1（紧急）。
付款方式为0（个人）、1（保险）或2（医疗补助）。
这是一些病人
patient(1, 'Bob Jones', 2014, 10, 1, 4, 55, 0, 2).
patient(2, 'Sally Smith', 2014, 9, 29, 5, 15, 1, 0).
patient(3, 'Ted Overton', 2014, 9, 30, 14, 15, 0, 0).
patient(4, 'Arnold Abouja', 2014, 10, 1, 5, 0, 0, 0).
patient(5, 'Seth Humbolt', 2014, 10, 1, 5, 10, 0, 0).
根据以下规则限定病人：
1.先看紧急的病例，再看正常的病例。
2.对于处于相同状态（紧急/正常）的患者，请按到达的顺序查看病人，除非
3.如果支付方式为个人或保险的病人在接受医疗补助的患者之后一个小时内到达，请先看他们。
提示：使用lex_chain
13.3. element(?Index, +List, ?Element)
Element是约束 nth1/3的等价物。
它通过列表中元素的位置来约束它。元素必须是列表相应索引的成员，从1开始计数。
苏西调情示例
%
% 苏西想和纳森调情
% 但当她的老男友约翰在身边的时候就不会
%
% 苏西、纳森和约翰都必须参加课程1..6
%
% 苏西如何安排日程以便在至少3个课程调情？
flirt_constraint(Suzy, Nathan, John, FlirtPeriods) :-
length(Suzy, 6),
length(Nathan, 6),
length(John, 6),
Suzy ins 1..6,
Nathan ins 1..6,
John ins 1..6,
all_different(Suzy),
all_different(Nathan),
all_different(John),
FlirtPeriods = [A,B,C],
FlirtPeriods ins 1..6,
A #< B, % remove unwanted symmetry
B #< C,
flirty_period(A, Suzy, Nathan, John),
flirty_period(B, Suzy, Nathan, John),
flirty_period(C, Suzy, Nathan, John),
label(Suzy),
label(FlirtPeriods).
flirty_period(Period, Suzy, Nathan, John) :-
Class in 1..6,
DiffClass #\= Class,
element(Period, Suzy, Class),
element(Period, Nathan, Class),
element(Period, John, DiffClass).
element谓词的一个非常重要的用途是帮助约束不同的事实。
例如，假设我们有一群人，要按照他们名字的字母顺序对其进行编号。现在我们要使一对成为浪漫的伴侣。作为异性恋和重视年龄代沟的人，我们要限制他们是异性并且年龄差在10年以内。
这个示例还显示了从索引号到我们最终想要的名称。出于教学之便，它违反了clp(fd)的风格规则——在一个谓词中设定模型，在另一个谓词中标记。
示例7. 浪漫情侣
:- use_module(library(clpfd)).
names([amy,bill,charley,deanna,eric,frieda,george,harley]).
% 女人是1，男人是0
genders([1,0,0,1,0,1,0,0]).
ages([22,19,73,65,40,38,25,27]).
% 映射一致的名称
romance(A, B) :-
names(Names),
length(Names, NameLength),
AIndex in 1..NameLength,
BIndex in 1..NameLength,
genders(G),
element(AIndex, G, AG),
element(BIndex, G, BG),
AG #\= BG,
ages(Ages),
element(AIndex, Ages, AAge),
element(BIndex, Ages, BAge),
AAge #< BAge #==> AAge + 10 #>= BAge,
AAge #>= BAge #==> BAge + 10 #>= AAge,
AIndex #< BIndex, % remove unwanted symmetry and reflexiveness
label([AIndex, BIndex]),
nth1(AIndex, Names, A),
nth1(BIndex, Names, B).
7 ?- romance(A,B).
A = amy,
B = bill ;
A = amy,
B = george ;
A = amy,
B = harley ;
A = charley,
B = deanna ;
A = eric,
B = frieda ;
false.
13.4. circuit(+List)
关于这方面的文档，所带来的困惑要多于启发。
circuit/1读取变量列表并约束它们形成一个序列，其中第1个之后每个数字为 Vn+1 = Vn mod L + 1。其中Vn是元素，Vn+1是下一个元素，L是列表长度。
因此，这是时钟算法。
circuit示例
?- length(Vs, _), circuit(Vs), label(Vs).
Vs = [] ;
Vs = [1] ;
Vs = [2, 1] ;
Vs = [2, 3, 1] ;
Vs = [3, 1, 2] ;
Vs = [2, 3, 4, 1] .
13.5. 自动机
自动机是900磅的排序大块头。
自动机出自自动机理论，即抽象机器的研究。automaton / 3将其第一个参数约束为可以被有限接受器识别的语言元素。 automaton / 8会将其第一个参数约束为下推接受器可以识别的语言元素。
做什么？（数学家们避开眼睛，我将在快速而宽松的游戏中解释有限自动机）。
有限自动机有点像跳房子游戏。你有一组有限的状态和有方向弧线。每个线都与一个输入关联。这就是一个典型的自动机。

从绿色状态开始。阅读序列中的第一个元素，如果有一个标有它的弧线，请转到该状态。如果不是，则序列不在语言中。如果存在，请在新状态下重复——读取下一个元素，然后尝试沿弧线运行。如果您处于蓝色状态，那么到此为止，你所阅读的内容就是该语言的一部分。
我们的语言接受一个或多个0，然后是1，然后是2。
绿色状态称为源状态，蓝色状态为宿状态。一个状态可以同时是源和宿。
这是如何在SWI-Prolog中编写它：
示例8 单源自动机
single_source_automaton(Vs) :-
automaton(Vs, [source(a), sink(d)],
[arc(a,0,b),
arc(b,0,b),
arc(b,1,c),
arc(c,2,d)
]).
demo_single_source(Vs) :-
length(Vs, 4),
single_source_automaton(Vs),
label(Vs).
这是我们第一个自动机的变体，它与第一个自动机相同，但是使所有数字加10，因此它接受10、10、10、10、11、12这样的序列。

示例9 多源自动机
multi_source_automaton(Vs) :-
automaton(Vs, [source(a),source(e), sink(d), sink(h)],
[arc(a,0,b),
arc(b,0,b),
arc(b,1,c),
arc(c,2,d),
arc(e,10,f),
arc(f,10,f),
arc(f,11,g),
arc(g,12,h)]).
demo_len(Vs) :-
length(Vs, 4),
multi_source_automaton(Vs),
label(Vs).
automaton/3示例——某些员工晚上不工作，其他一些周末不工作，我们使用自动机对它进行编码，读取轮班人员的列表。也许员工示例够多了——那有效消息如何？
automaton/8——暂停，直到我明白为止
计数器示例——对员工示例示例进行拓展，获得员工的最大和最小班次数。

14.安排
日程安排是我们每天都要做的事情。鲍勃只能在2点到3点见面；你要连续几个小时考虑数据库；妈妈要过来吃午饭。这也是一个主要的经济制约因素——工厂可以在3月到7月生产拖拉机部件，但得为圣诞节转而生产豆豆娃。
序列化表示不能在两个地方出现同样的约束。它需要两个长度相同的列表，第一个是开始时间，第二个是持续时间。限制它们开始和持续时间所定义的区间不重叠。 请注意，它不必按顺序排列——即，serialized([4,0,2], [1,1,1])也是可以通过的。
示例10. 日程安排
:- use_module(library(pairs)).
my_schedule_today(Starts, Durations) :-
% 杂乱的待办事项清单
% 这些都是24小时制的小时，在实际问题中，我们可能会使用分钟
Starts = [PrepForSmith, MeetWithSmith, _WriteDBInstaller, Lunch, _CallAlice, _ReadDocs],
% 它们所需的时间
Durations = [2, 1, 2, 1, 1, 1],
% 它们都在从上午9点到下午5点的范围内
Starts ins 9..17,
% 并确保午餐在时间在中午或下午1点
Lunch in 12 \/ 13,
% 与史密斯的会面定于下午1点
MeetWithSmith #= 13,
% 在会议前要做的准备
PrepForSmith #< MeetWithSmith, % 执行被序列化
serialized(Starts, Durations).
demo_my_schedule(Starts, Durations) :-
my_schedule_today(Starts, Durations),
append(Starts, Durations, Vars),
label(Vars),
pairs_keys_values(NameDurs ,
['Prep for Smith', 'Meet With Smith', 'Write DB Installer', 'Lunch', 'Call Alice', 'Read Flubbercalc Docs'], Durations),
pairs_keys_values(Pairs, Starts, NameDurs),
keysort(Pairs, Sorted),
pairs_keys_values(Sorted, SortStarts, SortNameDurs),
print_sched(SortStarts, SortNameDurs).
print_sched([], _).
print_sched([Start | ST], [Name-Duration | T]) :-
format('~w: ~w (~w hr)~n', [Start, Name, Duration]),
print_sched(ST, T).
8 ?- demo_my_schedule(Starts, Durations).
9: Prep for Smith (2 hr)
11: Call Alice (1 hr)
12: Lunch (1 hr)
13: Meet With Smith (1 hr)
14: Write DB Installer (2 hr)
16: Read Flubbercalc Docs (1 hr)
Starts = [9, 13, 14, 12, 11, 16],
Durations = [2, 1, 2, 1, 1, 1] ;
9: Prep for Smith (2 hr)
11: Call Alice (1 hr)
12: Lunch (1 hr)
13: Meet With Smith (1 hr)
14: Write DB Installer (2 hr)
17: Read Flubbercalc Docs (1 hr)
Starts = [9, 13, 14, 12, 11, 17],
Durations = [2, 1, 2, 1, 1, 1]
14.1. global_cardinality/3
global_cardinality/3计算每个值在第一个参数中出现次数。
这有一个例子。假设我们有一个24/7便利店轮班的员工名单。
shifts([1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,4,5,6,4,5,3]).
我们想知道每个员工轮班多少次。
shifts([1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,4,5,6,4,5,3]).
count_shifts(Counts) :-
shifts(Shifts),
bagof(X, between(1,6,X), Keys),
length(Values, 6),
pairs_keys_values(Counts, Keys, Values),
global_cardinality(Shifts, Counts, []).
记住，我们在限制条件下，所以即使你先前不知道轮班情况，也是可行的
post_shifts(Counts) :-
length(UnknownShifts, 21),
bagof(X, between(1,6,X), Keys),
length(Values, 6),
pairs_keys_values(Counts, Keys, Values),
global_cardinality(UnknownShifts, Counts, []),
% 在这一点上，我已经限制了Counts和UnknownShifts，
% 尽管我不知道UnknownShifts
shifts(UnknownShifts).% now it's bound
global_cardinality/3有两个选项
consistency(value) -呈现较弱的一致性，我不知道这是什么，如果你发现了请告诉我
cost(Cost, Matrix) -给定一个由键i在位置j的值组成的矩阵，将总价值约束为Cost
global_cardinality练习
设计一个练习，该练习涵盖global_cardinality的cost/2选项。并包括解决方案。
14.2. cumulative/2和cumulative/1
cumulative/2获取任务列表，并约束它们在任务期间的任何时间不超过限制。
可以通过开始、持续时间和结束中两者的任意组合灵活地指定任务。每个任务还具有其使用的资源和一个任务标识符。
umulative/1默认限制为1。
示例11. 机械
%
% 我们有3个机械师，一些维修工作需要2个机械师来完成%
% 找出每天10小时一组工作的开始时间
%
task_names([ transmission, brake_job_1, brake_job_2, diagnosis_1,
diagnosis_2, fuel_injection]).
tasks([ task(S1,3,_,2,1),
task(S2,1,_,1,2),
task(S3,1,_,1,3),
task(S4,3,_,1,4),
task(S5,3,_,1,5),
task(S6,2,_,1,6)], [S1, S2, S3, S4, S5, S6]).
find_task_starts(S) :-
length(S, 6),
S ins 0..9,
tasks(Tasks, S),
cumulative(Tasks, [limit(3)]),
label(S).
2 ?- find_task_starts(S).
S = [0, 0, 1, 2, 3, 3] ;
S = [0, 0, 1, 2, 3, 4] ;
S = [0, 0, 1, 2, 3, 5] ;
S = [0, 0, 1, 2, 3, 6] ;
S = [0, 0, 1, 2, 3, 7] .
cumulative练习
1）看起来技工不是很忙。添加更多任务。
2）机械师仅在一天的前3个小时工作。考虑这一点修改示例。
15. 优化
我们经常要不光满足一组约束条件，还要找到最优解。像“工厂应该生产哪些产品来实现利润最大化？”和“有3个机械师，我们能多快修好所有这些车？”这样的问题都是优化问题。
label/1有两个版本，名称稍有不同，即labeling/2。选项是第一个参数。这些选项对于优化问题和提高标记过程的效率都很重要。
现在我们要关注的两个是max/1和min/1。将其中一个变量添加到选项，将使解决方案按顺序显示，最左边为最大值或最小值，然后按序向下排列。条件为max则按递减顺序排序，条件为min则按递增顺序排序。
中序遍历
7 ?- [X,Y] ins 1..3, labeling([max(X), min(Y)], [X,Y]).
X = 3,Y = 1 ;
X = 3,Y = 2 ;
X = Y, Y = 3 ;
X = 2,Y = 1 ;
X = Y, Y = 2 ;
X = 2,Y = 3 ;
X = Y, Y = 1 ;
X = 1,Y = 2 ;
X = 1,Y = 3 ;
false.

希望那个教程网站能早日恢复正常。🙏

那个网站还是打不开，但发现Github上也有这个教程。以后有时间会继续更新的。

最近比较忙，但愿有时间就写。