Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for The Shortest Knight's Path by Renelvon
from collections import deque
def checkio(setting):
x0, y0 = ord(setting[0]) - ord('a'), ord(setting[1]) - ord('1')
x1, y1 = ord(setting[3]) - ord('a'), ord(setting[4]) - ord('1')
visited = [[False for _ in range(8)] for _ in range(8)]
moves = (
(-1, -2), (1, -2), (-1, 2), (1, 2),
(-2, -1), (-2, 1), (2, -1), (2, 1)
)
q = deque([(x0, y0, 0)])
visited[x0][y0] = True
while q:
x, y, d = q.popleft()
if (x, y) == (x1, y1):
break
for xx, yy in ((x + dx, y + dy) for dx, dy in moves):
if 0 <= xx < 8 and 0 <= yy < 8 and not visited[xx][yy]:
q.append((xx, yy, d + 1))
visited[xx][yy] = True
return d
June 1, 2014