Knight's tour: Difference between revisions

<lang Haskell>import Data.Char (ord, chr)

import Data.List (minimumBy, (\\), intercalate, sort)

board =

[ (x, y)

| x <- [1 .. 8]

, y <- [1 .. 8] ]

knightMoves (x, y) = filter (`elem` board) jumps

where

jumps =

[ (x + i, y + j)

| i <- jv

, j <- jv

, abs i /= abs j ]

jv = [1, -1, 2, -2]

| null candMoves = reverse moves

| otherwise = knightTour $ newSquare : moves

where

newSquare = minimumBy (comparing (length . findMoves)) candMoves

candMoves = findMoves $ head moves

findMoves = (\\ moves) . knightMoves

toSq :: String -> (Int, Int)

toSq [x, y] = (ord x - 96, ord y - 48)

toAlg :: (Int, Int) -> String

toAlg (x, y) = [chr (x + 96), chr (y + 48)]

-- TEST -----------------------------------------------------------------------

sq :: (Int, Int)

sq = toSq "e5" -- Input: starting position on the bord, e.g. (5, 5) as "e5"

main :: IO ()

main = printTour $ toAlg <$> knightTour [sq]

where

printTour [] = return ()

printTour tour = do

putStrLn $ intercalate " -> " $ take 8 tour

printTour $ drop 8 tour</lang>

{{Out}}

<pre>e5 -> f7 -> h8 -> g6 -> h4 -> g2 -> e1 -> f3

h6 -> g4 -> h2 -> f1 -> e3 -> f5 -> e7 -> d5</pre>