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コードです（指定された開始位置に対して1つのソリューションを提供します）：
> 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