Home / Questions / 564131
Accepted
Martin Flores
Asked: 2022-10-25 18:30:58 +0800 CST 2022-10-25 18:30:58 +0800 CST

How can I put coordinates in a chess knight tour?

  • 772

Hello, good, I have a problem with this horse chess code, the execution is more than good when executing it, but when putting the coordinates using the values ​​of m and n with the signs // to be able to take it, it does not work as I want since the user It will ask me if I want it to be in the mere right, left, top, bottom corner and any point but when executing it takes a long time in some numbers when executing it as -9 and 2 in another if it gives me a point like -7 and 9 Could you help me if I can use this method or another method to put the coordinates:

# Dimensiones: para que exista un ciclo pedimos que ninguno sea
# par, ambos mayores que 5. Hay otros casos donde existe ciclo.
m = 8
n = 8
ciclo = True # buscar recorrido cerrado (ciclo)
print("Esto es a traves de division")
Valor1= int(input("Ingrese el número de fila deseada ==> "))
Valor2= int(input("Ingrese el número de colummna deseada ==> "))  
#############################################################################
# - El vértice correspondiente a (i, j) es k = 1 + i + j * m,
# i, j = divmod(k - 1, m)
# - Los vecinos de (i, j) son de la forma
# (i ± 2, j ± 1) y (i ± 1, j ± 2)
# siempre que queden en el tablero.
def kdeij(i, j):
   return 1 + i + m * j
###############################################################################
def ijdek(k):
   return divmod(k - 1, m)
