#!/usr/bin/python

# TODO: Make solve function faster!!! Have it check for singles, doubles,
# triples, and quads both naked and hidden

from random import random

def rand(lst):
	"returns a random element in list or integer"
	if type(lst)==type([]):
		return lst[int(random()*len(lst))]
	elif type(lst)==type(0):
		return int(random()*lst)
	else:
		raise Exception,"don't know what do do with type %s!!!"%type(lst)

def reorder(lst):
	"reorders a list to a random order"
	ret=[]
	for item in lst:
		ret.insert(rand(len(ret)),item)
	return ret

def row(row,puzzle):
	return puzzle[row*9:row*9+9]

def col(col,puzzle):
	ret=[]
	for i in range(9):
		ret.append(row(i,puzzle)[col])
	return ret

def box(box,puzzle):
	x=box%3
	if box<3:
		y=0
	elif box<6:
		y=1
	else:
		y=2
	ret=[]
	for i in range(3):
		ret.extend(row(y*3+i,puzzle)[x*3:x*3+3])
	return ret

def remaining(wcb):
	ret=[]
	for i in range(1,10):
		if not i in wcb:
			ret.append(i)
	return reorder(ret) # does not significantly slow program
						# and allows for generation of random puzzles

def coordToBox(x,y):
	box=0
	if x<3:
		pass
	elif x<6:
		box+=1
	else:
		box+=2
	if y<3:
		pass
	elif y<6:
		box+=3
	else:
		box+=6
	return box

def coordToLinear(x,y):
	return y*9+x

def linearToCoord(index):
	y=8
	for i in range(9):
		if index<i*9:
			y-=1
	x=index%9
	return x,y

def possible(x,y,puzzle):
	if not puzzle[coordToLinear(x,y)]==0:
		return [puzzle[coordToLinear(x,y)]]
	imp=[]
	imp.extend(row(y,puzzle))
	imp.extend(col(x,puzzle))
	imp.extend(box(coordToBox(x,y),puzzle))
	return remaining(imp)

def printPuzzle(puzzle):
	string=((((("%s "*3)+"| ")*2+("%s "*3)+"\n")*3+"------|-------|------\n")*3)[:-22]+"\n"
	text=(string%tuple(puzzle)).replace("0","_")
	print text,
	return text

def check(x,y,puzzle):
	for i in range(9):
		if not i==y and len(possible(x,i,puzzle))==0:
			return False
		if not i==x and len(possible(i,y,puzzle))==0:
			return False
	box_x,box_y=linearToCoord(coordToBox(x,y))
	for i in range(box_x,box_x+3):
		if i==x:
			break
		for j in range(box_y,box_y+3):
			if j==y:
				break
			if len(possible(i,j,puzzle))==0:
				return False
	return True

def solve(puzzle,start=0): # TODO: Make this function faster!!!
	if start==81:
		return [puzzle[:]]
	ret=[]
	x,y=linearToCoord(start)
	possibilities=possible(x,y,puzzle)
	if len(possibilities)==0:
		return
	for possibility in possibilities:
		p=puzzle[:]
		p[coordToLinear(x,y)]=possibility
		x,y=linearToCoord(start)
		if not check(x,y,puzzle):
			continue
		solved=solve(p,start+1)
		if solved:
			ret.extend(solved)
			if 1<len(ret): # there is more than one puzzle
				return ret # enough already!!!
	return ret

def solve_no_check_for_dups(puzzle,start=0):
	"This solver function does not check for multiple solutions."
	if start==81:
		return puzzle[:]
	x,y=linearToCoord(start)
	possibilities=possible(x,y,puzzle)
	if len(possibilities)==0:
		return
	for possibility in possibilities:
		p=puzzle[:]
		p[coordToLinear(x,y)]=possibility
		x,y=linearToCoord(start)
		if not check(x,y,puzzle):
			continue
		solved=solve_no_check_for_dups(p,start+1)
		if solved:
			return solved
	return []

def generate(sym=True,goodness=0): # goodness=0 means evil
	if sym:
		RANGE=41
	else:
		RANGE=81
	puzzle=[0]*81
	soln=solve_no_check_for_dups(puzzle)
	puzzle=soln[:]
	spaces=range(RANGE)
	for i in range(RANGE-goodness):
		space=spaces.pop(rand(len(spaces)))
		puzzle[space]=0
		if sym:
			puzzle[80-space]=0
		if 1<len(solve(puzzle)):
			puzzle[space]=soln[space]
			if sym:
				puzzle[80-space]=soln[80-space]
	return puzzle

#puzzle=[]
#for i in range(9):
#	puzzle.extend(map(int,raw_input().split()))

try:
	import psyco
	psyco.full()
except ImportError:
	print "You do not have psyco installed. The program will run slower."

if __name__=="__main__":
	#puzzle=generate()
	#printPuzzle(puzzle)
	#soln=solve(puzzle)
	#printPuzzle(soln[0])
	#if 1<len(soln):
	#	print "More than one solution!!!"
	#puzzle=generate(sym=False)
	#printPuzzle(puzzle)
	#soln=solve(puzzle)
	#printPuzzle(soln[0])
	#if 1<len(soln):
	#	print "More than one solution!!!"
	from time import sleep
	while True:
		puzzle=generate(sym=False)
		text=printPuzzle(puzzle)
		f=open("./sudoku","a")
		f.write(text)
		f.close()
		sleep(180)