Arc Forumnew | comments | leaders | submitlogin
Solving the Knight's Tour Puzzle In 60 Lines of ... (slashdot.org)
4 points by babo 5869 days ago | 5 comments


4 points by rntz 5869 days ago | link

    (set board-size 8)

    (set moves
      '((-2 . -1) (-2 . 1)
        (-1 . -2) (-1 . 2)
        ( 1 . -2) ( 1 . 2)
        ( 2 . -1) ( 2 . 1)))

    (def move (pos diff)
      (cons (+ car.pos car.diff) (+ cdr.pos cdr.diff)))

    (def valid (pos visited)
      (and
        (< -1 car.pos board-size)
        (< -1 cdr.pos board-size)
        (~mem pos visited)))

    (def moves-from (pos) (map [move pos _] moves))

    (def succs (pos visited)
      (let valid [valid _ visited]
        (sort (compare < [count valid moves-from._])
          (keep valid moves-from.pos))))

    (def knights-tour (start (o visited))
      (let visited (cons start visited)
        (if (is len.visited (* board-size board-size)) rev.visited
          (ormap [knights-tour _ visited] (succs start visited)))))
Although I aimed for clarity and modularity when writing the above, rather than lines of code or speed, it actually does quite well in both departments. It takes about three seconds on a 20x20 board, and about ten for a 30x30. I suspect that using a hashtable to keep track of visited squares rather than a simple list would speed it up on higher board sizes.

-----

5 points by rntz 5867 days ago | link

Actually, the above code contains an error:

    (~mem pos visited)
should be:

    (~mem [iso _ pos] visited)
Otherwise, the code will generate incorrect tours. This increases runtime. However, I've also tested a version which uses hashtables, and as I suspected, this significantly decreases runtime. To use hashtables, replace 'valid and 'knights-tour in the original with the following:

    (def valid (pos visited)
      (and
        (< -1 car.pos board-size)
        (< -1 cdr.pos board-size)
        (no visited.pos)))
    
    (def trace (k e)
      (cons k (let v e.k (if (isnt t v) (trace v e)))))

    (def knights-tour (start (o prev t) (o visited (table)))
      (= visited.start prev)
      (do1 (if (is len.visited (* board-size board-size)) (rev:trace start visited)
             (ormap [knights-tour _ start visited] (succs start visited)))
        (= visited.start nil)))

-----

1 point by babo 5868 days ago | link

Elegant solution, hats off!

-----

2 points by lojic 5868 days ago | link

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

-----

1 point by babo 5869 days ago | link

Forget speed for a while but how is a solution for this challenge in arc?

-----