re-jeu Ricosheep (problème de solveur) Fermé

Question

Bonjour, 

Je dois faire un solveur qui doit déterminer s’il est possible.

De gagner à partir d’un état du jeu donné. En cas de réponse positive, le solveur doit aussi fournir.

Une solution à la grille, c’est-à-dire une liste des coups à jouer pour arriver à la victoire.

Et voici l'algorithme que l'on m'a donné (qui ressemble à l'algorithme de recherche en profondeur):



Si l’état du jeu est actuellement gagné, répondre [] : il n’y a rien à faire de plus.



2. Si l’état du jeu est déjà dans visite, répondre None. Cet état a déjà été considéré, on interrompt la recherche.



3. Sinon, on commence par ajouter l’état du jeu dans visite. Puis pour chaque direction dans ['Left', 'Right', 'Up', 'Down'] :



• On calcule l’état atteint en jouant direction.

• On lance la recherche récursivement à partir de cet état.

• Si la recherche renvoie une solution S, on renvoie [direction] + S.

• Sinon, on annule le coup joué et on passe à la direction suivante.



4. Si aucune direction ne permet d’arriver à une solution, on déduit qu’il n’y a pas de solution à partir de l’état donné, et on renvoie None. Je ne sais pas où sont mes erreurs pouvez-vous m'aider s'il vous plaît.

Je vous remercie d'avance.

def solveur(plateau,moutons,visite,nombre_herbe):
    """
    Le rôle du solveur est de déterminer s’il est possible
    de gagner à partir d’un état du jeu donné. En cas de réponse positive, le solveur doit aussi fournir
    une solution à la grille, c’est-à-dire une liste des coups à jouer pour arriver à la victoire.
    param: plateau : list
    param: moutons : list de tuple
    param: visite : dico
    """
    moutons_tuples = moutons[0]
    if victoire(plateau,moutons,nombre_herbe) :
        return []
    if moutons_tuples in visite :
        if plateau == visite[moutons_tuples] :
            return None
    else :
        visite[moutons_tuples] = plateau
        if solveur(jouer(plateau,moutons,'Left'),moutons,nombre_herbe,visite) == [] :
            return ['Left'] + solveur(jouer(plateau,moutons,'Left'),moutons[1:],nombre_herbe,visite)
        if solveur(jouer(plateau,moutons,'Right'),moutons,nombre_herbe,visite) == [] :
            return ['Right'] + solveur(jouer(plateau,moutons,'Right'),moutons[1:],nombre_herbe,visite)
        if solveur(jouer(plateau,moutons,'Up'),moutons,nombre_herbe,visite) == [] :
            return ['Up'] + solveur(jouer(plateau,moutons,'Up'),moutons[1:],nombre_herbe,visite)
        if solveur(jouer(plateau,moutons,'Down'),moutons,nombre_herbe,visite) == [] :
            return ['Down'] + solveur(jouer(plateau,moutons,'Down'),moutons,nombre_herbe,visite)
        return None
Configuration: Windows / Chrome 100.0.4896.127

yg_be · Answer

bonjour,
as-tu une question?  j'ai l'impression que tu as recopié l'énoncé de ton exercice.
https://www.commentcamarche.net/infos/25899-demander-de-l-aide-pour-vos-exercices-sur-ccm/

Ak_j · Answer

Ok, oui bien sur. j'aimerais comprendre pourquoi ça ne marche pas car  je voudrais enregistrer les déplacements des moutons dans un dictionnaire, mais le problème, c'est que c'est une liste de tuple du coup, ça ne me facile pas la tâche.



Et j'aimerais avoir quelques idées ou conseils (peu importe ) pour améliorer ma fonction pour quel soit optimal.

Ak_j · Answer

c'est visite

Ak_j · Answer

oui car quand j'appelle la fonction j'initialise visite en un dictionnaire vide

Ak_j · Answer

Désolé, je rectifie, je n'ai pas partagé le code complet parce qu'il est trop long , du coup non j'ai partagé l'appel.

Ak_j · Answer

