# sudoku.py
# Robert Wohleb
# 20051115

import random

class board:
	boardlist = []
	partialboardlist = []

	def generate(self, numFilled=(9*9)):
		slots = []
		fillOrder = []

		random.seed()

		# setup board
		row = [0,0,0,0,0,0,0,0,0]
		for i in range(0, 9):
			self.boardlist.append(row[:])

		for j in range(0, 9):
			for i in range(0, 9):
				slots.append((i,j))

		self.search(slots, 0)
		
		while len(slots) > 0:
			i = random.randint(0, len(slots)-1)
			fillOrder.append(slots[i])
			del slots[i]

		# setup board
                for i in range(0, 9):
                        self.partialboardlist.append(row[:])

		for i in range(0, numFilled):
			j = fillOrder[i]
			self.partialboardlist[j[0]][j[1]] = self.boardlist[j[0]][j[1]]

	def search(self, slots, index):
		nums = []
		fillOrder = []

		if len(slots) == index:
			return self.check()

		for i in range(1, 10):
			nums.append(i)

		while len(nums) > 0:
			i = random.randint(0, len(nums)-1)
			fillOrder.append(nums[i])
			del nums[i]

		for i in fillOrder:
			x = slots[index][0]
			y = slots[index][1]
			self.boardlist[x][y] = i
			#print
			#print x, y, i
			#self.printBoard()
			if (self.check()):
				if self.search(slots, index+1):
					return True
			self.boardlist[x][y] = 0
		return False

	def check(self):
		for i in range(0, 9):
			if (not self.checkRow(i)) or (not self.checkCol(i)) or (not self.checkSquare(i)):
				return False
		return True

	def checkRow(self, row):
		found = []
		for i in range(0, 9):
			if not self.boardlist[i][row] == 0:
				if self.boardlist[i][row] in found:
					#print 'checkRow', i, row, self.boardlist[i][row]
					return False
				found.append(self.boardlist[i][row])
		return True

	def checkCol(self, col):
		found = []
		for j in range(0, 9):
			if not self.boardlist[col][j] == 0:
				if self.boardlist[col][j] in found:
					#print 'checkCol', j, col, self.boardlist[col][j]
					return False
				found.append(self.boardlist[col][j])
		return True

	def checkSquare(self, square):
		found = []
		xoffset = (3*(square % 3))
		yoffset = int(square / 3) * 3
		#print 'checkSquare(', xoffset, yoffset, ')'
		for j in range(0, 3):
			for i in range(0, 3):
				if not self.boardlist[xoffset+i][yoffset+j] == 0:
					if self.boardlist[xoffset+i][yoffset+j] in found:
						#print 'checkSquare -- ', i, j, self.boardlist[xoffset+i][yoffset+j]
						return False
					found.append(self.boardlist[xoffset+i][yoffset+j])
		return True

	def getList(self):                # setup board
                row = [0,0,0,0,0,0,0,0,0]
                for i in range(0, 9):
                        self.boardlist.append(row[:])
		return self.boardlist

	def printBoard(self):
		for j in range(0, 9):
			for i in range(0, 9):
				if self.boardlist[i][j] == 0:
					print '.',
				else:
					print self.boardlist[i][j],
			print

	def printPartialBoard(self):
		for j in range(0, 9):
			for i in range(0, 9):
				if self.partialboardlist[i][j] == 0:
					print '.',
				else:
					print self.partialboardlist[i][j],
			print

# -------------------------------------------------

if __name__ == '__main__':
	import sys

	if len(sys.argv) == 1:
		b = board()
		b.generate()
		b.printBoard()
	elif int(sys.argv[1]) > 0:
		b = board()
		b.generate(int(sys.argv[1]))
		#b.printBoard()
		#print
		b.printPartialBoard()
	else:
		print 'Use: python sudoku.py [NUM_PREFILLED]'