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

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()

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

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

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 ?

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

Bonjour, des vidéos intéressantes : https://www.bing.com/videos/search?q=python+the+genius+square&qpvt=python+the+genius+square&FORM=VDRE

Programmer le jeu The Genius Square sur Python [Résolu]

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?

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.

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.

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.

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.

Ximista > yg_be Messages postés 20761 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 6 décembre 2022
3 janv. 2021 à 18:02

Voici le code en entier :

import numpy as np
import matplotlib.pyplot as plt
import random as rd

M=np.zeros((6,6)) #Grille de jeu où poser les pièces


# carré de 2 par 2: 1 orientation
PIECE_1 = np.array([[1,1],[1,1]])

# carré simple : 2 orientations
PIECE_2 = np.array([[2]])

# ligne de 2 : 2 orientations
PIECE_3 = np.array([[3,3]])

# ligne de 4 : 4 orientations
PIECE_4 = np.array([[4,4,4,4]])

# ligne de 3 : 2 orientations
PIECE_5 = np.array([[5,5,5]])

# forme en L: 4 orientations
PIECE_6 = np.array([[6,0,0],[6,6,6]])

# zig-zag: 4 orientations
PIECE_7 = np.array([[7,7,0],[0,7,7]])

# forme en T : 8 orientations
PIECE_8 = np.array([[8,0],[8,8],[8,0]])

# forme coudée : 1 orientation
PIECE_9 = np.array([[9,9],[9,0]])


DE_1=[[5,3],[4,5],[4,4],[5,4],[4,3],[3,4]]
DE_2=[[5,5],[3,5],[2,5],[2,4],[1,4],[0,3]]
DE_3=[[1,2],[1,1],[1,0],[2,1],[0,2],[0,1]]
DE_4=[[4,1],[3,1],[3,0],[5,2],[2,0],[0,0]]
DE_5=[[3,3],[3,2],[2,3],[4,2],[2,2],[1,3]]
DE_6=[[0,4],[5,1],[4,0],[1,5]]
DE_7=[[0,5],[5,0]]

# DE_1=["A3","B1","B2","A2","B3","C2"]
# DE_2=["A1","C1","D1","D2","E2","F3"]
# DE_3=["E4","E5","E6","D5","F4","F5"]
# DE_4=["B5","C5","C6","A4","D6","F6"]
# DE_5=["C3","C4","D3","B4","D4","E3"]
# DE_6=["F2","A5","F2","A5","B6","E1"]
# DE_7=["F1","A6","F1","A6","F1","A6"]

## VARIABLES GLOBALES

ORDRE_DES_PIECES = [PIECE_1]+[PIECE_4]+[PIECE_6]+[PIECE_7]+[PIECE_8]+[PIECE_9]+[PIECE_5]+[PIECE_3]+[PIECE_2]

##FONCTIONS ANNEXES

def affichage_grille():
    # plt.axis('off') #Rendre les axes invisibles
    plt.axis('equal') #Grille complète avec coordonnées
    for i in range(8):
        plt.plot([i-1.5,i-1.5],[-1.5,7-1.5],'k')
        for j in range(8):
            plt.plot([-1.5,7-1.5],[j-1.5,j-1.5],'k')
    nommer_lignes()
    nommer_colonnes()
    #placer_bloqueurs(tirage_7des())
    plt.imshow(M,cmap='gist_rainbow',clim=(-1,9))
    plt.show()

def nommer_lignes():
    L=["A","B","C","D","E","F"]
    for i in range(0,6):
        plt.text(-1,i,L[i])
plt.show()

def nommer_colonnes():
    for i in range(0,6):
        plt.text(i-0.1,-1,i+1)
plt.show()



#Fonction "tirer un dé"
def tirage_de(D):
    i=rd.randint(0,len(D)-1)
    return(D[i])

