Re-jeu Ricosheep (problème de solveur)
Ak_j
Messages postés
18
Date d'inscription
Statut
Membre
Dernière intervention
-
Ak_j Messages postés 18 Date d'inscription Statut Membre Dernière intervention -
Ak_j Messages postés 18 Date d'inscription Statut Membre Dernière intervention -
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.
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
yg_be
Messages postés
23541
Date d'inscription
Statut
Contributeur
Dernière intervention
Ambassadeur
1 584
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/
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/
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.
Et j'aimerais avoir quelques idées ou conseils (peu importe ) pour améliorer ma fonction pour quel soit optimal.
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
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.
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
Messages postés
23541
Date d'inscription
Statut
Contributeur
Dernière intervention
Ambassadeur
1 584
Rien à voir, je pense, avec tes erreurs, et je pense préférable, au lieu de:
de faire
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
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:])
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:])
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']))