Haskell: 八皇后问题的求解和效率优化
编程思路
n皇后问题，在前m步保留已经放了m个之后的所有可能情况。在第m+1步再试图放1个上去，保留所有不产生冲突的情况，也就是已经放了m+1个之后的所有可能情况。以此类推，放满n个皇后为止。
初步的实现和问题
queen :: Int -> Int -> [[Int]]
queen n 1 = [[i] | i <- [1..n]]
queen n num = [ls ++ [index] | index <- [1..n], ls <- queen n (num-1),
not (elem index ls)
&& not (elem (num - index - 1) [i - (ls !! i) | i <- [0..(num-2)]])
&& not (elem (num + index - 1) [i + (ls !! i) | i <- [0..(num-2)]])
但是很失败，执行
queen 8 8
的运行时间为一分钟以上。
之所以出现这种情况，原因是
queen n (num-1)
被计算了好多次。
细节原因待探寻，不过应该和dfs中的计算顺序有关。在
queen n num
里面，
queen n (num-1)
应该是被计算了
n
次。
标准实现
两个解决方法：
1.用
let
储存
queen n (num-1)
的结果，避免反复计算。
queen :: Int -> Int -> [[Int]]
queen n 1 = [[i] | i <- [1..n]]
queen n num = let ls_ls = queen n (num-1) in
[ls ++ [index] | index <- [1..n], ls <- ls_ls,
not (elem index ls)
&& not (elem (num - index - 1) [i - (ls !! i) | i <- [0..(num-2)]])
&& not (elem (num + index - 1) [i + (ls !! i) | i <- [0..(num-2)]])
]
2.换一下循环内主次变量的顺序，让求解难度较大，取值较多的做遍历的主变量（放在前面）
queen :: Int -> Int -> [[Int]]
queen n 1 = [[i] | i <- [1..n]]
queen n num = [ls ++ [index] | ls <- queen n (num-1), index <- [1..n],
not (elem index ls)
&& not (elem (num - index - 1) [i - (ls !! i) | i <- [0..(num-2)]])
&& not (elem (num + index - 1) [i + (ls !! i) | i <- [0..(num-2)]])
]
除此之外，发现，终止条件其实可以写得更简洁一些。
queen n 0 = [[]]
运行结果：
*Main> :l eight-queen.hs
[1 of 1] Compiling Main ( eight-queen.hs, interpreted )
Ok, modules loaded: Main.
(0.02 secs,)
*Main> length $ queen 8 8
92
(0.05 secs, 20,472,904 bytes)
如果直接执行
queen 8 8
，可以输出符合八皇后问题要求的所有排列情况。
附赠一个Python版本对照参考，基本就是照着上面Haskell代码翻译的：
def queen(n, num):
pos_lst = list(range(1, n+1))
if num == 0: return [[]]
# if num == 1:
# return [[i] for i in range(1, n+1)]
else:
ls_lst = queen(n, num-1)
result = [(ls, pos) for ls in ls_lst for pos in pos_lst]
return [ls+[pos] for (ls, pos) in result \
if not (pos in ls) \
and not ((num - pos - 1) in [(i - ls[i]) for i in range(num-1)]) \
and not ((num + pos - 1) in [(i + ls[i]) for i in range(num-1)]) \
]
print(len(queen(8,8))) # 92
改善效率
把判定条件提炼出来，为
safe
函数，另外：
1.考虑到ls的长度就是num-1，所以优化掉之前显式出现的num-2，num-1.
2.对之前的
ls ++ [index]
改为
index:ls
，通过使用默认构造器改善效率。同时，因为这种情况导致列表里面的元素（对应已放置皇后的位置）为反序，需要对条件进行一些恒等变换：
safe :: [Int] -> Int -> Bool
safe ls index = notElem index ls
&& notElem (index + 1) [ls !! i - i | i <- take (length ls) [0..]]
&& notElem (index - 1) [ls !! i + i | i <- take (length ls) [0..]]
queen :: Int -> Int -> [[Int]]
queen n 0 = [[]]
queen n num = [index:ls | ls <- queen n (num-1), index <- [1..n], safe ls index]
再用
zipWith
改善列表推导式，优化掉take。
safe :: [Int] -> Int -> Bool
safe ls index = notElem index ls
&& notElem (index + 1) (zipWith (-) ls [0..])
&& notElem (index - 1) (zipWith (+) ls [0..])
queen :: Int -> Int -> [[Int]]
queen n 0 = [[]]
queen n num = [index:ls | ls <- queen n (num-1), index <- [1..n], safe ls index]
优化掉列表解析式中的
ls <- queen n (num-1)
，显式地保证
queen n (num-1)
在求
queen n num
的时候只运行一次：
safe :: [Int] -> Int -> Bool
safe ls index = notElem index ls
&& notElem (index + 1) (zipWith (-) ls [0..])
&& notElem (index - 1) (zipWith (+) ls [0..])
oneMoreQueen :: Int -> [[Int]] -> [[Int]]
oneMoreQueen n lss = [index:ls | ls <- lss, index <- [1..n], safe ls index]
queen :: Int -> Int -> [[Int]]
queen n 0 = [[]]
queen n num = oneMoreQueen n (queen n $ num-1)
程序在这样的优化下基本达到了最优执行效率：从最初的26秒优化到10秒。
q :: Int -> [[Int]]
q n = iterate (. (oneMoreQueen n)) id !! n $ [[]]
以上的代码代替
queen
，把递归显式化，但是并没有改善执行效率。
main :: IO ()
main = putStrLn $ show $ length $ queen 12 12 -- for test
-- main = putStrLn $ show $ length $ q 12
在以上的时间测试中，我们执行main获得12皇后的结果，作为此程序的基准测试。
最终代码
safe :: [Int] -> Int -> Bool
safe ls index = notElem index ls
&& notElem (index + 1) (zipWith (-) ls [0..])
&& notElem (index - 1) (zipWith (+) ls [0..])
oneMoreQueen :: Int -> [[Int]] -> [[Int]]
oneMoreQueen n lss = [index:ls | ls <- lss, index <- [1..n], safe ls index]
-- q :: Int -> [[Int]]
-- q n = iterate (. (oneMoreQueen n)) id !! n $ [[]]
queen :: Int -> Int -> [[Int]]
queen n 0 = [[]]
queen n num = oneMoreQueen n (queen n $ num-1)
q :: Int -> [[Int]]
q n = queen n n
main = putStrLn $ show $ length $ q 10 -- for test