diff --git a/lab6/PSC.py b/lab6/PSC.py
index f5883b6..aa41b06 100644
--- a/lab6/PSC.py
+++ b/lab6/PSC.py
@@ -22,6 +22,10 @@
 ##contient les solutions de l'algorithme
 SOLUTION=[]
 
+##applique l'algorithme de Variable Ordering
+def variableOrdering():
+	NOEUDS.sort()
+
 ##retourne toutes les contraintes unaires pour un noeud donnne
 ##@param noeud le noeud
 def retourneContraintesUnaires(noeud):
@@ -32,18 +36,49 @@
 	return contraintes
 
 ##retourne toutes les contraintes binaires pour deux noeuds donnnes
-##@param noeud1 le noeud 1
-##@param noeud2 le noeud 2
-##@ret toutes les contraintes bineaires ente n1 et n2
+##@param noeud1 le noeud de depart de la contrainte
+##@param noeud2 le noeud d'arrive de la contrainte
+##@ret toutes les contraintes bineaires ente n1 -> n2
 def retourneContraintesBinaires(noeud1,noeud2):
 	contraintes=[]
 	for a in ARCS:
-		if (a.refContrainte.depart==noeud1.refVar and a.refContrainte.arrive==noeud2.refVar) or (a.refContrainte.depart==noeud2.refVar and a.refContrainte.arrive==noeud1.refVar):
+		if (a.refContrainte.depart==noeud1.refVar and a.refContrainte.arrive==noeud2.refVar):
 			if a.refContrainte not in contraintes:
 				contraintes.append(a.refContrainte)
 	return contraintes
 
+##verifie si deux noeud ayant chacun une valeur sont consitant avec les contraintes entre ces deux neouds
+##@param n1 le noeud 1
+##@param n2 le noeud 2
+##@param contraintes contraintes entre n1 et n2
+##@ret true <=> consistant; else False
+def consistant(n1,n2,contraintes):
+	if len(contraintes)==0:
+		return True
+	touteVraie = lambda x, y :  x and y
+	resultat=map(libPSC.ContrainteBinaire.estValide, contraintes)
+	const = reduce(touteVraie,resultat)
+	return const
+	
 
+##verifie la consistance des varibles PAS ENCORE instantiee
+##@param n1 le noeud 1 instantiee
+##@param n2 le noeud a verifier si consitent,
+##@param containtes les contraintes entre n1 et n2
+def consistanceFuture(n1,n2,contraintes):
+	if len(contraintes)==0:
+		return True
+	touteVraie = lambda x, y :  x and y
+	n2.refVar.enleveDuLabel(n1.refVar.valeur)
+	resultat=map(libPSC.ContrainteBinaire.estPossibleAvecLabel, contraintes)
+	const = reduce(touteVraie,resultat)
+	return const
+   
+	
+##reinitialise le label de tous les variables
+def initLabelDesVariables():
+	for n in NOEUDS:
+		n.refVar.initLabel()
 
 ##affiche la solution avec queques informations utile
 ##@param algo le nom de l'algo
@@ -56,13 +91,28 @@
 ##@param k la pronfondeur actuelle
 def afficheNbIteration(algo,k):
 	print algo,": Ieration:=",ITERATION," pronfondeur actuelle:=",k ,"et",libPSC.NBCONTRAINTE," contraintes verifiees"
+
+
+##retourne le contenu des label de tous les noeuds dans un tableau
+def retournelabels():
+	labels=[]
+	for n in NOEUDS:
+		labels.append(copy.deepcopy(n.refVar.label))
+	return labels
+
+##met a jour les labels de tous les noeuds
+##@param labels les nouveau labels
+def metAJourlabels(labels):
+	for i in range(0,len(NOEUDS)):
+		 NOEUDS[i].refVar.label=copy.deepcopy(labels[i])
+
 			
 ##gere tous les noeuds dans NOEUDS
 class Noeuds:
 
 	##initialise le tableau de noeuds	
 	def __init__(self):
