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