#!/usr/bin/python

"""
 * Copyright (C) 2005 Varun Hiremath.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.

 * @author Varun Hiremath
 * @version 0.1
"""

BR=[]
assumption=[]
counter=[0]
history=[0]

f=open('sudoku_input','r+')
L=f.readlines()

for i in range(9):
	L[i]=L[i].split(" ")
	L[i][8]=L[i][8][0]
	BR.append([int(k) for k in L[i]])


def columns(BR) :
	Bc=[]
	Tc=[]
	for r in range(9) :
		for c in range(9) :
			Tc.append(BR[c][r])
		Bc.append(Tc)
		Tc=[]
	return	Bc	

def nine_blocks(BR) :

	bb=[]
	Tbb=[]
	for j in range(0,7,3) :
		for k in range(0,7,3) :
			for r in range(j,j+3) :
				for c in range (k,k+3) :
					Tbb.append(BR[r][c])
			bb.append(Tbb)
			Tbb=[]
	return bb

def positions(digit,block,x,y) :
	all_pos=[]
	for r in range(3*x,3*x+3) :
		for c in range(3*y,3*y+3) :
			if BR[r][c] == 0 :
				if valid_pos(digit,block,r,c) :
				    pos=[]
				    pos.append(r)
				    pos.append(c)
				    all_pos.append(pos)
	return all_pos

def valid_pos(digit,block,r,c) :
	import copy
	br = copy.deepcopy(BR)
	bc = columns(br)
	if digit in br[r] or digit in bc[c]:
		return 0
	br[r][c]=digit
	bc[c][r]=digit
	sb = nine_blocks(br)

	check=range(1,10)
	for b in range(9):
		found=0
		if digit not in sb[b]:
			x=b/3
			y=b % 3
			for i in range(3*x,3*x+3):
				for j in range(3*y,3*y+3):
					if digit not in br[i] or digit not in bc[j]:
						found=1
			if not found :
				check[b]=0
				break
	if 0 in check:
		return 0
	else:
		return 1

def all_elements(BR) :
	temp=[]
	for i in range(9): 
		temp=temp+BR[i] 
	return temp

def print_sudoku(a) :
	for i in range(9) :
		print a[i]
	print " "

def make_assumption():
	b=nine_blocks(BR)
	for digit in range(1,10) : 
   	    for block in range (9):
 		    if digit not in b[block]:
				x=block/3
				y=block%3
				pos_obt = positions(digit,block,x,y)
				if len(pos_obt) == 2 :
					counter.append(counter[-1]+1)
					history.append(pos_obt[0])
					assumption.append([pos_obt,digit,block,counter[-1]])
					BR[pos_obt[0][0]][pos_obt[0][1]]=digit
#					print "Assuming Digit :",digit," Block :",block+1
					return
				


print "Input SO-DU-KO"
print_sudoku(BR)

print "Please wait for the output"



all_elem=all_elements(BR)
BC=columns(BR)
Bb=nine_blocks(BR)
	

found=1
while 0 in all_elem and found ==1: 
    found=0
    for digit in range(1,10) : 
 	   	for block in range (9):
 			if digit not in Bb[block]:
 			   	x=block/3
 				y=block % 3
 				pos_obt = positions(digit,block,x,y)
				if len(pos_obt) == 0 :
#					print "Contradiction Digit :",digit," Block :",block+1
#					print "Changing previous assumption"
#					print " "
					assump=assumption.pop()
					while counter[-1]>=assump[3]:
						counter.pop()
						hist=history.pop()
						BR[hist[0]][hist[1]]=0
					counter.append(counter[-1]+1)
					history.append(assump[0][1])
#					print "Digit :",assump[1]," Block :",assump[2]+1
					BR[assump[0][1][0]][assump[0][1][1]]=assump[1]
#					print_sudoku(BR)
					BC=columns(BR)
 					Bb=nine_blocks(BR)
										
 				elif len(pos_obt) == 1 :
					found=1
					counter.append(counter[-1]+1)
					history.append(pos_obt[0])
 					BR[pos_obt[0][0]][pos_obt[0][1]]=digit
 					BC=columns(BR)
 					Bb=nine_blocks(BR)
# 					print "Found Digit :",digit," Block :",block+1
# 					print_sudoku(BR)
    all_elem=all_elements(BR)
    if found==0:
		make_assumption()
		BC=columns(BR)
		Bb=nine_blocks(BR)
#		print_sudoku(BR)
		all_elem=all_elements(BR)
		found=1


print "Final SU-DO-KU"
print_sudoku(BR)

raw_input("Press any key...")