P98 - 数织游戏（Nonogram）
Nonograms
官方模块：
Problems.P98核心函数：nonogram
题目描述
每行、每列给出连续实心块的长度。相邻块之间至少有一个空格；求满足全部行列线索的布尔矩阵。
生成单行候选
1import Data.List (isPrefixOf, transpose)
2
3linePatterns :: Int -> [Int] -> [[Bool]]
4linePatterns width [] = [replicate width False]
5linePatterns width (block:rest)
6 | block <= 0 = []
7 | otherwise =
8 [ replicate start False ++ replicate block True ++ separator ++ suffix
9 | start <- [0..width - block - minimumTail]
10 , let separator = if null rest then [] else [False]
11 , suffix <- linePatterns (width - start - block - length separator) rest]
12 where
13 minimumTail = sum rest + length rest
minimumTail 是剩余块及它们所需分隔空格的最小长度，因此起点枚举不会产生越界布局。
求解
方法一：按行回溯并检查列前缀
1nonogram :: [[Int]] -> [[Int]] -> Maybe [[Bool]]
2nonogram rowClues columnClues = build [] rowOptions
3 where
4 height = length rowClues
5 width = length columnClues
6 rowOptions = map (linePatterns width) rowClues
7 columnOptions = map (linePatterns height) columnClues
8
9 build rows []
10 | transpose rows `matches` columnOptions = Just rows
11 | otherwise = Nothing
12 build rows (options:remaining) = firstJust
13 [build rows' remaining | row <- options
14 , let rows' = rows ++ [row]
15 , compatible rows']
16
17 compatible rows = and
18 [any (column `isPrefixOf`) options
19 | (column, options) <- zip (transpose rows) columnOptions]
20
21 actual `matches` options = and (zipWith elem actual options)
22
23firstJust [] = Nothing
24firstJust (Just value:_) = Just value
25firstJust (Nothing:rest) = firstJust rest
方法二：从候选较少的方向搜索
1nonogramAdaptive :: [[Int]] -> [[Int]] -> Maybe [[Bool]]
2nonogramAdaptive rowClues columnClues
3 | rowCost <= columnCost = nonogram rowClues columnClues
4 | otherwise = transpose <$> nonogram columnClues rowClues
5 where
6 height = length rowClues
7 width = length columnClues
8 rowCost = product
9 [toInteger (length (linePatterns width clue)) | clue <- rowClues]
10 columnCost = product
11 [toInteger (length (linePatterns height clue)) | clue <- columnClues]
横纵转置后仍是同一个 Nonogram。先估算逐行和逐列候选组合数，从更小的一侧调用基准求解器；按列求解得到的棋盘最后再转置回来。线索不对称时，这个选择可以显著减少搜索分支。
方法对比
| 方法 | 搜索方向 |
|---|---|
| 固定按行 | 实现直接，表现取决于行线索强弱 |
| 自适应 | 比较候选组合数后选择行或列 |
测试
1>>> fmap (map (map (\b -> if b then '#' else '.')))
2... (nonogram [[1],[3],[1]] [[1],[3],[1]])
3Just [".#.","###",".#."]
4>>> nonogram [[3]] [[1],[1]]
5Nothing
6>>> nonogramAdaptive [[1],[3],[1]] [[1],[3],[1]] ==
7... nonogram [[1],[3],[1]] [[1],[3],[1]]
8True
逐行加入后立即检查所有列前缀，可以在错误行布局出现时马上回溯。