# Less number of movements of a horse to a given house in Chess

31

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 should go to it: Imustusethesimplestpathandtakeintoaccountthemovementofthehorse(inL)andcountthemovementsuntilarrivingatthedeterminedpoint:

Asintheexamplebelow:

How can I do this using python? I have in mind that I have to use array and list as input position, but I do not know how to continue.

asked by anonymous 03.12.2016 / 01:06

28

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

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, ",", passo, "], vindo de", passo)

# vamos testar todos os movimentos possiveis a partir deste passo
for movimento in movimentos:
x = passo+movimento
y = passo+movimento

# armazenamos o caminho feito ate chegar aqui
caminho = list(passo)
caminho.append([passo,passo])

# 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

# 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+movimento, passo+movimento
if [x,y] == destino:
return passo+[[x,y]]
if 0 <= x < 8 and 0 <= y < 8 and not casasTestadas[x][y]:
proximosPassos.append([x,y,passo+[[x,y]]])
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+]

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+movimento, passo+movimento
if [x,y] == destino:
return passo+1
if 0 <= x < 8 and 0 <= y < 8 and not casasTestadas[x][y]:
proximosPassos.append([x,y,passo+1])
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. 10.12.2016 / 22:51
22

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

• At 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 movement's L).
• Calculate the distance from each of these houses to the house of the target piece (over distances, read this answer >, any one is valid as heuristic, but Euclidean gives better results). Sort them from the smallest to the longest distance.
• Iterate over this ordered list (that is, from the lowest to the longest distance). If the distance from the current house of the iteration is 0, you have arrived at the solution. Otherwise, if it is smaller than 2, disregard the house and go to the next one (because jumping there will not help, since it will be too close to the target, without reaching it). If not, you have found the best move at the moment, then 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 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 ).

03.12.2016 / 03:14
13

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

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.

09.12.2016 / 14:13
4

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.

07.12.2016 / 19:03
1

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
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+movimento, atual+movimento
if prox_mov > fim or prox_mov > fim or prox_mov < 1 or prox_mov < 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

10.12.2016 / 11:50
1

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

20.01.2017 / 20:46
0

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.

07.12.2016 / 18:56