Taquin 4*4

Soyez le premier à donner votre avis sur cette source.

Snippet vu 11 198 fois - Téléchargée 18 fois

Contenu du snippet

Je débute en programmation.
je vous poste le célèbre problème de la résolution du taquin 4*4 avec un affichage tkinter qui m'a donné du mal.
la recherche de la solution ce fait par un arbre que l'on remonte lorsque le but est atteint
l'image de départ est la position recherche.
pour démarrer appuyer sur mel(mélange)
et pour obtenir le résultat appuyez sur res(résultat)
un peu d'info sorte sur le terminal

fonctionne sur python3 ubuntu10.10

je remercie les forums qui m'ont permis d'avancer sur ce prog.
ca va pas faire avancer le shmilbliq mais!!!!moi si.

Source / Exemple :


#! /usr/bin/python3
# -*- coding:Utf8 -*-
# fred.fabry@hotmail.fr
#Fonctionne

from tkinter import*
from math import *
from random import randrange
import time

#Constante
oRdre,pEre,fIls,jEu,pOsZ,dEv = 0,1,2,3,4,5

class Taquin(Tk):
    "Frame specialise pour dessiner un taquin 4*4"

    def __init__(self,larg,haut):
        "Constructeur du damier"
        #appel au constructeur de la classe parente
        Tk.__init__(self)
        #constante
        self.larg,self.haut=larg,haut
        #construction du Canvas
        self.can=Canvas(self,width=self.larg,height=self.haut-40,bg='black')
        self.can.pack(side =TOP, padx =20, pady =20)
        #Construction du damier 4*4
        for i in range(0,4,1):
            for j in range(0,4,1):
                self.can.create_rectangle ((20+40*i),(20+40*j),(60+40*i),(60+40*j),fill='white')
        #construction des boutons
        Button(self,text='MEL',command=self.melanger).pack(side=LEFT)
        Button(self,text='RESO',command=self.resoudre).pack(side=LEFT)
        #affichage des chiffres
        self.taquin=taquin_final[:]
        self.afficher(self.taquin)

    def melanger(self):
        "Melange le taquin"
        #le melange d'un taquin 4*4
        taquin_m=taquin_final[:]
        pos_z=0
        for i in range(0,20,1):                     #20 mellanges aleatoire
            dep = depl[pos_z]
            l=dep[randrange(len (dep))]             #choix d'un deplacement
            taquin_m[pos_z],taquin_m[l] = taquin_m[l],taquin_m[pos_z]   #on interverti les positions 
            pos_z=l
        print("taquin : ",taquin_m)                 #afficher dans console
        self.taquin=taquin_m[:]                     #copier
        self.afficher(self.taquin)                  #afficher

    def resoudre(self):
        "Resoudre le taquin"
        solveur = Solveur(self.taquin)
        res = solveur.resoudre()
        if res == None :
            print ("Pas de solution trouvee")
        else:
            print ("Solution trouvee en ",len(res),"coups")
            self.afficherResult(res)

    def afficherResult(self, res, i=1):
        "Avec la methode recursive after permet d'afficher le resultat"
        taquin = res.pop(0)
        self.afficher(taquin)
        print("coup",i," : ",taquin)
        if res:
            self.after(1500, self.afficherResult, res, i+1) #méthode récursive avec la méthode w.after ( delay_ms, callback=None, *args ) de tkinter, qui permet de faire un timer.
        else:
            print ("Fin")
        
    def afficher(self,taquin):
        "Affiche les caractéres sur le canvas"
        for j in range (0,4,1):
            for i in range (0,4,1):
                eff=self.can.create_rectangle((20+40*i),(20+40*j),(60+40*i),(60+40*j),fill='white')#efface l'ancien caractere
                aff=self.can.create_text((40+40*i),(40+40*j),text=str(taquin[i+4*j]))

