In today’s Programming Praxis exercise, our goal is to list all the potential ways a knight on a chess board can get from one position to another. Let’s get started, shall we?

import Data.Ix

A knight can move to 8 positions, assuming they fit on the board. Each move is a combination of moving one square in one direction and two in the other.

moves :: (Int, Int) -> [(Int, Int)]
moves (x,y) = [(x+dx,y+dy) | [dx,dy] <- combos [[-1,1],[-2,2]]
, inRange (1,8) (x+dx), inRange (1,8) (y+dy)]
where combos xs = sequence xs ++ sequence (reverse xs)

To find the possible paths to the target square we simply generate all possible sequences of n moves and take the ones that end in the desired position.

paths :: (Int, Int) -> (Int, Int) -> Int -> [[(Int, Int)]]
paths from to n = map reverse . filter (\(x:_) -> x == to) $
iterate (>>= \(x:xs) -> map (:x:xs) $ moves x) [[from]] !! n

A test to see of everything is working properly:

main :: IO ()
main = mapM_ print $ paths (8,8) (1,1) 6

### Like this:

Like Loading...

*Related*

Tags: bonsai, chess, code, Haskell, kata, knight, moves, praxis, programming

This entry was posted on March 8, 2013 at 11:01 am and is filed under Programming Praxis. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply