Dado o tamanho do tabuleiro, o caminho mais curto de Dijkstra não traz vantagens significativas em relação a um Breadth-first search, que é simplesmente uma busca que parte da raíz, e depois vai explorando cada subnível.
Num tabuleiro muito grande, uma busca dessas seria problemática, pois o número de passos e a estrutura para armazenar os nós e o trabalho da busca é exponencial.
Acontece que no caso prático, que é um tabuleiro 8 × 8, as possibilidades são muito limitadas, então em parte dos casos o BFS acaba achando o destino em até menos tempo do que levaríamos para organizar os nós para aplicar o caminho curto de Dijkstra.
O BFS é praticamente uma busca por força-bruta, mas que fica bem otimizada neste caso, com a eliminação das casas já visitadas.
Ilustrando um pouco melhor
C = cavalo
* = destino
× = casas já visitadas, eliminadas da busca, não vão pra lista
numeros = casas que verificaremos no passo atual
(vão ser os pontos de partida do próximo passo)
? = casas da lista armazenada no passo anterior, que estamos processando
Num primeiro momento, fariamos a busca nas casas numeradas a seguir:
· · · · · 1 · 6
· · · · 2 · · ·
· · · · · · C ·
· · · · 3 · · ·
· · * · · 4 · 5
· · · · · · · ·
· · · · · · · ·
· · · · · · · ·
Como não encontramos o destino:
Em seguida "movemos" o cavalo para cada uma das casas do passo anterior, e repetimos o procedimento, sempre eliminando as casas já visitadas:
· · · · · C · ? · · 2 · · × 2 ? · · × · · × × ?
· · · 1 ? · · 1 · · · × C · · × · · · × × 3 · ×
· · · · 1 · × · · · 2 · × · × · · · × · × · × ·
· · · · ? · · · · · · 2 ? 2 · · · · · × C × · ·
· · * · · ? · ? · · * · · ? · ? · ·[3]· · ? 3 ?
· · · · · · · · · · · · · · · · · · · 3 · 3 · ·
· · · · · · · · · · · · · · · · · · · · · · · ·
· · · · · · · · · · · · · · · · · · · · · · · ·
Por acaso, no cenário da pergunta, encontramos o destino já no passo 2, "subpasso" 3. Nem precisamos testar as últimas casas (subpassos 4, 5 e 6).
O importante aqui é notar que apesar da natureza exponencial do algoritmo, o limite do tabuleiro e o fato de eliminarmos as casas já visitadas tornam a solução um bocado simples (e sempre resolvida numa etapa só). Mesmo que alguns casos levem mais alguns passos, no segundo deles já eliminamos quase metade do tabuleiro.
Vamos ao código?
Se quiser ir direto pra versão que apenas conta o número de movimentos necessários, veja ao final da resposta. Para facilitar o entendimento do algoritmo fiz uma versão mais complexa que retorna os passos dados, não apenas a contagem.
Confesso que não tenho experiência com Python, provavelmente cometi uma série de deslizes de estilo, e talvez tenha ignorado otimizações óbvias, mas espero que o algoritmo, que é o que nos importa, tenha ficado bem fácil de se acompanhar.
Se tirar os comentários e debugs de print™ de dentro da função, vai notar que mesmo com a minha inexperiência, o código ficou extremamente enxuto:
(eu coloquei os prints justamente para que quem for testar possa aferir a eficiência do algoritmo)
def vaiCavalo( origemX, origemY, destinoX, destinoY ):
# criamos uma matriz 8x8 preenchida com False
# para anotar as casas ja testadas
casasTestadas = [[False]*8 for i in range(8)]
# todos os movimentos possiveis do cavalo
movimentos = [[-1,-2],[-2,-1],[-2,1],[-1,2],[1,2],[2,1],[2,-1],[1,-2]]
# o primeiro passo e a origem do cavalo
# X, Y e caminho percorrido ate entao (vazio no comeco)
passos = [[origemX, origemY,[]]]
while True:
proximosPassos = []
for passo in passos:
print("Cavalo atualmente em [", passo[0], ",", passo[1], "], vindo de", passo[2])
# vamos testar todos os movimentos possiveis a partir deste passo
for movimento in movimentos:
x = passo[0]+movimento[0]
y = passo[1]+movimento[1]
# armazenamos o caminho feito ate chegar aqui
caminho = list(passo[2])
caminho.append([passo[0],passo[1]])
# o cavalo chegou ao destino, retornamos o caminho completo
if x == destinoX and y == destinoY:
print(" PRONTO! Chegamos em [", x, y, "]")
caminho.append([x,y])
return caminho
# senao, armazenamos a posicao para a proxima rodada
elif 0 <= x < 8 and 0 <= y < 8 and not casasTestadas[x][y]:
print(" Destino nao encontrado em [", x, y, "], coordenadas na pilha")
proximosPassos.append([x,y,caminho])
# vamos descartar novas tentativas partindo daqui
casasTestadas[x][y] = True
# todos os passos realizados, vamos para os seguintes
passos = proximosPassos
print("\nCaminho feito:", vaiCavalo(3, 2, 3, 3))
Veja o cavalo em ação no IDEONE.
O mesmo código, sem firulas
Para comparação, segue versão simplificada e reorganizada do código acima.
Quase a mesma coisa, basicamente sem os comentários e prints, e com algumas coisas inline, mas ainda retornando todos os passos:
def vaiCavalo( origem, destino ):
casasTestadas = [[False]*8 for i in range(8)]
passos = [origem+[[]]]
while True:
proximosPassos = []
for passo in passos:
for movimento in [[-1,-2],[-2,-1],[-2,1],[-1,2],[1,2],[2,1],[2,-1],[1,-2]]:
x,y = passo[0]+movimento[0], passo[1]+movimento[1]
if [x,y] == destino:
return passo[2]+[[x,y]]
if 0 <= x < 8 and 0 <= y < 8 and not casasTestadas[x][y]:
proximosPassos.append([x,y,passo[2]+[[x,y]]])
casasTestadas[x][y] = True
passos = proximosPassos
Também no IDEONE.
E, finalmente, como pede a pergunta, apenas a contagem:
def vaiCavalo( origem, destino ):
casasTestadas = [[False]*8 for i in range(8)]
passos = [origem+[0]]
while True:
proximosPassos = []
for passo in passos:
for movimento in [[-1,-2],[-2,-1],[-2,1],[-1,2],[1,2],[2,1],[2,-1],[1,-2]]:
x,y = passo[0]+movimento[0], passo[1]+movimento[1]
if [x,y] == destino:
return passo[2]+1
if 0 <= x < 8 and 0 <= y < 8 and not casasTestadas[x][y]:
proximosPassos.append([x,y,passo[2]+1])
casasTestadas[x][y] = True
passos = proximosPassos
Exemplo de uso:
movimentosNecessarios = vaiCavalo([1,1],[1,2])
E, é claro, mais um IDEONE.
Vale a pena uma lida nesta versão do algoritmo acima, com um formato bem mais Acadêmico, deixada gentilmente pelo colega @JJoao, que fez uma implementação com queue
/deque
. Ficou bem elegante o código, por sinal.
Nota:
Não faz parte do problema, mas é interessante notar que o cavalo não se move em "L" de fato. O "L" é uma forma de facilitar para o aprendiz entender aonde é que o cavalo pode ir. O cavalo se move direto para o destino, como qualquer outra peça. Apenas acontece da "linha reta" dele não coincidir com o alinhamento do tabuleiro.