#!/usr/bin/python
import sys
 
'''Solves a sudoku using recursive backtracking
   Licensed under the terms of the GNU GPL v2'''
import re

class InvalidSudokuError:
	def __str__(self):
		return "Invalid sudoku"

class SudokuUnsolvableError:
	def __str__(self):
		return "Sudoku not solvable"

class SudokuSolver:
	def __init__(self,sudoku=0):
		self.sudoku = sudoku
	def solveFile(self,filename):
		self.readSudoku(filename)
		return self.solve()
	def setSudoku(self,sudoku):
		checkSudoku(sudoku)
		self.sudoku = sudoku
	def checkSudoku(self,sudoku):
		pass
	def solve(self,sudoku=0):
		if sudoku == 0 and self.sudoku == 0:
			raise InvalidSudokuError
		if sudoku != 0:
			self.sudoku = sudoku
		self.unknown_count = 0
		for i in self.sudoku:
			for j in i:
				if j == 0:
					self.unknown_count =\
					self.unknown_count + 1
		if self.nextUnknown():
			return self.sudoku
		raise SudokuUnsolvableError
	'''Returns the coordinates of the next missing number'''
	def findNextMissing(self):
		for i,line in enumerate(self.sudoku):
			for j,val in enumerate(line):
				if val == 0:
					return i,j
		return -1,-1
	'''Finds a suitable number for the next missing one'''
	def nextUnknown(self):
		x,y = self.findNextMissing()
		if x == -1:
		#No missing number left, we solved it
			return True
		for i in range(1,10):
			if self.isValid(x,y,i):
				self.sudoku[x][y] = i
				if self.nextUnknown():
					return True
				self.sudoku[x][y] = 0
		return False
	'''Checks wether number n at [x][y] would be valid'''
	def isValid(self,x,y,n):
		#Check same row:
		if n in self.sudoku[x]:
			return False
		#Check same column:
		for row in self.sudoku:
			if row[y] == n:
				return False
		#Check same square:
		p,q = int(x/3),int(y/3)
		for i in range(3*p,3*p+3):
			for j in range(3*q,3*q+3):
				if self.sudoku[i][j] == n:
					return False
		return True
	'''Reads a sudoku from a file, zeros denote unknown numbers'''
	def readSudoku(self,filename):
		f = file(filename)
		lines = f.readlines()
		f.close()
		if len(lines) != 9:
			raise InvalidSudokuError
		regexp = re.compile("[0-9]{9}")
		self.sudoku = []
		for line in lines:
			tmp = []
			if regexp.match(line) == None:
				raise InvalidSudokuError
			for char in line:
				if char == "\n" or char == "\r":
					continue
				tmp.append(int(char))
			self.sudoku.append(tmp)



if len(sys.argv) != 2:
	print "USAGE:",sys.argv[0],"filename"
	sys.exit(1)
solver = SudokuSolver()
try:
	solution = solver.solveFile(sys.argv[1])
	if solution == False:
		print "No solution possible"
	else:
		for i in solution: print i
except InvalidSudokuError,inst:
	print str(inst)