Hard Sudoku solver | Python Fiddle

import copy

sudoku_arr_in = [[9,0,0, 3,5,0, 0,0,0],
                 [1,0,0, 0,0,0, 8,0,6],
                 [0,0,0, 4,0,0, 0,0,0],
                 
                 [0,0,0, 0,2,0, 7,0,0],
                 [0,0,3, 0,0,0, 0,5,0],
                 [0,4,0, 9,0,0, 0,0,0],
                 
                 [6,0,0, 0,0,8, 1,0,0],
                 [0,0,0, 0,0,0, 0,3,0],
                 [0,0,0, 0,0,0, 0,0,0]]#IMPOSSIBLE
##sudoku_arr_in = [[3,0,0, 6,0,0, 0,0,0],
##                 [0,0,0, 0,1,0, 0,4,0],
##                 [0,0,0, 0,0,0, 0,2,0],
##                 
##                 [0,2,0, 0,0,0, 0,8,0],
##                 [0,0,0, 5,0,0, 7,0,0],
##                 [0,0,8, 3,0,0, 0,0,0],
##                 
##                 [1,4,0, 0,2,0, 0,0,0],
##                 [5,0,0, 0,0,0, 6,0,0],
##                 [0,0,0, 0,0,0, 3,0,0]]#IMPOSSIBLE

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

sudoku_arr = copy.deepcopy(sudoku_arr_in)

def get_flat_sub_square_for(i,j):
    start_i = int(i/3)*3
    start_j = int(j/3)*3
    sub_square = [l[start_j:start_j+3] for l in sudoku_arr[start_i:start_i+3]]
    return [val for sublist in sub_square for val in sublist]

def get_column_for(c):
    return [line[c] for line in sudoku_arr]

def x_is_wrong_candidate(x,l,c):
    return (
        (x in sudoku_arr[l]) or
        (x in get_column_for(c)) or
        (x in get_flat_sub_square_for(l,c)))

def get_square_no_for(l,c):
    return int(l/3)*3+int(c/3)

def generate_candidate(l,c):
    lst = []#[x for x in range(1,10)]
    for x in range(1,10):
        if not x_is_wrong_candidate(x,l,c):
            lst.append(x)
    return {"line":l, "col":c, "square":get_square_no_for(l,c), "values":lst}

def get_all_candidates():
    res = []
    for l in range(0,9):
        for c in range(0,9):
            if sudoku_arr[l][c]==0:
                res.append(generate_candidate(l,c))
    return res

def get_candidates_for_line(l, candidates):
    return [d for d in candidates if d["line"]==l]

def get_candidates_for_col(c, candidates):
    return [d for d in candidates if d["col"]==c]

def get_candidates_for_square(s, candidates):
    return [d for d in candidates if d["square"]==s]

def get_unique_value(c, candidates):
    if len(c["values"])==1:
        return c["values"][0]
    other_candidates = [cc for cc in candidates if cc!=c]
    for x in c["values"]:
        if(not [cc for cc in other_candidates if x in cc["values"]]):
            return x
    return -1

def find_unique_values_and_apply_chages(all_candidates):
    for c in all_candidates:
        xl = get_unique_value(c, get_candidates_for_line(c["line"],all_candidates))
        if(xl>0):
            #print("found by line\t", xl, c)
            sudoku_arr[c["line"]][c["col"]]=xl
            return True
        xc = get_unique_value(c, get_candidates_for_col(c["col"],all_candidates))
        if(xc>0):
            #print("found by col\t", xc, c)
            sudoku_arr[c["line"]][c["col"]]=xc
            return True
        xs = get_unique_value(c, get_candidates_for_square(c["square"],all_candidates))
        if(xs>0):
            #print("found by square\t", xs, c)
            sudoku_arr[c["line"]][c["col"]]=xs
            return True
    return False

def reduce_candidates_by_pairs(all_candidates):
    for c in all_candidates:
        if len(c["values"])==2:
            other_sets = []
            other_sets.append([cc for cc in get_candidates_for_line(c["line"], all_candidates) if cc!=c])
            other_sets.append([cc for cc in get_candidates_for_col(c["col"], all_candidates) if cc!=c])
            other_sets.append([cc for cc in get_candidates_for_square(c["square"], all_candidates) if cc!=c])
            for other_set in other_sets:
                if c["values"] in [cc["values"] for cc in other_set]:
                    #print ("found same")
                    for cc in other_set:
                        if cc["values"]!=c["values"]:
                            for x in c["values"]:
                                if x in cc["values"]:
                                    cc["values"].remove(x)

def remove_x_from_candidates(x, candidate_list):
    for c in candidate_list:
        if x in c["values"]:
            c["values"].remove(x)

def reduce_candidates_by_square_line_intersection(all_candidates):
    #print(all_candidates)
    for s in range (0,9):
        square_list = get_candidates_for_square(s, all_candidates)
        for l in range(0,9):
            line_list = get_candidates_for_line(l, all_candidates)
            intersection_list = get_candidates_for_line(l, square_list)
            intersection_set = {v for cc in intersection_list for v in cc["values"]}
            if intersection_list:
                list_other_in_square = [cc for cc in square_list if cc not in intersection_list]
                set_other_in_square = {v for cc in list_other_in_square for v in cc["values"]}
                list_other_in_line = [cc for cc in line_list if cc not in intersection_list]
                set_other_in_line = {v for cc in list_other_in_line for v in cc["values"]}
                for c in intersection_list:
                    for x in c["values"]:
                        if (
                            (x in set_other_in_square and x not in set_other_in_line)
                            or (x not in set_other_in_square and x in set_other_in_line)
                            ):
                            remove_x_from_candidates(x, list_other_in_line)
                            remove_x_from_candidates(x, list_other_in_square)
    #print(all_candidates)

def search_unique_candidates_loop():
    while True:
        all_candidates = get_all_candidates()
        reduce_candidates_by_pairs(all_candidates)
        reduce_candidates_by_square_line_intersection(all_candidates)
        if find_unique_values_and_apply_chages(all_candidates):
            all_candidates = get_all_candidates()
        else:
            break
    #print results
    for l in sudoku_arr:
        print(l)
    print()
    all_candidates = get_all_candidates()
    if all_candidates:
        print("Sudoku was not solved! There are unknown cells left:")
        for c in all_candidates:
            print(c)
    else:
        print("Sudoku SOLVED!")

search_unique_candidates_loop()

Python Fiddle

Python Cloud IDE