#!/usr/bin/env python2
"""
Soduko solver. Everybody writes one.
"""   

sample = "003020600900305001001806400008102900700000008006708200002609500800203009005010300"

all_bits = int('1'*9,2)

def load_puzzle(s):
    return [all_bits if c in '0.' else 1 << (int(c)-1) for c in s]    

sample_puzzle = load_puzzle(sample)
assert 81 == len(sample_puzzle)

def itr_digits(b):
    return (d for d in xrange(9) if b & (1 << d))

def itr_bits(b):
    return (1 << d for d in xrange(9) if b & (1 << d))

def str_cell(b):
    return "".join([str(d+1) for d in itr_digits(b)])
        
def popcount(i):
    count = 0
    while i:
        i &= (i - 1) # clear the least signficiant bit set
        count += 1
    return count 

assert 0 == popcount(0)
assert 1 == popcount(1)
assert 2 == popcount(3)

def pprint_puzzle(bp):    
    space_per_cell = max(popcount(c) for c in bp)    
    for row in xrange(9):        
        print " ".join("".join(str_cell(bp[row*9+col])).center(space_per_cell) for col in xrange(9))

def neighbour_indices(i):    
    row, col = i / 9, i % 9
    return set([(row*9 + c) for c in xrange(9)] +\
               [(r*9 + col) for r in xrange(9)] +\
               [(r+3*(row/3))*9 + (c+3*(col/3)) for r in xrange(3) for c in xrange(3)]) - set([row*9+col])

neighbours = [neighbour_indices(i) for i in xrange(81)]

assert all((i not in neighbours[i]) for i in xrange(81))

def validate_cell(bp, i):
    "Validate that the value(s) in cell i don't invalidate the Soduko property"
    if 0 == popcount(bp[i]):
        return False
    if 1 == popcount(bp[i]):
        for j in neighbours[i]:
            if 1 == popcount(bp[j]) and bp[i] & bp[j]:
                return False
    return True

def validate_puzzle(bp):  
    "Validate that the whole matrix does not invalidate the Soduko property"
    # Not as optimal as it could be, but only used for asserting the result    
    return all(validate_cell(bp, i) for i in xrange(81))
        
assert validate_puzzle(sample_puzzle)

def is_solved(bp):
    return bp and all((1 == popcount(x)) for x in bp) and validate_puzzle(bp)

assert (not is_solved(sample_puzzle))

def set_value_and_prune(bp, i, bit_v):
    if 1 != popcount(bit_v):
        raise ValueError("Only set a single value at a time")
        
    bp[i] = bit_v
    mask = (~bp[i] & all_bits)
    for j in neighbours[i]:   
        bp[j] = bp[j] & mask
        if 0 == popcount(bp[j]):
            return False             
    return bp

def solve(bp):
    try:
        c_i, c_val, _ = min(((i, x, popcount(x)) for (i, x) in enumerate(bp) if 1 < popcount(x)), key=lambda t: t[2])
    except ValueError:
        return bp if validate_puzzle(bp) else False
        
    for bit in itr_bits(c_val):                
        maybe_solution = set_value_and_prune(bp[:], c_i, bit)
        if maybe_solution:
            maybe_solution = solve(maybe_solution) 
            if maybe_solution:
                return maybe_solution
            
    return False

assert is_solved(solve(sample_puzzle))