fredericfabry
Messages postés5Date d'inscriptionmercredi 21 juillet 2010StatutMembreDernière intervention11 décembre 2011
-
26 nov. 2011 à 17:39
fredericfabry
Messages postés5Date d'inscriptionmercredi 21 juillet 2010StatutMembreDernière intervention11 décembre 2011
-
3 déc. 2011 à 20:54
Bonjour
je me suis lance dans la resolution du probleme du taquin (puzzle) de4*4
mon programme donne le resultat mais je ne suis pas content car j'ai un problème d'affichage autour de la ligne de codes n°63
je demande un peu d'aide car j'apprend presque tout seul(merci internet)
je vous donne le code:
#! /usr/bin/python3
# -*- coding:Utf8 -*-
# en construction
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"
res=[]
taquin_m=taquin_final[:]
for i in range(0,len(taquin_final),1):
l=randrange(len(taquin_m))
res.append(taquin_m[l])
del taquin_m[l]
self.taquin=res[:]
#pour les tests
self.taquin=[1,2,3,7,0,5,6,11,4,9,10,15,8,12,13,14]
self.afficher(self.taquin)
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")
print("res",res)
for i in range (0,len(res),1):
self.afficher(res[i])
print("coup",i," : ",res[i])
fin=time.time() + 5
while time.time() < fin:
self.afficher(res[i]) #pas d'affichage
pass
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]))
def quitter(self):
"Quitter"
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()
fredericfabry
Messages postés5Date d'inscriptionmercredi 21 juillet 2010StatutMembreDernière intervention11 décembre 2011 3 déc. 2011 à 20:54
Bon je remerci les forums
je poste mon projet qui fonctionne comme je veux:
#! /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()