fork download
  1.  
  2. def vaiCavalo( origemX, origemY, destinoX, destinoY ):
  3.  
  4. # criamos uma matriz 8x8 preenchida com False
  5. # para anotar as casas ja testadas
  6. casasTestadas = [[False]*8 for i in range(8)]
  7.  
  8. # todos os movimentos possiveis do cavalo
  9. movimentos = [[-1,-2],[-2,-1],[-2,1],[-1,2],[1,2],[2,1],[2,-1],[1,-2]]
  10.  
  11. # o primeiro passo e a origem do cavalo
  12. # X, Y e caminho percorrido ate entao (vazio no comeco)
  13. passos = [[origemX, origemY,[]]]
  14.  
  15. while True:
  16. proximosPassos = []
  17. for passo in passos:
  18. print("Cavalo atualmente em [", passo[0], ",", passo[1], "], vindo de", passo[2])
  19.  
  20. # vamos testar todos os movimentos possiveis a partir deste passo
  21. for movimento in movimentos:
  22. x = passo[0]+movimento[0]
  23. y = passo[1]+movimento[1]
  24.  
  25. # armazenamos o caminho feito ate chegar aqui
  26. caminho = (list(passo[2]))
  27. caminho.append([passo[0],passo[1]])
  28.  
  29. # o cavalo chegou ao destino, retornamos o caminho completo
  30. if x == destinoX and y == destinoY:
  31. print(" PRONTO! Chegamos em [", x, y, "]")
  32. caminho.append([x,y])
  33. return caminho
  34.  
  35. # senao, armazenamos a posicao para a proxima rodada
  36. elif 0 <= x < 8 and 0 <= y < 8 and not casasTestadas[x][y]:
  37. print(" Destino nao encontrado em [", x, y, "], coordenadas na pilha")
  38. proximosPassos.append([x,y,caminho])
  39.  
  40. # vamos descartar novas tentativas partindo daqui
  41. casasTestadas[x][y] = True
  42.  
  43. # todos os passos realizados, vamos para os seguintes
  44. passos = proximosPassos
  45.  
  46. print("\nCaminho feito:", vaiCavalo(3, 2, 3, 3))
  47.  
Success #stdin #stdout 0.01s 9992KB
stdin
Standard input is empty
stdout
Cavalo atualmente em [ 3 , 2 ], vindo de []
  Destino nao encontrado em [ 2 0 ], coordenadas na pilha
  Destino nao encontrado em [ 1 1 ], coordenadas na pilha
  Destino nao encontrado em [ 1 3 ], coordenadas na pilha
  Destino nao encontrado em [ 2 4 ], coordenadas na pilha
  Destino nao encontrado em [ 4 4 ], coordenadas na pilha
  Destino nao encontrado em [ 5 3 ], coordenadas na pilha
  Destino nao encontrado em [ 5 1 ], coordenadas na pilha
  Destino nao encontrado em [ 4 0 ], coordenadas na pilha
Cavalo atualmente em [ 2 , 0 ], vindo de [[3, 2]]
  Destino nao encontrado em [ 0 1 ], coordenadas na pilha
  Destino nao encontrado em [ 1 2 ], coordenadas na pilha
  Destino nao encontrado em [ 3 2 ], coordenadas na pilha
  Destino nao encontrado em [ 4 1 ], coordenadas na pilha
Cavalo atualmente em [ 1 , 1 ], vindo de [[3, 2]]
  Destino nao encontrado em [ 0 3 ], coordenadas na pilha
  Destino nao encontrado em [ 2 3 ], coordenadas na pilha
  Destino nao encontrado em [ 3 0 ], coordenadas na pilha
Cavalo atualmente em [ 1 , 3 ], vindo de [[3, 2]]
  Destino nao encontrado em [ 0 5 ], coordenadas na pilha
  Destino nao encontrado em [ 2 5 ], coordenadas na pilha
  Destino nao encontrado em [ 3 4 ], coordenadas na pilha
  Destino nao encontrado em [ 2 1 ], coordenadas na pilha
Cavalo atualmente em [ 2 , 4 ], vindo de [[3, 2]]
  Destino nao encontrado em [ 1 6 ], coordenadas na pilha
  Destino nao encontrado em [ 3 6 ], coordenadas na pilha
  Destino nao encontrado em [ 4 5 ], coordenadas na pilha
  Destino nao encontrado em [ 4 3 ], coordenadas na pilha
Cavalo atualmente em [ 4 , 4 ], vindo de [[3, 2]]
  Destino nao encontrado em [ 5 6 ], coordenadas na pilha
  Destino nao encontrado em [ 6 5 ], coordenadas na pilha
  Destino nao encontrado em [ 6 3 ], coordenadas na pilha
  Destino nao encontrado em [ 5 2 ], coordenadas na pilha
Cavalo atualmente em [ 5 , 3 ], vindo de [[3, 2]]
  Destino nao encontrado em [ 7 4 ], coordenadas na pilha
  Destino nao encontrado em [ 7 2 ], coordenadas na pilha
  Destino nao encontrado em [ 6 1 ], coordenadas na pilha
Cavalo atualmente em [ 5 , 1 ], vindo de [[3, 2]]
  Destino nao encontrado em [ 7 0 ], coordenadas na pilha
Cavalo atualmente em [ 4 , 0 ], vindo de [[3, 2]]
Cavalo atualmente em [ 0 , 1 ], vindo de [[3, 2], [2, 0]]
  Destino nao encontrado em [ 2 2 ], coordenadas na pilha
Cavalo atualmente em [ 1 , 2 ], vindo de [[3, 2], [2, 0]]
  Destino nao encontrado em [ 0 0 ], coordenadas na pilha
  Destino nao encontrado em [ 0 4 ], coordenadas na pilha
  PRONTO! Chegamos em [ 3 3 ]

Caminho feito: [[3, 2], [2, 0], [1, 2], [3, 3]]