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:

• We saved the 6 possible destinations in a list.

• We have marked the 6 destinations as visited

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

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.

A possible algorithm involves minimizing the distance between the horse and the target piece until it is captured. Try to do this:

You will need to use some auxiliary list to check if a "move" has already been made, in order to avoid infinite repetition loops. Of course this is not the best algorithm, but it can at least help you get started with solving your problem.

  

* As colleague @JJoao well   commented ,   be careful about restrictive situations, such as   Available options are very close (distance less than 2) and   still did not reach the target. In this case, a good heuristic can   be reversed behavior, and so try to move away from the target in the   next 2 moves (in order to create more freedom of movement).   It is worth remembering that this algorithm that I proposed is quite heuristic   and serves mainly to help you understand the problem. He    is not the best implementation. You have already received other suggestions (in other answers), and one of the best approaches involves   state space graph of the game (or, more efficiently, directly in the board considering the houses as graph nodes and the connecting edges the possible movements of the horse ).

Proposed strategy:

• see this problem as looking for path in a graph: nodes = positions in the board; branches = horse jumps;
• calculate the list of all horse jumps (= branches) - list in understanding;
• based on it build the graph (= g)
• find the shortest path in this graph

ie

from igraph import *

ramos=[ ( a*10+b , (a+dx)*10+b+dy )
    for a in range(1,9)                        ## 1 .. 8
    for b in range(1,9)                        ## a .. h
    for dx,dy in [(1,-2),(2,-1),(1,2),(2,1)]   ## delta do movimento do cavalo
    if 0 < a+dx <= 8 and 0 < b+dy <= 8 ]       ## nao sai borda-fora

g = Graph()
g.add_vertices(89)
g.add_edges(ramos)

print g.get_shortest_paths(43, to=67, mode=OUT, output="vpath")

For laziness, the abscissa were translated into numbers (4C => 43 and 6G => 67). Running gives:

[[43, 55, 67]]

Update : additional explanation (\ thanks {Luiz Vieira})

Sorry, I admit that the calculation of the branches was quite cryptic.

• Actually, the igraph module uses number vertices as numbers contiguous integers (I wanted pairs of coordinates). If we simply use an integer followed for each vertex, the calculation of the jumps and the reading of the final path gets complicated to read ...

• The chosen solution was, during the creation of the branches, to consider each vertex as an ordered pair (example (6,7)) and at the end convert it to integer, juxtaposing the digits (6 * 10 + 7). "branches" is: [(13, 21), (14, 22), (15, 23), (16, 24), ...]

• This leads to the sum of vertices ranging from 11 to 88 but not the vertices containing "0" or "9" are being used (hence the strange declaration of 89 vertices ...)

• In the case of an unguided graph, consider only half of the possible jumps (hence the jump delta - only contain 4 pairs that climb on the board)

• The "if" condition of the list in understanding is to ensure that the horse does not jump off the board

If necessary, install python-igraph.

I'm not an expert in python, but I have a little notion of graph theory. This type of problem can be solved using the Dijkstra algorithm . According to Wikipedia, it is used for the following:

  

A practical example of the problem that can be solved by the Dijkstra algorithm is: someone needs to move from one city to another. For this, it has several roads, which pass through several cities. Which of these offers a path of least path?

I did a quick search on the internet and found a code that could help this link . I have not tested it, so I can not tell you whether it works or not. But here's the research suggestion.

Taking into account a little of what everyone said I came to this: I would like the opniao and would be correct the logic that I used:

distancia = {}
caminho = {}

def movimento():
    inicio = 3,2
    fim = 8,8

    fila = [inicio]
    distancia[inicio] = 0
    caminho[inicio] = 1

    while len(fila):
        atual = fila[0]
        fila.pop(0)
        if atual == fim:
            print "Possivel ir em %d movimentos"%(distancia[atual])
            return

        for movimento in [ (1,2),(2,1),(-1,-2),(-2,-1),(1,-2),(-1,2),(-2,1),(2,-1) ]:
            prox_mov = atual[0]+movimento[0], atual[1]+movimento[1]
            if prox_mov[0] > fim[0] or prox_mov[1] > fim[1] or prox_mov[0] < 1 or prox_mov[1] < 1:
                continue
            if prox_mov in distancia and distancia[prox_mov] == distancia[atual]+1:
                caminho[prox_mov] += caminho[atual]
            if prox_mov not in distancia:
                distancia[prox_mov] = distancia[atual] + 1
                caminho[prox_mov] = caminho[atual]
                fila.append(prox_mov)

if __name__ == '__main__':
    movimento()

  

Possible to go in 5 moves

Without answering the question, but trying to contribute to the topic, I did a function that initializes the horse's movements, making the next steps faster

Calculates Destination for the horse from a coordinate [l, c]

#dadas as direçoes em X e em Y e a chave k=[1,2]
def  R(c,l,i=-1,j=-1,k=2):
    #c=Origem.Coluna, l=Origem.Linha
    #i,j=[-1,1]=[move p traz ou p cima,move p frente ou p baixo]
    m=l+i*k #Destino.Linha
    n=c+j*(3-k) #Destino.Coluna
    if m in xrange(8)and n in xrange(8):
        return m,n
    else: 
        return () #O cavalo está no canto

def  Init_Map():
    A=xrange(8)
    B=[-1,1]
    matrix={}
    for c in A:
        for l in A:
            matrix[l,c]= [R(c,l,i,j,k1)  for i in B for j in B for k1 in [1,2]]
    return matrix     

MAP=Init_Map()

#A variável map ficará na memoria com todos movimentos do cavalo possíveis-
print MAP

{  - (0, 0): [(1, 2), (2, 1)],  - (0,1): [(2, 0), (1, 3), (2, 2)],  - (0, 2): [(1.0), (2, 1), (1, 4), (2, 3)],  - (0, 3): [(1, 1), (2, 2), (1, 5), (2, 4)],  - ...]}

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

#Estando o cavalo em [2,6] ou em qualquer coordenada[l,c] basta fazer
print 'C[2,6]=', MAP[2,6]

C [2,6] = [(1,4), (0, 5), (0,7), (3,4), (4,5), (4,7) >     

I already did something similar in a final course paper, it was a library map that had an origin, which would be the computer where the system was being accessed, and destined the book on the shelf. But to use the same idea I had, it's simple but it worked.

It is as follows, construct an 8x8 matrix representing your board, in the source position put 1, in the destination and in the other positions leave with 0.

From there, while the target position is 0, move the horses from 1 and place 2 in the possible positions. Save the positions in a map structure, where 2 is the key and the positions you keep a list of them in the part of the value ... then take this list of positions 2 and move the horse by putting 3 and saving and so on. p>

One hour, the destination will be filled, and then the reverse path will be made, for example the destination is 3, search for the 2 that can reach it and then the 1.