Résoudre un labyrinthe en PYTHON récursif

Question

Bonjour, Dans le cadre d'un projet universitaire je suis amené à écrire un programme qui est censé trouver le chemin d'un labyrinthe parfait (à partir d'une liste de liste : 0 représente un mur, 2 l'entrée et 3 la sortie) c'est à dire qu'il n'y a que un chemin et aucune impasse. Je voulu pousser la chose plus loin en essayant pour tous types de labyrinthes. Le problème semble après plusieurs essais de "débuguages" le retour de la liste (chemin) en récursif. Disclaimer, j'ai un niveau débutant en python et je me doute que mon code n'est pas le plus efficient: Voici le code de la fonction qui est censé résoudre le problème : def solution(location:tuple,lst:list,laby:list): lst.append(location) voisin = voisin_lab_cal(location,laby) # ~ print(location,lst) voisin_copy =list(voisin)#copy de la liste, une sert à parcourir les éléments et l'autre à mettre a jour/supprimer ceux deja effectuer n=-1 #conteur, office d'indice, pour supprimer si une cellule est deja dans la liste (evite les retours en arrière) for e in voisin: n += 1 if e in lst: del voisin_copy[n] n=n-1 #enlève un a "l'indce" car un élément à été retirer de la liste # ~ print(voisin_copy) if len(voisin_copy) == 1: #une seule case voisine donc soit sortie soit suite du chemin v1 = voisin_copy[0] #change en tuple # ~ print(v1) if laby[v1[0]][v1[1]] == 1: return solution(v1,lst,laby) elif laby[v1[0]][v1[1]] == 3: lst.append(v1) # ~ print(lst) return lst else : return 103 #le seul voisin n'est pas la fin du lab donc mauvais chemin elif len(voisin_copy) == 2 : #situation de debut si deux chemin sont possible v1,v2 = voisin_copy[0], voisin_copy[1] #sépare les deux tuples # ~ print (v1,v2) lst_chemin_1 = list(lst) #copie indépendante de la liste lst_chemin_2 = list(lst) #copie indépendante de la liste chemin_1 = solution(v1,lst_chemin_1,laby) #dans chaque chemin vaut une liste et si ce dernier element correspond à un 3 c'est le chemin à suivre chemin_2 = solution(v2,lst_chemin_2,laby) #pas pratique niveaux calcul mais plus simple pour trouver des potentiels bug # ~ print("retour recursif") # ~ print(chemin_1," ",chemin_2) if type(chemin_1) == list: # ~ print("ici") end1 = chemin_1[-1] # ~ print(end1) if laby[end1[0]][end1[1]] == 3: #test si le dernier élément vaut 3 ce qui serait la fin du lab # ~ print("la") return lst_chemin_1 elif type(chemin_2) == list: end2 = chemin_2[-1] if laby[end2[0]][end2[1]] == 3: return lst_chemin_2 else : return 111 #return normalement pas utilisé car un des deux chemins doit être la solution # on ne traite pas le cas ou il y a trois chemin possible else : return 102 def resout_lab(labyrinthe): #fonction wrapper, test si entrée et sortie et retourne liste du chemin à faire e = entre(labyrinthe) s = sortie(labyrinthe) if e != None and s != None : return solution(e,[],labyrinthe) else : return 101 J'ai essayé de mettre des indications pour vous aider à la compréhension et les print me servent pour comprendre par ou l'algorithme passe et ce qu'il risque de renvoyer; En testant sur ce labyrinthe : lab1 =[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 2, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0], [0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0], [0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0], [0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0], [0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0], [0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0], [0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0], [0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0], [0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 3, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]] le print(location,list) puis plus loin le print(voisin) lors de l'exécution m'indique qu'il arrive jusqu'à la case voisine de la sortie rentre dans la boucle de retour mais ne semble rien en faire par après ! PS : Voici le code qui me sert à trouver les voisins d'une "case" ef voisin_lab_cal(t:tuple,lst:list): # retourne les voisins d'une location dans une liste de liste (pour labyrinthe) lgn = t[1] cln = t[0] vg= (cln-1,lgn) vd= (cln+1,lgn) vh= (cln,lgn-1) vb= (cln,lgn+1) l=[] if cln < 0 or lgn < 0 or cln > len(lst) or lgn > len(lst[0]): return 0 if cln > 0 and ((lst[cln-1][lgn] == 1) or (lst[cln-1][lgn] == 3)): l += [vg] if cln < len(lst) and ((lst[cln+1][lgn] == 1) or (lst[cln+1][lgn] == 3)): l += [vd] if lgn > 0 and ((lst[cln][lgn-1] == 1) or (lst[cln][lgn-1] == 3)): l += [vh] if lgn < len(lst[0]) and ((lst[cln][lgn+1] == 1) or (lst[cln][lgn+1] == 3)): l += [vb] return l Si quelqu'un saurait m'aider de n'importe quel sorte cela serait avec plaisir surtout que en déplaçant l'entré le code marche des fois ! Merci d'avance à tous ceux qui ont pris le temps de lire.

hbouia · Answer

Bonjour,

- Une idée est de travailler avec une liste aplatissant ta matrice (labyrinthe de départ de dimension (nlig, ncol)).

- Une case (i, j) portera le numéro n = ncol * i + j.

- Une case de numéro n a pour coordonnées (i, j) = divmod(n, ncol).

- Tu peux calculer (une fois pour toutes) pour chaque case non nulle les numéros des cases voisines non nulles.

- Après tu peux t'inspirer de la structure définie ci-dessus (à toi de la compléter par ce qui manque).

# Solveur du labyrinthe (défin par une matrice contenant des 0 (mur), 1 (porte), 2 (Entrée du labyrinthe) et 3 (Sortie du labyrinthe))
def solveur(labyrinthe):
    # Transformer la matrice en une liste lab1D (une dimension) avec l'ordre de numérotation indiqué ci-dessus
    lab1D = list(labyrinthe.flatten())
    
    # Dimensions du labyrinthe (Taille de la matrice)
    nlig, ncol = labyrinthe.shape
    
    # Calcul des voisins autorisés
    vois = voisins(lab1D, nlig, ncol)
    
    # Rang de l'entrée dans lab1D    
    rang_E = lab1D.index(2)
    
    # Initialisation des solutions (chemins possibles de E (Entrée valeur 2) vers S (Sortie valeur 3))
    chemin = [rang_E]
    solutions = []
    
    def _solveur(chemin, solutions):
        last = chemin[-1]
        if lab1D[last] == 3: 
            solutions.append(chemin)
            return True
        else:
            for n in vois[last]:
                if n in chemin:
                    continue
                if _solveur(chemin + [n], solutions):
                    return True
            return False
        
    status = _solveur(chemin, solutions)
    return status

Le résultat pourrait ressembler à ça :

Résoudre un labyrinthe en PYTHON récursif

1 réponse

Votre réponse

Discussions similaires