## Knight Moves

### March 8, 2013

First Lipovača provides us with a function `moveKnight` that determines a knights next possible moves from a position on the board. He treats a Knight’s position as a pair of integers for a column and a row. The function returns a list of next possible moves (were the knight remains on the chessboard).

`type KnightPos = (Int,Int)`

```moveKnight :: KnightPos -> [KnightPos] moveKnight (c, r) = filter onBoard [(c + 2, r + 1), (c + 2, r - 1),                                     (c - 2, r + 1), (c - 2, r - 1),                                     (c + 1, r + 2), (c + 1, r - 2),                                     (c - 1, r + 2), (c - 1, r - 2)]     where onBoard = \(c',r') -> c' `elem` [1..8] && r' `elem` [1..8]```

Using `moveKnight`, the function `nKnightMoves` returns a list of all possible moves that can be made from some starting position in n moves. We denote a path as a list of knight positions. So from (5,5), in 2 moves we could move to [ [(7,4),(5,2)], [(7,6),(5,7)] …] and so on. After that we define the function `pathsTo` which accepts n moves to make, the starting position, the end position, and then filters the list from `nKnightMoves` for only paths that reach the end position.

`type Path = [KnightPos]`

```nKnightMoves :: Int -> KnightPos -> [Path] nKnightMoves n pos     | n == 0 = return []     | otherwise = do         ps <- map return (moveKnight pos)         ps' <- nKnightMoves (n - 1) (last ps)         return (ps ++ ps')```

```pathsTo :: Int -> KnightPos -> KnightPos -> [Path] pathsTo n start end = filter ((==end) . last) \$ nKnightMoves n start```

You can run the program at http://programmingpraxis.codepad.org/wjpQvvAo, where you can also see the 109 ways to move a knight from one corner of the board to the other in six moves.

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 […]

```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 + perm != 0]

def pos_moves(pos):
for tran in transformations:
move = (pos + tran, pos + tran)
if move in nums and move 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).