-		NOEUDS=[]
+		del NOEUDS[:]
 
 	##retourne le noeud referencant le variable ayant un nom=nom
 	##@param nom le nom de la variable
@@ -82,11 +132,22 @@
 		for n in NOEUDS:
 			n.consistanceDuNoeud(retourneContraintesUnaires(n));  
 
+	##retourne une liste d'instances initialisee a -1
+	##utilise dans le backtrack et forward checking
+	##@ret [-1,...,-1]
+	def instances(self):
+		inst=[]
+		for n in NOEUDS:
+			inst.append(-1)
+		return inst
+
 	##affiche tous les noeuds
 	def __str__(self):
+		counter=1
 		str = "Noeuds\n"
 		for n in NOEUDS:
-			str+="\t1. "+ n.__str__()+"\n"
+			str+="\t" +n.__str__()+"\n"
+			counter+=1
 		return str
 
 
@@ -95,7 +156,7 @@
 
 	##initialise le tableau des ARCS   
 	def __init__(self):
-		ARCS=[]
+		del ARCS[:]
 
 	##ajoute un arc a la lite
 	def ajouteArc(self,arc):
@@ -146,14 +207,12 @@
 		initialise=False
 		
 	ITERATION=ITERATION+1
-
+	afficheNbIteration(algo,k)
 	if k >= len(NOEUDS):
-		if touteLesSolutions:
-			SOLUTION = SOLUTION + instances
-		else:
-			SOLUTION = [instances]
-			afficheSolution(algo,instances)
-			return SOLUTION
+		afficheSolution(algo,instances)
+		SOLUTION.append(copy.deepcopy(instances))
+		if not touteLesSolutions:
+			return instances 
 	else:
 		n = NOEUDS[k]
 		for x in n.refVar.domaine:
@@ -164,15 +223,12 @@
 					consistant = False
 			if consistant:
 				instances[k] = x
-				rest = backtrack(instances, k+1, touteLesSolutions)
+				rest = backtrack(instances, k+1, touteLesSolutions, initialise)
 				if rest != ECHEC:
 					return rest
 
 	return ECHEC			
 
-def initLabelDesVariables():
-	for n in NOEUDS:
-		n.refVar.label = n.refVar.domaine
 
 ## Algorithme de Forward Chekcing simple 
 ## @param instances les n variables; rempli jusqu'a k
@@ -186,7 +242,7 @@
 	global SOLUTION
 	if touteLesSolutions==None:
 		touteLesSolutions=False
-	if initialise==None:
+	if initialise==None or initialise==True:
 		ITERATION=0
 		SOLUTION=[]
 		libPSC.NBCONTRAINTE=0
@@ -195,36 +251,28 @@
 		
 	ITERATION=ITERATION+1
 	afficheNbIteration(algo,k)
-
-	# TODO
-	if k >= len(NOEUDS):
-		if touteLesSolutions:
-			SOLUTION = SOLUTION + instances
-		else:
-			SOLUTION = [instances]
-			afficheSolution(algo,instances)
-			return SOLUTION
+	if k>(len(NOEUDS)-1):
+		afficheSolution(algo,instances)
+		SOLUTION.append(copy.deepcopy(instances))
+		if not touteLesSolutions:
+			return instances
+		
 	else:
