P91 - 骑士巡游
Knight’s tour
官方模块：
Problems.P91核心函数：knightsTour、closedKnightsTour
Warnsdorff 规则
回溯时优先尝试“下一步可走位置最少”的格子，让最受约束的位置尽早决定，显著减少死路搜索。
实现
方法一：Warnsdorff 排序回溯
1import Data.List (sort, sortOn)
2import qualified Data.Set as Set
3
4type Position = (Int, Int)
5
6knightsTour :: Int -> Position -> Maybe [Position]
7knightsTour n end
8 | not (inside n end) = Nothing
9 | otherwise = search n [end] (Set.delete end board)
10 where board = Set.fromList [(x,y) | x <- [1..n], y <- [1..n]]
11
12search n path@(current:_) remaining
13 | Set.null remaining = Just path
14 | otherwise = firstJust
15 [search n (next:path) (Set.delete next remaining)
16 | next <- ranked]
17 where
18 ranked = sortOn (length . moves remaining) (moves remaining current)
19search _ [] _ = Nothing
20
21moves remaining (x,y) =
22 filter (`Set.member` remaining)
23 [(x+dx,y+dy) | (dx,dy) <- jumps]
24 where jumps = [(1,2),(1,-2),(-1,2),(-1,-2),
25 (2,1),(2,-1),(-2,1),(-2,-1)]
26
27firstJust [] = Nothing
28firstJust (Just x:_) = Just x
29firstJust (Nothing:xs) = firstJust xs
30
31inside n (x,y) = 1 <= x && x <= n && 1 <= y && y <= n
从终点反向搜索，最终得到的列表自然以指定位置结尾。
闭合巡游
1closedKnightsTour :: Int -> Maybe [Position]
2closedKnightsTour n
3 | n < 1 = Nothing
4 | otherwise = firstJust
5 [pathTo end [(1,1)] (Set.delete end withoutStart)
6 | end <- moves withoutStart (1,1)]
7 where
8 board = Set.fromList [(x,y) | x <- [1..n], y <- [1..n]]
9 withoutStart = Set.delete (1,1) board
10
11 pathTo end path@(current:_) remaining
12 | Set.null remaining =
13 if knightMove current end
14 then Just (reverse path ++ [end])
15 else Nothing
16 | otherwise = firstJust
17 [pathTo end (next:path) (Set.delete next remaining)
18 | next <- sortOn (length . moves remaining)
19 (moves remaining current)]
20 pathTo _ [] _ = Nothing
21
22 knightMove (x,y) (x',y') =
23 sort [abs (x-x'), abs (y-y')] == [1,2]
方法二：朴素回溯
1knightsTourPlain :: Int -> Position -> Maybe [Position]
2knightsTourPlain n end
3 | not (inside n end) = Nothing
4 | otherwise = searchPlain [end] (Set.delete end board)
5 where
6 board = Set.fromList [(x, y) | x <- [1..n], y <- [1..n]]
7
8 searchPlain path@(current:_) remaining
9 | Set.null remaining = Just path
10 | otherwise = firstJust
11 [searchPlain (next : path) (Set.delete next remaining)
12 | next <- moves remaining current]
13 searchPlain [] _ = Nothing
朴素版本保持相同的回溯状态，却完全按照坐标顺序尝试下一步。它适合说明 Warnsdorff 排序没有改变解集合，只是把最可能形成死路的选择提前。
方法对比
| 方法 | 候选顺序 | 实际表现 |
|---|---|---|
| Warnsdorff | 后续出口少的格子优先 | 大棋盘通常很快 |
| 朴素回溯 | 坐标顺序 | 搜索树巨大，只适合小棋盘对照 |
测试
1>>> fmap length (knightsTour 6 (3,5))
2Just 36
3>>> fmap length (closedKnightsTour 6)
4Just 36
5>>> knightsTour 3 (1,1)
6Nothing
7>>> knightsTourPlain 1 (1,1)
8Just [(1,1)]