由计算工具解决的很大一部分问题都可以归类为约束满足问题（CSPs, constraint-satisfaction problems）。CSP 一般包含三个基本概念：变量（variables）、域（domains）和约束条件（constraints）。
比如需要在星期五为 Joe、Mary、Sue 三个人安排一场会议，要求 Sue 必须和另外的至少一个人同时在场。针对此问题：
- Joe、Mary、Sue 三个人即为变量（variables）
- 每个人（变量）各自空闲的时间点即为对应的域（domains）。比如变量 Mary 在下午 2 点和 3 点的时候有空，这两个时间点即为变量 Mary 对应的域
- 约束条件（constraints）有两点：Sue 必须在场；除 Sue 以外至少还需要另一人到场
构建 CSP 框架
约束条件通过 Constraint 类实现。该类中包含被约束的变量以及测试其是否满足约束的 satisfied() 方法。确定是否满足约束条件是针对某个特定的 CSP 的核心逻辑，该 satisfied() 方法必须为抽象方法，由子类覆盖后发挥实际作用，以满足不同问题的不同约束条件。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15# csp.py
from typing import Generic, TypeVar, Dict, List, Optional
from abc import ABC, abstractmethod
V = TypeVar('V') # variable type
D = TypeVar('D') # domain type
class Constraint(Generic[V, D], ABC):
def __init__(self, variables: List[V]) -> None:
self.variables = variables
def satisfied(self, assignment: Dict[V, D]) -> bool:
pass
约束满足框架的核心部分代码是 CSP 类，该类集中处理变量、域和约束条件。CSP 的类型使用 Generic，目的是使其足够灵活，能够处理各种类型的 variables 和 domains。其中 variables 是 list 类型，domains 是由 variable 和对应的 list （所有可能的值）关联成的 dict 类型，constraints 则是由 variable 和对应的 list（约束条件列表）关联成的 dict 类型。
__init__() 初始化方法会创建 constraints 字典，将 variables 中的值作为键，每个键关联一个空列表。add_constraint() 方法遍历 variables 中的值（同时也是 constraints 中的键），将对应的 constraint 添加到 constraints 字典的该 variable 键关联的列表中。
从而完成对 variables、domains、constraints 三类数据的初始化。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17# csp.py
class CSP(Generic[V, D]):
def __init__(self, variables: List[V], domains: Dict[V, List[D]]) -> None:
self.variables = variables
self.domains = domains
self.constraints: Dict[V, List[Constraint[V, D]]] = {}
for variable in self.variables:
self.constraints[variable] = []
if variable not in self.domains:
raise LookupError("Every variable should have a domain assigned to it")
def add_constraint(self, constraint: Constraint[V, D]) -> None:
for variable in constraint.variables:
if variable not in self.variables:
raise LookupError("Variable in constraint not in CSP")
else:
self.constraints[variable].append(constraint)
consistent() 方法用于检查给定的 variable 对应的每一个约束条件是否一一符合当前预设的方案。这个临时的方案用 assignment 表示。
即先有某个 variable，然后为其选择对应的 domain 中的任意一个值作为临时的 assignment，再检查该 assignment 是否符合对应的 variable 关联的所有约束条件。1
2
3
4
5
6# csp.py
def consistent(self, variable: V, assignment: Dict[V, D]) -> bool:
for constraint in self.constraints[variable]:
if not constraint.satisfied(assignment):
return False
return True
约束满足框架还需要一个简单的 backtracking 搜索用于查找问题的解决方案。Backtracking 意味着一旦在搜索路径的某个节点上终止，则返回到上一个已知的搜索节点，选择另一条搜索路径。有点类似于深度优先搜索（DFS, depth-first search）。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16def backtracking_search(self, assignment: Dict[V, D] = {}) -> Optional[Dict[V, D]]:
# assignment is complete if every variable is assigned
if len(assignment) == len(self.variables):
return assignment
# get all variables in the CSP but not in the assignment
unassigned: List[V] = [v for v in self.variables if v not in assignment]
first: V = unassigned[0]
for value in self.domains[first]:
local_assignment = assignment.copy()
local_assignment[first] = value
if self.consistent(first, local_assignment):
result: Optional[Dict[V, D]] = self.backtracking_search(local_assignment)
if result is not None:
return result
return None
逐条分析以上代码：1
2if len(assignment) == len(self.variables):
return assignment
上面的 backtracking 搜索采用了递归的形式，此 if 语句则提供了一种递归的终止条件。即当所有 variable 都被赋予了合法的值时，意味着其中一种搭配方案已被找到，则停止进一步的搜索，返回该搭配方案。
1 | unassigned: List[V] = [v for v in self.variables if v not in assignment] |
取出 variables 中第一个还未被赋值（未做选择）的 variable，作为下一步中进行赋值（做决定）和约束条件测试的对象。
1 | if self.consistent(first, local_assignment): |
为前面未赋值的某个 variable “做决定”。将对应的 domain 中所有存在的值依次赋值给该 variable，形成一个新的方案（local_assignment）。若该方案符合所有的约束条件（通过 consistent() 方法检测），则借助递归进行下一轮对另一个 variable 的赋值，直到触发终止条件（所有 variable 都被赋值）。
return None
若针对某个特定的 variable，已经检查完 domain 中包含的所有可能的值，仍没有找到符合要求的方案，则返回 None 表示没有解决。这会导致 backtracking 搜索结束本轮 for 循环，返回到递归的上一层中的 for 循环，尝试为上一步中已赋值的 variable 做出不同的决定，并继续递归（或回溯）下去。
地图上色问题
假如有一张澳大利亚地图，需要按州进行上色。要求所有相邻的州不能有相同的颜色。
借助前面构建的约束符合框架，实现代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47# map_coloring.py
from csp import Constraint, CSP
from typing import Dict, List, Optional
class MapColoringConstraint(Constraint[str, str]):
def __init__(self, place1: str, place2: str) -> None:
super().__init__([place1, place2])
self.place1 = place1
self.place2 = place2
def satisfied(self, assignment: Dict[str, str]) -> bool:
# if either place is not in the assignment, then it is not
# yet possible for their colors to be conflicting
if self.place1 not in assignment or self.place2 not in assignment:
return True
# check the color assigned to place1 is not the same as the
# color assigned to place2
return assignment[self.place1] != assignment[self.place2]
if __name__ == "__main__":
variables: List[str] = ["Western Australia", "Northern Territory", "South Australia",
"Queensland", "New South Wales", "Victoria", "Tasmania"]
domains: Dict[str, List[str]] = {}
for variable in variables:
domains[variable] = ["red", "green", "blue"]
csp: CSP[str, str] = CSP(variables, domains)
csp.add_constraint(MapColoringConstraint("Western Australia", "Northern Territory"))
csp.add_constraint(MapColoringConstraint("Western Australia", "South Australia"))
csp.add_constraint(MapColoringConstraint("South Australia", "Northern Territory"))
csp.add_constraint(MapColoringConstraint("Queensland", "Northern Territory"))
csp.add_constraint(MapColoringConstraint("Queensland", "South Australia"))
csp.add_constraint(MapColoringConstraint("Queensland", "New South Wales"))
csp.add_constraint(MapColoringConstraint("New South Wales", "South Australia"))
csp.add_constraint(MapColoringConstraint("Victoria", "South Australia"))
csp.add_constraint(MapColoringConstraint("Victoria", "New South Wales"))
csp.add_constraint(MapColoringConstraint("Victoria", "Tasmania"))
solution: Optional[Dict[str, str]] = csp.backtracking_search()
if solution is None:
print("No solution found")
else:
print(solution)
# => {'Western Australia': 'red', 'Northern Territory': 'green', 'South
# Australia': 'blue', 'Queensland': 'red', 'New South Wales': 'green',
# 'Victoria': 'red', 'Tasmania': 'green'}
简单梳理一下程序逻辑：
在上述 CSP 中，地图中的 7 个州即为 variables（为方便，以 a、b、c、d、e、f、g 代替）variables = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
每个州都可以涂成红绿蓝三种颜色（假设用 1、2、3 指代）中的任何一种，各 variable 对应的所有颜色即组成对应 variable 的 domain：domains = {'a': [1, 2, 3], 'b': [1, 2, 3], 'c': [1, 2, 3], 'd': [1, 2, 3], 'e': [1, 2, 3], 'f': [1, 2, 3], 'g': [1, 2, 3]}
constraints 的逻辑在 MapColoringConstraints 类中实现，即已经涂色的相邻的两个州色彩须不一致。比如 a 与 b 相邻，则该 constraint 的表示如下：MapColoringConstraint('a', 'b')
而所有的 constraints 都会关联到对应的以 variable 为键的字典中。即若 a 同时与 b 和 c 相邻，则变量 a 的 constraints 表示为：{'a': [MapColoringConstraint('a', 'b'), MapColoringConstraint('a', 'c')]}
backtrack_search() 方法的执行流程为：
- 在 variables 中取第一个未被赋值（涂色）的 variable，为其赋予对应 domain 中的某个数值作为临时方案
- 用该 variable 对应的所有 constraints 测试上述临时方案的可行性。若符合要求，则借助递归开启下一轮循环，继续为另一个未被赋值（涂色）的 variable 赋值
- 若不符合要求，则继续本轮循环，为本 variable 赋予 domain 中的另一个值
- 若对应 domain 中的所有值赋予 variable 后都不能符合约束要求，则返回 None。本轮循环结束，回到递归的上一轮继续循环，为上一轮中已赋值的 variable 赋予不同的值，延续递归操作
- 若所有 variable 都已被赋值，则返回 variable 及其对应的值作为最终的解决方案；若所有循环（递归/回溯）结束，返回结果最终为 None，则表示无法找到合理的解决方案
国际象棋的八王后问题
国际象棋的棋盘由 8x8 的方格组成，棋子落于方格上。而棋子王后能够吃掉处于同一行、同一列、同一斜线上的任何一个敌方棋子。
八王后问题是指需要将 8 个王后放置到国际象棋棋盘上且彼此之间不会产生冲突（即不会有任意两枚棋子位于同一行、同一列或者同一斜线上）。
其中一种可能的解决方案如下图：
实现代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37from csp import Constraint, CSP
from typing import Dict, List, Optional
class QueensConstraint(Constraint[int, int]):
def __init__(self, columns: List[int]) -> None:
super().__init__(columns)
self.columns = columns
def satisfied(self, assignment: Dict[int, int]) -> bool:
# q1c = queen 1 column, q1r = queen 1 row
for q1c, q1r in assignment.items():
# q2c = queen 2 column
for q2c in range(q1c + 1, len(self.columns) + 1):
if q2c in assignment:
q2r = assignment[q2c]
if q1r == q2r: # same row?
return False
if abs(q1r - q2r) == abs(q1c - q2c): # same diagonal?
return False
return True
if __name__ == "__main__":
columns: List[int] = [1, 2, 3, 4, 5, 6, 7, 8]
rows: Dict[int, List[int]] = {}
for column in columns:
rows[column] = [1, 2, 3, 4, 5, 6, 7, 8]
csp: CSP[int, int] = CSP(columns, rows)
csp.add_constraint(QueensConstraint(columns))
solution: Optional[Dict[int, int]] = csp.backtracking_search()
if solution is None:
print("No solution found!")
else:
print(solution)
# => {1: 1, 2: 5, 3: 8, 4: 6, 5: 3, 6: 7, 7: 2, 8: 4}
简单解释下 satisfied() 方法中的两个 for 循环。assignment 采用类似 {1: 1, 2: 5, 3: 8, 4: 6, 5: 3, 6: 7, 7: 2, 8: 4} 的字典类型（一开始会短一些），上述两个 for 循环的作用在于，先以棋盘上的第一列为标准，若第一列与剩余的几列不存在冲突，则去掉第一列，再比较第二列与剩余的几列是否存在冲突，以此类推。一旦出现任何冲突，则返回 False。
参考资料
Classic Computer Science Problems in Python
davecom/ClassicComputerScienceProblemsInPython