三种编程范式解决八皇后问题(2)

在该系列上一篇中，我们以Python为例介绍了如何用命令式编程解决八皇后问题。今天，我们来说说函数式编程。函数式编程虽然已经有了几十年的历史，但依旧不是今日的主流编程风格。不过随着Scala等语言的出现和广泛应用，相信函数式编程会受到越来越多人多关注。函数式编程的理论基础为λ演算，和命令式编程中我们给予计算机编写指令不同，函数式编程将计算机的运算抽象为函数的计算，并且没有状态的转变（例如给变量赋值）。两者从思路上最大的区别是命令式编程关心解决问题的步骤，而函数式编程关心数据的映射。此文中我们以纯函数语言Haskell为例。作为纯函数式编程语言中最流行的语言之一，Haskell采用惰性求值（Lazy Evaluation）。Haskell中没有变量的赋值，没有循环（用递归代替），对于大部分没有接触过函数式编程的初学者，往往在刚开始学习时摸不着头脑。在这里强烈推荐使用Learn You a Haskell for Great Good!这本书进行学习。该书中文名为《Haskell趣学指南》，可以在网上免费查阅，也是Haskell官方推荐的教材。不想直接学习纯函数式语言的学习者也可以学习如何在一些支持函数特性的编程语言中进行函数式编程，以Python为例，推荐阅读Functional Programming in Python。

接下来进入正文，首先和在Python中的解决方法一样，我们用一个一维列表表示棋盘，[4,7,3,8,2,5,1,6]便是八皇后问题的一个解。我们枚举随意可能的排列并且检验它们是否满足条件，得到以下解决方法：

queens :: Int -> [[Int]]
queens n = filter test (generate n)
    where generate 0      = [[]]
          generate k      = [q : qs | q <- [1..n], qs <- generate (k-1)]
          test []         = True
          test (q:qs)     = isSafe q qs && test qs
          isSafe   try qs = not (try `elem` qs || sameDiag try qs)
          sameDiag try qs = any (\(colDist,q) -> abs (try - q) == colDist) $ zip [1..] qs

第一行定义了函数的输入和输出的数据类型，对于我们这个名为queens的函数，接受一个整数作为输入参数，返回一个整数二维数组。如果不定义输入输出的数据类型，Haskell会尝试自动推演出数据类型，这样较容易发生错误，所以建议不能省略这个步骤。接下来，generate这个函数会生成所有的Permutation，test函数用来检测特定的排列是否满足皇后问题的要求，并且用filter函数过滤得到所有满足要求的组合。我们可以发现，Haskell中大量使用递归，高阶函数（如filter,zip等），模式匹配（如q : qs的表示方法），λ函数（如sameDiag中的语句）等等。不得不说，Haskell的学习门槛的确远高于一般的编程语言，再次无法对这些细节一一详解。但是函数式语言为我们带来了解决问题的不同思路，在实际运用中，尤其是大数据处理，程序验证，快速软件开发等等方面都有着很重要的地位。希望可以通过八皇后问题这个小例子展示一下它的魅力。

要运行以上程序，你需要首先安装ghci解释器，然后将以上代码保存并命名为n_queens.hs。然后在同样的目录下的终端中输入ghci命令打开Haskell解释器，然后用:l n_queens加载文件。最后，输入queens 8求解八皇后问题。

运行完可以发现，该解决方法运行速度较慢，和在Python中的解决方法一样，我们动态的添加皇后，可以大幅提高运行速度。代码如下：

queens :: Int -> [[Int]]
queens n = map reverse $ queens' n
    where queens' 0       = [[]]
          queens' k       = [q:qs | qs <- queens' (k-1), q <- [1..n], isSafe q qs]
          isSafe   try qs = not (try `elem` qs || sameDiag try qs)
          sameDiag try qs = any (\(colDist,q) -> abs (try - q) == colDist) $ zip [1..] qs