#Fonction "tirage des 7 dés"
def tirage_7des():
    D = [DE_1,DE_2,DE_3,DE_4,DE_5,DE_6,DE_7]
    Liste_des_tires=[]
    for i in D:
        j=tirage_de(i)
        Liste_des_tires = Liste_des_tires + [j]
    return(Liste_des_tires)

#Placer les bloqueurs sur le plateau selon les dés
def placer_bloqueurs(L):
    for i in L:
        (n,p)=(i[0],i[1])
        M[n,p]=-1
    return(M)


def recuperation_coordonnees(piece): #Recupère les coordonnées des chiffres différents de 0 qui composent la pièce dans une position
    N=[]
    (r,t)= np.shape(piece)
    for k in range(r):
        for j in range(t):
            if piece[k,j]!=0:
                N = N + [(k,j)]
    return(N)



def verifier_place(N,piece,i,j):
    bloqueur_dans_la_zone=len(N)
    for k in N:
        b=(k[0]+i,k[1]+j)
        if b[0]<6 and b[1]<6:
            if M[b]==0:
                bloqueur_dans_la_zone=bloqueur_dans_la_zone-1
    if bloqueur_dans_la_zone!=0:
        return(False)
    else:
        return(True) #renvoie true si on peut placer la pièce dans ce rectangle


def positions_possibles(N,piece):
    (r,t)=np.shape(piece)
    (l,m)=np.shape(M)
    positions_possibles=[]
    for i in range(l): #ligne i de la matrice M
      for j in range(m): #colonne j de la matrice M
                if j+t<=m: #si la largeur max de la pièce rentre dans M
                    if i+r<=l:#si la hauteur max de la pièce rentre dans M
                        if verifier_place(N,piece,i,j):
                            positions_possibles.append((i,j))
    return positions_possibles


def rotation_piece(piece): #Permet de changer la position de la pièce 7 + stocke dans une liste ces 4 positions
    L=[piece] #Liste qui contient toutes les positions de la pièce
    if np.array_equal(piece,PIECE_2) or np.array_equal(piece,PIECE_1): #Cas de la pièce 2 ou 1 (Une seule position possible)
        return(L)

    if np.array_equal(piece,PIECE_6): #Cas de la pièce 6 (8 positions possibles)
        T1 = np.transpose(PIECE_6)
        T2=echanger_2_colonnes(T1)
        T3 = np.transpose(T2)
        T4 = echanger_colonnes_extremites(T3)
        T5 = np.transpose(T4)
        T6=echanger_2_colonnes(T5)
        T7 = np.transpose(T6)
        L=[piece]+[T1]+[T2]+[T3]+[T4]+[T5]+[T6]+[T7]

        return(L)

    if np.array_equal(piece,PIECE_8) : #Cas de la pièce 8 (4 positions possibles)
        T1=np.transpose(piece)
        T2=echanger_2_colonnes(piece)
        T3 = np.transpose(T2)
        L=[piece]+[T1]+[T2]+[T3]
        return(L)

    if np.array_equal(piece,PIECE_9): #Cas de la piece 9 (4 positions possibles)
        T1 = echanger_2_colonnes(piece)
        T2=np.transpose(T1)
        T3=echanger_2_colonnes(T2)
        L=[piece]+[T1]+[T2]+[T3]
        return(L)

    if np.array_equal(piece,PIECE_7):
        T1=np.transpose(PIECE_7)
        T2=echanger_2_colonnes(T1)
        T3=np.transpose(T2)
        L=[piece]+[T1]+[T2]+[T3]
        return(L)

    else : #Cas des pièces  3, 4, 5
        L=[piece]+[np.transpose(piece)]
        return(L)


def echanger_2_colonnes(P1): #échange deux colonnes côte à côte dans un tableau
    (n,p) = np.shape(P1)
    P2 = np.zeros([n,p])
    for i in range(n):
        for j in range(p-1):
            P2[i,j] = P1[i,j+1]
            P2[i,j+1] = P1[i,j]
    return (P2)

