在该系列上一篇中，我们展示了如何使用纯函数语言haskell解决八皇后问题，今天我们来了解一下声明式编程(Declarative Programming)。和常见的命令式编程范式相比，我们在声明式编程中主要就是声明我们需要解决的问题，程序会自动解答。说到声明式编程就不得不提到大名鼎鼎的Prolog语言，但是由于网上已经有大量Prolog相关的资料以及Prolog解决八皇后问题的讲解，所以本文以在Python中使用python-constraint利用声明式的思想解八皇后问题。
1 python-constraint简介
python-constraint是一个用来解决约束编程(Constraint programming)的Python库，可以使用pip直接安装：
pip install python-constraint
我们以求以下方程组的整数解为例：
$$\begin{cases} a + b = 7 \ a \times b = 12 \end{cases}$$
具体代码如下：
from constraint import Problem
problem = Problem()
problem.addVariables(['a', 'b'], range(1, 7))
problem.addConstraint(lambda a, b: a + b == 7, ('a', 'b'))
problem.addConstraint(lambda a, b: a * b == 12, ('a', 'b'))
problem.getSolutions()
在以上代码中，我们首先声明一个Problem对象，然后添加了变量$a$和$b$。值得注意的是，我们这里添加的$a$和$b$的范围均为$1 \leqslant a \leqslant 6,1 \leqslant b \leqslant 6$。接下来，再依次添加约束条件$a + b = 7$以及$a \times b = 12$。至此我们完成了对待解决问题的声明，最后，我们让计算机给出答案。最终返回的结果为：
[{'a': 4, 'b': 3}, {'a': 3, 'b': 4}]
2 八皇后问题
八皇后问题在该系列的第一篇中已经解释过了，即能否在一个棋盘上放置8枚皇后，并且没有一枚皇后收到攻击。对于$n \times n$的棋盘，我们需要$n$个变量，分别表示该列上摆放皇后的行号。然后我们添加任意两个皇后均不相互攻击的约束条件，即任意两个皇后均不在同一行或者同一斜线上。完成问题的定义后即可让程序自动计算答案，详细代码如下：
from constraint import Problem
def solve(n=8):
problem = Problem()
cols = range(n)
rows = range(n)
problem.addVariables(cols, rows)
for col1 in cols:
for col2 in cols:
if col1 < col2:
problem.addConstraint(lambda row1, row2, col1=col1, col2=col2:
abs(row1 - row2) != abs(col1 - col2) and
row1 != row2, (col1, col2))
solutions = problem.getSolutions()
return solutions
在$n=8$的情况下，程序准确的返回了$92$个不同的结果。
3 总结
虽然Python是一种命令式的编程语言，但是我们利用python-constraint的扩展来体验了一下声明式编程的思想。一般来讲，声明式编程会缩短我们编程花费的时间，因为我们只需关注问题的定义而不需要考虑具体的解决算法。但是，声明式编程范式并不会让程序运行的速度变快，求解程序一般采用暴力搜索类的算法，反而往往会增加程序所需的运行时间。
本文为"三种编程范式解决八皇后问题"系列中的第3篇:
Comments