#############################################################################
# ponemos la raíz en el centro para que sea rápido
#raiz = kdeij(m // Valor1, n // Valor2) este es el que estaba usando
raiz = kdeij(m //2, n//2)
#################################################################################
# Construcción de vecinos
mn = m * n # cantidad de vértices
mn1 = mn + 1 # para range
###################################################################################
vecinos = [[] for k in range(mn1)]
vecinos[0] = None
#######################################################################################
# No hay vecinos con un mismo j,
# Ponemos sólo los de arriba (los de abajo se dan por simetría).
vecinos = [[] for v in range(mn1)]
vecinos[0] = None

for i in range(m):
   for j in range(n):
     k = kdeij(i, j)
       ii = i - 2
       if ii >= 0:
           jj = j + 1
           if jj < n:
              kk = kdeij(ii, jj)
                vecinos[k].append(kk)
                vecinos[kk].append(k)
       ii = i - 1
       if ii >= 0:
           jj = j + 2
           if jj < n:
              kk = kdeij(ii, jj)
                vecinos[k].append(kk)
                vecinos[kk].append(k)
       ii = i + 1
       if ii < m:
           jj = j + 2
           if jj < n:
              kk = kdeij(ii, jj)
                vecinos[k].append(kk)
                vecinos[kk].append(k)
       ii = i + 2
       if ii < m:
           jj = j + 1
           if jj < n:
              kk = kdeij(ii, jj)
                vecinos[k].append(kk)
                vecinos[kk].append(k)
#----------------------------------------------#
# Función a usar
#----------------------------------------------#
def hamilton(m, n, vecinos, raiz=1, ciclo=True):
#####################################################################################
  def grado(v):
    a = [u for u in vecinos[v] if padre[u] == None]
    return len(a)
#####################################################################################
def visitar(u):
    nonlocal cuenta, llegamos
    cuenta = cuenta + 1

    if llegamos:
        return
    if len(ciclov) < mn: # En este punto todavía no llegamos
        a = [v for v in vecinos[u] if padre[v] == None]
        if a != []:
            a.sort(key=grado)
            for v in a:
                padre[v] = u
                ciclov.append(v)
                visitar(v)
                if llegamos:
                   return
                padre[v] = None
                ciclov.pop()
    elif (len(ciclov) == mn):
        if not ciclo:
            llegamos = True
        if (u in vecinosraiz):
            llegamos = True
            ciclov.append(raiz)
# en otro caso len(ciclov) == mn1
mn = m * n # cantidad de vértices
mn1 = mn + 1 # para vértices entre 1 y mn

vecinosraiz = vecinos[raiz]

ciclov = [raiz] # empezamos desde la raíz
padre = [None for v in range(mn1)]

padre[raiz] = raiz

cuenta = 0
llegamos = False

visitar(raiz)

print(40 * "-")
print("Cantidad de entradas a visitar:", cuenta)
if llegamos:
    return ciclov
print("No hay ciclo de hamilton")
return []
############################################################################
# fin de función
#################################################################################
ciclo = hamilton(m, n, vecinos, raiz, True)
#################################################################################
print(40 * '-')
print('Ciclo resultante:')
print(ciclo)
print('Longitud:', len(ciclo))
#----------------------------------------------
# Representación como tablero
#----------------------------------------------
# cantidad de espacios para que no se superpongan los números
s = len(str(mn1)) + 1
formato = "{:" + str(s) + "}"
# buscamos la inversa del ciclo
pos = [None for v in range(mn1)]
for p in range(mn):
      pos[ciclo[p]] = p + 1
print(40 * "-")
print("Recorrido del tablero (posiciones en cada movimiento representadas en un numero de 
inicio al final):")
#######################################################################################
for j in range(n-1, -1, -1):
  k = 1 + m * j
  for i in range(m):
      print(formato.format(pos[k + i]), end="")
  print()
#####################################################################################
python

1 Answers

  1. Best Answer

    I made this simple, not very efficient algorithm to traverse a chessboard with a knight without passing the same square twice.

    The board is represented by a list of lists, that is, an N x N matrix.

    Valid moves are expressed as a list of moves relative to the current square:

    movidas = [
    (-2, -1), (-2, +1),
    (-1, +2), (+1, +2),
    (+2, +1), (+2, -1),
    (+1, -2), (-1, -2)
]

    We have a function that receives a position and a move and returns the final position, or Noneif it went off the board:

    def mover(board, pos, mov):
    #   Intenta mover pieza desde pos
    #   usando el desplazamiento mov.
    #   Retorna la nueva posición o None.
    row = pos[0] + mov[0]
    col = pos[1] + mov[1]
    if 0 <= row < len(board):
        if 0 <= col < len(board):
            return row, col
    return None

    We implement a search with backtracing , whose result is reflected in the list posiciones, which will give us the path of the horse.

    posiciones = []

    The recursive function does the following:

    • Add the received position to posiciones, assuming this cell leads to the destination.
    • Then check out the eight possible jumps. If someone hits an unoccupied square, it is called recursively to check if it is the correct choice.
    • If the review returns False, everything is undone: the position is removed and the box is unchecked.
    • If it is True, it is returned.

    To check if we have completed the tour we use the function all(). If there is any zero somewhere (unvisited cell), the function fails.

    def analiza(board, pos):
    posiciones.append(pos)
    board[pos[0]][pos[1]] = 1
    for mov in movidas:
        nueva = mover(board, pos, mov)
        if nueva and board[nueva[0]][nueva[1]] == 0:
            if analiza(board, nueva):
                return True

    completo = all([x for row in board for x in row])
    if not completo:
        board[pos[0]][pos[1]] = 0
        posiciones.pop()
    return completo

    The rest are printing functions.

    show

    I tried it with a 5x5 board and it seems to work. You can check it.

    movidas = [
    (-2, -1), (-2, +1),
    (-1, +2), (+1, +2),
    (+2, +1), (+2, -1),
    (+1, -2), (-1, -2)
]

def mover(board, pos, mov):
    #   Intenta mover pieza desde pos
    #   usando el desplazamiento mov.
    #   Retorna la nueva posición o None.
    row = pos[0] + mov[0]
    col = pos[1] + mov[1]
    if 0 <= row < len(board):
        if 0 <= col < len(board):
            return row, col
    return None

def imprimir(board):
    print("   ", end='')
    for row in range(len(board)):
        print(f"{row:2d}", end=' ')
    print("")
    for row in range(len(board)):
        print(f"{row:2d} ", end=' ')
        for col in range(len(board)):
            pieza = 'K' if board[row][col] else ' '
            print(f"{pieza} ", end= ' ')
        print()
    print()

posiciones = []
def analiza(board, pos):
    posiciones.append(pos)
    board[pos[0]][pos[1]] = 1
    for mov in movidas:
        nueva = mover(board, pos, mov)
        if nueva and board[nueva[0]][nueva[1]] == 0:
            if analiza(board, nueva):
                return True

    completo = all([x for row in board for x in row])
    if not completo:
        board[pos[0]][pos[1]] = 0
        posiciones.pop()
    return completo

dim = 5
tablero = [[0] * dim for x in range(dim)]
analiza(tablero, (0,0))

tablero = [[0] * dim for x in range(dim)]
anterior = None
for pos in posiciones:
    if anterior:
        print(f"Caballo de ({anterior[0]}, {anterior[1]}) a ({pos[0]},{pos[1]})")
    else:
        print(f"Caballo a ({pos[0]},{pos[1]})")
    anterior = pos
    tablero[pos[0]][pos[1]] = 1
    imprimir(tablero)
print(posiciones)

    produces:

    Caballo a (0,0)
    0  1  2  3  4 
 0  K              
 1                 
 2                 
 3                 
 4                 

Caballo de (0, 0) a (1,2)
    0  1  2  3  4 
 0  K              
 1        K        
 2                 
 3                 
 4                 

Caballo de (1, 2) a (0,4)
    0  1  2  3  4 
 0  K           K  
 1        K        
 2                 
 3                 
 4                 

Caballo de (0, 4) a (2,3)
    0  1  2  3  4 
 0  K           K  
 1        K        
 2           K     
 3                 
 4                 

Caballo de (2, 3) a (0,2)
    0  1  2  3  4 
 0  K     K     K  
 1        K        
 2           K     
 3                 
 4                 

Caballo de (0, 2) a (1,4)
    0  1  2  3  4 
 0  K     K     K  
 1        K     K  
 2           K     
 3                 
 4                 

Caballo de (1, 4) a (3,3)
    0  1  2  3  4 
 0  K     K     K  
 1        K     K  
 2           K     
 3           K     
 4                 

Caballo de (3, 3) a (4,1)
    0  1  2  3  4 
 0  K     K     K  
 1        K     K  
 2           K     
 3           K     
 4     K           

Caballo de (4, 1) a (2,0)
    0  1  2  3  4 
 0  K     K     K  
 1        K     K  
 2  K        K     
 3           K     
 4     K           

Caballo de (2, 0) a (0,1)
    0  1  2  3  4 
 0  K  K  K     K  
 1        K     K  
 2  K        K     
 3           K     
 4     K           

Caballo de (0, 1) a (1,3)
    0  1  2  3  4 
 0  K  K  K     K  
 1        K  K  K  
 2  K        K     
 3           K     
 4     K           

Caballo de (1, 3) a (3,4)
    0  1  2  3  4 
 0  K  K  K     K  
 1        K  K  K  
 2  K        K     
 3           K  K  
 4     K           

Caballo de (3, 4) a (2,2)
    0  1  2  3  4 
 0  K  K  K     K  
 1        K  K  K  
 2  K     K  K     
 3           K  K  
 4     K           

Caballo de (2, 2) a (1,0)
    0  1  2  3  4 
 0  K  K  K     K  
 1  K     K  K  K  
 2  K     K  K     
 3           K  K  
 4     K           

Caballo de (1, 0) a (3,1)
    0  1  2  3  4 
 0  K  K  K     K  
 1  K     K  K  K  
 2  K     K  K     
 3     K     K  K  
 4     K           

Caballo de (3, 1) a (4,3)
    0  1  2  3  4 
 0  K  K  K     K  
 1  K     K  K  K  
 2  K     K  K     
 3     K     K  K  
 4     K     K     

Caballo de (4, 3) a (2,4)
    0  1  2  3  4 
 0  K  K  K     K  
 1  K     K  K  K  
 2  K     K  K  K  
 3     K     K  K  
 4     K     K     

Caballo de (2, 4) a (0,3)
    0  1  2  3  4 
 0  K  K  K  K  K  
 1  K     K  K  K  
 2  K     K  K  K  
 3     K     K  K  
 4     K     K     

Caballo de (0, 3) a (1,1)
    0  1  2  3  4 
 0  K  K  K  K  K  
 1  K  K  K  K  K  
 2  K     K  K  K  
 3     K     K  K  
 4     K     K     

Caballo de (1, 1) a (3,0)
    0  1  2  3  4 
 0  K  K  K  K  K  
 1  K  K  K  K  K  
 2  K     K  K  K  
 3  K  K     K  K  
 4     K     K     

Caballo de (3, 0) a (4,2)
    0  1  2  3  4 
 0  K  K  K  K  K  
 1  K  K  K  K  K  
 2  K     K  K  K  
 3  K  K     K  K  
 4     K  K  K     

Caballo de (4, 2) a (2,1)
    0  1  2  3  4 
 0  K  K  K  K  K  
 1  K  K  K  K  K  
 2  K  K  K  K  K  
 3  K  K     K  K  
 4     K  K  K     

Caballo de (2, 1) a (4,0)
    0  1  2  3  4 
 0  K  K  K  K  K  
 1  K  K  K  K  K  
 2  K  K  K  K  K  
 3  K  K     K  K  
 4  K  K  K  K     

Caballo de (4, 0) a (3,2)
    0  1  2  3  4 
 0  K  K  K  K  K  
 1  K  K  K  K  K  
 2  K  K  K  K  K  
 3  K  K  K  K  K  
 4  K  K  K  K     

Caballo de (3, 2) a (4,4)
    0  1  2  3  4 
 0  K  K  K  K  K  
 1  K  K  K  K  K  
 2  K  K  K  K  K  
 3  K  K  K  K  K  
 4  K  K  K  K  K  

[(0, 0), (1, 2), (0, 4), (2, 3), (0, 2), (1, 4), (3, 3), (4, 1), (2, 0), (0, 1), (1, 3), (3, 4), (2, 2), (1, 0), (3, 1), (4, 3), (2, 4), (0, 3), (1, 1), (3, 0), (4, 2), (2, 1), (4, 0), (3, 2), (4, 4)]

Process finished with exit code 0
    • 0