def echanger_colonnes_extremites(P1):#echanges les deux colonnes aux extrémités du tableau
    (n,p)=np.shape(P1)
    P2=np.zeros([n,p])
    for i in range(n):
        for j in range(p-2):
            P2[i,j] = P1[i,j+2]
            P2[i,j+1]=P1[i,j+1]
            P2[i,j+2]=P1[i,j]
    return (P2)



def coloriage_coordonnees(N,position): #Change les valeurs de la matrice par le numéro de la pièce si celle-ci peut être positionnée
    """Prends en entrée une pièce dans une position
    et la liste N issue de la fonction recuperation_coordonnees"""
    (r,t)=np.shape(position)
    (l,m)=np.shape(M)
    for i in range(l): #ligne i de la matrice M
        for j in range(m): #colonne j de la matrice M
            if j+t<=m: #si la largeur max de la pièce rentre dans M
                if i+r<=l:#si la hauteur max de la pièce rentre dans M
                    if verifier_place(N,position,i,j) == True:
                        for k in N:
                            a = (k[0]+i,k[1]+j)
                            b = identifier_numero_piece(position)
                            M[a] = b
                        return(M)



def identifier_numero_piece(piece):
    """Renvoie le numéro de la pièce sélectionnée"""
    k = 0
    B = []
    for u in TOUTES_LES_PIECES:
        B = []
        B = rotation_piece(u)
        for v in B:
            (a,b) = np.shape(v)
            (c,d) = np.shape (piece)
            if a==c and b==d:
                if np.array_equal(v,piece):#Si la pièce en entrée appartient à la liste des orientations possibles d'une pièce
                    for w in range(len(TOUTES_LES_PIECES)):
                        k = k + 1
                        if np.array_equal(TOUTES_LES_PIECES[w],u): #u correspond à la 1ère position par défaut de la pièce en entrée
                            break
    return(k)


def effacer(piece):
    (n,m)=np.shape(M)
    for j in range(n):#si la case k ne rentre pas on retire la piece placé en k-1 de la grille (piece k)
        for i in range(m):
            if M[j,i] == identifier_numero_piece(piece):
                M[j,i] = 0


def placer(piece):
    k=0
    for i in rotation_piece(piece):
        if verifier_piece_placee(i) == True:
            break
        else:
            for j in  positions_possibles(recuperation_coordonnees(i),i): #on parcourt les positions possibles de la pièce dans sa i-ième orientation possible
                if len(positions_possibles(recuperation_coordonnees(i),i)) == 0:
                    k=k+1 #Ajoute +1 à chaque fois qu'il n'existe pas de place disponible pour une orientation
                    continue
                else:
                    coloriage_coordonnees(recuperation_coordonnees(i),i)
                    break
        if k == len(rotation_piece(piece)): #Si toutes les positions de toutes les orientations ont été testées
        #revenir à la pièce précente
            return(k)


def coloriage_nouvelles_coordonnees(position,N,coordonnees):
    """Prends en entrée une pièce dans une position,
    la liste N issue de la fonction recuperation_coordonnees
    et la liste coordonnees issue de la fonction positions_possibles"""
    (r,t)=np.shape(position)
    (l,m)=np.shape(M)
    (a,b) = coordonnees[0]
    if b+t<=m: #si la largeur max de la pièce rentre dans M
        if a+r<=l:#si la hauteur max de la pièce rentre dans M
            if verifier_place(N,position,a,b) == True:
                for k in N:
                    c = (k[0]+a,k[1]+b)
                    d = identifier_numero_piece(position)
                    M[c] = d
                return(M)



def verifier_piece_placee(piece):
    """Renvoie true si la pièce est déjà placée dans la matrice"""
    b = identifier_numero_piece(piece)
    if b in M:
        return(True)
    else:
        return(False)

