import datetime
import copy
import random

__TIMES = 0

def crs(A,B):
    return [a+b for a in A for b in B]

_DTS = '123456789'
_RS = 'ABCDEFGHI'
_RU = ('ABC','DEF','GHI')
_CS = _DTS
_CU = ('123','456','789')
_SQS = crs(_RS,_CS)
_UL = [crs(_RS,c) for c in _CS]+[crs(r,_CS) for r in _RS] + [crs(r1,c1) for r1 in _RU for c1 in _CU]
_US = dict((s,[u for u in _UL if s in u]) for s in _SQS)
_PS = dict((s,set(sum(_US[s],[]))-set([s])) for s in _SQS)

def getValue(src):
    cs = [c for c in src if c in _DTS or c in '0. ']
    if(len(cs)!=81):
        print('Wrong Sudoku')
        return False
    valueso = dict(zip(_SQS,cs))
    values = dict((s,_DTS) for s in _SQS)
    for s,d in valueso.items():
        if(d in _DTS and not assignValue(values,s,d)):
            return False
    return values

def assignValue(values,s,d):
    valuesToElim = values[s].replace(d,'')
    if(all(elimValue(values,s,d) for d in valuesToElim)):
        return values
    else:
        return False

def elimValue(values,s,d):
    if(d not in values[s]):
        return values
    values[s] = values[s].replace(d,'')
    if(len(values[s])==0):
        return False
    elif(len(values[s])==1):
        d1 = values[s]
        if(not all(elimValue(values,s1,d1) for s1 in _PS[s])):
            return False
    for u in _US[s]:
        dp = [s2 for s2 in u if d in values[s2]]
        if(len(dp)==0):
            return False
        elif(len(dp)==1):
            if(not assignValue(values,dp[0],d)):
                return False
    return values

def getAnswer(seq):
    for e in seq:
        if(e):
            return e
    return False

def search(values):
    if(values is False):
        return False
    global __TIMES
    __TIMES += 1
    if(all(len(values[s])==1 for s in _SQS)):
        return values
    n,s = min((len(values[s]),s) for s in _SQS if len(values[s])>1)
    return getAnswer(search(assignValue(values.copy(),s,d)) for d in values[s])

def printSudoku(values):
    if(values is False):
        print 'Failed'
        return False
    line = '+'.join(['-' * 3 * 2] * 3)
    for r in _RS:
        print (''.join(values[r+c].center(2) + ('|' if c in '36' else '') for c in _CS))
        if(r in 'CF'):
            print line
    print

grid1 = '800000000003600000070090200050007000000045700000100030001000068008500010090000400'

printSudoku(search(getValue(grid1)))
print('search times:' + str(__TIMES))