问题

《魔力 Haskell》第 17.2 节提到:

八皇后问题最早由棋手马克斯·贝瑟尔于 1848 年提出。之后,陆续有数学家对其进行研究,其中包括高斯和康托,并将其推广为更一般的 n 皇后摆放问题。

八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任何两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的 n 皇后摆放问题:这时棋盘的大小变为 n×n,而皇后个数也变成 n。当且仅当 n = 1 或 n ≥ 4 时问题有解。

分析

我们使用一个长度等于 8 的列表来表示国际象棋的棋盘,左上角定义为坐标的原点,列表中第 i 个元素表示第 i 行的棋子所在的横坐标。注意,这里 i 和横坐标都是从 1 开始计算的。

根据摆放皇后的规则,即同一条横行、纵行或斜线上不能出现两个皇后,您可能想写一个函数来判断坐标列表对应的情况晃是符合摆放规则。但仔细思考一下,是否冲突的这个事情只能每两个皇后作一次判断。要判断列表中任意两个皇后不冲突,需要计算很多对皇后组合的情况。

所以我们换一种思考方式,考虑逐步构造符合要求的列表:每一步在新的一行添加一个皇后。在和之前的摆放不冲突的情况下,可能会产生若干种方案,然后把所有可能的方案分别继续添加下去,直到摆满棋盘,最后所有的方案就不难得出了,这实际上正是动态规划的一种。

解答

根据以上分析,我们有以下 Haskell 程序 queens.hs:

safe _ [] _ = True
safe x (x1:xs) n = x /= x1 && x /= x1+n && x /= x1-n && safe x xs (n+1)
queensN n = queens n where
  queens 0 = [[]]
  queens m = [x:xs | xs <- queens (m-1), x <- [1..n], safe x xs 1]

上述程序中:

  • safe 函数可以判断新的坐标加到列表的最前面之后,和后面每一行的棋子是否冲突,n 的初始值是 1。每次递归时,n 加 1 表示要判断的行数向下移动了 1 行,直到把之前的方案都判断完毕,任意一步不成功,都会返回 False,代表新的坐标 x 和之前的摆放方案冲突。

  • queens 函数计算第 m 步所有可能的摆放列表,所以返回值是列表的列表 [[Int]]。第 m 步所有的摆放方案,等同于向第 m-1 步的所有可能性中添加全部可能的横坐标 x。所以,这里使用列表归纳语法,取出之前所有的摆放方案 xs,从 1 到 n 任取一个值作为新坐标 x,经过 safe 函数过滤出不冲突的摆放。

  • queensN 函数调用 queens n,递归计算出 n×n 棋盘上全部的可能摆放。

使用 foldM

Haskell 有一个把列表的折叠操作推广到单子运算后得到的函数 foldM,可以解决很多递归问题:

foldM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b
foldM _ acc [] = return acc
foldM f acc (x:xs) = do
  acc' <- f acc x
  foldM f acc' xs

foldM 依次把 [a] 中的值和累积值 acc 交给 f,然后通过 >>= 获得新的累积值,直到最后把累积值 return 出来。foldM 函数可以结合列表单子来解决动态规划问题。queens.hs 程序中最后 3 行的 queensN 函数可以使用 foldM 函数实现,如下所示:

queensN n = foldM (\xs _ -> [x:xs | x <- [1..n], safe x xs 1]) [] [1..n]

注意,foldM 是在 Control.Monad 模块中定义的,所以需要在程序的开头添加一句:

import Control.Monad ( foldM )

运行

我们使用 GHCi 来解释执行 queens.hs:

$ ghci
GHCi, version 8.0.1: http://www.haskell.org/ghc/  :? for help
Prelude> :load queens.hs
[1 of 1] Compiling Main             ( queens.hs, interpreted )
Ok, modules loaded: Main.
*Main> mapM_ print $ queensN 6
[5,3,1,6,4,2]
[4,1,5,2,6,3]
[3,6,2,5,1,4]
[2,4,6,1,3,5]
*Main> mapM_ print $ queensN 8
[4,2,7,3,6,8,5,1]
[5,2,4,7,3,8,6,1]
[3,5,2,8,6,4,7,1]
...
[1,7,4,6,8,2,5,3]
...
[5,7,2,6,3,1,4,8]
*Main> length $ queensN 8
92

从上述运行结果可以看出,六皇后问题总共有 4 种不同的解,而八皇后问题总共有 92 种不同的解,其中第 15 种解如下所示:

参考资料

  1. Wikipedia: Eight queens puzzle
  2. 魔力 Haskell

magic-haskell