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