-		n = NOEUDS[k]
-		for x in n.refVar.label:
-			# TODO
-			n.refVar.metAJourValeur(x)
-			consistant = True
-			for i in range(k+1, len(NOEUDS)):
-				# TODO
-				if not reduce(lambda x,y: x and y.estValide(), retourneContraintesBinaires(n, NOEUDS[i]), True):
-					# TODO
-					consistant = False
-			if consistant:
-				instances[k] = x
-				rest = forwardChecking(instances, k+1, touteLesSolutions, True)
-				if rest != ECHEC:
+		noeud = NOEUDS[k]
+		labels = retournelabels()
+		for d in noeud.refVar.label: ##domaine:
+			noeud.refVar.metAJourValeur(d)   
+			consistantFuturOK=True
+			for i in range(k+1,len(NOEUDS)):
+				##print "\t\tVerification de la consitance da la valeur", d, "avec la variable non instantie",NOEUDS[i] 
+				if not consistanceFuture(noeud,NOEUDS[i],retourneContraintesBinaires(noeud,NOEUDS[i])):
+					consistantFuturOK=False
+			if consistantFuturOK:
+				instances[k]=d
+				rest = forwardChecking(instances,k+1,touteLesSolutions,initialise)
+				if rest!= ECHEC:
 					return rest
-			for i in range(k+1, len(NOEUDS)):
-				# TODO
-				NOEUDS[i].refVar.label = NOEUDS[i].refVar.domaine
-
-
+			metAJourlabels(labels)
 	return ECHEC
 
 #execfile("testConsistance.py")
diff --git a/lab6/libPSC.py b/lab6/libPSC.py
index 784ecaa..6550e2e 100644
--- a/lab6/libPSC.py
+++ b/lab6/libPSC.py
@@ -17,7 +17,24 @@
 		self.nom=nom
 		self.domaine=domaine
 		self.valeur=-1
-		
+		self.label=[]
+		self.initLabel()
+
+	
+	##reinitialise le contenu de l'attribut label
+	def initLabel(self):
+		self.label=copy.deepcopy(self.domaine)
+
+	##efface du label la valeur d et stock d dans self.efface
+	##@param d la veleur de domaine
+	def enleveDuLabel(self,d):
+		if d in self.label:
+			self.label.remove(d)
+
+	##met a jour le label
+	##@param label le nouveau label
+	def metAJourValeur(self,label):
+		self.label=label 
 		
 	##met a jour la valeur
 	##@param valeur la nouvelle valeur
@@ -187,6 +204,16 @@
 	def __init__(self,variable):
 		self.refVar=variable
 
+	##compare deux noeuds par rapport à leur taille de domaine
+	def __cmp__(self,n2):
+		a = len(self.refVar.domaine)
+		b = len(n2.refVar.domaine)
+		if a == b:
+			return 0
+		if a < b:
+			return -1
+		if a > b:
+			return 1
 
 	##fait la consistance du noeud
 	##@param contraintes la liste de contraintes unaires pour ce noeud
