Given the size of the board, Dijkstra's shortest path does not bring significant advantages over a < a breadth-first search , which is simply a search that starts from the root, and then goes.

exploring each sub-level.

On a very large board, such a search would be problematic, since the number of steps and the structure to store the nodes and the search job is exponential.

It turns out that in the practical case, which is an 8 × 8 board, the possibilities are very limited, so in some cases the BFS ends up finding the target in even less time than we would take to organize the nodes to apply the short path of Dijkstra.

BFS is almost a brute-force search, but it is well optimized in this case, with the elimination of the houses already visited.

## Illustrating a little better

```
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
```

At first, we would search the following numbered homes:

```
· · · · · 1 · 6
· · · · 2 · · ·
· · · · · · C ·
· · · · 3 · · ·
· · * · · 4 · 5
· · · · · · · ·
· · · · · · · ·
· · · · · · · ·
```

How can not find the destination:

Then we "moved" the horse to each of the houses of the previous step, and we repeat the procedure, always eliminating the houses already visited:

```
· · · · · C · ? · · 2 · · × 2 ? · · × · · × × ?
· · · 1 ? · · 1 · · · × C · · × · · · × × 3 · ×
· · · · 1 · × · · · 2 · × · × · · · × · × · × ·
· · · · ? · · · · · · 2 ? 2 · · · · · × C × · ·
· · * · · ? · ? · · * · · ? · ? · ·[3]· · ? 3 ?
· · · · · · · · · · · · · · · · · · · 3 · 3 · ·
· · · · · · · · · · · · · · · · · · · · · · · ·
· · · · · · · · · · · · · · · · · · · · · · · ·
```

By chance, in the scenario of the question, we find the destination already in step 2, "substep" 3. We do not even need to test the last houses (substeps 4, 5 and 6).

The important thing here is to note that despite the exponential nature of the algorithm, the boundary of the board and the fact of eliminating the houses already visited make the solution a bit simple (and always solved in a single step). Even though some cases take a few more steps, in the second case we have eliminated almost half the board.

##

Let's go to the code?

If you want to go straight to the version that only counts the number of movements required, see the end of the answer. To facilitate understanding the algorithm I did a more complex version that returns the given steps, not just the count.

I confess I do not have experience with Python, I've probably made a series of style slips, and maybe ignored obvious optimizations, but I hope the algorithm, which is what matters to us, has been pretty easy to keep up with. p>

If you take the comments and debugs from print from within the function, you will notice that even with my inexperience, the code has become extremely lean:

```
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))
```

See the horse in action at IDEONE .

##

The same code, no firsts

For comparison, follow simplified and reorganized version of the above code.

Almost the same thing, basically without the comments and prints , and with some things inline , but still returning all the steps:

```
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
```

Also IDEONE .

And finally, as the question asks, just the count:

```
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
```

Example usage:

```
movimentosNecessarios = vaiCavalo([1,1],[1,2])
```

And, of course, one more IDEONE .

Worth a read in this release of the algorithm above, with a much more Academic format , kindly left by colleague @Joao, who made an implementation with `queue`

/ `deque`

. It was very elegant code, by the way.

### Note:

It is not part of the problem, but it is interesting to note that the horse does not move in "L" in fact. The "L" is a way to make it easier for the learner to understand where the horse can go. The horse moves straight to the destination, like any other piece. It just happens that the "straight line" does not match the board's alignment.