board = [[0,0,0,2,6,0,7,0,1],
         [6,8,0,0,7,0,0,9,0],
         [1,9,0,0,0,4,5,0,0],
         [8,2,0,1,0,0,0,4,0],
         [0,0,4,6,0,2,9,0,0],
         [0,5,0,0,0,3,0,2,8],
         [0,0,9,3,0,0,0,7,4],
         [0,4,0,0,5,0,0,3,6],
         [7,0,3,0,1,8,0,0,0]]


def solve(bo):
    
    find = find_empty(bo)
    if not find:
        return True
    else:
        row, col = find
    
    for i in range(1,10):
        if valid(bo, i, (row,col)):
            bo[row][col] = i
            
            if solve(bo):
                return True
            
            bo[row][col] = 0
            
    return False

def valid(bo, num, pos):
    
    # check row
    
    for i in range(len(bo[0])):
        if bo[pos[0]][i] == num and pos[1]!=i:
            return False
    
    # check coloumn
    
    for j in range(len(bo)):
        if bo[j][pos[1]] == num and pos[0]!=j:
            return False
        
    # check box
    
    box_x = pos[1] // 3
    box_y = pos[0] // 3
    
    for i in range(box_y*3, box_y*3 + 3):
        for j in range(box_x*3, box_x*3 + 3):
            if bo[i][j] == num and (i,j)!=pos:
                return False
    
    return True
    

def print_board(boa):
    for i in range(len(boa)):
        if i % 3 == 0 and i!=0:
            print("- - - - - - - - - - - - - - -")
            
        for j in range(len(boa[0])):
            if j%3 == 0 and j!=0:
                print("| ", end="")
            
            if j!=8:
                print(boa[i][j]," ",end="")
            else:
                print(boa[i][j])
            
def find_empty(boa):
    for i in range(len(boa)):
        for j in range(len(boa[0])):
            if boa[i][j] == 0:
                return(i,j)
            

print_board(board)
print()
solve(board)
print()
print_board(board)