def attribution_positions_possibles():
    """Attribue à chaque pièce la liste de ses positions possibles en début de partie"""
    (A,B,C,D,E,F,G,H)=(list(),list(),list(),list(),list(),list(),list(),list())
    L = [A,B,C,D,E,F,G,H]
    for j in range(len(L)):
        L[j] = L[j] + positions_possibles(recuperation_coordonnees(ORDRE_DES_PIECES[j]),ORDRE_DES_PIECES[j])
    return(L)

Vient ensuite la fonction resolution() qui ne prend rien en argument et qui est censé résoudre le jeu.
Elle se construit de cette manière :

def resolution():  
    placer_bloqueurs(tirage_7des())
    n = 0 #nombre de pièces placées
    attribution_positions_possibles()
    for k in range(len(ORDRE_DES_PIECES)):
        placer(ORDRE_DES_PIECES[k])
        if resolu():
            break
            print('C'est fini !')
        if verifier_piece_placee(ORDRE_DES_PIECES[k]) :
            n = n+1
        while n<9:

J'ai tenté de mettre ce "while n<9" pour faire continuer l'algorithme tant que toutes les pièces ne sont pas placées mais on finit alors dans une boucle infinie.
Et à la suite de ce while, j'ai tenté d'imbriquer plusieurs boucles de type "if" de la manière suivante :

            if verifier_piece_placee(ORDRE_DES_PIECES[k]) == False:
                revenir_a_piece_precedente(ORDRE_DES_PIECES[k-1],H)
                if verifier_piece_placee(ORDRE_DES_PIECES[k-1]) == False:
                    revenir_a_piece_precedente(ORDRE_DES_PIECES[k-2],G)
                    if verifier_piece_placee(ORDRE_DES_PIECES[k-2]) == False:
                        revenir_a_piece_precedente(ORDRE_DES_PIECES[k-3],F)
                        if verifier_piece_placee(ORDRE_DES_PIECES[k-3]) == False:
                            revenir_a_piece_precedente(ORDRE_DES_PIECES[k-4],E)
                            if verifier_piece_placee(ORDRE_DES_PIECES[k-4]) == False:
                                revenir_a_piece_precedente(ORDRE_DES_PIECES[k-5],D)
                                if verifier_piece_placee(ORDRE_DES_PIECES[k-5]) == False:
                                    revenir_a_piece_precedente(ORDRE_DES_PIECES[k-6],C)
                                    if verifier_piece_placee(ORDRE_DES_PIECES[k-6]) == False:
                                        revenir_a_piece_precedente(ORDRE_DES_PIECES[k-7],B)
                                        if verifier_piece_placee(ORDRE_DES_PIECES[k-7]) == False:
                                            if verifier_piece_placee(ORDRE_DES_PIECES[k-8]) == False:
                                                revenir_a_piece_precedente(ORDRE_DES_PIECES[k-8],A)
                                            placer(ORDRE_DES_PIECES[k-7])
                                        else:
                                            placer(ORDRE_DES_PIECES[k-6])
                                    else:
                                        placer(ORDRE_DES_PIECES[k-5])
                                else:
                                    placer(ORDRE_DES_PIECES[k-4])
                            else:
                               placer(ORDRE_DES_PIECES[k-3])
                        else:
                            placer(ORDRE_DES_PIECES[k-2])
                    else:
                        placer(ORDRE_DES_PIECES[k-1])
                else:
                    placer(ORDRE_DES_PIECES[k])

Le raisonnement étant celui que j'ai évoqué dans mon message précédent, l'algorithme parvient à ne pas placer les 9 pièces en suivant cet ordre. J'ai essayé de remplacer les "if" par des "while" pour traduire le "tant que la pièce k-1 n'est pas sur le plateau, tu ne places pas la pièce k" mais encore une fois on aboutit à une boucle infinie.

A ce stade, je n'arrive plus à prendre du recul pour comprendre où cela ne fonctionne pas.

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
3 janv. 2021 à 20:32

le while

n<9

est une bonne idée, tandis que

for k in range

est une fausse piste.
moi je ferais ainsi:

piéceplacée=0
tant que la dernière pièce n'est pas placée:
	si je trouveuneplace pour pieceplacee+1:
		pieceplacee = pieceplacee + 1
	sinon:
		si pieceplacee == 0:
			fini, perdu
		sinon:
			pieceplacee = pieceplacee - 1
fini, gagné

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
Modifié le 3 janv. 2021 à 23:53

n=0
tant que je n'ai pas placé toutes les pièces, donc tant que n < nombre de pièces
je place ou déplace la pièce n
si cela marche, je continuerai ensuite avec la prochaine pièce, n=n+1
sinon, je continuerai ensuite avec la pièce précédente, n=n-1

Ximista > yg_be Messages postés 20761 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 6 décembre 2022
5 janv. 2021 à 19:29

pieceplacee correspond au nombre de pièces placées ?
Parce que dans ce cas-là, que signifie "pieceplacee+1" ?

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
5 janv. 2021 à 21:19

c'est la somme du nombre de pièces placées et de 1

Ximista > yg_be Messages postés 20761 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 6 décembre 2022
10 janv. 2021 à 10:35

Si le "for k in range" est une fausse piste, comment puis-je faire alors pour parcourir les pièces ?
J'ai essayé de mettre en place le programme mais je ne sais pas comment sélectionner la pièce n si ce n'est en parcourant une liste de toutes les pièces

Ximista > Ximista
10 janv. 2021 à 10:46

De plus, la fonction "placer(piece)" se charge déjà de vérifier qu'il y a la place pour mettre une pièce à un endroit. Il n'est donc pas utile d'avoir le test "si je trouveuneplace pour pieceplacee+1:"
On utilisait plutôt le test "est-ce que la pièce n est déjà placée" : si oui, on passe à n+1, sinon on revient à n-1

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
10 janv. 2021 à 12:28

tu n'as peut-être pas compris ce que j'écrivais en #15 et #16.

quand j'écris "si je trouveuneplace:"
cela signifie:
"je cherche une place, et, si j'en ai trouvé une:"

une de tes difficultés, c'est que tu as fait le programme à l'envers.
tu n'as pas commencé par la partie la plus importante, la logique principale.
tu as créé des fonctions, et tu te demandes maintenant comment les utiliser.
il est préférable de d'abord réfléchir à la logique principale, de déterminer quelles fonctions sont utiles, puis de créer les fonctions.

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
10 janv. 2021 à 12:22

q'as-tu essayé? ai-je suggéré de sélectionner une pièce?

Ximista > yg_be Messages postés 20761 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 6 décembre 2022
10 janv. 2021 à 12:35

J'ai essayé de mettre en place ta proposition sauf que sans le "for k in range", je ne sais pas comment désigner à quelle pièce correspond la pièce n (ou alors je le fais manuellement en enchaînant les boucles pour la pièce 1 puis 2 puis 3, etc)

J'ai essayé de changer de tactique. Comme la fonction "placer(piece)" vérifiait plusieurs paramètres, je l'ai allégée de sorte qu'elle se contente de placer une pièce à un endroit. A la place, j'ai rentré ces paramètres de vérification directement dans la fonction de résolution et ça donne ça :

def resolution2():
    placer_bloqueurs(tirage_7des())
    n=0
    for a in rotation_piece(PIECE_1):
        n=n+1
        if len(positions_possibles(recuperation_coordonnees(a),a)) != 0:
            placer2(a)
            for b in rotation_piece(PIECE_7):
                n=n+1
                if len(positions_possibles(recuperation_coordonnees(b),b)) != 0:
                    placer2(b)
                    for c in rotation_piece(PIECE_6):
                        n=n+1
                        if len(positions_possibles(recuperation_coordonnees(c),c)) != 0:
                            placer2(c)
                            for d in rotation_piece(PIECE_4):
                                n=n+1
                                if len(positions_possibles(recuperation_coordonnees(d),d)) != 0:
                                    placer2(d)
                                    for e in rotation_piece(PIECE_8):
                                        n=n+1
                                        if len(positions_possibles(recuperation_coordonnees(e),e)) != 0:
                                            placer2(e)
                                            for f in rotation_piece(PIECE_5):
                                                n=n+1
                                                if len(positions_possibles(recuperation_coordonnees(f),f)) != 0:
                                                    placer2(f)
                                                    for g in rotation_piece(PIECE_9):
                                                        n=n+1
                                                        if len(positions_possibles(recuperation_coordonnees(g),g)) != 0:
                                                            placer2(g)
                                                            for h in rotation_piece(PIECE_3):
                                                                n=n+1
                                                                if len(positions_possibles(recuperation_coordonnees(h),h)) != 0:
                                                                    placer2(h)
                                                                    for i in rotation_piece(PIECE_2):
                                                                        n=n+1
                                                                        if len(positions_possibles(recuperation_coordonnees(i),i)) != 0:
                                                                            placer2(i)
    affichage_grille()

Je me suis inspirée de ce qu'a fait ce programme : https://github.com/Level-314/genius_square_solver/blob/master/first_solver.py
J'avoue que je ne comprends pas tout ce qui est écrit (c'est en anglais et le programmeur raisonne en binaire).
Je ne sais pas comment il fait mais lorsqu'une pièce ne peut pas être placée, son programme remonte automatiquement à la pièce précédente et encore fois, c'est ce qu'il me manque dans mon programme.
Et ce qui m'étonne, c'est que dans son programme, il n'y a pas de fonctions annexes qui permettent spécifiquement ce retour en arrière.

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
Modifié le 10 janv. 2021 à 14:55

