1

我使用 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
4

1 回答 1

1

Community-wiki 以最终近似的解决方案回答：

“恐怕如果你想要所有的旅行，无论如何你都会有一个缓慢的算法，从一个起点开始的开放旅行的数量对于不太小的板来说是巨大的”

于 2016-03-19T07:12:55.957 回答