# Resolving Sudoku, by Julian Coccia (http://julian.coccia.com)
# Published under GNU General Public License GPL (http://www.gnu.org/copyleft/gpl.html)
#
# Enter your matrix here:
problema=(
(0,2,0,6,0,3,0,0,0), 
(1,8,5,0,7,0,0,0,0),
(0,4,3,8,0,0,0,0,0), 
(3,0,7,0,0,0,0,0,6), 
(0,6,0,0,0,0,0,9,0),
(8,0,0,0,0,0,1,0,5), 
(0,0,0,0,0,9,2,4,0), 
(0,0,0,0,5,0,3,7,8),
(0,0,0,1,0,2,0,6,0))

matriz = [0]*9
for x in range(9):
     matriz[x] = [0] * 9
     for y in range(9):
	     matriz[x][y] = problema[x][y]

parcial = [0]*9

def limpiaparcial():
	for x in range(9):
	     parcial[x] = [0] * 9
	     for y in range(9):
		     parcial[x][y] = [0] * 9

def mostrar():
	for x in range(0,9,+1):
		linea=""
		for y in range(0,9,+1):
			linea=linea+str(matriz[x][y])
		print linea

def mostrarev():
	for x in range(0,9,+1):
		linea=""
		for y in range(0,9,+1):
			linea=linea+str(parcial[x][y])
		print linea


def aplicar():
	for x in range(0,9,+1):
		for y in range(0,9,+1):
			if (parcial[x][y][1]==0):
				if matriz[x][y]==0:
					matriz[x][y]=parcial[x][y][0]
	limpiaparcial()

def evaluar(x,y):

	indice=0
	for i in range(1,10,+1):
		existe=0
		for xx in range(0,9,+1):
			if matriz[xx][y]==i:
				existe=1
				xx=99
		for yy in range(0,9,+1):
			if matriz[x][yy]==i:
				existe=1
				xx=99
		xa=(((x/3)+1)*3)-3
		ya=(((y/3)+1)*3)-3
		for yy in range(ya,ya+3,+1):
			for xx in range(xa,xa+3,+1):
 				if matriz[xx][yy]==i: existe=1

		if not existe: 
			if matriz[x][y]==0:
				parcial[x][y][indice]=i
				indice=indice+1


def evaluartodos():
	for x in range(0,9,+1):
		for y in range(0,9,+1):
			evaluar(x,y)


limpiaparcial()

print "Problema:"
mostrar()

for i in range(0,81,+1):
	evaluartodos()
	aplicar()	
	todavia=0
	for x in range(0,9,+1):
		for y in range(0,9,+1):
			if matriz[x][y]==0:
				todavia=1
	if not todavia:
		print "Solucion (resuelto en",i,"pasadas):"
		break

mostrar()