"""
Sujet capes 2017
"""

L = [
[0,6,0,0,0,0,2,0,5],
[4,0,0,9,2,1,0,0,0],
[0,7,0,0,0,8,0,0,1],
[0,0,0,0,0,5,0,0,9],
[6,4,0,0,0,0,0,7,3],
[1,0,0,4,0,0,0,0,0],
[3,0,0,7,0,0,0,6,0],
[0,0,0,1,4,6,0,0,2],
[2,0,6,0,0,0,0,1,0]
]


M = [
[2,0,0,0,9,0,3,0,0],
[0,1,9,0,8,0,0,7,4],
[0,0,8,4,0,0,6,2,0],
[5,9,0,6,2,1,0,0,0],
[0,2,7,0,0,0,1,6,0],
[0,0,0,5,7,4,0,9,3],
[0,8,5,0,0,9,7,0,0],
[9,3,0,0,5,0,8,4,0],
[0,0,2,0,6,0,0,0,1]
]

N = [ [ 0 for i in range(9) ] for j in range(9) ]

 
 
 
# la liste des valeurs utilisées pour remplir la grille
VALEURS = (1,2,3,4,5,6,7,8,9)
# valeur pour une case vide :
VIDE = 0




def affiche_grille(L) :
	"""
	Pour afficher les grilles de sudoku à peu près proprement.
	"""
	for i in range(9) :
		for j in range(9) :
			print(L[i][j], end=' ')
		print()
		
		
def ligne_complete(L,i) :
	"""
	Question A2.
	Il y a 9 places dans L[i] : si chacun des entiers entre 1 et 9 est 
	présent, c'est alors que chacun s'y trouve une fois et une seule.
	"""
	for k in VALEURS :
		if k not in L[i] : return False
	return True 
	
def colonne_complete(L,j) :
	"""
	Question A2.
	"""
	colonne = [ L[k][j] for k in range(9) ]
	for v in VALEURS :
		if v not in colonne : return False
	return True 
	
def carre_complet(L,k) :
	"""
	Question A2.
	Pour le carré de numéro k. 
	"""
	carre = [ L[i][j] for i in range(9) for j in range(9) if 3*(i//3)+(j//3) == k ]
	 
	for p in VALEURS :
		if p not in carre : return False
	return True 
	
	
def complet(L) :
	"""
	Question A3.
	"""
	for i in range(9) : 
		if not(ligne_complete(L,i)) or not(colonne_complete(L,i)) or not(carre_complet(L,i)) : 
			return False
	return True
	
	
def ligne(L,i) :
	"""
	Question A4
	"""
	chiffre = []
	for j in range(9) :
		if L[i][j] != VIDE :
			chiffre.append(L[i][j])
	return chiffre
	
	
	
def colonne(L,j) :
	"""
	Question A4
	"""
	return [ L[k][j] for k in range(9) if L[k][j] != VIDE ]
	
	
	
def carre(L,i,j) :
	"""
	Question A6	 
	"""
	icoin = 3 * (i//3)
	jcoin = 3 * (j//3)
	chiffre = []
	for ii in range(icoin, icoin+3) :  
		for jj in range(jcoin, jcoin+3) :
			if L[ii][jj] != VIDE :
				chiffre.append(L[ii][jj])
	return chiffre
	

def carreNumerote(L, k) :
	"""
	Question A6 :
	les carrés ont été numérotés ! Pourquoi ne pas s'en servir !
	"""
	return [ L[i][j] for i in range(9) for j in range(9) if 3*(i//3)+(j//3) == k and L[i][j] != VIDE ]
	 
	
	
def conflit(L,i,j) :
	"""
	Question A7.
	"""
	
	liste = []
	liste.extend(ligne(L,i))
	if L[i][j] != VIDE : liste.remove(L[i][j])
	liste.extend(colonne(L,j))
	if L[i][j] != VIDE : liste.remove(L[i][j])
	liste.extend(carre(L,i,j))
	if L[i][j] != VIDE : liste.remove(L[i][j])
	
	# si on veut supprimer les doublons :
	liste = list(set(liste))
	return liste 
	
	
def chiffres_ok(L,i,j) :
	"""
	Question A8.
	"""
	ok = []
	conflictuel = conflit(L,i,j)
	for k in VALEURS :
		if k not in conflictuel :
			ok.append(k)
	return ok
	
	
def nb_possible(L,i,j) :
	"""
	Question B9
	"""
	return len( chiffres_ok(L,i,j) )
	
	
def un_tour(L) :
	"""
	Question B10
	"""
	changement = False
	for i in range(9) :
		for j in range(9) :
			if L[i][j] == VIDE :
				if nb_possible(L,i,j) == 1 :
					L[i][j] = chiffres_ok(L,i,j)[0]
					changement = True
	return changement


def complete(L):
	"""
	Question B11
	"""
	modif = True
	while modif :
		modif = un_tour(L)
	return complet(L)
		
		



	
	
def case_suivante(pos) :
	"""
	Question C12
	"""
	if pos[1] == 8 :
		if pos[0] < 8 : return [pos[0] + 1, 0]
		else : return [9,0]
	else : return [pos[0], pos[1]+1]
	
	
def backtracking(L,pos) :
	"""
	Question C13
	"""
	if pos == [9,0] : return True
	
	i,j = pos[0], pos[1]
	if L[i][j] != VIDE : return backtracking(L,case_suivante(pos))
	
	for k in VALEURS :
		L[i][j] = k
		if k in chiffres_ok(L,i,j) and backtracking(L,case_suivante(pos)) :
			return True
			
	L[i][j] = VIDE
	return False

def solution_sudoku(L) :
	return backtracking(L,[0,0])
	
	
	
	
def fonction_verif_partieB() :
	complete(M)
	affiche_grille(M)
	print()
	complete(L)
	affiche_grille(L)
	
	

if __name__ == "__main__" :
	solution_sudoku(M)
	affiche_grille(M)
	
	print()
	solution_sudoku(L)
	affiche_grille(L)
	print()
	
	solution_sudoku(N)
	affiche_grille(N)
	print()