from sys import exit
from copy import deepcopy
from math import log

def f(n):
	return (1 << (n-1))

size = 9
rows = frozenset(xrange(0, size))
columns = rows
flags = []
undone = set( )
all = 0
for flag in rows:
	for col in rows:
		undone.add( (flag, col) )
	flags.append(1 << flag)
	all += flags[flag]
flags = frozenset(flags)
box = frozenset( range(3) ) # 3 cells to a box

done = set( ) # these are coordinates that are finalized
investigate = [ (0,1) ] # prime with coords of first number
board = [		# defaults to board from sudoku.com's homepage
	#  0     1    2     3    4     5     6     7    8
	[ all, f(6), all,	f(1), all, f(4),	all, f(5), all ], # 0
	[ all, all, f(8),	f(3), all, f(5),	f(6), all, all ], # 1
	[ f(2), all, all,	all, all, all,	all, all, f(1) ], # 2
	
	[ f(8), all, all,	f(4), all, f(7),	all, all, f(6) ], # 3
	[ all, all, f(6),	all, all, all,	f(3), all, all ], # 4
	[ f(7), all, all,	f(9), all, f(1),	all, all, f(4) ], # 5
	
	[ f(5), all, all,	all, all, all,	all, all, f(2) ], # 6
	[ all, all, f(7),	f(2), all, f(6),	f(9), all, all ], # 7
	[ all, f(4), all,	f(5), all, f(8),	all, f(7), all ]  # 8
]

for row in board:
	print row
print ""
print ""

limit = 10000
count = 0

# Returns an identifying block number for the given coordinates
def block_num(coords):
	row, col = coords
	return (row%3)*3 + (col/3)%3
	
blocks = [ # avoid generating these sets programatically at every script initialization
	set( [(0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2)] ),
	set( [(0,3), (0,4), (0,5), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5)] ),
	set( [(0,6), (0,7), (0,8), (1,6), (1,7), (1,8), (2,6), (2,7), (2,8)] ),
	set( [(3,0), (3,1), (3,2), (4,0), (4,1), (4,2), (5,0), (5,1), (5,2)] ),
	set( [(3,3), (3,4), (3,5), (4,3), (4,4), (4,5), (5,3), (5,4), (5,5)] ),
	set( [(3,6), (3,7), (3,8), (4,6), (4,7), (4,8), (5,6), (5,7), (5,8)] ),
	set( [(6,0), (6,1), (6,2), (7,0), (7,1), (7,2), (8,0), (8,1), (8,2)] ),
	set( [(6,3), (6,4), (6,5), (7,3), (7,4), (7,5), (8,3), (8,4), (8,5)] ),
	set( [(6,6), (6,7), (6,8), (7,6), (7,7), (7,8), (8,6), (8,7), (8,8)] )
]

# for rippling, ignore the rows and columns coming out from this cell
def get_block(coords):
	block = []
	row, col = coords
	delta_row = row % 3
	delta_col = col % 3
	_rows = box.difference( [delta_row] )
	_cols = box.difference( [delta_row] )
	for row_cell in _rows:
		for col_cell in _cols:
			_row = row_cell + row - delta_row
			_col = col + col_cell - delta_col
			block.append( (_row, _col) )
	return block
			
def unset(row, col, cell):
	board[row][col] &= ~cell # 1011 &= ~10 == 1001 ;;; this indicates that the surrounding row+col+block cells can't be this cell
	
	if board[row][col] == 0:
		print "conflict! board not solved"
		for row in board:
			print row
		exit(0)
	
	if board[row][col] in flags and (row,col) not in done:
		print "[%d][%d] looks interesting  ( %d )" % (row, col, log(board[row][col], 2) + 1 )
		investigate.append( (row, col) )
	
	global limit
	limit = limit - 1
	
	if limit < 0:
		print "limit reached. This may mean that sudoku is trying to execute an infinite loop (unlikely), or maybe just that it's a particularly complex puzzle. Try increasing the limit and restarting the script"
		for row in board:
			print row
		exit(0)

	
def ripple_unset(coords):
	row, col = coords
	#print "rippling out of [%d][%d]" % (row, col)
	cell = board[row][col]
	for offset in rows:
		if offset != row:
				unset(offset, col, cell)
		if offset != col:
				unset(row, offset, cell)
	
	block = get_block(coords) # partial
	for cell_coords in block:
		_row, _col = cell_coords
		unset(_row, _col, cell)


def sweep():
	""" Iterates through a list of cells with a single bit set, and unsets that bit from surrounding row + column + block cells
		As new single-bit cells are created, adds them to the list.
	"""
	while len(investigate) > 0:
		coords = investigate.pop()
		if coords not in done:
			global count
			count = count + 1
			done.add(coords)
			undone.discard(coords)
			ripple_unset(coords) # unset this flag for the "surrounding" cells


sweep() # go through once and get as many hard values written as possible


def block_match(coords):
	row, col = coords
	cell = board[row][col]
	block = deepcopy(blocks[block_num(coords)]) # get a list of the coordinates of the cells in the current cell's "block"
	block.discard(coords) # remove the current cell from the list
	for cell_coords in block:
		_row, _col = cell_coords
		if board[_row][_col] not in flags: # for each multi-bit cell in the block...
			cell ^= board[_row][_col] # removes the current cell's bits from the passed cell's bits
	return cell & board[row][col]

while len(undone) != 0: # look only at cells with multiple bits set
	coords = undone.pop()
	row, col = coords
	
	if board[row][col] in flags: # some sort of mismatch has occurred -- |done| should contain only multi-bit cells, and |flags| is just powers of 2, e.g. single-bit numbers
		print "undone is done! [%d][%d]" % (row, col) # shouldn't happen, and haven't seen it happen yet
		continue
		
	match = block_match(coords) # figures out possible values for the cell @ coords, based on the surrounding block's values
	if match:
		print "block (un)match for [%d][%d] == %d 	as	%d" % (row, col, board[row][col], match)
		if match in flags: # only one possibility -- score!
			print "ooh, a flag-match!"
			board[row][col] = match # note that we only overwrite the board if we get a single flag back
			investigate.append(coords)
			sweep() # any more one-bit values we can squeeze out?

#print ""
#print blocks[ block_num( (4,0) ) ]
#print ""
		
#print count

print ""
print ""

print undone

print ""
print ""

def log2(n):
	return int(log(n, 2) + 1)
	
def space(n):
	return "%3d" % n
	
	
for row in board:
	print map(space, row)
	
	
print ""
print ""


# converts bitfield-numbers to "real" numbers
for row in board:
	print map(log2, row)