"""
Sujet capes 2017
"""


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

 
 
 
# 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 chiffres_possibles(L,i,j) :
	"""
	retourne la liste des valeurs qui ne sont pas déjà présentes
	dans la ligne, le carré ou la colonne de la case (i,j)
	"""
	
	# valeurs dans la ligne i :
	ligne = [ L[i][col] for col in range(9) if L[i][col] != VIDE and col != j]
	# valeurs dans la colonne j :
	colonne = [ L[lig][j] for lig in range(9) if L[lig][j] != VIDE and lig != i]
	# valeurs dans le carré de (i,j)
	k = 3*(i//3)+(j//3)  # numéro du carré
	carre = [ L[lig][col] for lig in range(9) for col in range(9) if 3*(lig//3)+(col//3) == k and L[lig][col] != VIDE and (lig, col) != (i,j) ]
	# cumul 
	cumul = ligne + colonne + carre
	return [ v for v in VALEURS if v not in cumul ]


 
	
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_possibles(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])
	
	
	
 

if __name__ == "__main__" :
	 
	solution_sudoku(G3)
	affiche_grille(G3)
	print()