Arc Forumnew | comments | leaders | submitlogin
2 points by lojic 5789 days ago | link | parent

Here's a Haskell version from: http://www.haskell.org/haskellwiki/99_questions/90_to_94

It's longer than the 8 line naive Haskell version because it's optimized.

  import Data.List

  knightMoves :: Int -> (Int,Int) -> [(Int,Int)]
  knightMoves n (x, y) = filter (onBoard n)
          [(x+2, y+1), (x+2, y-1), (x+1, y+2), (x+1, y-2),
           (x-1, y+2), (x-1, y-2), (x-2, y+1), (x-2, y-1)]

  onBoard :: Int -> (Int,Int) -> Bool
  onBoard n (x, y) = 1 <= x && x <= n && 1 <= y && y <= n

  knightsTo :: Int -> (Int,Int) -> [[(Int,Int)]]
  knightsTo n finish = [pos:path | (pos, path) <- tour (n*n)]
    where tour 1 = [(finish, [])]
          tour k = [(pos', pos:path) |
                  (pos, path) <- tour (k-1),
                  pos' <- sortImage (entrances path)
                          (filter (`notElem` path) (knightMoves n pos))]
          entrances path pos =
                  length (filter (`notElem` path) (knightMoves n pos))

  sortImage :: Ord b => (a -> b) -> [a] -> [a]
  sortImage f xs = map snd (sortBy cmpFst [(f x, x) | x <- xs])
    where cmpFst x y = compare (fst x) (fst y)

  main = do
    print ((knightsTo 64 (1,1)) !! 0)


  $ ghc -O2 knights_tour.hs --make
  $ time ./knights_tour

  30x30 = 0.22 s
  64x64 = 4.17 s