Taquin 4*4
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.
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()
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.