# (C) BL-APMEP, le 03/09/2014 en Python 3.2
from lycee import *
from pylab import *

# ***************************************************************
#                 Fonction AfficheGrille                        *
# Cette fonction affiche la grille dans une fenêtre graphique   *
# Elle est donnée et peut être utilisée comme une "boîte noire" *
# ***************************************************************
def AfficheGrille():
    repere.axis([-0.1,9.1,-0.1,9.1])
    xticks(arange(0))
    yticks(arange(0))
    for n in range(0,10):
        if n in [0,3,6,9]:
            ep='3'
        else:
            ep='1'
        repere.plot([0,9],[n,n],'k',lw=ep)
        repere.plot([n,n],[0,9],'k',lw=ep)
    for k in range(0,81):
        lig=quotient(k,9)
        col=reste(k,9)
        val=grille[k]
        if val!=0:
            text(col+0.35,8-lig+0.20,val,fontstyle='normal',fontsize=26,fontname='Times New Roman', weight='bold',color='k')
    return

# ********************************************************
# Fonction InitGrille                                    *
# Cette fonction effectue la mise en place des chaînages *
# ********************************************************
def InitGrille():
    global grille, prem, prec, suiv
    prec=[]
    suiv=[]
    for i in range(0,81):
        prec=prec+[0]
        suiv=suiv+[0]
    i=0
    while grille[i]!=0:
        i=i+1
    prem=i
    prec[i]=-1
    while i<81:
        j=i+1
        while ((grille[j]!=0)and(j<81)):
            j=j+1
        if (j==81):
            suiv[i]=-2
        else:
            suiv[i]=j
            prec[j]=i
        i=j
    return

# ****************************************************
# Fonction ListeAuxiliaire                           *
# Cette fonction détermine la liste auxiliaire       *
# respectant les règles S                            *
# ****************************************************
def ListeAuxiliaire(p):
    global grille
    l=quotient(p,9)
    c=reste(p,9)
    lc=3*quotient(l,3)
    cc=3*quotient(c,3)
    pp=9*lc+cc
    listAux=[]
    for i in range(0,9):
        k1=9*i+c
        k2=9*l+i
        k3=pp+9*quotient(i,3)+reste(i,3)
        listAux=listAux+[grille[k1],grille[k2],grille[k3]]
    return listAux

# ********************************************************
# Fonction ChercheCandidat                               *
# Cette fonction rechercherche le premier candidat       *
# respectant les règles S                                *
# ********************************************************
def ChercheCandidat(c):
    global grille
    listAux=ListeAuxiliaire(c)
    v=grille[c]
    ok=False
    while ((v<9) and (not ok)):
        v=v+1
        ok=(v not in listAux)
    if not(ok):
        v=0
    return v

# ********************
# Fonction Sudoku    *
# Module principal   *
# ********************
def Sudoku():
    c=prem
    while (c>=0):
        grille[c]=ChercheCandidat(c)
        if grille[c]==0:
            c=prec[c]
        else:
            c=suiv[c]
    return

# ********************
# Début du programme *
#*********************

# Jeu d'essai
grille=[]
grille=[3,5,0,0,0,2,7,0,0]
grille=grille+[8,9,0,3,0,0,0,0,0]
grille=grille+[0,0,2,0,8,0,0,0,6]
grille=grille+[0,2,0,1,0,0,0,0,4]
grille=grille+[0,0,9,0,0,0,6,0,0]
grille=grille+[6,0,0,0,0,4,0,7,0]
grille=grille+[9,0,0,0,4,0,1,0,0]
grille=grille+[0,0,0,0,0,0,0,2,9]
grille=grille+[0,0,5,6,9,7,0,8,3]

# *************************************************************************
# Désactivez les lignes ci-dessous pour utiliser le jeu d'essai précédent *
# Activez ces lignes pour saisir une nouvelle grille                      *
# *************************************************************************
#for i in range(1,10):
#    mes="Ligne N°"+str(i)+" --> Tapez les valeurs sans espaces, les cases vides étant remplacées par des '0' : "
#    ch=input(mes)
#    print(ch)
#    for j in range(0,9):
#        grille=grille+[int(ch[j])]
# Fin de saisie

grille=grille+[0]
InitGrille()
Sudoku()
AfficheGrille()
repere.show()