Knight Moves

March 8, 2013

[ Today’s exercise comes from “Learn You a Haskell for Great Good” written by Miran Lipovača; the solution was written by Kyle Ilantzis. Guest authors are always welcome; if you are interested, contact me at the email address on the menu bar. By the way, that’s a fine place to start if you want to learn about Haskell. ]

This exercise comes from “Learn You a Haskell for Great Good!” by Miran Lipovača. Lipovača demonstrates a solution to find out if a single knight piece on a chessboard can reach a position in three moves. As an exercise he suggests that we try to find out if that knight can reach a position on the board in n moves and if so, what are the moves that the knight should make.

Your task is to write a function that given a starting position, ending position, and n number of moves to take, returns a list of all possible paths that that knight piece could take to reach the goal. If some input has no solution then simply return an empty list. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

6 Responses to “Knight Moves”

  1. […] today’s Programming Praxis exercise, our goal is to list all the potential ways a knight on a chess board […]

  2. My Haskell solution (see http://bonsaicode.wordpress.com/2013/03/08/programming-praxis-knight-moves/ for a version with comments):

    import Data.Ix
    
    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)
    
    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
    
  3. Simon Wo said

    My attempt in Python:

    def knightMoves(current, target, remaining):
    	if remaining == 0:
    		if current == target: yield [current]
    		else: return
    	else:
    		x, y = current
    		for move in [(x+i, y+j) for i in [2,1,-1,-2] for j in [2,1,-1,-2] 
    						if j != i and -j != i and x+i >= 1 and x+i <= 8 and y+j >= 1 and y+j <= 8]:
    			for path in knightMoves(move, target, remaining-1):
    				yield [current] + path
    

    Also, just thought I’d point out that you said there are 109 ways to move from (1,1) to (8,8) but there are actually only 108. (Your output has 109 lines but the top line is just the description!)

  4. Python, too

    from itertools import permutations
    nums = range(1, 9)
    transformations = [perm for perm in
                       permutations([1, -1, 2, -2], 2) if perm[0] + perm[1] != 0]
    
    
    def pos_moves(pos):
        for tran in transformations:
            move = (pos[0] + tran[0], pos[1] + tran[1])
            if move[0] in nums and move[1] in nums:
                yield move
    
    
    def knight_moves(start, end, n, path=[], slns=[]):
        if n == 0:
            if start == end:
                slns.append(path)
        elif n > 0:
            for move in pos_moves(start):
                knight_moves(move, end, n - 1, path[:] + [move])
        return slns
    
    for i, mv in enumerate(knight_moves((8, 8), (1, 1), 6)):
        print i, mv
    
  5. jpverkamp said

    Here’s my version in Racket:

    ; find all paths from src to dst in exactly the given moves
    (define (knight-moves src dst moves)
      (cond
        ; if we're out of moves, check if we've found a solution
        ; either return just the destination or the empty list
        [(= moves 0)
         (if (equal? src dst) (list dst) '())]
        ; otherwise, step in all 8 possible directions
        ; only keep solutions that stay on the board
        [else
         (for/list ([nxt (in-list (knight-neighbors src))]
                    #:when (in-bounds? nxt) 
                    [recur (in-list (knight-moves nxt dst (- moves 1)))])
           (cons src recur))]))
    

    Full writeup (including the source for knight-neighbors and in-bounds?, although they’re pretty much exactly what you’d expect) on my blog: Knight moves

  6. Mirko said

    My solution in Common Lisp closely follows the Racket solution, so I will not repeat it. But in the Racket and other codes I don’t see tests to see whether the path has either reached the target position in fewer than the required number of moves, or whether the path has revisited a previously visited position.

    This does not make a difference for n=6. But for n=8 if we allow for revisiting, I get 5124 paths, and if we prohibit them, we get 1896 paths.

    A related problem that I did not have the CPU, machine resources or patience to analyze is to obtain the distribution of the number of paths as function of number of moves. If we prohibit the path from revisiting positions after increasing (6: 108, 8: 1896, 10: 40252, 12: 731642, …) the number of paths for n-max large should eventually decrease and go to zero after 64 moves (The wikipedia page http://en.wikipedia.org/wiki/Knight%27s_tour shows a tour that covers the 8×8 board).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 643 other followers

%d bloggers like this: