Programmer le jeu The Genius Square sur Python

Résolu/Fermé
Ximista - 20 déc. 2020 à 20:56
yg_be Messages postés 20761 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 6 décembre 2022 - 17 janv. 2021 à 19:44
Bonjour,

Pour un projet en cours, je dois programmer le jeu The Genius Square (si vous ne connaissez pas, voici un lien qui explique le principe du jeu : https://www.philibertnet.com/fr/the-happy-puzzle-company/76246-the-genius-square-732068459932.html#tab-features

J'ai programmé le plateau de jeu et le placement aléatoire des "bloqueurs" selon le lancer des 7 dés correspondant à ceux du jeu.
J'ai également programmé une fonction qui permet de placer une pièce sur le plateau dans un espace disponible(qui tient compte des bloqueurs et des pièces déjà placées) ainsi qu'une fonction capable de déplacer une pièce déjà placée à sa position possible suivante.

Pour expliciter, je peux placer la pièce n°1 puis la n°2 et si je n'ai pas de place disponible pour la n°2, je peux déplacer la n°1 à un autre endroit afin de réessayer de placer la 2 (je ne sais pas si je suis suffisamment claire, dites moi si vous avez besoin de plus de détails ^^)

Mon problème est le suivant : j'essaie maintenant de programmer la fonction résolution() capable de résoudre le puzzle en entier et les combinaisons que j'ai essayé ne permettent jamais de placer les 9 pièces (il en manque toujours une).
Mon raisonnement est le suivant : je lui demande de placer toutes les pièces dans un certain ordre et si la pièce n°k n'est pas placée, on remonte à la pièce n°k-1 pour la déplacer et ensuite réessayer avec la k.
Le souci, c'est qu'en faisant ça, il arrive que la pièce k-1 soit carrément enlevée du plateau (ce qui permet de placer la pièce k car de la place se libère).
J'ai essayé de demander à remonter à la pièce k-2 puis ainsi de suite mais il existe toujours une faille dans le programme qui permet de laisser une pièce de côté.

Voici le début de la fonction :

def resolution():
placer_bloqueurs(tirage_7des()) #Place les 7 bloqueurs sur le plateau de jeu
n = 0 #nombre de pièces placées
attribution_positions_possibles() #Fonction qui collecte les listes de toutes les positions possibles pour chaque pièce en début de jeu
for k in range(len(ORDRE_DES_PIECES)): #Parcourt la liste des pièces selon l'ordre dans lequel les placer
placer(ORDRE_DES_PIECES[k]) #Place chaque pièce une par une
if resolu(): #Si le puzzle est résolu = toutes les pièces sont placées
break
print('Terminé !')
if verifier_piece_placee(ORDRE_DES_PIECES[k]) : #Rajoute +1 au compteur à chaque fois qu'une pièce est placée
n = n+1
if n<9: #Dans le cas où toutes les pièces ne sont pas encore placées


Et c'est là que je souhaite rajouter les commandes pour gérer la situation dans le cas où une pièce n'a pas été placée par manque de place

7 réponses

Phil_1857 Messages postés 1532 Date d'inscription lundi 23 mars 2020 Statut Membre Dernière intervention 5 décembre 2022 151
21 déc. 2020 à 12:17
Bonjour ximista,

Il faudrait que tu ré affiches ton code avec les balises de code Python pour plus de clarté
mode d'emploi:
https://codes-sources.commentcamarche.net/faq/11288-les-balises-de-code

Visuellement, ça doit ressembler à ceci (avec la coloration syntaxique) :

def test():
    print('test')

test()
0
ah oui pardon, merci ! ^^
Voilà :

def resolution():
    placer_bloqueurs(tirage_7des()) #Place les 7 bloqueurs sur le plateau de jeu
    n = 0 #nombre de pièces placées
    attribution_positions_possibles() #Fonction qui collecte les listes de toutes les positions possibles pour chaque pièce en début de jeu
    for k in range(len(ORDRE_DES_PIECES)): #Parcourt la liste des pièces selon l'ordre dans lequel les placer
        placer(ORDRE_DES_PIECES[k]) #Place chaque pièce une par une
        if resolu(): #Si le puzzle est résolu = toutes les pièces sont placées
            break
            print('Terminé !')
        if verifier_piece_placee(ORDRE_DES_PIECES[k]) : #Rajoute +1 au compteur à chaque fois qu'une pièce est placée
            n = n+1
        if n<9: #Dans le cas où toutes les pièces ne sont pas encore placées
0
yg_be Messages postés 20761 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 6 décembre 2022 1 269
23 déc. 2020 à 16:05
deux défauts du programme:
- il ne faut certainement pas faire ainsi une boucle for
- tu mélanges un peu n et k
0
Phil_1857 Messages postés 1532 Date d'inscription lundi 23 mars 2020 Statut Membre Dernière intervention 5 décembre 2022 151
Modifié le 22 déc. 2020 à 11:30
Bonjour Ximista,

D'après ce que je comprends des règles du jeu:

_ on a un tableau de 6x6 = 36 cases
_ on lance 7 dés qui indiquent les cases où placer les 7 pions bloqueurs
(il reste donc 29 cases libres)
_ on a des formes de couleurs qui sont des assemblages de cubes et qui ressemblent
à des L, ou des T, ou des I
_ il faut les placer dans les cases restantes, je ne pense pas qu'il y ait un ordre pour les
positionner, il faut simplement s'arranger pour que tout rentre dans les cases vides

Dans ton code, on ne voit pas comment tu "modélises" avec des variables les différentes
formes des pions et comment tu testes si une forme donnée (un L, par exemple)
rentre à un certain endroit du tableau ...
0
Effectivement ce sont bien les règles du jeu !
En réel, les pièces peuvent être placées n'importe comment mais j'ai choisi de les placer dans un certain ordre (d'abord les plus encombrantes) afin de faciliter la programmation.

Le code complet est beaucoup plus long, je n'ai mis ici que la fonction qui me pose problème pour simplifier !
Le plateau est modélisé par une matrice 6x6 et chaque pièce par une matrice. Par exemple, la pièce carrée de dimension 2x2 est modélisée par une matrice 2x2 [[1,1],
[1,1]]
pour les pièces avec une forme particulière, on place des 0 dans les espaces vides.
Ex : [[7,0], (pièce en Z)
[7,7],
[0,7]]

J'ai créé plusieurs fonctions auxiliaires qui permettent de vérifier si une pièce peut être placée à un endroit et si oui, qui peuvent la placer à cet endroit. Ces fonctions testent également les différentes orientations possibles pour chaque pièce. Je ne sais pas s'il est utile que je montre ces fonctions ?
0
yg_be Messages postés 20761 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 6 décembre 2022 1 269
23 déc. 2020 à 13:42
ton explication me semble très correcte, mais ton programme ne me semble pas faire ce que tu expliques.

comment s'appelle la fonction qui place une pièce sur le plateau dans un espace disponible(qui tient compte des bloqueurs et des pièces déjà placées)?
comment s'appelle la fonction capable de déplacer une pièce déjà placée à sa position possible suivante?

je ne vois pas de fonction qui supprime une pièce, n'en as-tu pas besoin?
0
Ximista > yg_be Messages postés 20761 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 6 décembre 2022
2 janv. 2021 à 19:09
Je n'ai pas détaillé tout le programme ici mais toutes ces fonctions existent et fonctionnent bien.
Ici je m'intéresse uniquement à la résolution finale puisque les étapes intermédiaires ont déjà été réalisées.
Il existe :
- une fonction qui place une pièce (qu'on appelle placer_piece et qui prend en argument la pièce à placer) à sa 1ère position possible
- une fonction qui peut déplacer une pièce à sa position possible suivante (on l'appelle deplacer_piece, elle prend en argument la pièce à déplacer et elle procède d'abord en enlevant la pièce du plateau puis en la mettant à une autre position)
Ces deux fonctions tiennent compte des bloqueurs et des pièces déjà placées.

Lorsque j'écris : "je peux placer la pièce n°1 puis la n°2 et si je n'ai pas de place disponible pour la n°2, je peux déplacer la n°1 à un autre endroit afin de réessayer de placer la 2", s'il y a de la place pour la pièce n°2, bien évidemment elle est directement placée et je passe à la pièce n°3 et ainsi de suite.

Concrètement, je commence par lui demander de placer les pièces dans l'ordre (d'abord la 1 puis la 2, la 3, etc).
J'ai ensuite mis des boucles qui raisonne de cette manière:
Si la pièce n°k n'est pas placée, on déplace la pièce n°(k-1) et on retente de placer la pièce n°k.
Si on ne peut toujours pas placer la pièce n°k, on revient encore une fois à la pièce k-1 et ainsi de suite. Si finalement, on épuise toutes les solutions pour la pièce k-1, alors on remonte à la pièce k-2 puis on retente de placer k-1 et une fois celle-ci placée, la pièce k.

Problème : pour éviter que l'algorithme ne se bloque, la fonction placer_piece peut ne pas placer de pièce s'il n'y a pas de place. En d'autres termes, si la pièce ne peut pas être mise sur le plateau de jeu, la fonction ne fera rien et ne renvoie pas de message particulier.
Ainsi, lors du raisonnement, si en déplaçant k-1 il n'existe pas de place pour cette pièce, elle est tout simplement sortie du plateau et la pièce k peut alors être posée car de la place s'est libérée. Mais l'algorithme ne revient plus à la pièce k-1 et elle ne sera jamais sur le plateau.

J'ai essayé de résoudre le problème à l'aide de boucles "while" mais l'algorithme finit par tourner à l'infini et si je ne mets que des boucles "if", il contourne le placement de toutes les pièces comme je viens de l'expliquer.

J'ai déjà vu les vidéos proposées par Phil_1857 mais il code en binaire et pour le projet, nous ne passons pas par cette méthode... J'ai donc un peu de mal à "traduire" sa façon de faire pour l'adapter à notre travail

Et je ne vois pas où je confonds les n et les k ? Le n représente seulement un compteur qui renvoie le nombre de pièces placées à l'issu du programme, c'est un simple outils pour me repérer.
0
yg_be Messages postés 20761 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 6 décembre 2022 1 269 > Ximista
2 janv. 2021 à 20:17
nous as-tu montré le code qui appelait placer_piece et deplacer_piece?
as-tu une fonction qui supprime une pièce?

quand tu décris ton algorithme "Concrétement, ...", le raisonnement me semble correct.
cependant, tu écris "J'ai ensuite mis des boucles", qui est très flou. peux-tu être plus précis?
par ailleurs, tu n'indiques pas à quel moment l'algorithme décide d'arreter, soit en ayant réussi, soit en ayant perdu. je pense que c'est en décrivant cela que tu vas progresser vers une solution.
0
yg_be Messages postés 20761 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 6 décembre 2022 1 269 > yg_be Messages postés 20761 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 6 décembre 2022
2 janv. 2021 à 20:31
Tu as essayé des boucles "while" ainsi que des boucles "if": montre-nous cela, cela nous aidera sans doute à te guider vers une solution, sans faire le travail à ta place.
0
yg_be Messages postés 20761 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 6 décembre 2022 1 269 > yg_be Messages postés 20761 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 6 décembre 2022
2 janv. 2021 à 20:48
en fait, quand tu écris "je commence par lui demander de placer les pièces dans l'ordre", je pense que c'est mal parti.
0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
Phil_1857 Messages postés 1532 Date d'inscription lundi 23 mars 2020 Statut Membre Dernière intervention 5 décembre 2022 151
22 déc. 2020 à 17:37
Bah non, si tu maitrise cette partie-là ....

Le truc c'est plutôt de trouver le bon algorithme pour placer toutes les pièces

J'avoue que la façon dont tu procèdes ne me parait pas claire

et que je n'ai pas encore réfléchi à tout ça ....
0
Phil_1857 Messages postés 1532 Date d'inscription lundi 23 mars 2020 Statut Membre Dernière intervention 5 décembre 2022 151
23 déc. 2020 à 13:08
0
yg_be Messages postés 20761 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 6 décembre 2022 1 269
23 déc. 2020 à 14:51
tu écris "je peux placer la pièce n°1 puis la n°2 et si je n'ai pas de place disponible pour la n°2, je peux déplacer la n°1 à un autre endroit afin de réessayer de placer la 2"

que fais-tu si tu as de la place disponible pour la pièce 2?
0