O cavalo quer o menor caminho.

Dados dois quadrados do tabuleiro, precisamos descobrir o menor número de movimentos do cavalo necessário para sair da origem e alcançar o destino.

Para resolver com grafos, basta reinterpretar o tabuleiro.

a1, a2, ..., h8

O cavalo sempre faz um deslocamento em “L”: duas casas em um eixo e uma no outro.

movimentos = [
    (2, 1),
    (2, -1),
    (-2, 1),
    (-2, -1),
    (1, 2),
    (1, -2),
    (-1, 2),
    (-1, -2)
]

A BFS percorre o grafo por camadas de distância.

Este exemplo precisa de 2 movimentos. A animação mostra a expansão por camadas.

from collections import deque


def bfs(posA, posB):

    # Converte a posição do xadrez para índices 0..7
    x = int(posA[1]) - 1
    y = ord(posA[0]) - ord('a')

    a = int(posB[1]) - 1
    b = ord(posB[0]) - ord('a')

    visited = [
        [False] * 8
        for _ in range(8)
    ]

    fila = deque()

    # (linha, coluna, distância)
    fila.append((x, y, 0))
    visited[x][y] = True

    movimentos = [
        (2, 1),
        (2, -1),
        (-2, 1),
        (-2, -1),
        (1, 2),
        (1, -2),
        (-1, 2),
        (-1, -2)
    ]

    while fila:

        linha, coluna, distancia = fila.popleft()

        # Primeiro momento em que o destino sai da fila:
        # encontramos a menor distância.
        if linha == a and coluna == b:
            return distancia

        for dx, dy in movimentos:

            nx = linha + dx
            ny = coluna + dy

            # Movimento continua dentro do tabuleiro?
            if 0 <= nx < 8 and 0 <= ny < 8:

                # Ainda não visitamos esta casa?
                if not visited[nx][ny]:

                    visited[nx][ny] = True

                    fila.append(
                        (nx, ny, distancia + 1)
                    )


while True:

    try:
        posA, posB = input().split()

    except EOFError:
        break

    resposta = bfs(posA, posB)

    print(
        f"To get from {posA} to {posB} takes "
        f"{resposta} knight moves."
    )