Re-jeu Ricosheep (problème de solveur)

Ak_j -  
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

12 réponses

  2. Ak_j Auteur
    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.
    0
    1. yg_be Contributeur
      Quelle variable devrait être un dictionnaire?
      0
  3. Ak_j Auteur
    c'est visite
    0
    1. yg_be Contributeur
      as-tu partagé ton code complet?
      je n'y vois pas la création de 
      visite
      .
      0
  4. Ak_j Auteur
    oui car quand j'appelle la fonction j'initialise visite en un dictionnaire vide
    0
    1. yg_be Contributeur
      as-tu partagé le code avec cet appel?
      0
  6. Ak_j Auteur
    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.
    0
    1. yg_be Contributeur
      Difficile de t'aider à corriger un code que tu ne montres pas.
      0
  7. Ak_j Auteur
    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é.
    0
    1. yg_be Contributeur
      Je crois que tu te prends les pieds dans l'ordre des paramètres à ta fonction solveur.
      Fais print() des paramètres à l'entrée de la fonction.
      0
  8. yg_be Contributeur
    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
    0
    1. Ak_j Auteur
      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:])
      0
      1. yg_be Contributeur
        Je crois que tu te prends les pieds dans l'ordre des paramètres à ta fonction solveur().
        Fais print() des paramètres à l'entrée de la fonction.
        0
    2. Ak_j Auteur
      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:])
      0
      1. yg_be Contributeur
        J'ai inséré ton code en #15 dans ton code en #10, cela ne tourne pas.
        Difficile de t'aider à corriger un code que tu ne montres pas.
        0
    3. Ak_j Auteur
      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']))
      0
      1. yg_be Contributeur
        Je te laisse progresser sur l'autre forum où, sans nous prévenir, tu as posé la même question.
        1
    4. Ak_j Auteur
      Oui tu as peut être raison tu peux m'aider s'il te plaît
      0
      1. Ak_j Auteur
        Oui tu as peut-être raison tu pourrais m'aider s'il te plaît
        0

        Discussions similaires

        jeu Ricosheep
        Ak_j

        10 réponses