主要想要解决在绪论中提到的「约束满足问题」（找到一个满足一系列约束的可行解）。
Key Idea: Remove values that cannot appear in any solution. i.e, not feasible ones.
Modeling Methodology:
- 使用推理得到一些推论，比如什么情况下必须要怎么做、什么情况下能判断剪枝等等。
- Give solvers as much information as possible。

一、四色问题

问题描述：用 4 色给一个地图上色，要求相邻的区域不能上相同的颜色。区域不存在飞地之类的。
- 用建模语言来描述，是这样的：
- 我觉得也可以用图模型来表示。
  - 当然，由于是二维地图衍生过来的图，也许这是一个几何上平铺的图，所有的边都不会存在交叉。
可能的优化思路：先决定那些具有更多相关约束的区域，这能通过对称性或者帮助优化剪枝降低搜索规模。
一种实现是 Constraint Programming System，也就是将所有的约束记录在一张大表格中，并在搜索的过程中追踪这些约束的激活情况，以此来剪掉不可行的分支。
- 比如下面是为 color[Belgium] 指配了 black 后的所有条件。
还有一种实现是，我们可以将相邻约束问题转化为为每一个区域追踪一个「还能选择的颜色」的列表，如果有一个待定区域没有可选颜色了就说明不可行；如果有且仅有一种颜色就是必走的路径。

二、八皇后问题

问题：将八个皇后放在 8×8 棋盘上。
推论：每个行必须有且仅有一个皇后（不然会有两个皇后处于同一列）。
在任意节点，我们可以记录下整个棋盘中有哪些位置不能放皇后了，然后可以这样进行逻辑判断：
- 如果有待定的一行或者一列都没有可放皇后的位置了，说明这个分支不可行。
- 如果有待定的一行或者一列有且仅有一个可放皇后的位置，说明这个分支后面只能把皇后放在这个位置。
一个模型
- 考虑到每个行有且仅有一个皇后，变量表示第 $i$ 行（$i \in [1..8]$）的皇后在第 $x_i$ 列，$x_i \in [1..8]$。
- 这样要考虑的约束就是各列有没有碰撞、各个对角线有没有碰撞。
- 这样的模型可以编写为：
```
range R = 1..8;
var{int} x[R] in R;

solve {
	forall (i in R, j in R: i < j) {
		x[i] \\neq x[j];
		x[i] \\neq x[j] - (j-i);
		x[i] \\neq x[j] + (j-i);
	}
}
```

三、Constraint Programming Solver

CPS 系统的目标：在极大规模的离散解空间中高效地排除无解分支，显著减少搜索量，解决各类组合优化与可行性问题。

3.1 接口与现成库

这是一个来自某个 CPS 库 https://pypi.org/project/python-constraint/ 的例子。

>>> from constraint import *

>>> problem = Problem()
>>> problem.addVariable("a", [1,2,3])
>>> problem.addVariable("b", [4,5,6])
>>> problem.getSolutions()
[{'a': 3, 'b': 6}, {'a': 3, 'b': 5}, {'a': 3, 'b': 4},
 {'a': 2, 'b': 6}, {'a': 2, 'b': 5}, {'a': 2, 'b': 4},
 {'a': 1, 'b': 6}, {'a': 1, 'b': 5}, {'a': 1, 'b': 4}]

>>> problem.addConstraint(lambda a, b: a*2 == b,
                          ("a", "b"))
>>> problem.getSolutions()
[{'a': 3, 'b': 6}, {'a': 2, 'b': 4}]

>>> problem = Problem()
>>> problem.addVariables(["a", "b"], [1, 2, 3])
>>> problem.addConstraint(AllDifferentConstraint())
>>> problem.getSolutions()
[{'a': 3, 'b': 2}, {'a': 3, 'b': 1}, {'a': 2, 'b': 3},
 {'a': 2, 'b': 1}, {'a': 1, 'b': 2}, {'a': 1, 'b': 3}]

3.2 构成与算法

下面来看看 CPS 的要素构成。
1. 变量取值域：各个变量离散或连续的取值域。
  - 比如 $x \in [1..8]$。
2. 变量间的约束
  1. 算术约束，比如 $x+y \le 10$、$x=2y$。
  2. 逻辑约束，比如 ${\rm if} \, x > 0 \, {\rm then} \, y > 0$。
  3. 其他复杂的约束，比如 AllDifferent（各自取值不同）等。
- 这些不仅可能是问题提供的静态域和约束，也可能存在搜索决策中的动态域和约束。
约束的作用：
- 可行性检测：看看现在的域是不是存在可行解的。
  - 比如说，约束 $x \neq y$ 对应的可行性判定方法是 $|D(x) \cup D(y) | \ge 2$。一个例子是当现在的可行域 $x \in \{ 0, 1, 2 \}, \, y \in \{ 1, 2, 3 \}$ 时，判定的结果是 $4 \ge 2$ 是通过的。
- 剪枝：看看能从域里面删减 (prune) 什么内容。一般会在有部分变量的确定性较高（可行域很小）的时候进行。
  - 比如说，约束 $x \neq y$ 当 $x$ 的可行域中只有唯一一个数值（它为确定的）时，显然可以将 $D(y)$ 更新为 $D(y) \backslash D(x)$。