基本算法问题的 Python 解法——约束满足问题（CSP）

由计算工具解决的很大一部分问题都可以归类为约束满足问题（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() 方法必须为抽象方法，由子类覆盖后发挥实际作用，以满足不同问题的不同约束条件。

# 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

@abstractmethod
    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 三类数据的初始化。

# 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 关联的所有约束条件。

# 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）。

def 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

逐条分析以上代码：

if len(assignment) == len(self.variables):
    return assignment

上面的 backtracking 搜索采用了递归的形式，此 if 语句则提供了一种递归的终止条件。即当所有 variable 都被赋予了合法的值时，意味着其中一种搭配方案已被找到，则停止进一步的搜索，返回该搭配方案。

unassigned: List[V] = [v for v in self.variables if v not in assignment]
first: V = unassigned[0]

取出 variables 中第一个还未被赋值（未做选择）的 variable，作为下一步中进行赋值（做决定）和约束条件测试的对象。

if self.consistent(first, local_assignment):
    result: Optional[Dict[V, D]] = self.backtracking_search(local_assignment)
    if result is not None:
        return result

为前面未赋值的某个 variable “做决定”。将对应的 domain 中所有存在的值依次赋值给该 variable，形成一个新的方案（local_assignment）。若该方案符合所有的约束条件（通过 consistent() 方法检测），则借助递归进行下一轮对另一个 variable 的赋值，直到触发终止条件（所有 variable 都被赋值）。

return None

若针对某个特定的 variable，已经检查完 domain 中包含的所有可能的值，仍没有找到符合要求的方案，则返回 None 表示没有解决。这会导致 backtracking 搜索结束本轮 for 循环，返回到递归的上一层中的 for 循环，尝试为上一步中已赋值的 variable 做出不同的决定，并继续递归（或回溯）下去。

地图上色问题

假如有一张澳大利亚地图，需要按州进行上色。要求所有相邻的州不能有相同的颜色。

借助前面构建的约束符合框架，实现代码如下：

# 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 个王后放置到国际象棋棋盘上且彼此之间不会产生冲突（即不会有任意两枚棋子位于同一行、同一列或者同一斜线上）。

其中一种可能的解决方案如下图：

实现代码如下：

from 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