04-八皇后问题

选择背景色：黄橙洋红淡粉水蓝草绿白色选择字体：宋体黑体微软雅黑楷体选择字体大小：小中大特恢复默认

3.3　八皇后问题

棋盘是8×8的正方形网格。皇后是可以在棋盘上沿任何行、列或对角线移动任意个格子的棋子。每次移动时，皇后会攻击其他的某个棋子，它能移动到该棋子所在的格子但不会越过任何其他棋子。换句话说，如果有其他棋子在皇后的视线范围内，它就会受到攻击。八皇后问题提出，如何在不发生相互攻击的情况下将8个皇后放在棋盘上，如图3-3所示。

图3-3　在八皇后问题的解（解有很多）中，两个皇后间不能相互构成威胁

为了表示棋盘上的格子，我们将为每个格子赋予整数的行号和列号。只要简单地按顺序从第1列到第8列赋值（图3-3中用a～h表示），即可确保8个皇后中的每一个都不在同一列上。不妨将此约束满足问题中的变量设为皇后所在的列号。值域则可以是摆放皇后的可能的行号（同样也是从1到8）。代码清单3-8展示了源码文件的最后部分，其中定义了这些变量和值域。

代码清单3-8　queens.py

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)

为了解决八皇后问题，我们需要有一个约束来检查任意两个皇后是否位于同一行或同一对角线上。（一开始它们已经都被赋予了不同的列号。）检查它们是否位于同一行十分简单，但检查它们是否位于同一条对角线则需用到一点点数学知识。如果任意两个皇后位于同一条对角线上，则它们所在的行差将与列差相同。你能在 QueensConstraint 中找出进行上述检查的代码吗？注意，代码清单3-9所示的代码位于源码文件的开始部分。

代码清单3-9　queens.py（续）

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: List[int] = 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: int = assignment[q2c] # q2r = queen 2 row
                    if q1r == q2r: # same row?
                        return False
                    if abs(q1r - q2r) == abs(q1c - q2c): # same diagonal?
                        return False
        return True # no conflict

剩下的工作就是加入约束并运行搜索了。现在回到源码文件的底部，如代码清单3-10所示。

代码清单3-10　queens.py（续）

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}

Previous 上一篇本节目录 Next 下一篇

04-八皇后问题

3.3 八皇后问题

3.3　八皇后问题