#!/usr/bin/env python
#---------------------------------------------------------------------------
# (C)2006 Joachim Schueth, Bonn.
# 
# Jo's Sudoku Solver v1.1
# 
# Save this script as sudokusolve.py and run it with Python as shown below.
# For information on the Python language, see http://www.python.org .
#
# This script solves Sodoku puzzles. The puzzle has to be presented
# as an ASCII file. Digits can be separated by spaces, and 9 digits
# per line must be present. Blank lines are ignored. The empty fields
# of the puzzle must be represented by the digit 0 in the input file.
#
# Sample input file 'sudoku01.txt':
#
#   4 0 0  1 0 0  0 2 0
#   1 0 0  0 9 7  0 0 4
#   0 0 0  0 6 0  8 0 0
#   
#   0 0 0  0 0 9  0 0 0
#   0 0 0  2 0 0  1 7 0
#   0 0 0  0 0 0  0 5 0
#   
#   5 3 0  0 0 4  6 0 0
#   7 0 0  0 2 0  0 4 0
#   0 6 0  8 0 0  3 0 0
#
# Sample run of the Sudoku Solver:
#
#   $ python sudokusolve.py sudoku01.txt
#   Input:
#   4 0 0   1 0 0   0 2 0
#   1 0 0   0 9 7   0 0 4
#   0 0 0   0 6 0   8 0 0
#   
#   0 0 0   0 0 9   0 0 0
#   0 0 0   2 0 0   1 7 0
#   0 0 0   0 0 0   0 5 0
#   
#   5 3 0   0 0 4   6 0 0
#   7 0 0   0 2 0   0 4 0
#   0 6 0   8 0 0   3 0 0
#   
#   Solution:
#   4 9 6   1 5 8   7 2 3
#   1 2 8   3 9 7   5 6 4
#   3 7 5   4 6 2   8 9 1
#   
#   2 1 7   5 8 9   4 3 6
#   8 5 3   2 4 6   1 7 9
#   6 4 9   7 3 1   2 5 8
#   
#   5 3 2   9 1 4   6 8 7
#   7 8 1   6 2 3   9 4 5
#   9 6 4   8 7 5   3 1 2
#
# Have fun!
#---------------------------------------------------------------------------
from copy import deepcopy
from sys import argv, exit
from string import atoi, join

def make_groups():
	groups = 27 * [[]]

	for k in range(27):
		groups[k] = 9 * [-1]

	g = 0

	for y in range(9):
		j = 0
		for x in range(9):
			groups[g][j] = 9 * y + x
			j += 1
		g += 1	

	for x in range(9):
		j = 0
		for y in range(9):
			groups[g][j] = 9 * y + x
			j += 1
		g += 1	

	for ybox in range(3):
		for xbox in range(3):
			j = 0
			for y in range(3):
				for x in range(3):
					groups[g][j] = 3 * xbox + 27 * ybox + 9 * y + x
					j += 1
			g += 1		

	return groups

def get_array(fname):
	f = open(fname, 'r')
	text = f.readlines()
	f.close()
	array = []
	for line in text:
		nums = map(atoi, join(line.split(), ''))
		if len(nums) == 0:
			continue
		if len(nums) != 9:
			print "Error: need 9 digits per line"
			print line.strip()
			exit(-1)
		array += nums
	if len(array) != 81:
		print "Bad number of lines in file %s" % fname
		exit(-1)
	return array	

def show_array(a):
	j = 0
	for x in a:
		print '%d' % x,
		if j % 27 == 26:
			print
			print
		elif j % 9 == 8:
			print
		elif j % 3 == 2:
			print ' ',
		j += 1

def allowed(num, idx, array, groups):
	if array[idx] > 0 and array[idx] != num:
		return False
	for g in groups:
		if idx not in g:
			continue
		for j in g:
			if array[j] == num:
				return False
	return True			
	
def possib(array, groups):
	poss = []
	for i in range(81):
		lst = []
		if array[i] == 0:
			for x in range(1, 10):
				if allowed(x, i, array, groups):
					lst += [x]
		poss += [lst]	
	return poss	

def straightsolve(array, groups):
	a = deepcopy(array)
	while 1:
		p = possib(a, groups)
		hits = 0
		for i in range(81):
			if len(p[i]) == 1:
				if not allowed(p[i][0], i, a, groups):
					return (None, None)
				a[i] = p[i][0]
				hits += 1
		if hits == 0:
			break
		#print "hits: %d" % hits	
	return (a, p)		
	
def recusolve(array, groups, level):
	a = deepcopy(array)
	(b, p) = straightsolve(a, groups)
	if not b:
		return None
	if not 0 in b:
		return b
	ls = map(len, p)
	m = 0
	for l in ls:
		if l > 1 and (l < m or m == 0):
			m = l
	if m == 0:
		return None	
	im = ls.index(m)	
	for x in p[im]:
		a[im] = x
		print "Level %2d: try %d at %2d" % (level, x, im)
		r = recusolve(a, groups, level + 1)
		if r:
			return r
	return None	

def check_array(array, groups):
	a = deepcopy(array)
	for i in range(81):
		x = a[i]
		if x == 0:
			continue
		if not x in range(1, 10):
			return False
		a[i] = 0
		if not allowed(x, i, a, groups):
			return False
		a[i] = x	
	return True		

gs = make_groups()	

a = get_array(argv[1])
print "Input:"
show_array(a)
if not check_array(a, gs):
	print "Illegal input!"
	exit(-1)
	
r = recusolve(a, gs, 0)

if not r:
	print "Not solvable!"
else:
	print "Solution:"
	show_array(r)
	if not check_array(r, gs):
		print "Programmer's error, illegal solution produced!"

# EOF