que veux-tu dire par "inspirée"?
le programme fonctionne-t'il?
pourquoi penses-tu avoir besoin d'une fonction qui remonte à la pièce précédente? que ferait cette fonction? où et comment l'appelerais-tu?

Ximista > yg_be Messages postés 20761 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 6 décembre 2022
10 janv. 2021 à 17:10

Quand je dis "inspirée" cest que j ai essayé de reprendre sa logique de raisonnement mais comme je l ai dit il y a quelque chose qui m echappe, je ne comprends pas tout ce qu il a fait.
Le sien oui, il fonctionne parfaitement
Je ne pense pas avoir besoin forcement d une fonction qui remonte à la pièce précédente mais dans la logique il faut en effet avoir un système qui me permet de revenir à la pièce n-1 pour la déplacer si je ne peux pas placer la pièce n

Pour ta proposition je n ai pas vraiment compris la logique dans le sens où le compteur m indique certes le nombre de pièce placée, cependant je ne vois pas ce qu il pouvait faire d'autres

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
10 janv. 2021 à 18:24

As-tu une question précise au sujet du code que tu as trouvé sur github?
Personnellement, je trouve que ces boucles imbriquées sont assez horribles. Le titre "Using the Force" est bien adapté, j'aurais préféré un peu plus d'intelligence et un peu moins de force.

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
10 janv. 2021 à 18:40

