#!/usr/bin/python
'''
	Sudoku solver
	first version with global square array (reconstruction after recursion)
	Malte John sudoku@ddd.de	
'''

import copy, pprint

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]
]

N = 0

EVIL = [
    [4, 2, N,   N, N, N,   N, 1, N],
    [N, N, N,   5, 4, N,   N, 3, N],
    [N, N, 6,   N, N, 7,   N, N, N],

    [N, N, N,   N, N, N,   2, 7, 9],
    [N, 1, N,   N, N, N,   N, 6, N],
    [3, 4, 2,   N, N, N,   N, N, N],

    [N, N, N,   9, N, N,   3, N, N],
    [N, 6, N,   N, 3, 8,   N, N, N],
    [N, 8, N,   N, N, N,   N, 5, 7]
    ]



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

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


def solve( array, x_, y_, level = 1 ):
	# erste freie Stelle suchen
	while array[y_][x_]:
		if x_ < 8:
			x_ += 1
			continue
		if y_ < 8:
			x_ = 0
			y_ += 1
			continue
		else:
			pprint.pprint( array )
			return
	
	for p in possible( array, x_, y_ ):
		array[y_][x_] = p
		if x_ < 8:
			x = x_ + 1
			y = y_
		else:
			x = 0
			if y_ < 8:
				y = y_ + 1
			else:
				print "done (tried all)"
				print array
				raise SystemExit
		
		solve( array, x, y, level + 1 )
		array[y_][x_] = 0


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