import copy
def decode_sudoku(n):
    i,s=0,''
    while(i<81):
        for ch in n:
            if ch.isdigit():
                s+=(ch)
                i+=1
            else:
                s+=' '*(ord(ch)-96)
                i+=ord(ch)-96
    #print_sudoku_s(s)
    g=[]
    for y in range(9):
        g.append(list(s[y*9:y*9+9]))
    return g
def print_grid(n):
    for i in n:
        print(''.join(i))
def print_sudoku_s(n):
    for i in range(0,81,9):
        print(n[i:i+9])
def print_sudoku(g):
    for y in range(9):
        if y==3 or y==6: print('===========')
        for x in range(0,9,3):
            print(g[y][x]+g[y][x+1]+g[y][x+2],end='')
            if x==6:       print('\n',end='')
            else:            print('|',end='')
            
#pos=['1','2','3','4','5','6','7','8','9']
pos='123456789'
def list_possible(g,x,y):
    adj=[]
    for i in range(9):
        if i==x: continue
        if g[y][i] in pos: adj.append(g[y][i])
    for j in range(9):
        if j==y: continue
        if g[j][x] in pos: adj.append(g[j][x])
    bx=(x//3)*3
    by=(y//3)*3
    for j in range(by,by+3):
        for i in range(bx,bx+3):
            if j==y and i==x: continue
            if g[j][i] in pos: adj.append(g[j][i])
#    print(x,y,adj)
    if g[y][x] in adj:
        print('line49')
        return False
    return complement(adj)
def complement(adj):
    return [c for c in pos if c not in adj]
def validate(g):
    for i in range(81):
        rv=list_possible(g,i//9,i%9)
        if rv==False: return False
    return True
def is_filled(g):
    for line in g:
        for ch in line:
            if not ch in '123456789': return False
    return True
def find_least_branches(g):
    lx,ly,lbranches=None,None,None
    min=10
    for y in range(9):
        for x in range(9):
            branches=list_possible(g,x,y)
            if branches==False: return False
            if g[y][x] in '123456789': continue
            if len(branches)<min:
                min=len(branches)
                lx,ly,lbranches=x,y,branches
    if (lx,ly,lbranches)==(None,None,None):
        print ('line76')
    return lx,ly,lbranches
def solve(g):
    counter=0
    rv=[]
    tup=find_least_branches(g)
    if tup==False: return False
    if is_filled(g): return [g]
    lx,ly,lbranches=tup
    stack.append([lx,ly,lbranches])
    while stack!=[]:
        if stack[-1][2]!=[]:
            lx,ly,lbranches=stack[-1]  
            g[ly][lx]=lbranches[-1]
            if is_filled(g):
                counter+=1
                print('solution number {} found'.format(counter))
                rv.append(copy.deepcopy(g))
                stack[-1][2].pop()
            else:
                nlx,nly,nlbranches=find_least_branches(g)
                if nlbranches!=[]:
                    stack.append([nlx,nly,nlbranches])
                else:
                    stack[-1][2].pop()
            
        else:
            g[ stack[-1][1] ][ stack[-1][0] ]=' '
            stack.pop()
            if stack!=[]: stack[-1][2].pop()
    return rv

#easy='1925b3bd3a29ac94c1b5a18a6a41e73a8a79a5b7c63d31a2db4b5638'
#p2='c82a1a48f3f465a9a2a7a41a1b645b9a43a1a7a6a584f1f24a6a81c'
#p3='iiiiiiiii'
#evil='b15b3bd8647a2a67bccc1b8b2a3b4b7cccb28a3a2539db8b72b'
eightball='a8c9743a5c8a1aa1g8d5cc8a4cc3d6g7aa3a5c8a9724c5a'
eightball=decode_sudoku(eightball)
#print_sudoku(eightball)
#print(validate(eightball))
stack=[]
solv=[]
solv2=solve(eightball)
#for eachg in solv2:
#    print_sudoku(eachg)
#    print()
#
#fake=' 12345678iiiiiiii'
#fake=decode_sudoku(fake)
#solv=solve(fake)
#print(solv)