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

1. in the current position, the horse has only a limited number of houses to which it can go. Get these houses (hint: sweep the neighborhood considering the "rectangles" formed by the L of the movement).
2. Calculate the distance from each of these houses to the House of the target piece (about distances, read this answer , any one is valid as heuristic, but Euclidean yields better results). Order them from the smallest to the largest distance.
3. iterates over this ordered list (i.e. from smallest to largest distance). If the distance from the current iteration House is 0, you have arrived at the solution. Otherwise, if it is less than 2, disregard^* the house and go to the next (because jumping there will not help, since it will be too close to the target, without reaching it). Otherwise, you have found the best move at the moment, then move the horse to this house and go back to step 1 (repeating until you find the solution).

You will need to use some helper list to check if a" move " has already been made, in order to avoid endless loops of repetition. This is certainly not the best algorithm, but it can at least help you have an initial path to solve your problem.

^* like colleague @JJoao well commented , you have to be careful with situations restrictions, such as those in which all available options are very close (distance less than 2) and still not reached the target. In this case, a good heuristic can be reverse the behavior, and thus 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 it serves mainly to help you understand the problem. They is not the best implementation. You have already received other suggestions (in other answers), and one of the best approaches involves searching in a graph of the game state space (or, more efficiently, directly on the board considering the houses as nodes of the graph and the edges connecting the possible movements of the horse ).

Proposed strategy:

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

I.e.

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

By laziness the abscesses were translated into numbers (4C = > 43 and 6G = > 67). Run gives:

[[43, 55, 67]]

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

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

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

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

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

• If this is a non-oriented graph, consider half of the possible jumps (hence the delta of jump - only contain 4 pairs that climb on the board)

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

If necessary, install python-igraph.

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

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

I did a quick search on the internet and found a code that could help you in this link. I haven't tested it, so I can't tell you if it works or not. But it remains the suggestion of research.

Taking into account a little of what everyone talked about I came to this: I would like opniao and if it would be correct the logic 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 movements

Without answering the question, but trying to contribute to the topic, I made 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've done 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 the destination the book on the shelf. But to use the same idea I had, it's simple but it worked.

Is as follows, build 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, as long as the target position is 0, make the movement of horses from 1 and put 2 in the possible positions. Save the positions in a map structure, where 2 is the key and the positions you save a list of them in the value part... then take this list of positions 2 and move the horse by putting 3 and guarding and so it goes.

One hour the destination will be filled, and then just do the reverse way, for example the destination got 3, look for the 2 that can reach it and then for the 1.

p=(5, 3)
s=(1, 1)
def f(x,y):x=abs(x);y=abs(y);s=x+y;return(.9+max(x/4,y/4,s/6)-s/2+(s==1or x==y==2))//1*2+s
print(int(f(s[0]-p[0],s[1]-p[1])))