import random

tab = [5, 3, 8, 0, 1, 2, 7, 6, 4]
expr = tab == [i for i in range(9)]

class Taquin:
    def __init__(self):
        self.tab = [0, 1, 2, 3, 4, 5, 6, 7, 8]
        self.pile = Pile()
        self.mode_resolution = False
        
    def est_gagnant(self):
        return self.tab == [i for i in range(9)]
    
    def indice(self, numero):
        assert type(numero) == int, 'numero doit être entier'
        assert 0 <= numero < 9, 'numero de case non valide'
        i = 0
        while self.tab[i] != numero and i < len(self.tab):
            i = i + 1
        return i
    
    def est_possible(self, numero):
        assert type(numero) == int, 'numero doit être entier'
        assert 0 <= numero < 9, 'numero de case non valide'
        i = self.indice(numero)
        j = self.indice(0)
        return (i == j - 1 and i % 3 != 2) or (i == j + 1 and i % 3 != 0) or (i == j - 3) or (i == j + 3)
    
    def jouer(self, numero):
        if self.est_possible(numero):
            i = self.indice(numero)
            j = self.indice(0)
            self.tab[i] = numero
            self.tab[j] = 0
            if not self.mode_resolution:
                if self.pile.est_vide():
                    self.pile.empiler(numero)
                else:
                    precedent = self.pile.depiler()
                    if numero != precedent:
                        self.pile.empiler(precedent)
                        self.pile.empiler(numero)
                        
    
    def coups_possibles(self):
        return [i for i in range(9) if self.est_possible(i)]
    
    def melanger(self, n):
        precedent = None
        i = 0
        while i < n:
            possibilites = self.coups_possibles()
            choix = random.choice(possibilites)
            if choix != precedent:
                self.jouer(choix)
                precedent = choix
                i = i + 1
    
    def resoudre(self):
        self.mode_resolution = True
        while not self.est_gagnant():
            numero = self.pile.depiler()
            self.jouer(numero)
            print("coup joué :", numero)

class Pile:
    def __init__(self):
        self.tab = []
    
    def est_vide(self):
        return len(self.tab) == 0
    
    def empiler(self, element):
        self.tab.append(element)
    
    def depiler(self):
        assert not self.est_vide(), 'la pile est vide'
        return self.tab.pop()