Fewer moves from a horse to a given house in Chess

Question

On a chessboard in any house I have a Horse (represented in red) and I will have only one other piece (represented in green) that the horse must go to it:

I must use the simplest path and take into account the movement of the horse (in L) and count the movements until reaching the given point:

As in the example below:

How can I do this using python? I have in mind that I have to use matrix and a list as position input, but I don’t know how to continue.

Answer 1

Given the size of the board, the shortest way to Dijkstra does not bring significant advantages over 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, because the number of steps and the structure to store the nodes and the work of the search 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 destination in even less time than it would take to organize the nodes to apply the Dijkstra short path.

The BFS is practically a search for brute force, 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 numbered houses below:

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

Since we can’t find destiny:

• We keep the 6 possible destinations in a list.

• We have marked the 6 destinations as visited

Then we "move" the horse to each of the houses of the previous step, and 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, "subpasso" 3. Nor do we need to test the last houses (subpassos 4, 5 and 6).

The important thing here is to note that despite the exponential nature of the algorithm, the board boundary and the fact that we eliminate the houses already visited make the solution a bit simple (and always solved in one step). Even if some cases take a few more steps, in the second we have already 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 moves required, see the end of the answer. To facilitate the understanding of the algorithm I made a more complex version that returns the steps given, not just the count.

I confess that I have no experience with Python, I probably committed a series of style slips, and maybe I ignored obvious optimizations, but I hope that the algorithm, which is what we care about, has become very easy to follow.

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

_{^{(I put the prints just so that whoever is testing can measure the efficiency of the algorithm)}}

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 on IDEONE.

Same code, no strings

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 every step:

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 in the IDEONE.

And finally, as the question asks, only 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 of use:

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

And, of course, one more IDEONE.

It’s worth a read in this version of the above algorithm, with a much more Academic format, kindly left by colleague @Jjoao, who made an implementation with queue/deque. The code was very elegant, by the way.

Note:

It is not part of the problem, but it is interesting to note that the horse does not actually move in "L". 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 his "straight line" doesn’t match the alignment of the board.

Answer 2

A possible algorithm involves minimizing the distance between the horse and the target piece until you capture it. Try to do so:

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 of each of these houses to the home of the target piece (about distances, read that answer, any one is valid as heuristic, but the Euclidean generates better results). Sort them from smaller to greater distance.
3. Scroll over this ordered list (that is, from the smallest to the greatest 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, so move the horse to that house and go back to step 1 (repeating until you find the solution).

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

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

Answer 3

Proposed strategy:

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

that is to say

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 sloth the abscissas were translated into numbers (4C => 43 and 6G => 67). Running gives:

[[43, 55, 67]]

Update : additional explanation ( Thanks{Luiz Vieira})

I’m sorry, I admit the branch calculation has become rather cryptic.

• In fact the igraph module uses as vertex numbering 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 becomes complicated to read...

• The solution chosen was, during the creation of the branches, to 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 with : [(13, 21), (14, 22), (15, 23), (16, 24), ...]

• This leads to the set 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 undirected graph, it is sufficient to consider half of the possible jumps (hence the jump delta - only contain 4 pairs which get on the board)

• The "if" condition of the list in understanding is to ensure that the horse don’t jump off the board

If necessary, install python-igraph.

Answer 4

I’m not an expert on python, but I have a small notion of graph theory. This kind of problem can be solved using Algorithm by 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 path of less path?

I did a quick search on the internet and found a code able to help you at this link. I didn’t test it, so I can’t tell you if it works or not. But here’s the search suggestion.

Answer 5

Taking into account a little of what everyone said I came to this: I would like the opinion 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 moves

Answer 6

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

Calculate 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)]

Answer 7

I already did something similar in a final work of course, 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 you can use the same idea I had, it’s simple but it worked.

It is the following, build an 8x8 matrix representing your board, at the origin position put 1, at the destination and at the other positions leave with 0.

From there, while the destination position is 0, make the movement of the horses from 1 and place 2 in the possible positions. Store the positions in a map structure, where the 2 is the key and the positions you keep a list of them in the value part... then take this list of positions 2 and move the horse by placing 3 and guarding and so on.

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

Answer 8

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