三种编程范式解决八皇后问题(3) - 声明式编程

在该系列上一篇中,我们展示了如何使用纯函数语言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篇:

  1. 三种编程范式解决八皇后问题(1) - 命令式编程
  2. 三种编程范式解决八皇后问题(2) - 函数式编程
  3. 三种编程范式解决八皇后问题(3) - 声明式编程

在手机上阅读或分享本文请扫描以下二维码:
By @Zhengyi Yang in
Tags : #eight queens, #declarative programming, #python,

Comments

评论功能已关闭。