Bonjour
je me suis lancé dans la resolution du taquin 4*4, mais en voulant afficher les reultats dans mon interface tkinter j'ai quelques problèmes.
notament autour de la ligne 63 (commenté par : pas d'affichage)
je desire donc un oeil neuf sur le sujet

programme en python3
editeur geany
OS ubuntu 10.10

#! /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()

J'ai pas le courage de lire et de tester le code... Peux tu détailler ce que tu attends du programme et ce qui se passe à l'exécution du code?

Mon code prend une liste ligne 46 qui est une position initiale du taquin
il fabrique un arbre de recherche mémorisé dans self.openlist
les resultats sont enregistré dans une liste de la forme:
[numero du noeud,liste des noeuds fils,nouveau taquin,position du zero(piece vide pour le mouvement),Il existe deja un taquin dans l'arbre (0 ou 1)]
les differentes evolutions du taquin pour arriver au resultat sont memorisé dans self.finalListe
ca ca marche

ce qui ne marche pas est l'affichage des differentes evolution du taquin de la ligne 58 a 65
je desire un affichage toute les 5 sec pour montrer l'evolution mais il m'affiche le debut puis la fin sans passer par les positions intermediaires.

le problème se situe donc entre les lignes 58 et 65.

Bonjour,
C'est normal que cela ne fonctionne pas. Pendant tes boucles while le mainloop de tkinter est bloquer, et aucune mise à jour graphique ne s'effectue. Tes évènements sont ajouter à la queue et son exécutés seulement à la fin de tes while (tous en même temps).

Pour ce genre de problème tu peux créer une méthode récursive avec la méthode w.after ( delay_ms, callback=None, *args ) de tkinter, qui permet de faire un timer.

Voici un exemple:

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)
        self.afficherResult(res)
        

def afficherResult(self, res, i=1):
    taquin = res.pop(0)
    self.afficher(taquin)
    print("coup",i," : ",taquin)
    if res:
        self.after(1000, self.afficherResult, res, i+1)
    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]))

Par contre, l'application ne trouve jamais de solution, je n'ai donc pas réellement tester cette méthode.

Merci beaucoup nyko77
je bloquais depuis quelque temps sur ce probleme
je n'ai pas tout compris mais je pioche
j'y arriverais
merci encore