#!/usr/bin/python
'''
	Sudoku solver
	version 2 with linear array (copy)
	Malte John sudoku@ddd.de	
'''
__author__ = 'Malte John'


try:
	import psyco
	psyco.full()
except:
	pass

ARRAY = [
	9,0,0, 0,0,0, 2,0,0,
	0,4,0, 8,2,0, 0,0,5,
	7,2,0, 0,3,0, 0,0,0,

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

	0,0,0, 0,1,0, 0,4,2,
	4,0,0, 0,6,2, 0,7,0,
	0,0,3, 0,0,0, 0,0,9
]


def	possible( array, x_, y_ ):
	'''return array with possible numbers for position x, y'''

	if array[y_ * 9 + x_]:
		return ()
	
	poss = range(0,10)
	
	for x in xrange( 9 ):
		poss[array[y_*9+x]] = 0
	
	for y in xrange( 9 ):
		poss[array[y*9+x_]] = 0
	
	x_ = x_ - x_%  3
	y_ = y_ - y_%  3
	
	for y in xrange( 3 ):
		xx = (y_+y)*9 +x_
		poss[array[xx  ]] = 0
		poss[array[xx+1]] = 0
		poss[array[xx+2]] = 0
		
	return 	[x for x in poss if x]


def solve( array_, x_, y_, level = 1 ):
#	print "\n%sSOLVE( %d, %d, %d )" % ( "  "* level, x_, y_, level )

	# erste freie Stelle suchen
	while array_[y_*9+x_]:
		if x_ < 8:
			x_ += 1
			continue
		if y_ < 8:
			x_ = 0
			y_ += 1
			continue
		else:
			for y in xrange( 9 ):
				print array_[y*9:y*9+9]
			print
			return

	for p in possible( array_, x_, y_ ):
		array = array_[:]
		array[y_*9+x_] = p
		if x_ < 8:
			x = x_ + 1
			y = y_
		else:
			x = 0
			if y_ < 8:
				y = y_ + 1
			else:
				print "done (tried all)"
				for y in xrange( 9 ):
					print array[y*9:y*9+9]
				raise SystemExit
		
		solve( array, x, y, level + 1 )
		

solve( ARRAY, 0, 0 )
print "normal"