from sets import Set

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

	0, 3, 0,  7, 0, 6,  2, 5, 0,
	0, 0, 0,  0, 2, 0,  0, 0, 0,
	0, 7, 4,  3, 0, 8,  0, 9, 0,

	0, 6, 8,  0, 0, 7,  0, 0, 5,
	4, 2, 0,  0, 0, 0,  3, 0, 1,
	7, 0, 1,  5, 0, 4,  0, 0, 0 
];

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

	3, 0, 0,  0, 5, 7,  0, 0, 6,
	8, 0, 9,  0, 0, 0,  2, 0, 4,
	7, 0, 0,  9, 4, 0,  0, 0, 1,

	0, 0, 5,  0, 8, 0,  0, 6, 3,
	1, 0, 0,  0, 7, 0,  4, 0, 0,
	0, 3, 6,  0, 2, 5,  0, 8, 0
]

def displayResult(problem):
	for i in range(0, len(problem)):
		if(i % 27 == 0):  print "\n"
		elif(i % 9 == 0): print "";
		elif( i % 3 == 0 ): print "",
		print problem[i],

fulldeck = Set([1, 2, 3, 4, 5, 6, 7, 8, 9])

def findChoices(problem, pos):
	row = pos/9
	col = pos % 9
	cellrow = 3 * (row/3)
	cellcol = 3 * (col/3)
	excludes = Set(problem[ 9 * row: 9 * (row+1)])
	for i in range(0, 9):
		excludes.add(problem[i*9 + col])
	for i in range(cellrow, cellrow+3):
		for j in range(cellcol, cellcol+3):
			excludes.add(problem[9*i + j])
	excludes.discard(problem[pos])
	# target value can't be in any of these 
	return fulldeck - excludes

hits = 0

def solve(problem, depth):
	global hits 
	hits = hits + 1
	print "Calls: %d\r" % (hits),
	if(depth > len(problem)):
		return 0
	choicelist = {};
	if not (0 in problem):
		return 1
	for i in range(0, len(problem)):
		if(problem[i] == 0):
			# blank, then branch
			choices = findChoices(problem, i)
			if(len(choices) == 0):
				return 0
			if(choicelist.has_key(len(choices))):
				choicelist[len(choices)].append((i, choices))
			else:
				choicelist[len(choices)] = [ (i, choices) ]

	# pick the ones with the smallest amount of choice
	for j in range(1, 9):
		if choicelist.has_key(j):
			for (i, choices) in choicelist[j]:
				for v in choices:
					problemCopy = problem[:]
					problemCopy[i] = v
					if not (0 in problemCopy):
						displayResult(problemCopy)
						return 1
					if solve(problemCopy, depth+1):
						return 1
	return 0

def validate(problem):
	for i in range(0, len(problem)):
		choices = findChoices(problem, i)
		if(len(choices) != 1 or (not (problem[i] in choices))):
			print "** Error !"

solve(problem, 0)
print ""