sudoku_solve.py

import time,copy

#check row is correct sudoku row ----------------------------------------------
def check_row(m,x,y,dx,dy):
    t = {1:0, 2:0, 3:0, 4:0, 5:0}
    for i in range(size):
        t[abs(m[y][x])] += 1
        x += dx
        y += dy
    for i in range(1,size+1):
        if (t[i] != 1):
            return False
    return True


# check matrix is right sudoku ------------------------------------------------
def check_matrix(m):
    for i in range(size):
        if not check_row(m,i,0,0,1): # column
            return False
        if not check_row(m,0,i,1,0): # row
            return False
    if not (check_row(m,0,0,1,1)): # top-left diagonal
        return False
    if not (check_row(m,0,4,1,-1)): # bottom-left diagonal
        return False
    return True

# this one find avialable nums for cell ---------------------------------------
def get_range_for_cell(m,x,y):
    r = [1,2,3,4,5]
    for j in range(size):
        try:
            i = r.index(abs(m[y][j]))
        except ValueError: pass
        else: del r[i]
        try:
            i = r.index(abs(m[j][x]))
        except ValueError: pass
        else: del r[i]
    return r

# main solve routine ----------------------------------------------------------
def solve(m):
    mout = copy.deepcopy(m)
    tmr = time.time()
    try:
        d = []
        modified = 0
        while (True):
            for y in range(size):
                for x in range(size):
                    if (m[y][x] <= 0):
                        rng = get_range_for_cell(mout,x,y) # searching possible variants for cell
                        if len(rng) == 1:
                            mout[y][x] = -(rng[0]) # just one variant - put it
                            modified += 1
                        elif len(rng) > 1:
                            d.append({'x':x, 'y':y, 'range':rng, 'pos':0 }) # put variants and set pointer to zero
            if (modified == 0):
                break
            modified = 0
            d.clear()

        # check variant count
        variant_count = 1
        for x in d:
            variant_count *= len(x['range'])
        #print(f'Variants: {variant_count}')
        if (variant_count>50000):
            return [-2,f'Too much variants({variant_count})']

        if (variant_count == 1):
            if (check_matrix(mout) == False):
                return [-1,'Just one incorrect solve :(']
            else:
                return [0,mout]
        while (True):

            #paste values
            for v1 in d:
                mout[v1['y']][v1['x']] = -(v1['range'][v1['pos']])

            #check matrix for done
            if (check_matrix(mout) == True):
                return [0,mout]

            #iterate values
            vc = 0
            for vc in range(len(d)):
                d[vc]['pos'] += 1
                if (d[vc]['pos'] == len(d[vc]['range'])):
                    d[vc]['pos'] = 0
                #check is last item reseted
                    if (vc == len(d)):
                        break
                else:
                    break

        return [-3,False]
    finally:
        pass
        #tmr = time.time()-tmr
        #print(f"Total taken: {tmr:.5f}s")
        #print(f"Per try: {(tmr/variant_count):.5f}s")

"""
matrix = [
[5,1,3,2,4],
[0,0,0,0,0],
[0,0,0,0,0],
[0,0,0,0,0],
[2,4,5,1,3]]


matrix = [
    [5,1,0,2,0],
    [0,0,0,5,1],
    [4,5,1,0,0],
    [0,0,0,4,5],
    [0,4,5,0,3]]
matrix = [
    [0,1,0,2,0],
    [0,0,0,5,1],
    [4,5,0,0,0],
    [0,0,0,4,5],
    [0,4,5,0,0]]


print(solve(matrix))

"""
size = 5