0

Hola Buenas tengo un problema con este Código de ajedrez de caballos la ejecución esta más que bien a la hora de ejecutarlo pero al poner las coordenadas usando los valores de m y n con los signos // para poder tomarlo no me resulta como quiero ya que el usuario me pedirá si quiere que este en la mera esquina derecha, izquierda, arriba, abajo y cualquier punto pero al hacer la ejecución tarda mucho en unos números al ejecutarlo como -9 y 2 en otro si me da un punto como el -7 y 9. Me podrían ayudar si puedo usar este método u otro método para poner las coordenadas:

# 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()
#####################################################################################
3
  • pos = [None] * mn1
    – Candid Moe
    el 25 oct. 2022 a las 7:09
  • No se entiende absolutamente nada.
    – Candid Moe
    el 25 oct. 2022 a las 7:09
  • A partir de la línea 46 está mal indentado.
    – Candid Moe
    el 25 oct. 2022 a las 10:25

1 respuesta 1

0

Hice este simple algoritmo, no muy eficiente, para recorrer un tablero de ajedrez con un caballo sin pasar dos veces por la misma casilla.

El tablero está representado por una lista de listas, o sea, una matriz de N x N.

Las movidas válidas están expresadas como una lista de desplazamientos respecto a la casilla actual:

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

Tenemos una función que recibe una posición y una movida y retorna la posición final, o None si se salió del tablero:

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

Implementamos una búsqueda con backtracing, cuyo resultado se refleja en la lista posiciones, que nos va a dar el recorrido del caballo.

posiciones = []

La función recursiva hace lo siguiente:

  • Agrega la posición recibida a posiciones, suponiendo que esta celda lleva al destino.
  • Luego revisa los ocho saltos posibles. Si alguno da en una casilla desocupada, se llama recursivamente para revisar si es la elección correcta.
  • Si la revisión arroja False, se deshace todo: se elimina la posición y se desmarca la casilla.
  • Si es True, se retorna.

Para revisar si hemos completado el recorrido usamos la función all(). Si hay algún cero en algún parte (celda no visitada), la función falla.

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

El resto son funciones de impresión.

Demo

Lo probé con un tablero de 5x5 y parece funcionar. Lo puedes chequear.

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)

produce:

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
4
  • Pregunta si intento extender el programa a 8 se tarda mas o solo se congela por un rato? ya que lo probe con 6, 7 pero 8 se esta tardando el 25 oct. 2022 a las 19:16
  • Lo probe con 9x9 y me aburri de esperar. Cada casilla adicional multiplica por ocho el número de posibilidades. 7x7 son 49 casillas; 8x8 son 64. Tienes que multiplicar el tiempo por 2^15 ~ 32 millones para pasar de 7x7 a 8x8.
    – Candid Moe
    el 25 oct. 2022 a las 19:20
  • Y como se puede poner las coordenadas en cualquier punto del tablero y que despues que siga el recorrido el caballo? el 26 oct. 2022 a las 3:39
  • @MartinFlores Si no lo puedes resolver tú mismo ....
    – Candid Moe
    el 26 oct. 2022 a las 7:54

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.