# -*- coding: utf-8 -*-
"""
Débuté le Thu Nov 19 19:10:40 2015

@author: Pierre-Henri Jondot
"""

from copy import deepcopy

dure = '000032970070045010000800000001060000000000000029000840500620007004000009100009036'

def litGrille(grille):
    """ en argument : un chaine d'une ligne avec 81 chiffres de 0 à 9.
    En sortie, une liste de 9 listes de 9 chiffres... """
    G = []
    for i in range(81):
        if i % 9 == 0:
            G.append([])
        G[-1].append(int(grille[i]))
    return G

def printGrille(g):
    """ en argument : une grille donnée sous la forme d'une liste de listes """
    for i in range(9):
        if i==3 or i==6:
            print('-----------------')
        s = ''
        for j in range(9):
            if j==3 or j==6:
                s += '|'
            elif j > 0:
                s+= ' '
            if g[i][j] == 0:
                s += ' '
            else:
                s += str(g[i][j])
        print(s)

def valeursPossibles(g, i, j):
    if g[i][j] != 0:
        return []
    possibles = list(range(1, 10))
    for k in range(9):
        if g[i][k] in possibles:
            possibles.remove(g[i][k])
        if g[k][j] in possibles:
            possibles.remove(g[k][j])
    i0 = (i // 3) * 3
    j0 = (j // 3) * 3
    for i1 in range(i0, i0 + 3):
        for j1 in range(j0, j0 + 3):
            if g[i1][j1] in possibles:
                possibles.remove(g[i1][j1])
    return possibles

def estComplete(g):
    for l in g:
        if 0 in l:
            return False
    return True

def complete1(grille):
    caseCompletee = True
    while caseCompletee:
        caseCompletee = False
        for i in range(9):
            for j in range(9):
                if len(valeursPossibles(grille, i, j)) == 1:
                    grille[i][j] = valeursPossibles(grille, i, j)[0]
                    caseCompletee = True
    return estComplete(grille)

def resout(g):
    if estComplete(g):
        return True
    mini = 10
    val = []
    for i in range(9):
        for j in range(9):
            poss = valeursPossibles(g, i, j)
            if len(poss) == 1:
                g[i][j] = poss[0]
                return resout(g)
            if len(poss) > 0 and len(poss) < mini:
                val = poss
                mini = len(poss)
                im, jm = i, j
    # il se peut que val soit [] ici, ce qui signifie que la grille est
    # impossible à compléter (d'où le backtracking...)
    for v in val:
        gCopie = deepcopy(g)
        gCopie[im][jm] = v
        if resout(gCopie):
            for i in range(9):
                g[i] = gCopie[i]
            # En procédant comme ci-dessus, on permet de continuer à
            # travailler sur le même objet, ce qui permet d'obtenir
            # la grille complétée...
            return True
    return False


def testeGrilles(fichier):
    f = open(fichier, 'r')
    nbGrilles, resolues = 0, 0
    for ligne in f: # chaque ligne du fichier correspond à une grille
        # on pourrait aussi utiliser readlines() pour lire une fois pour toutes
        # le fichier et ses grilles au lieu de le faire au fur et à mesure.
        g = litGrille(ligne)
        printGrille(g)
        print()
        nbGrilles += 1
        if resout(g): # ou resout, qui correspond à complete2 de l'énoncé
            printGrille(g)
            print()
            resolues += 1
        else:
            print('échec')
    print("nb Grilles " + str(nbGrilles) + " resolues : " + str(resolues))