So tonight I was helping a friend with a CS 134 assignment that involved a recursive solution to the Knight’s Tour problem. The assignment included a rather ugly solution in Java and I wondered what a comparable solution in Haskell might look like. I spent the past few minutes hacking together such a function.

    tourTo :: Int -> (Int,Int) -> [[(Int,Int)]]
    tourTo n finish = [pos:path | (pos,path) <- tour (n*n)]
        where tour 1 = [(finish, [])]
              tour k = [(pos', pos:path) |
                           (pos, path) <- tour (k-1),
                           pos' <- (filter (`notElem` path) (jumps n pos))]
              jumps n (r, c) = filter onBoard
                  [(r+2, c+1), (r+1, c+2), (r-2, c+1), (r+1, c-2),
                   (r+2, c-1), (r-1, c+2), (r-2, c-1), (r-1, c-2)]
                  where onBoard (r, c) = r >= 1 && c >= 1 && r <= n && c <= n
    

It works (as far as I can tell) but it’s unbearably slow. Two optimizations come to mind: using a map rather than a list to store the visited squares and using a heuristic to select the next move location. The latter is implemented in the Java version; if motivation strikes I’ll post a better/faster(/harder/stronger) version.