• Explore
• My scripts
• Calculator

def deplacements_valides_cavalier(n : int, pos : tuple):
    ''' entrée : n est la longueur n du côté de l’échiquier
                 pos est la position pos du cavalier
        sortie : la liste des positions suivantes que le cavalier peut occuper.
    '''
    lst_nv_pos = []
    lst_mv = [(1,2),(1,-2),(-1,2),(-1,-2),(2,1),(2,-1),(-2,1),(-2,-1)]
    for mv in lst_mv :
        nv_pos = (pos[0]+mv[0], pos[1]+mv[1])
        if 0<=nv_pos[0]<n and 0<=nv_pos[1]<n : lst_nv_pos.append(nv_pos)
    return lst_nv_pos

def parcours(n : int, pos : tuple, nbp = 1, s = None):
    ''' entrée : n est la longueur n du côté de l’échiquier
                 pos est la position pos du cavalier
                 nbp est le nombre de cases déjà parcourues (valant par défaut 1)
                 s est la matrice des successeurs (valant par défaut None).
        sortie : True et la matrice s complétée si un chemin permettant de passer une unique fois par toutes les cases a été trouvé
                 False et la matrice s incomplète sinon
    '''
    if nbp == n*n : return True, s
    else :
        if nbp == 1 : s=[[None for col in range(n)] for lg in range(n)]
        for dv in deplacements_valides_cavalier(n,pos):
            if s[dv[0]][dv[1]] == None :
                s[pos[0]][pos[1]] = dv
                b, s2 = parcours(n, dv, nbp+1, s)
                if b == True : return b, s2
                else : s[pos[0]][pos[1]] = None
        return False, s

def  affiche_successeurs(pos : tuple, s : list):
    ''' affiche la position du cavalier suivie de sa position suivante (contenue dans la case de s de coordonnées pos), et ainsi de suite jusqu’à ce que la position suivante soit None.
    '''
    print(pos, end=" ")
    suivant = s[pos[0]][pos[1]]
    if not(suivant is None) : affiche_successeurs(suivant, s)

if __name__ == "__main__" :
    print( deplacements_valides_cavalier(6, (4,3)) )
    print( deplacements_valides_cavalier(7, (1,1)) )
    for n in range(2,6) :
        b, s = parcours(n, (0,0))
        if b == True :
            print("Il existe un chemin pour n=", n)
            affiche_successeurs((0,0), s)