tu comprendras peut-être mieux ceci:

def trouver_place3(piece):
    # piece est le numéro de la piéce à placer
    # la fonction doit, si la pièce n'est pas placée, placer la pièce,
    #       ou, si elle est déjà placée, la déplacer à sa position suivante
    # la fonction retourne "vrai" si la pièce a pu être placée,
    #              sinon elle retourne "faux"
    pass
def resolution3(npieces):
    # npieces est le nombre total de pièces à placer
    nplaces=0   #nplaces est le nombre de pièces déjà placées
    while nplaces<npieces:
        if not trouver_place3(nplaces+1):
            if nplaces==0:
                return False
            else:
                nplaces=nplaces-1
        else:
            nplaces=nplaces+1
    return True

Ximista > yg_be Messages postés 20761 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 6 décembre 2022
11 janv. 2021 à 21:54

Le code je l'ai trouvé dans la description de cette vidéo : https://www.youtube.com/watch?v=QzJo-Oj0X3A&t=917s
Le "using the force" est en fait juste une référence à la force dans Star Wars x)
Malheureusement, je ne crois pas qu'il existe de réelle "stratégie" pour ce jeu si ce n'est de tester tout un par un.
Si tu comprends son code, est-ce que tu pourrais m'expliquer quelle en est la logique parce que j'ai l'impression que quelque chose m'échappe.

