P90 - N 皇后问题

Find all solutions to the n queens problem
官方模块：Problems.P90　核心函数：queens

表示与剪枝

结果列表第 $c$ 个数表示第 $c$ 列皇后的行号。逐列放置时，候选行不能重复，并且与之前任一皇后不能满足 $|c-c'|=|r-r'|$ 。

实现

方法一：list monad 回溯

 1queens :: Int -> [[Int]]
 2queens n
 3  | n < 0     = []
 4  | otherwise = place 1 [] [1..n]
 5  where
 6    place _ reversedRows [] = [reverse reversedRows]
 7    place column reversedRows availableRows = do
 8      row <- availableRows
 9      guard (safe column row reversedRows)
10      place (column + 1) (row : reversedRows)
11        (filter (/= row) availableRows)
12
13    safe column row reversedRows = and
14      [abs (column - previousColumn) /= abs (row - previousRow)
15      | (previousColumn, previousRow) <- zip [column-1,column-2..1] reversedRows]

需要 Control.Monad (guard)。列表 Monad 自动收集每个合法分支的结果。

方法二：位掩码搜索

 1import Data.Bits ((.&.), (.|.), bit, complement, shiftL, shiftR)
 2
 3queens :: Int -> [[Int]]
 4queens n
 5  | n < 0     = []
 6  | otherwise = map columnsToRows (search 0 0 0 0 [])
 7  where
 8    full :: Integer
 9    full = bit n - 1
10
11    search row columns diagonalLeft diagonalRight reversedColumns
12      | row == n = [reverse reversedColumns]
13      | otherwise = concat
14          [ search (row + 1)
15              (columns .|. columnBit)
16              (((diagonalLeft .|. columnBit) `shiftL` 1) .&. full)
17              ((diagonalRight .|. columnBit) `shiftR` 1)
18              (column : reversedColumns)
19          | column <- [0..n-1]
20          , let columnBit = bit column
21          , available .&. columnBit /= 0
22          ]
23      where
24        available = full .&. complement
25          (columns .|. diagonalLeft .|. diagonalRight)
26
27    columnsToRows columnsByRow =
28      [row + 1
29      | column <- [0..n-1]
30      , (row, placedColumn) <- zip [0..] columnsByRow
31      , placedColumn == column]

这个版本逐行放置皇后，用整数的二进制位同时记录已占用的列和两组对角线。一个按位与即可得到整行候选位置，避免逐个比较此前皇后。最后把“每行所在列”转换回题目要求的“每列所在行”。

方法对比

方法	冲突状态	特点
list monad	皇后行号列表	教学直观，适用于任意棋盘表示
位掩码	三个整数	常数更小，适合较大的 n

测试

1>>> length (queens 8)
292
3>>> minimum (queens 8)
4[1,5,8,6,3,7,2,4]
5>>> queens 1
6[[1]]

最坏搜索仍是指数级，但行占用和对角线剪枝会在很浅的位置排除冲突。

参考

← P89 二分图判定 | P91 骑士巡游 →