Hola a todos, se trata de resolver el problema de, dado un tablero de ajedrez de 5x5, pisar todas las casillas con un caballo (sin pisar la misma casilla 2+ veces)
Estoy intentando averiguar por qué este código no funciona
def nextMovement(posActual, movedores, iter):
""" Devuelve el siguiente movimiento a realizar
posActual: vector de 2 comp. (coords x e y) ==> posicion actual del caballo
movedores: matriz de 2x8 que indica los posibles movimientos que se pueden hacer con el caballo
iter: número que indica que movedor aplicar
"""
casilla = [None] * 2
casilla[0] = posActual[0] + movedores[0][iter]
casilla[1] = posActual[1] + movedores[1][iter]
return casilla
def casillaAdmisible(tablero, casilla):
x=casilla[0]
y=casilla[1]
tam=len(tablero)
if(x>=tam or y>=tam or x<0 or y<0 or tablero[x][y]!=0):
return False
return True
def mover(casilla, tablero, etapa):
tablero[ casilla[0] ][ casilla[1] ] = etapa
def anularMovimiento(casilla, tablero):
tablero[ casilla[0] ][ casilla[1] ] = 0
def backTrackingChessHorse(tablero, posActual, etapa, movedores):
exito = False
for i in range(len(movedores[0])):
if(exito):
break
casilla = nextMovement(posActual, movedores, i)
if not casillaAdmisible(tablero, casilla):
continue
aux=posActual
mover(casilla, tablero, etapa)
posActual=casilla
if(etapa == len(tablero)**2):
exito = True
else:
exito = backTrackingChessHorse(tablero, posActual, etapa + 1, movedores)
if(not exito):
anularMovimiento(casilla, tablero)
posActual=aux
return exito
def printTablero(tablero):
for i in range(len(tablero)):
print(tablero[i])
Problema: se consigue llegar a la etapa 25 (la última), pero nunca devuelve True, entre en bucle infinito.
No veo el error, ¿alguien puede ayudarme?