#################################################################################
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")