我使用 Haskell 为 Knight's tour 实现了一个递归解决方案。我的算法基本上是基于 Warnsdorff 的规则。
例子:
- 棋盘尺寸:5x5
- 起始位置:(3,3)
基于这个例子的基本思想:
(1) 计算从当前点 (3,3)
=> (1,2),(1,4),(2,1),(2,5),(4,1),(4,5)允许的移动),(5,2),(5,4)
(2) 对于这些点中的每一个,计算到达该点可以执行的移动次数(“入口”数)
=> ((1,2),2),((1,4),2) ,((2,1),2),((2,5),2),((4,1),2),((4,5),2),((5,2),2) ,((5,4),2)
(3) 如果所有点的入口数量相同,则找到入口最少的点或第一个点
=> (1,2)
(4) 调用与确定点相同的函数(开始递归)
这样我就可以确定解决问题的方法。但现在我需要确定起始位置的所有其他可能解决方案(在示例 (3,3) 中)。不幸的是,我真的不知道如何实现这一目标。
想法非常感谢。
这是我当前的 Haskell 代码(为指定的起始位置提供一种解决方案):
> kt :: Int -> (Int,Int) -> [(Int,Int)]
> kt dimension startPos = kt' (delete startPos allFields) [startPos] startPos
> where allFields = [(h,v) | h <- [1..dimension], v <- [1..dimension]]
> kt' :: [(Int,Int)] -> [(Int,Int)] -> (Int,Int) -> [(Int,Int)]
> kt' [] moves _ = moves
> kt' freeFields moves currentPos
> | nextField /= (0,0) = kt' (delete nextField freeFields) (moves ++ [nextField]) nextField
> | otherwise = error "Oops ... dead end!"
> where h = fst currentPos
> v = snd currentPos
> nextField = if nextFieldEnv /= [] then fst (head (sortBy sortGT nextFieldEnv)) else (0,0)
> nextFieldEnv = fieldEnv' currentPos freeFields
> sortGT ((a1,a2),a3) ((b1,b2),b3)
> | a3 > b3 = GT
> | a3 < b3 = LT
> | a3 == b3 = EQ
> fieldEnv :: (Int,Int) -> [(Int,Int)] -> [(Int,Int)]
> fieldEnv field freeFields = [nField | nField <- [(hor-2,ver-1),(hor-2,ver+1),(hor-1,ver-2),(hor-1,ver+2),(hor+1,ver-2),(hor+1,ver+2),(hor+2,ver-1),(hor+2,ver+1)], nField `elem` freeFields]
> where hor = fst field
> ver = snd field
> fieldEnv' :: (Int,Int) -> [(Int,Int)] -> [((Int,Int),Int)]
> fieldEnv' field freeFields = [(nField,length (fieldEnv nField freeFields)) | nField <- (fieldEnv field freeFields)]
> where hor = fst field
> ver = snd field