Pardon , je vais te montrer avec les rectifications que j'ai pu apporter. Mais il me renvoie toujours une erreur, voici ce qui est marqué sur le terminal. : if moutons_tuples in visite : TypeError: unhashable type: 'list' def init_plateau(plateau): plateau_jeu = [] tmp = [] for i in range(len(plateau)): tmp = [] for j in range(len(plateau)): tmp.append(plateau[i][j]) plateau_jeu.append(tmp) return(plateau_jeu) def premiere_case_vide(plateau,pos,i): ''' Retourne la 1ere case adjacente à 'pos' vide''' liste_dir = [[0,1],[0,-1],[1,0],[-1,0]] case_vide = [pos[0],pos[1]] case = plateau[pos[0]+liste_dir[i][0]][pos[1]+liste_dir[i][1]] if(case == None) or (case == 'G'): case_vide = [pos[0]+liste_dir[i][0],pos[1]+liste_dir[i][1]] return(case_vide) def jouer(plateau,moutons,direction): plateau_jeu = init_plateau(plateau) droite = len(moutons) - 1 gauche = 0 bas = len(moutons) - 1 haut = 0 compteur_droite = moutons[droite][1] compteur_gauche = moutons[gauche][1] compteur_haut = moutons[haut][0] compteur_bas = moutons[bas][0] if (direction == 'Right') : while droite >= 0 : if compteur_droite == len(plateau[0])-1 : plateau_jeu[moutons[droite][0]][moutons[droite][1]] = 'S' droite -= 1 compteur_droite = moutons[droite][1] if droite >= 0 and compteur_droite < len(plateau)-1 : moutons[droite] = premiere_case_vide(plateau_jeu,moutons[droite],0) compteur_droite += 1 if (direction == 'Left') : while gauche <= len(moutons) - 1: if compteur_gauche > 0: moutons[gauche] = premiere_case_vide(plateau_jeu,moutons[gauche],1) compteur_gauche -= 1 else: plateau_jeu[moutons[gauche][0]][moutons[gauche][1]] ='S' gauche += 1 if gauche < len(moutons): compteur_gauche = moutons[gauche][1] if (direction == 'Down') : while bas >= 0: if compteur_bas == len(plateau[0])-1: plateau_jeu[moutons[bas][0]][moutons[bas][1]] = 'S' bas -= 1 compteur_bas = moutons[bas][0] if bas >= 0 and compteur_bas < len(plateau)-1 : moutons[bas] = premiere_case_vide(plateau_jeu,moutons[bas],2) compteur_bas += 1 if (direction == 'Up'): while haut <= len(moutons) - 1: if compteur_haut > 0 : moutons[haut] = premiere_case_vide(plateau_jeu,moutons[haut],3) compteur_haut -= 1 else: plateau_jeu[moutons[haut][0]][moutons[haut][1]] ='S' haut += 1 if haut < len(moutons): compteur_haut = moutons[haut][0] return moutons def victoire(plateau,moutons,nombre_herbe): """ la victoire sera détectée par une fonction victoire(plateau, moutons) renvoyant True si la partie est actuellement gagnée (chaque touffe d’herbe est couverte par un mouton) et False sinon. param: plateau : list param: moutons : list de tuple return boolean """ moutons_sur_herbe = [] for ligne in range(len(plateau)): for colonne in range(len(plateau)): for mouton_actuel in moutons : if ligne == mouton_actuel[0] and colonne == mouton_actuel[1] : if plateau[ligne][colonne] == 'G' : moutons_sur_herbe.append('présent') if len(moutons_sur_herbe) == nombre_herbe : return True return False def solveur(plateau,moutons,visite,nombre_herbe): """ Le rôle du solveur est de déterminer s’il est possible de gagner à partir d’un état du jeu donné. En cas de réponse positive, le solveur doit aussi fournir une solution à la grille, c’est-à-dire une liste des coups à jouer pour arriver à la victoire. param: plateau : list param: moutons : list de tuple param: visite : dico """ moutons_tuples = moutons[0] if victoire(plateau,moutons,nombre_herbe) : return [] if moutons_tuples in visite : if plateau == visite[moutons_tuples] : return None else : print(visite) visite[moutons_tuples] = plateau if solveur(plateau,jouer(plateau,moutons,'Left'),nombre_herbe,visite) != [] : return ['Left'] + solveur(plateau,jouer(plateau,moutons,'Left'),visite,nombre_herbe) if solveur(plateau,jouer(plateau,moutons,'Left'),nombre_herbe,visite) == [] : return solveur(plateau,jouer(plateau,moutons,'Left'),visite,nombre_herbe) if solveur(plateau,jouer(plateau,moutons,'Right'),nombre_herbe,visite) != [] : return ['Right'] + solveur(plateau,jouer(plateau,moutons,'Right'),visite,nombre_herbe) if solveur(plateau,jouer(plateau,moutons,'Right'),nombre_herbe,visite) == [] : return solveur(plateau,jouer(plateau,moutons,'Right'),visite,nombre_herbe) if solveur(plateau,jouer(plateau,moutons,'Up'),nombre_herbe,visite) != [] : return ['Up'] + solveur(plateau,jouer(plateau,moutons,'Up'),visite,nombre_herbe) if solveur(plateau,jouer(plateau,moutons,'Up'),nombre_herbe,visite) == [] : return solveur(plateau,jouer(plateau,moutons,'Up'),visite,nombre_herbe) if solveur(plateau,jouer(plateau,moutons,'Down'),visite,nombre_herbe) == [] : return solveur(plateau,jouer(plateau,moutons,'Down'),visite,nombre_herbe) if solveur(plateau,jouer(plateau,moutons,'Down'),visite,nombre_herbe) != [] : return ['Down'] + solveur(plateau,jouer(plateau,moutons,'Down'),visite,nombre_herbe) return None plateau =[[None, 'B', None, 'B', None], ['B', 'B', None, None, None], [None, 'G', 'B', 'B', None], [None, 'B', 'G', None, None], [None, None, None, 'B', None]] moutons = [(2,4), (1,3),(0,4),(4,4)] >>> solveur(plateau,moutons,{},2) #je cherche à obtenir ça comme résultat ['Down', 'Left', 'Down', 'Left', 'Down', 'Left', 'Right', 'Left', 'Up', 'Right', 'Up'] c'est la liste de direction qui me permettra de gagné.

yg_be · Answer

Rien à voir, je pense, avec tes erreurs, et je pense préférable, au lieu de:
if solveur(plateau,jouer(plateau,moutons,'Left'),visite,nombre_herbe) != [] :
            return ['Left'] + solveur(plateau,jouer(plateau,moutons,'Left'),visite,nombre_herbe)
de faire
sol = solveur(plateau,jouer(plateau,moutons,'Left'),visite,nombre_herbe)
if sol != [] :
            return ['Left'] + sol

Ak_j · Answer

J’ai encore corrigé mon code. visite n’est plus un dictionnaire, mais un ensemble, j’ai rajouté liste_direction dans le paramètre de la fonction (elle contient toutes les directions.) et j’ai enlevé les lignes inutiles maintenant, j’ai un souci ???? J’obtiens cette erreur (à cause de la ligne 21) : if moutons_tuples in visite : TypeError: argument of type 'int' is not iterable

def solveur(moutons,plateau,visite,nombre_herbe,liste_direction):
    """
    Le rôle du solveur est de déterminer s’il est possible
    de gagner à partir d’un état du jeu donné. En cas de réponse positive, le solveur doit aussi fournir
    une solution à la grille, c’est-à-dire une liste des coups à jouer pour arriver à la victoire.
    param: plateau : list
    param: liste_direction : list
    param: moutons : list de tuple
    param: visite : set 
    """
    moutons_tuples = tuple(moutons)
    if victoire(plateau,moutons,nombre_herbe) :
        return []
    if moutons_tuples in visite :
        if plateau == visite[moutons_tuples]:
            return None
    else :
        
        visite.add(moutons_tuples)
        dir = liste_direction[0]
        sol = solveur(jouer(plateau,moutons,dir),plateau,nombre_herbe,visite,liste_direction)
        print('valeur :' , sol)
    
        if sol != [] and dir == 'Left':
            return ['Left'] + sol
        
        if sol != [] and dir == 'Right':
            return ['Right'] + sol
        
        if sol != [] and dir == 'Up':
            return ['Up'] + sol
        if sol != [] and dir == 'Down':
            return ['Down'] + sol
        else : 
            return solveur(jouer(plateau,moutons,dir),plateau,nombre_herbe,visite,liste_direction[1:])

Ak_j · Answer

j'ai réussi à corriger le problème mais j'ai un autre souci, mon code renvoie qu' une seule direction accompagnée d'un None comment corrigé ça ???

def solveur(moutons,plateau,visite,nombre_herbe,liste_direction):
    """
    Le rôle du solveur est de déterminer s’il est possible
    de gagner à partir d’un état du jeu donné. En cas de réponse positive, le solveur doit aussi fournir
    une solution à la grille, c’est-à-dire une liste des coups à jouer pour arriver à la victoire.
    param: plateau : list
    param: liste_direction : list
    param: moutons : list de tuple
    param: visite : set 
    """
    plateau,plateau_jeu = init_plateau(plateau)
    plateau_jeu = tuple(plateau_jeu)
    moutons_tuples = tuple(moutons)
    if victoire(plateau,moutons,nombre_herbe) :
        return []

if moutons_tuples in visite :
            if plateau_jeu in visite:
                return None   
                
    else :
        
        visite.add(tuple(plateau_jeu))
        visite.add(moutons_tuples)
        dir = tuple(liste_direction[0])
        sol = solveur(jouer(plateau_jeu,moutons,dir),
            plateau_jeu,visite,nombre_herbe,liste_direction)

if sol != [] and dir[0] == 'L':
            return ['Left'] + [sol]
        
        if sol != [] and dir[0] == 'R':
            return ['Right'] + [sol]
        
        if sol != [] and dir[0] == 'U':
            return ['Up'] + [sol]

if sol != [] and dir[0] == 'D':
            return ['Down'] + [sol]
        else : 
            return solveur(moutons,plateau_jeu,visite,
            nombre_herbe,liste_direction[1:])

Ak_j · Answer

je te redonne une version qui marche from copy import * def init_plateau(plateau): plateau_jeu = [] plateau_tmp = [] tmp = [] for i in range(len(plateau)): tmp = [] for j in range(len(plateau)): tmp.append(plateau[i][j]) plateau_tmp.append(tuple(tmp)) plateau_jeu.append(tmp) return(plateau_jeu,plateau_tmp) def premiere_case_vide(plateau,pos,i): ''' Retourne la 1ere case adjacente à 'pos' vide''' liste_dir = [[0,1],[0,-1],[1,0],[-1,0]] case_vide = [pos[0],pos[1]] case = plateau[pos[0]+liste_dir[i][0]][pos[1]+liste_dir[i][1]] if(case == None) or (case == 'G'): case_vide = [pos[0]+liste_dir[i][0],pos[1]+liste_dir[i][1]] return(case_vide) def jouer(plateau,moutons,direction): """ recevant en paramètre l’état du jeu et une direction représentée par la chaine 'Left', 'Right', 'Up' ou 'Down'. La fonction ne renvoie rien et met directement à jour les positions des moutons dans la liste moutons en respectant les règles du jeu. param: plateau : list param: moutons : list de tuple param: direction : string """ plateau_jeu,plateau_tmp = init_plateau(plateau) droite = len(moutons) - 1 gauche = 0 bas = len(moutons) - 1 haut = 0 memoire = set() compteur_droite = moutons[droite][1] compteur_gauche = moutons[gauche][1] compteur_haut = moutons[haut][0] compteur_bas = moutons[bas][0] if (direction == 'Right') : while droite >= 0 : if compteur_droite == len(plateau[0])-1 : x,y = moutons[droite][0] , moutons[droite][1] if (x,y) in memoire: moutons[droite] = x , y - 1 mout = x , y - 1 memoire.add(mout) if (x,y) not in memoire: mout = x , y memoire.add(mout) plateau_jeu[moutons[droite][0]][moutons[droite][1]] = 'S' droite -= 1 compteur_droite = moutons[droite][1] if droite >= 0 and compteur_droite < len(plateau)-1 : moutons[droite] = premiere_case_vide(plateau_jeu,moutons[droite],0) compteur_droite += 1 if (direction == 'Left') : while gauche <= len(moutons) - 1: if compteur_gauche > 0: moutons[gauche] = premiere_case_vide(plateau_jeu,moutons[gauche],1) compteur_gauche -= 1 else: x,y = moutons[gauche][0] , moutons[gauche][1] if (x,y) in memoire: moutons[gauche] = x , y + 1 mout = x , y + 1 memoire.add(mout) if (x,y) not in memoire: mout = x , y memoire.add(mout) plateau_jeu[moutons[gauche][0]][moutons[gauche][1]] ='S' gauche += 1 if gauche < len(moutons): compteur_gauche = moutons[gauche][1] if (direction == 'Down') : while bas >= 0: if compteur_bas == len(plateau[0])-1: x,y = moutons[bas][0] , moutons[bas][1] if (x,y) in memoire: moutons[bas] = x - 1 , y mout = x - 1 , y memoire.add(mout) if (x,y) not in memoire: mout = x , y memoire.add(mout) plateau_jeu[moutons[bas][0]][moutons[bas][1]] = 'S' bas -= 1 compteur_bas = moutons[bas][0] if bas >= 0 and compteur_bas < len(plateau)-1 : moutons[bas] = premiere_case_vide(plateau_jeu,moutons[bas],2) compteur_bas += 1 if (direction == 'Up'): while haut <= len(moutons) - 1: if compteur_haut > 0 : moutons[haut] = premiere_case_vide(plateau_jeu,moutons[haut],3) compteur_haut -= 1 else: x,y = moutons[haut][0] , moutons[haut][1] if (x,y) in memoire: moutons[haut] = x + 1 , y mout = x + 1 , y memoire.add(mout) if (x,y) not in memoire: mout = x, y memoire.add(mout) plateau_jeu[moutons[haut][0]][moutons[haut][1]] ='S' haut += 1 if haut < len(moutons): compteur_haut = moutons[haut][0] return moutons def victoire(plateau,moutons,nombre_herbe): """ la victoire sera détectée par une fonction victoire(plateau, moutons) renvoyant True si la partie est actuellement gagnée (chaque touffe d’herbe est couverte par un mouton) et False sinon. param: plateau : list param: moutons : list de tuple return boolean """ moutons_sur_herbe = [] for ligne in range(len(plateau)): for colonne in range(len(plateau)): for mouton_actuel in moutons : if ligne == mouton_actuel[0] and colonne == mouton_actuel[1] : if plateau[ligne][colonne] == 'G' : moutons_sur_herbe.append('présent') if len(moutons_sur_herbe) == nombre_herbe : return True return False def solveur(moutons,plateau,visite,nombre_herbe,liste_direction): """ Le rôle du solveur est de déterminer s’il est possible de gagner à partir d’un état du jeu donné. En cas de réponse positive, le solveur doit aussi fournir une solution à la grille, c’est-à-dire une liste des coups à jouer pour arriver à la victoire. param: plateau : list param: liste_direction : list param: moutons : list de tuple param: visite : set """ plateau,plateau_jeu = init_plateau(plateau) plateau_jeu = tuple(plateau_jeu) moutons_tuples = tuple(moutons) if victoire(plateau,moutons,nombre_herbe) : return [] if moutons_tuples in visite : if plateau_jeu in visite: return None else : visite.add(tuple(plateau_jeu)) visite.add(moutons_tuples) dir = tuple(liste_direction[0]) sol = solveur(jouer(plateau_jeu,moutons,dir[0]), plateau_jeu,visite,nombre_herbe,liste_direction) if sol != [] and dir[0] == 'L': return ['Left'] + [sol] if sol != [] and dir[0] == 'R': return ['Right'] + [sol] if sol != [] and dir[0] == 'U': return ['Up'] + [sol] if sol != [] and dir[0] == 'D': return ['Down'] + [sol] else : return solveur(moutons,plateau_jeu,visite, nombre_herbe,liste_direction[1:]) plateau = [[None, 'B' , None, 'B' , None], ['B' , 'B' , None, None, None], [None, 'G' , 'B' , 'B' , None], [None, 'B' , 'G' , None, None], [None, None, None, None , None]] moutons = [(2,4), (1,3),(0,4),(4,4)] print(solveur(moutons,plateau,set(),2,['Left','Right','Up','Down']))

Ak_j · Answer

Oui tu as peut être raison tu peux m'aider s'il te plaît

Ak_j · Answer

Oui tu as peut-être  raison tu pourrais m'aider s'il te plaît

Re-jeu Ricosheep (problème de solveur)

12 réponses