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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
#!/usr/bin/env python3
from collections import deque
def knights_move(start, end):
""" A Knight in chess can move from its current position to any square two
rows or columns plus one column or row away. Take a starting position and
an ending position and calculate the least number of moves required.
>>> knights_move('g2', 'a8') # g2 -> e3 -> d5 -> c7 -> a8
4
>>> knights_move('g2', 'h2') # g2 -> e3 -> f1 -> h2
3
"""
start_p = (ord(start[0]) - 96, int(start[1]))
end_p = (ord(end[0]) - 96, int(end[1]))
queue = deque([start_p])
visited = {start_p}
number_moves = 0
while queue:
for _ in range(len(queue)):
current = queue.popleft()
if current == end_p:
return number_moves
for position in possible_moves(current):
if position not in visited:
visited.add(position)
queue.append(position)
number_moves += 1
return -1
def possible_moves(position):
'''
Return all possible knight moves within the board from a position
>>> possible_moves((4, 4))
[(6, 5), (5, 6), (3, 6), (2, 5), (2, 3), (3, 2), (5, 2), (6, 3)]
>>> possible_moves((1, 1))
[(3, 2), (2, 3)]
'''
moves = ([2, 1], [1, 2], [-1, 2], [-2, 1], [-2, -1], [-1, -2], [1, -2],
[2, -1])
return [(position[0] + move[0], position[1] + move[1])
for move in moves
if (position[0] + move[0]) in range(1, 9)
and (position[1] + move[1]) in range(1, 9)]
if __name__ == "__main__":
import doctest
doctest.testmod(verbose=True)
|