class Solveur:
    "Solveur de taquin"

    def __init__(self,taquin=None):
        #definition des variables
        self.taquinInitial = taquin[:]
        self.openList = []
        self.finalList = []
        self.noeudList=[]
        #etat initial
        self.openList.append([1,0,[],self.taquinInitial,self.numCaseVide(self.taquinInitial),1])
        self.noeudList.append(1)

    def resoudre(self):
        "resolution"
        compt=0
        butAtteind=0
        print("Recherche de solution")
        while butAtteind == 0:                                       
            node = self.noeudATraiter(self.noeudList[-1])                       #determination du noeud courant a traiter
            noeudCourant = self.openList[node-1]                                #affectation du noeud courant
            taquin = noeudCourant[jEu]
            ordre = self.openList[-1][oRdre]
            pere = noeudCourant[oRdre]
            posZ = noeudCourant[pOsZ]
            depla = self.deplacement(posZ)
            for i in range (0,len(depla),1):                                    #on effectu toute les possibilités de mouvement                                                       
                taquin_temp = taquin[:]                                         #copie dans une variable temporaire
                j = depla[i]                                                    #j est la position d'echange avec la case vide 0
                taquin_temp[posZ],taquin_temp[j] = taquin[j],0                  #echange de la position du zero avec son deplacement
                nouvOrdre = ordre+i+1                                           #incrementation numero d'ordre
                noeudCourant[fIls].append(nouvOrdre)                            #construction de la liste des fils
                if self.testExist(taquin_temp) == 1:                            #l'index pour savoir si on developpe la suite de l'arbre a cet endroit
                    dev=0                                                       #Ca ne sert a rien de develloper cette branche elle existe plus haut
                else :
                    dev=1
                self.openList.append([nouvOrdre,pere,[],taquin_temp,self.numCaseVide(taquin_temp),dev])
                if self.testBut(taquin_temp) == 1:                              #Si le but est atteind
                    butAtteind = 1
                #print(self.openList)
                compt = compt+1
            node = node+1
            self.noeudList.append(node) 
        #print(self.openList)
        papa=self.openList[-1][pEre]                                            #On recupere le pere de but
        #print("papafinal",papa)
        self.finalList.append(self.openList[-1][jEu])
        while papa != 1:                                                        #tant que papa n'est pas la racine de l'arbre
            #print("papa",papa)
            self.finalList.append(self.openList[papa-1][jEu])
            papa=self.openList[papa-1][pEre]
        self.finalList.append(self.taquinInitial)    
        self.finalList.reverse()                                                #On renverse le resultat final pour aller dans le bon sens
        return self.finalList

    def numCaseVide(self,taquin):
        "Renvoi la position de zero (entier)"
        for i in range(0,len(taquin),1):
            if taquin[i]==0:
                return i

    def deplacement(self,posz):
        "Renvoi les possibilités de deplacement(liste d'entier)"
        return depl[posz]

    def noeudATraiter(self,node):
        "Defini le noeud courant a traiter(entier)"
        dev = self.openList[node-1][dEv]
        if dev == 0:
            return node+1
        else :
            return node    

    def testBut(self,taquin):
        "Verifie si le but est atteint(entier[0,1])"
        if taquin == taquin_final:
            return 1
        else :
            return 0

    def testExist(self,taquin):
        "Verifie si le jeu est deja en memoire(entier[0,1])"
        for i in range (0,len(self.openList),1):
            if self.openList[i][jEu] == taquin :
                return 1
            else :
                return 0

#Programme test
taquin_final = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
depl = {0:[1,4],1:[2,5,0],2:[3,6,1],3:[7,2],4:[5,8,0],5:[6,9,4,1],6:[7,10,5,2],7:[11,6,3],8:[9,12,4],9:[10,13,8,5],10:[11,14,9,6],11:[15,10,7],12:[13,8],13:[14,12,9],14:[15,13,10],15:[14,11]}

taq = Taquin(200,240)
taq.mainloop()

A voir également

Ajouter un commentaire Commentaires
Messages postés
3
Date d'inscription
jeudi 28 janvier 2010
Statut
Membre
Dernière intervention
11 décembre 2011

Pas de quoi, ce fut très enrichissant la lecture de ton programme.
je suis impatient de voir ton prochaine oeuvre, a bientôt.
Messages postés
5
Date d'inscription
mercredi 21 juillet 2010
Statut
Membre
Dernière intervention
11 décembre 2011

effectivement ca marche
je débute en programmation avec le livre de gerard swinnen
il est très pédagogique

je te remercie ezleq d'avoir pris le temps de me répondre et de me corriger.

mon prochain programme sera un grand classique:
bataille navale avec un pc linux et l'autre windows toujours sur python3

a plus et bonnes fêtes de navidad.
Messages postés
3
Date d'inscription
jeudi 28 janvier 2010
Statut
Membre
Dernière intervention
11 décembre 2011

Ci le return juste après la boucle "for"

for...
if self.openList[i][jEu] == taquin :
print("jeu",i," ",self.openList[i][jEu])
return 1
return 0
Messages postés
5
Date d'inscription
mercredi 21 juillet 2010
Statut
Membre
Dernière intervention
11 décembre 2011

tu as completement raison ezleq
je n'avais pas vu

donc pour que ca marche:
def testExist(self,taquin):
"Verifie si le jeu est deja en memoire(entier[0,1])"
for i in range (0,len(self.openList),1):
if self.openList[i][jEu] == taquin :
print("jeu",i," ",self.openList[i][jEu])
return 1

sans le return0
c'est ca?
Messages postés
3
Date d'inscription
jeudi 28 janvier 2010
Statut
Membre
Dernière intervention
11 décembre 2011

bonjour,

Trés jolie travail en somme. Cependant, quant tu fait le testExist tu ne compare l'élément qu'au premier élément?

Cordialement ezleq.
Afficher les 6 commentaires

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (fredericfabry)