def sudokuSolver(board):
    if not valid(board): #Previously made a bad move
        return
    if board.find(".")==-1:      #Base case
        printAid(board)
        return
    nextEmpty = board.find(".")  #recursive cases
    #print(nextEmpty)
    for tile in range(1,10):
        sudokuSolver(board[:nextEmpty]+str(tile)+board[nextEmpty+1:])


def valid(board):
    #check rows
    for row in range(9):
        for tile in range(1,10):
            count=0
            for col in range(9):
                if board[row*9+col]==str(tile):
                    count+=1
            if count>1:
                return False
    #check columns
    for col in range(9):
        for tile in range(1,10):
            count=0
            for row in range(9):
                if board[row*9+col]==str(tile):
                    count+=1
            if count>1:                
                return False    
    #check clusters
    for c1 in range(3):
        for c2 in range(3):
            for tile in range(1,10):
                count=0
                for roff in range(3):
                    for coff in range(3):
                        if board[(c1*3+roff)*9+(c2)*3+coff]==str(tile):
                            count+=1
                if count>1:
                    #print(c1,c2)
                    return False
    return True

def printAid(puzzle):
    for x in range(9):
        print(puzzle[x*9:x*9+9])

puzzle = "8.45.6........4.6967....8.4......1.....13.9..139...485.12..364.45.9....17....1..."
printAid(puzzle)
input("Ready?")
print()
sudokuSolver(puzzle)