# -*- coding: utf-8 -*- ## ## ## Corrigé TP 03-04 - La ronde du cavalier """ On définit ici des alias de type pour simplifier les annotations de type plus bas. """ Case = tuple[int, int] Position = int Chemin = dict[Position] ## ## Quelques outils """ 1) """ DEPLACEMENTS = [(-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1), (-2, -1)] """ 2) """ def est_dans_l_echiquier(case: Case, l: int, h: int) -> bool: x, y = case return (x >= 0 and x < l and y >= 0 and y < h) """ 3) """ def numero(case: Case, l: int) -> Position: x, y = case return l*y + x def coord(position: Position, l: int) -> Case: return (position % l, position // l) """ 4) """ def a_portee_depuis(position: Position, l: int, h: int) -> list[Position]: x, y = coord(position, l) rep = [] for u, v in DEPLACEMENTS: case = x + u, y + v if est_dans_l_echiquier(case, l, h): rep.append(numero(case, l)) return rep """ On peut aussi le faire en une ligne, en utilisant la compréhension de liste avec un filtrage. """ def a_portee_depuis2(position: Position, l: int, h: int) -> list[Position]: x, y = coord(position, l) return [numero((x+u, y+v), l) for u,v in DEPLACEMENTS if est_dans_l_echiquier((x+u, y+v), l, h)] ## ## Recherche récursive """ 5) On utilise un dictionnaire parce que la recherche d'un élément dans un dictionnaire est en moyenne en O(1) alors que la recherche d'un élément dans une liste est en O(n) où n est la longueur de la liste. Or, on va tester à de nombreuses reprises si on est déjà passé à un endroit donné. 6) On peut tester si l'on a parcouru toutes les cases simplement en comparant le nombre de cases atteintes, i.e. la taille du dictionnaire, avec le nombre total de cases de l'échiquier. 7) La hauteur maximale de la pile de récursion sera exactement le nombre de cases $N$ de l'échiquier. La taille totale de la mémoire sera proportionnelle à $1+2+...+N$ donc un $O(N^2)$. 8) """ def existe_ronde(origine: Position, l: int, h: int) -> bool: nb_cases = l*h voisins = [a_portee_depuis(n, l, h) for n in range(nb_cases)] def existe_rec(position: Position, chemin: Chemin) -> bool: n = len(chemin) if n == nb_cases: # On a fini la recherche return True a_portee = voisins[position] for p in a_portee: if p not in chemin: new = existe_rec(p, chemin | {p: n}) if new: return True return False return existe_rec(origine, {origine: 0}) """ Au lieu de stocker le chemin dans une nouvelle variable locale à chaque appel récursif, augmentant d'autant la taille de la pile, on peut avoir une seule variable qui augmente ou diminue. La complexité spatiale passe ainsi de O((lh)^2) à O(lh). """ def existe_ronde2(origine: Position, l: int, h: int) -> bool: nb_cases = l*h voisins = [a_portee_depuis(n, l, h) for n in range(nb_cases)] chemin = {origine: 0} def existe_rec(position: Position) -> bool: n = len(chemin) if n == nb_cases: # On a fini la recherche return True a_portee = voisins[position] for p in a_portee: if p not in chemin: chemin[p] = n # on ajoute la position p au chemin new = existe_rec(p) if new: return True # Cette nouvelle position n'aboutit à rien, # on la supprime du chemin. del chemin[p] return False return existe_rec(origine) """ 9) Il suffit de modifier un tout petit peu l'algorithme précédent. """ def cherche_ronde(origine: Position, l: int, h: int) -> Chemin: nb_cases = l*h voisins = [a_portee_depuis(n, l, h) for n in range(l*h)] def cherche_rec(position: Position, chemin: Chemin) -> Chemin: n = len(chemin) if n == nb_cases: return chemin a_portee = voisins[position] for p in a_portee: if p not in chemin: new = cherche_rec(p, chemin | {p: n}) if new: return new return {} return cherche_rec(origine, {origine: 0}) """ Là encore, on peut utiliser une seule variable locale. """ def cherche_ronde2(origine: Position, l: int, h: int) -> Chemin: nb_cases = l*h voisins = [a_portee_depuis(n, l, h) for n in range(l*h)] chemin = {origine: 0} def cherche_rec(position: Position) -> Chemin: n = len(chemin) if n == nb_cases: return chemin a_portee = voisins[position] for p in a_portee: if p not in chemin: chemin[p] = n new = cherche_rec(p) if new: return new del chemin[p] return {} return cherche_rec(origine) """ 10) Constatez par vous-mêmes. 11) """ def affichage_texte(chemin: Chemin, l: int, h: int) -> None: nb_chiffres = len(str(l*h)) default = "." * nb_chiffres for y in range(h): ligne = "" for x in range(l): rang = default p = numero((x, y), l) if p in chemin: rang = chemin[p] ligne += f"{rang:{nb_chiffres+1}}" print(ligne) print() ## ## L'heuristique de Warnsdorff """ 12) """ def tri(positions: list[Position], chemin: Chemin, voisins: list[list[Position]]) -> list[Position]: """On se contente de ranger chaque numéro de case dans le bac de ceux qui ont le même nombre de voisins non encore atteints que lui. Il suffit ensuite de concaténer ces bacs dans l'ordre.""" bacs = [[] for _ in range(9)] for n in positions: nb = len([p for p in voisins[n] if p not in chemin]) bacs[nb].append(n) return sum(bacs, start=[]) """ 13) """ def cherche_ronde_Warnsdorff(origine: Position, l: int, h: int) -> Chemin: nb_cases = l*h voisins = [a_portee_depuis(n, l, h) for n in range(l*h)] def cherche_rec(position: Position, chemin: Chemin) -> Chemin: n = len(chemin) if n == nb_cases: return chemin a_portee = voisins[position] for p in tri(a_portee, chemin, voisins): if p not in chemin: new = cherche_rec(p, chemin | {p: n}) if new: return new return {} return cherche_rec(origine, {origine: 0}) def cherche_ronde_Warnsdorff2(origine: Position, l: int, h: int) -> Chemin: nb_cases = l*h voisins = [a_portee_depuis(n, l, h) for n in range(l*h)] chemin = {origine: 0} def cherche_rec(position: Position) -> Chemin: n = len(chemin) if n == nb_cases: return chemin a_portee = voisins[position] for p in tri(a_portee, chemin, voisins): if p not in chemin: chemin[p] = n new = cherche_rec(p) if new: return new del chemin[p] return {} return cherche_rec(origine) """ 14) """ def cherche_ronde_fermee(l: int, h: int) -> Chemin: nb_cases = l*h voisins = [a_portee_depuis(n, l, h) for n in range(l*h)] origine = 2 # On choisit par défaut de toujours commencer en position 2 def cherche_rec(position: Position, chemin: Chemin) -> Chemin: n = len(chemin) a_portee = voisins[position] if n == nbcases: if origine in a_portee: return chemin else: return {} for p in tri(a_portee, chemin, voisins): if p not in chemin: new = cherche_rec(p, chemin | {p: n}) if new: return new return {} return cherche_rec(origine, {origine: 0}) ## ## Toujours plus grand """ 15) À chaque sommet, on a au plus 7 possibilités de choisir de le sommet suivant. Le nombre d'opérations effectué en chaque sommet est borné (tri d'une liste d'au plus 7 valeurs) donc le nombre total d'opérations est un O(7^(l*h)). 16) """ def contraintes(l: int, h: int) -> dict[Position]: """Renvoie un dictionnaire qui à chaque position imposée associe une liste des positions qui doivent lui être liées. C'est une liste ayant la plupart du temps un seul élément mais parfois deux lorsque l ou h est inférieur ou égal à 5.""" #On veut s'assurer que les 4 coins aient les bonnes arêtes aretes_imposees = [((0, 1), (2, 0)), ((0, 2), (1, 0)), ((l-2, 0), (l-1, 2)), ((l-3, 0), (l-1, 1)), ((0, h-2), (2, h-1)), ((0, h-3), (1, h-1)), ((l-2, h-1), (l-1, h-3)), ((l-3, h-1), (l-1, h-2))] voisins_imposes = {} for deb, fin in aretes_imposees: n_deb, n_fin = numero(deb, l), numero(fin, l) voisins_imposes[n_deb] = [] voisins_imposes[n_fin] = [] for deb, fin in aretes_imposees: n_deb, n_fin = numero(deb, l), numero(fin, l) voisins_imposes[n_deb].append(n_fin) voisins_imposes[n_fin].append(n_deb) return voisins_imposes def cherche_ronde_fermee_contrainte(l: int, h: int, verb=10**5) -> Chemin: nb_cases = l*h max_search = 200*nb_cases voisins = [a_portee_depuis(n, l, h) for n in range(nb_cases)] contrainte = contraintes(l, h) cherche_ronde_fermee_contrainte.current_backtracks = 0 cherche_ronde_fermee_contrainte.total_backtracks = 0 def tri_depuis_position(positions: list[Position], position : Position) -> list[Position]: bacs = [[] for _ in range(9)] for n in positions: nb = 1 if (n in contrainte and position not in contrainte[n]) else len([p for p in voisins[n] if p not in chemin]) bacs[nb].append(n) return sum(bacs, start=[]) def cherche_rec(position: Position, prev: Position) -> Chemin: if cherche_ronde_fermee_contrainte.current_backtracks > max_search: raise LookupError n = len(chemin) a_portee = voisins[position] if n == nb_cases: if origine in a_portee: return chemin else: return {} if position in contrainte and prev not in contrainte[position]: # le sommet position est une extrémité d'une arête imposée # et le sommet prev n'est pas l'autre extrémité accessibles = contrainte[position] else: accessibles = [p for p in a_portee if p not in chemin] for p in tri_depuis_position(accessibles, position): chemin[p] = n new = cherche_rec(p, prev=position) if new: return new cherche_ronde_fermee_contrainte.current_backtracks += 1 cherche_ronde_fermee_contrainte.total_backtracks += 1 del chemin[p] return {} rep = {} origines = list(range(l*h)) rd.shuffle(origines) i = -1 while not rep: i += 1 try: origine = origines[i] if verb: print(f"J'essaie depuis l'origine : {origine}.") chemin = {origine: 0} rep = cherche_rec(origine, prev=None) except LookupError: if verb: print("Trop d'impasses...") cherche_ronde_fermee_contrainte.current_backtracks = 0 if verb: print("Trouvé !") print(f"Pour trouver une ronde fermée de taille {l}x{h} :") print(f"{cherche_ronde_fermee_contrainte.total_backtracks} impasses au total") print(f"{cherche_ronde_fermee_contrainte.current_backtracks} impasses dans le dernier essai d'exploration") return rep """ 17) """ def to_list(ronde: Chemin) -> list[Position]: n = len(ronde) rep = [-1]*n # -1 est une valeur par défaut for p in ronde: rep[ronde[p]] = p return rep def to_dict(l_parcours: list[Position]) -> Chemin: return {num: ordre for ordre, num in enumerate(l_parcours)} """ 18) """ def change_ordre(l_parcours: list[Position], deb: int, fin: int) -> list[Position]: """Fonction qui prend une liste représentant une ronde fermée et change le point de départ et, si besoin, le sens de parcours, afin que deb soit le premier élément de la liste et fin le dernier. Cela suppose que deb-fin soit une arête de la ronde.""" for i, n in enumerate(l_parcours): if n == deb: if l_parcours[i-1] == fin: # la valeur précédente dans la liste est fin return l_parcours[i:] + l_parcours[:i] elif l_parcours[(i+1) % len(l_parcours)] == fin: # la valeur suivante est fin return l_parcours[i::-1] + l_parcours[-1:i:-1] else: raise LookupError(f"L'arête {deb}-{fin} n'existe pas dans cette ronde") """ On fournit ici des solutions, c'est-à-dire des rondes fermées, pour les échiquiers $6\times 6$, $8 \times 5$ et $10 \times 10$. Cela permet notamment d'initialiser notre dictionnaire de mémoïsation plus bas. """ SOL6_6 = to_dict([33, 29, 16, 5, 9, 1, 12, 25, 14, 6, 2, 10, 23, 34, 21, 17, 4, 8, 0, 13, 24, 32, 28, 20, 31, 18, 7, 3, 11, 15, 26, 30, 19, 27, 35, 22]) SOL8_5 = to_dict([2, 8, 25, 35, 29, 39, 22, 7, 13, 3, 9, 24, 34, 19, 4, 14, 31, 37, 20, 5, 15, 30, 36, 26, 32, 17, 0, 10, 27, 33, 16, 1, 18, 28, 11, 21, 38, 23, 6, 12]) SOL10_10 = to_dict([2, 10, 31, 50, 71, 90, 82, 70, 91, 83, 95, 87, 99, 78, 97, 89, 68, 49, 28, 9, 17, 5, 13, 1, 20, 12, 0, 21, 40, 61, 80, 92, 84, 96, 88, 76, 57, 69, 77, 98, 79, 58, 39, 18, 6, 14, 22, 30, 11, 3, 24, 32, 51, 72, 60, 41, 62, 81, 93, 85, 73, 94, 86, 74, 53, 65, 44, 52, 33, 25, 4, 16, 8, 29, 37, 45, 64, 43, 35, 56, 75, 63, 42, 54, 66, 47, 59, 67, 55, 36, 48, 27, 46, 34, 26, 38, 19, 7, 15, 23]) """ On définit un alias représentant un couple de dimension d'échiquier et on importe la bibliothèque |{random}| pour pouvoir choisir aléatoirement une position d'origine lors de la recherche de rondes fermées de petite taille. """ Dim = tuple[int, int] import random as rd """ Enfin, la dernière fonction cherche une grande ronde fermée en utilisant un dictionnaire de mémoïsation pour éviter d'avoir à chercher deux fois des plus petites rondes de même taille. """ def cherche_grande_ronde_fermee(l: int, h: int, memo: dict[Dim]=None, verb=0) -> Chemin: if memo is None: #s'il n'y a pas encore de dictionnaire de mémoïsation #on l'initialise avec quelques solutions memo = {}#(6,6): SOL6_6, (8, 5): SOL8_5, (10,10): SOL10_10} if l%2 == 1 and h%2 == 1: if verb: print("Il n'existe pas de ronde fermée sur un échiquier dont les deux dimensions sont impaires.") return {} # Aucun espoir de trouver une ronde fermée if (l, h) in memo: #si les dimensions sont mémoïsées, #on renvoie directement la ronde correspondante if verb: print(f"Je connais déjà une ronde fermée de taille {l}x{h}.") return memo[(l, h)] elif (h, l) in memo: #si les dimensions transposées sont mémoïsées #on fabrique une ronde en transposant la ronde existante if verb: print(f"Je transpose une ronde fermée connue de taille {h}x{l}.") ronde_t = memo[(h, l)] ronde = {} for p in ronde_t: (u, v) = coord(p, h) ronde[numero((v, u), l)] = ronde_t[p] elif l < 12 or h < 12: #on cherche une 'petite' ronde fermée avec contraintes #qui n'est pas encore dans le dictionnaire de mémoïsation if verb: print(f"Je cherche une ronde fermée de taille {l}x{h}.") ronde = cherche_ronde_fermee_contrainte(l, h, verb=verb) else: if verb: print(f"Je fabrique une ronde fermée de taille {l}x{h}.") #on coupe la largeur et la hauteur en 2 lg, hh = l//2, h//2 if lg % 2 == 1: lg += 1 # on s'assure que lg est pair if hh % 2 == 1: hh += 1 # on s'assure que hh est pair ld = l - lg hb = h - hh #On calcule des rondes pour chacun des 4 sous-rectangles #et on les transforme en listes l_ronde_hg = to_list(cherche_grande_ronde_fermee(lg, hh, memo, verb=verb)) l_ronde_hd = to_list(cherche_grande_ronde_fermee(ld, hh, memo, verb=verb)) l_ronde_bd = to_list(cherche_grande_ronde_fermee(ld, hb, memo, verb=verb)) l_ronde_bg = to_list(cherche_grande_ronde_fermee(lg, hb, memo, verb=verb)) #On change l'ordre des 4 listes pour que dans chacune d'elles # l'arête à faire disparaître soit celle qui relie le numéro # du début de la liste et le numéro de la fin l_ronde_hg = change_ordre(l_ronde_hg, numero((lg-3, hh-1), lg), numero((lg-1, hh-2), lg)) l_ronde_hd = change_ordre(l_ronde_hd, numero((1, hh-3), ld), numero((0, hh-1), ld)) l_ronde_bd = change_ordre(l_ronde_bd, numero((2, 0), ld), numero((0, 1), ld)) l_ronde_bg = change_ordre(l_ronde_bg, numero((lg-2, 2), lg), numero((lg-1, 0), lg)) #on recalcule les coordonnées puis les numéros des cases #des quatre sous-rondes pour qu'ils correspondent au grand rectangle #et on concatène le tout dans le bon ordre l_total = [numero(coord(n, lg), l) for n in l_ronde_hg] for n in l_ronde_hd: x, y = coord(n, ld) l_total.append(numero((x + lg, y), l)) for n in l_ronde_bd: x, y = coord(n, ld) l_total.append(numero((x + lg, y + hh), l)) for n in l_ronde_bg: x, y = coord(n, lg) l_total.append(numero((x, y + hh), l)) #enfin on reconvertit la liste en chemin ronde = to_dict(l_total) #on enregistre la ronde trouvée dans le dictionnaire de mémoïsation memo[(l, h)] = ronde #et on la renvoie return ronde ## Bonus : affichage graphique """Utilisable seulement après avoir réussi les questions 3 et 17""" import matplotlib.pyplot as plt def graphique(parcours, l, h): l_parcours = to_list(parcours) x, y = [], [] for n in l_parcours: u, v = coord(n, l) x.append(u + .5) y.append(v + .5) fig = plt.figure() fig.set_layout_engine('tight') plot1 = fig.gca() plot1.plot(x + x[:1], y + y[:1], color='red', marker='o') plot1.set_title(f"Ronde sur un échiquier {l}x{h}") plot1.set_xticks(range(l+1)) plot1.set_yticks(range(h+1)) plot1.invert_yaxis() plot1.grid(visible=True, which='both') plt.show() def affiche_grande_ronde_fermee(l, h, verb=0): graphique(cherche_grande_ronde_fermee(l, h, verb=verb), l, h)