diff --git a/lab6/sudoku.py b/lab6/sudoku.py
new file mode 100644
index 0000000..cecfe6a
--- /dev/null
+++ b/lab6/sudoku.py
@@ -0,0 +1,287 @@
+#################################################################################
+print "Chargement du module variable et noeud pour PSC"
+print "\t@version: 1.0  date: 1/05/2006 modified by the vincent.schickel-zuber@epfl.ch"
+print "\t@author: vincent.schickel-zuber@epfl.ch date: 1/05/2006"
+print "\t@copyright: EPFL-IC-IIF-LIA 2006"
+#################################################################################
+
+import copy
+import libPSC
+import PSC
+
+##le symbol vide dans la grille = 0
+X = 0
+
+##le domaine des variables
+DOMAINE=range(1,10)
+
+##contient l'ennonce de depart
+PROBLEME=[]
+##defini la grille du sudoku
+GRILLE=[[]]
+##nombre de collone de la grille
+NBCOL=9
+##nombre de ligne de la grille
+NBLGN=9
+
+NOEUDS = PSC.Noeuds()
+ARCS =  PSC.Arcs()
+
+##taille des sous grille
+TAILLESOUSGRILLE=3
+
+ ##retourne la position de la ss_grille correspondant a la position absolue
+##@pos la position absolue
+def retournePosSSGille(pos):
+    return pos/TAILLESOUSGRILLE
+
+##retourne la position DANS dans la ss_grille correspondant a la position absolue
+##@pos la position absolue
+def retournePosINSSGille(pos):
+    return pos%TAILLESOUSGRILLE 
+
+
+## verifie si un symbole passe en parametre = symbole vide
+def estVide(symb):
+    return symb==X
+
+##definit une sous grille (qui fera partie de la grille)
+class SSGrille:
+
+   
+    ##constructeur
+    ##@param posL la position sur la ligne[0..2]
+    ##@param posC la position dans la colonne[0..2]
+    def __init__(self, posL,posC):
+        global X
+        global DOMAINE
+        self.posL=posL
+        self.posC=posC
+        self.ssgrille=[]
+        self.notPossible=[]
+        ##self.domaine=copy.deepcopy(DOMAINE)
+        for i in range(0,TAILLESOUSGRILLE):
+            self.ssgrille.append([])
+            
+        for i in range(0,TAILLESOUSGRILLE):
+            for j in range(0,TAILLESOUSGRILLE):
+                id="v["+str(self.posL)+","+str(self.posC)+"]["+str(i)+","+str(j)+"]"
+                noeud = libPSC.Noeud(libPSC.Variable(id,DOMAINE))
+                self.ssgrille[i].append(noeud)
+                NOEUDS.ajouteNoeud(noeud)
+
+    ##met a jour la valeur du noeud dans la sous grille a un endroit specifique
+    ##@param valeur la valeur de la variable
+    ##@param domaine le domaine de la variable
+    ##@param posX la position en X
+    ##@param posY la position en Y
+    def ajouteNoeud(self, valeur, domaine , posX,posY):   
+        global X
+        self.ssgrille[posX][posY].refVar.metAJourValeur(valeur)
+        if valeur in DOMAINE:
+            ##self.domaine.remove(valeur)
+            self.ssgrille[posX][posY].refVar.domaine=[valeur]
+            self.notPossible.append(valeur)
+        else:
+            self.ssgrille[posX][posY].refVar.domaine=copy.deepcopy(DOMAINE)         
+
+    ##retourne la coordonne absolue d'un element dans la grille
+    ##@param x la position en axe x dans la sous-grille
+    ##@param y la position en axe y dans la sous-grille
+    ##@ret (x_abolue,y_abolue)
+    def positionAbolue(self,x,y):
+        global TAILLESOUSGRILLE
+        posx=self.posL*TAILLESOUSGRILLE+x
+        posy=self.posC*TAILLESOUSGRILLE+y
+        return (posx,posy)
+
+    ##retourne la valeur a une position donnee
+    def valeur(self,posX,posY):
+        return self.ssgrille[posX][posY].refVar.valeur
+
+    ## genre toutes les contraintes de groupes
+    def genereContraintesSSGrille(self):
+        global NBLGN
+        for i in range(0,TAILLESOUSGRILLE):
+            for j in range(0,TAILLESOUSGRILLE):                
+                for k in range(0,TAILLESOUSGRILLE):
+                    for l in range(0,TAILLESOUSGRILLE):
+                        if i<>k and j<>l:
+                            n1=self.ssgrille[i][j]
+                            n2=self.ssgrille[k][l]
+                            c=libPSC.ContrainteBinaire(n1.refVar,"<>",n2.refVar)
+                            c2=libPSC.ContrainteBinaire(n2.refVar,"<>",n1.refVar)
+                            ARCS.ajouteArc(libPSC.Arc(c2))
+                            ARCS.ajouteArc(libPSC.Arc(c))     
+
+##definit la grille, qui est faite de 9 sous grille        
+class Grille:    
+
+    ##constructeur
+    ##initilaise la variable globale GRILLE
+    def __init__(self):
+        self.init()
+
+    ##initialise la grille avec le contenu du probleme
+    def init(self):
+        global GRILLE
+        global PROBLEME
+        global TAILLESOUSGRILLE
+        global GRILLE
+        global NBLGN
+        global NBCOL
+        del GRILLE[:]
+        for i in range(0,TAILLESOUSGRILLE):
+            GRILLE.append([])
+
+        ##remplit la grille de sous-grille
+        ssgrillecol=0
+        ssgrillelgn=0            
+        for i in range(0,TAILLESOUSGRILLE):
+            for j in range(0,TAILLESOUSGRILLE):
+                GRILLE[i].append(SSGrille(i,j))
+        
+
+        ##remplit les sous-grille                  
+        ssgrillecol=0
+        ssgrillelgn=0
+        for i in range(0,NBLGN):
+            ssgrillecol=0
+            if i>0 and i%TAILLESOUSGRILLE==0:
+                ssgrillelgn+=1
+            for j in range(0,NBCOL):
+                if j>0 and j%TAILLESOUSGRILLE==0:
+                    ssgrillecol+=1
+                if not (PROBLEME[i][j]==X):
+                    GRILLE[retournePosSSGille(i)][retournePosSSGille(j)].ajouteNoeud(PROBLEME[i][j],[PROBLEME[i][j]],retournePosINSSGille(i),retournePosINSSGille(j))
+                else:
+                    GRILLE[retournePosSSGille(i)][retournePosSSGille(j)].ajouteNoeud(PROBLEME[i][j],DOMAINE,retournePosINSSGille(i),retournePosINSSGille(j))
+                ##GRILLE[retournePosSSGille(i)][retournePosSSGille(j)].ssgrille[retournePosINSSGille(i)][retournePosINSSGille(j)].refVar.metAJourValeur(PROBLEME[i][j])
+                self.retourneNoeud(i,j).refVar.metAJourValeur(PROBLEME[i][j])
+      
+
+    ##retourne la grille en string
+    def __str__(self):
+        global NBLGN
+        global NBCOL
+        global GRILLE
+        ssgrillecol=0
+        ssgrillelgn=0
+        ligne=""
+        for i in range(0,NBLGN):
+            ssgrillecol=0
+            if i>0 and i%TAILLESOUSGRILLE==0:
+                ssgrillelgn+=1
+            ligne+="\t"
+            for j in range(0,NBCOL):
+                if j>0 and j%TAILLESOUSGRILLE==0:
+                    ssgrillecol+=1
+                ligne+=str(GRILLE[retournePosSSGille(i)][retournePosSSGille(j)].valeur(retournePosINSSGille(i),retournePosINSSGille(j)))+" "    
+            ligne+="\n"
+        return ligne
+
+    ##retourne un noeud se trouvant une position en valeur absolue
+    ##@param posX la position absolue X
+    ##@param posY la position absolue Y
+    def retourneNoeud(self,posX,posY):
+        n=GRILLE[retournePosSSGille(posX)][retournePosSSGille(posY)].ssgrille[retournePosINSSGille(posX)][retournePosINSSGille(posY)]
+        return n
+
+    ## genere toutes les contraintes de lignes
+    def genereContraintesLignes(self):
+        global NBLGN
+        for i in range(0,NBCOL):
+            for j in range(0,NBLGN):
+                for k in range(j+1,NBLGN):
+                    n1=self.retourneNoeud(j,i)
+                    n2=self.retourneNoeud(k,i)
+                    c=libPSC.ContrainteBinaire(n1.refVar,"<>",n2.refVar)
+                    c2=libPSC.ContrainteBinaire(n2.refVar,"<>",n1.refVar)
+                    ARCS.ajouteArc(libPSC.Arc(c2))
+                    ARCS.ajouteArc(libPSC.Arc(c))
+                    
+    ## genere toutes les contraintes de colonne
+    def genereContraintesColonnes(self):
+        global NBLGN
+        for i in range(0,NBLGN):
+            for j in range(0,NBCOL):
+                for k in range(j+1,NBCOL):
+                    n1=self.retourneNoeud(i,j)
+                    n2=self.retourneNoeud(i,k)
+                    c=libPSC.ContrainteBinaire(n1.refVar,"<>",n2.refVar)
+                    c2=libPSC.ContrainteBinaire(n2.refVar,"<>",n1.refVar)
+                    ARCS.ajouteArc(libPSC.Arc(c2))
+                    ARCS.ajouteArc(libPSC.Arc(c))                    
+
+    ##genere toutes les contraintes de sous-grille
+    def genereContraintesSSGrilles(self):
+        for i in range(0,TAILLESOUSGRILLE):
+            for j in range(0,TAILLESOUSGRILLE):
+                GRILLE[i][j].genereContraintesSSGrille()
+## initialise le jeu (la grille) et trouve la solution
+def run(algo,grille):
+    print "|+| Chargement du probleme"
+    global PROBLEME
+    if grille=="A":
+        PROBLEME=[[9,X,X,X,X,X,X,X,2], 
+               [3,X,7,1,X,X,4,X,8],
+               [X,1,X,X,5,4,X,6,X],
+               [X,X,1,X,X,X,X,7,X],
+               [X,X,4,X,X,X,9,X,X],
+               [X,2,X,X,X,X,8,X,X],
+               [X,8,X,3,2,X,X,4,X],
+               [7,X,3,X,X,6,2,X,1],
+               [4,X,X,X,X,X,X,X,5]]
+    elif grille=="B":
+        PROBLEME=[[1,X,4,X,X,8,X,5,2], 
+               [8,X,X,4,X,X,9,X,X],
+               [X,5,X,X,9,1,X,X,8],
+               [3,X,2,7,X,5,X,1,X],
+               [X,X,6,X,X,X,5,X,X],
+               [X,7,X,1,X,2,8,X,4],
+               [7,X,X,3,8,X,X,9,X],
+               [X,X,5,X,X,4,X,X,6],
+               [9,6,X,5,X,X,1,X,3]]
+    else:
+        print "|-| Grille" ,grille,"pas definit"
+    
+    global NOEUDS
+    global ARCS
+    NOEUDS = PSC.Noeuds()
+    ARCS = PSC.Arcs()
+    
+    print "|+| Initialisation de la grille"
+    grille = Grille()
+    print grille
+
+    print "|+| Ajoute les contraintes"
+    grille.genereContraintesLignes()
+    grille.genereContraintesColonnes()
+    grille.genereContraintesSSGrilles()
+    
+    print "|+| Fait la consitance des noeuds"    
+    NOEUDS.consistanceDesNoeuds()
+    ##print NOEUDS
+
+    print "|+| Fait la consitance des arcs"
+    ARCS.consistanceDesArcs()
+    ##print ARCS
+    print grille
+
+    PSC.variableOrdering()
+        
+    if algo=="FC":
+        sol=PSC.forwardChecking(NOEUDS.instances(),0,False,True)
+    else:
+       sol=PSC.backtrack(NOEUDS.instances(),0,False,True)
+    print grille
+
+## genre toutes les contraintes de lignes
+## @param grille l'objet
+
+
+    
+#################################################################################################################    
+##run
+run("FC","A")
+
diff --git a/lab6/test.py b/lab6/test.py
index 18f35e8..91e3ebe 100644
--- a/lab6/test.py
+++ b/lab6/test.py
@@ -40,8 +40,9 @@
 arcs.consistanceDesArcs()
 print noeuds
 
-sol=backtrack([-1,-1,-1],0,True)
-print "Solution trouv�e avec bt:=", SOLUTION
-
-sol=forwardChecking([-1,-1,-1],0,True)
+##sol=backtrack([-1,-1,-1],0,True)
+##print "Solution trouv�e avec bt:=", SOLUTION
+variableOrdering()
+print noeuds
+sol=forwardChecking([-1,-1,-1],0,True,True)
 print "Solution trouv�e avec fc:=", SOLUTION