用 Haskell 实现的8皇后问题

    这两天在学习 Haskell，倒不是为了多会一门编程语言，主要是想学习函数式编程的思维方式。进展不快，需要一些练习。于是想起了多年以前的8皇后问题。问题的描述可以参见 wikipedia:

网上找到一篇文章有各种语言的解法，牛！

参看 Haskell 的部分，有三种方法，极其简洁明了（Perl版的也很简洁，可是好像很难懂，象是使用字符串处理的方式建模解决数学问题，对Perl的大侠有时真是不得不佩服）。个人喜欢第一个：

    queens 0 = [[]]
    queens (n+1) = [ q:b | b <- queens n; q <- [0..7]; safe q b ]
    safe q b = and [ not checks q b i | i <- [0..(b-1)] ]
    checks q b i = q=b!!i || abs(q - b!!i)=i+1

因为这个解法没有使用任何预定义的库函数（Haskell的库函数很强大，有时候就像魔术师手中的魔杖，神奇，但让新人摸不着头脑）。不过这个解法有不少的毛病：

1. 不少的语法错，连作者都说通不过编译
2. 没有主函数，只能在交互式环境中运行
3. 直接打印的话显得输出太过粗糙，连一共有几组解都要自己去数吗？

        [[4,2,7,3,6,8,5,1],[5,2,4,7,3,8,6,1],……]

还是自己改吧，就当作习题了。

1. 下载安装了 Haskell Platform，作为编译运行环境
2. 在Eclipse上按装了 EclipseFP 插件，于是有了全功能的Haskell的IDE

改订的版本如下：

main = do
    putStrLn $ "There are " ++ show(length result) ++ " solutions in total"
    mapM_ (print.zipWith (\x y -> x:show y) ['A'..'H']) result
    where
        result = queens 8

queens 0 = [[]]
queens n = [ q:b | b <- queens (n-1), q <- [1..8], safe q b ]
safe q b = and [ not (checks q b i) | i <- [0..(length b-1)] ]
checks q b i = q==b!!i || abs(q - b!!i)==i+1

这段代码可以用GHC编译运行，让我们来分析解释一下，幸好代码不长

1. queens n 的结果是一个列表的列表，你可以看作是在棋盘左边n列上已经放置了n个皇后的所有可能解法。列表的每个元素就是一个解，每个解依次标明n个皇后在各自的列上放置的行号。当然任何两个皇后间不能互相攻击。例如[1,3,5]就是 queens 3 的一个解，标明3个皇后的位置分别是：第0列第1行、第1列第3行 和 第2列第5行
2. queens 0 当然只有一个解，那就是空 [[]]，没有皇后，哪有位置
3. queens n 那句的意思是，如果放置了n-1个皇后，那么再放一个在第n列的解法集合是：对于 queen (n-1) 中的每个解，试着把第n个皇后放到1～8的各行上（列是固定的，不是吗？）就得到了所有的候选解法，但是必须满足条件，那就是新放置皇后的位置针对原有的n-1个皇后的位置必须是安全的。这个安全性由函数safe来判断并在列表解析中过滤出满足条件的解法。注意到b是一个列表，标识n-1个皇后的位置，q是新放置皇后的位置。q：b就是有n个元素的列表，标识了n个皇后的位置
4. safe q b 的那一句是说：针对已放置的n-1个皇后（b中的一个解），新放置的皇后（位置由q标示）都（and）不（not）与之冲突，那新放置的皇后就是安全的（safe 返回 True），反之则不安全。i只是一个索引，可以看作是列表b的下标，也就是已放置皇后的列位置
5. checks q b i 检查新放置的皇后（位置q）是否与第i列的皇后位置（位置第i列，b!!i行）冲突。注意b!!i的意思是列表b中的第i个元素，象C/C++中的数组元素b[i]。checks是国际象棋中 将军（就是你下一步打算吃掉对方的老头） 的意思，不是检查。那么两个皇后怎么算冲突呢？很简单，在同一行上，或是在同一斜线上（就是行位置差值和列位置差值的绝对值相等）。另外，我们放置的两个皇后本来就在不同的列上，不是吗？
6. 好了，现在我们应该得到了所有的解，每个解包含8个皇后的行位置，例如[4,2,7,3,6,8,5,1]。我们知道国际象棋棋盘是8x8的，列标识为A到H，行标识为1到8，每个格子由列号加行号标识，例如A2，G5等。也就是说对于每个解，应该用列号['A','B','C','D','E','F','G','H']分别对应上行号。(\x y->x:showy)是个lambda函数，就是匿名函数，它接受两个参数（x='A', y=3)，把它们连成字符串（"A3"）。zipWith接受两个列表，将相应位置的元素取出并传递给指定的函数处理（在这里就是上面的lambda函数）。mapM_针对列表中的每个元素（每个解）做相同的处理（转换并打印）

得，最后的结果如下：

There are 92 solutions in total

["A4","B2","C7","D3","E6","F8","G5","H1"]

["A5","B2","C4","D7","E3","F8","G6","H1"]

["A3","B5","C2","D8","E6","F4","G7","H1"]

["A3","B6","C4","D2","E8","F5","G7","H1"]

["A5","B7","C1","D3","E8","F6","G4","H2"]

["A4","B6","C8","D3","E1","F7","G5","H2"]

["A3","B6","C8","D1","E4","F7","G5","H2"]

["A5","B3","C8","D4","E7","F1","G6","H2"]

["A5","B7","C4","D1","E3","F8","G6","H2"]

["A4","B1","C5","D8","E6","F3","G7","H2"]

["A3","B6","C4","D1","E8","F5","G7","H2"]

["A4","B7","C5","D3","E1","F6","G8","H2"]

["A6","B4","C2","D8","E5","F7","G1","H3"]

["A6","B4","C7","D1","E8","F2","G5","H3"]

……