问题
《魔力 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: https://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 种解如下所示:
对于 n×n 的棋盘呢?
#include <iostream>
#include <string>
using namespace std;
//t表示被占领的行,s表示未测试过的行
int i=0;
void queen(const string t, const string s)
{ printf("t:%s s:%s\n",t.c_str(),s.c_str());
if (s=="") i++;
else
//第一个for循环测试当前测试列的每一行
for (int i=0; i<s.length(); i++) {
bool safe=true;
//第二个for循环测试当前点与之前点是否处于同一对角线上
//由于字符串的设计巧妙,使判断冲突情况(即皇后可以互相吃掉对方)限制在了对角线的情况上而已
for (int j=0;j<t.length();j++)
{
//列间隔等于行间隔,即为对角线关系
if (t.length()-j==abs(s[i]-t[j]))
{
safe=false;
break;
}
}
if (safe) //如果对角线没有冲突,探索下一列
queen(t+s[i], s.substr(0,i)+s.substr(i+1));
}
}
int main()
{
//string中的每一位代表一列,从左到右开始,而每一位中的数字代表了行号
//由于每个位的数字都是唯一的,因此可以保证已探索列和待探索列之间不会有
//行相同的情况.逻辑上也是一个二维矩阵
string s="01234";
queen("",s);
printf("%d",i);
exit(EXIT_SUCCESS);
return 0;
}
https://en.wikibooks.org/wiki/Algorithm_Implementation/Miscellaneous/N-Queens
https://www.jsomers.com/nqueen_demo/nqueens.html
local N=6
local solutions={}
function NQueen(q,r)
if r==N+1 then
-- debug
char=""
local qcopy = {}
for e=1,N do
char=char..q[e].." "
qcopy[e] = q[e]
end
print(char.."\n") -- THIS PRINT THE RIGHT ARRAYS
-- end debug
solutions[#solutions+1]=qcopy
else
for j=1,N do
valid=true
for i=1,(r-1) do
if ((q[i]==j or math.abs(q[i]-j)==math.abs(r-i)) and r>1) then
valid=false
end
end
if valid then
q[r]=j
NQueen(q,r+1)
end
end
end
end
Dq={}
for i=1,N do
Dq[i]=0
end
NQueen(Dq,1)
print(#solutions.." solutions found") -- RIGHT NUMBER OF SOLUTIONS
https://rosettacode.org/wiki/N-queens_problem
pandoc (豆瓣)
摘要 pandoc [options(选项)] [input-file(输入文件)]… 描述 Pandoc是一个用于从一种标记格式转换为另一种的Haskell库,还是一个使用该库的命令行工具。
t: s:01234
t:0 s:1234
t:02 s:134
t:024 s:13
t:0241 s:3
t:02413 s:
t:03 s:124
t:031 s:24
t:0314 s:2
t:03142 s: //找到一个解
t:04 s:123
t:041 s:23
t:1 s:0234
..
int main()
{
//string中的每一位代表一列,从左到右开始,而每一位中的数字代表了行号
//由于每个位的数字都是唯一的,因此可以保证已探索列和待探索列之间不会有
//行相同的情况.逻辑上也是一个二维矩阵
string s="abcdefghijkl";//"0123456789";
for(int n=1;n&lt;=12;n++)
{
i=0;
int t=clock();
queen("",s.substr(0,n));
printf("sum[%d]=%d\t%d\n",n,i,clock()-t);
}
exit(EXIT_SUCCESS);
return 0;
}
sum[1]=1 0
sum[2]=0 0
sum[3]=0 0
sum[4]=2 0
sum[5]=10 0
sum[6]=4 0
sum[7]=40 0
sum[8]=92 0
sum[9]=352 15
sum[10]=724 78
sum[11]=2680 312
sum[12]=14200 1716