Pour ta proposition, j'ai déjà deux fonctions qui permettent de placer et déplacer la pièce (je ne sais pas si ca change quelque chose de les séparer ?)
Cependant, si je suis ta logique de ne créer qu'une seule fonction qui prend en argument une pièce, je ne comprends pas comment tu te retrouves avec ce test : "if not trouver_place3(nplaces+1):" puisque là, tu mets en argument un nombre (issu d'un compteur) et non pas une pièce

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
12 janv. 2021 à 11:28

le nombre est le numéro de la pièce.

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
10 janv. 2021 à 15:27

qu'as-tu essayé pour mettre en place ma proposition?

Ximista > 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:13

J'ai tenté ceci :

def resolution(): 
    placer_bloqueurs(tirage_7des()) #Place les bloqueurs
    pieces_placees = 0 #nombre de pièces placées
    L = [] #Liste composée des listes des positions possibles pour chaque pièce en début de partie
    for a in ORDRE_DES_PIECES:
        for b in range(9):
            b = attribution_positions_possibles(a) 
            L.append(b)
    k = ORDRE_DES_PIECES[0]
    l = 0
    while pieces_placees < 9:
        if not verifier_piece_placee(k):
            placer(k,L[l])
            if not verifier_piece_placee(k):
                k = ORDRE_DES_PIECES[l-1]
            else:
                pieces_placees = pieces_placees + 1
                k = ORDRE_DES_PIECES[l+1]

def placer(piece,A):
    """Permet de placer la pièce ou de la déplacer si elle est déjà sur le plateau"""
    k=0
    m=0
    if verifier_piece_placee(piece): #Cas où l'on souhaite déplacer une pièce déjà placée
        for i in rotation_piece(piece):
            if A == []:
                m=m+1
                continue
            else:
                effacer(piece)
                print(m)
                A[m].pop(0)
                print(A)
                coloriage_coordonnees(i,recuperation_coordonnees(i),A[m][0])
                break
    else: #Cas où on place la pièce la 1ère fois
        for j in rotation_piece(piece):
            if verifier_piece_placee(j):
                break
            else:
                for l in  positions_possibles(recuperation_coordonnees(j),j): #on parcourt les positions possibles de la pièce dans sa j-ième orientation possible
                    if len(positions_possibles(recuperation_coordonnees(j),j)) == 0:
                        k=k+1 #Ajoute +1 à chaque fois qu'il n'existe pas de place disponible pour une orientation
                        continue
                    else:
                        coloriage_coordonnees(j,recuperation_coordonnees(j),l)
                        return(M)
    if not verifier_piece_placee(piece):
        return(False)

La fonction attribution_positions_possibles(piece) prend en argument une pièce donnée à laquelle elle attribue la liste de toutes ses positions possibles en début de partie quelle que soit son orientation.

Le programme tourne encore dans le vide

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
17 janv. 2021 à 19:44

quelques erreurs, pour commencer:
- partout, tes noms de variables ne signifient rien
- évite d'utiliser les mêmes noms dans différentes fonctions
- dans resolution(), ta variable l est en trop, essaie sans.
- dans resolution(), change de nom pour la variable k, et assigne-là une seule fois, au bon endroit.
- dans resolution(), à quoi sert le test en ligne 12? que se passe-t'il si verifier_piece_placee() retourne vrai?
- dans resolution(), pourquoi ne pas tester la valeur retournée par placer(), au lieu d'appeler à nouveau verifier_piece_placee?
- je m'inquiète de ce que je vois en ligne 32: qu'y fais-tu?

Programmer le jeu The Genius Square sur Python

7 réponses

Newsletters