Shortest Knight Moves From a to B in Haskell
I’ve got back onto the excellent ’Learn you a Haskell for Great Good’ recently, which I would highly recommend.
Near the end of chapter 12 (about Monads), there is a section on the list monad, which has an example ‘a knight’s quest’ at the end. Modification of the example code to print out possible routes from one position to another is left as an exercise to the reader. I decided to give it a go in attempt to solidify my knowledge about monads a bit, and below is the result.
I’m sure there are far more efficient ways of doing this, and potentially more monad-y ways of implementing shortestMovesFor, so if any other beginners come across this, I’d be interested to see what you came up with!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
And here’s some example output:
As you can see it returns a list of the shortest chains of moves from the start square to the target square.
Changes I made to the code from the book:
moveNWithHistory is a new function to apply moveKnight n times. It also generates a list of chains of moves for a given n, rather than just the final positions (by passing
nextMove : current : historyto the next iteration, rather than just the next move).
shortestMovesFor is not monadic, and returns the final list of moves. We first generate all move chains from our starting position for increasing n, until we find the smallest n which creates a set of chains that contains a chain ending on the target square. We then filter down the set we found to return only chains that do end on the target square. Finally we map reverse over the chains to make them more readable.