def sudoku_solver(sudoku):

    variables=np.array([])
    complete=False;
    returned=False;
    for i in range(81):
        if sudoku[i//9,i%9] == 0.0:
            variables = np.append(variables,i)
    x = 0;

    while complete == False:
        if len(variables)==0:
            complete=True
            break;
        if sudoku[int(variables[x]//9),int(variables[x]%9)] == 9:
            sudoku[int(variables[x]//9),int(variables[x]%9)] = 0;
            x=x-1;

        if sudoku[int(variables[x]//9),int(variables[x]%9)] != 9:
            sudoku[int(variables[x]//9),int(variables[x]%9)] = sudoku[int(variables[x]//9),int(variables[x]%9)]+1
            if isSquareLegal(sudoku,int(variables[x]//9)+1,int(variables[x]%9)+1) == True:
                x=x+1

        if isSquareLegal(sudoku,int(variables[len(variables)-1])//9+1,int(variables[len(variables)-1])%9+1) == True:
            complete = True

    if len(variables)>0:
        if sudoku[int(variables[0]//9),int(variables[0]%9)]==0:
            for i in range(9):
                for j in range(9):
                    sudoku[i,j] = -1;




    solved_sudoku = sudoku
    return solved_sudoku

def getRow(a,i,j):
    return a[i-1,:]

def getColumn(a,i,j):
    return a[:,j-1]

def getSquare(a,i,j):
    if i<4 and j<4:
        return np.concatenate((a[0,0:3],a[1,0:3],a[2,0:3]))
    elif  i<4 and 3<j<7:
        return np.concatenate((a[0,3:6],a[1,3:6],a[2,3:6]))
    elif  i<4 and 6<j<10:
        return np.concatenate((a[0,6:9],a[1,6:9],a[2,6:9]))
    elif  3<i<7 and j<4:
        return np.concatenate((a[3,0:3],a[4,0:3],a[5,0:3]))
    elif  3<i<7 and 3<j<7:
        return np.concatenate((a[3,3:6],a[4,3:6],a[5,3:6]))
    elif  3<i<7 and 6<j<10:
        return np.concatenate((a[3,6:9],a[4,6:9],a[5,6:9]))
    elif  6<i<10 and j<4:
        return np.concatenate((a[6,0:3],a[7,0:3],a[8,0:3]))
    elif  6<i<10 and 3<j<7:
        return np.concatenate((a[6,3:6],a[7,3:6],a[8,3:6]))
    elif  6<i<10 and 6<j<10:
        return np.concatenate((a[6,6:9],a[7,6:9],a[8,6:9]))


def isSquareLegal(a,i,j):
    if (allDiff(getRow(a,i,j)) and allDiff(getColumn(a,i,j)) and allDiff(getSquare(a,i,j))) and a[i-1,j-1]!=0:
        return True
    else:
        return False

def allDiff(a):
    temp = np.flip(np.sort(a),0);
    for i in range(len(a)):
        if i == len(a)-1:
            return True
        elif temp[i+1] == 0:
            return True
        elif temp[i] == temp[i+1]:
            return False



sudoku = sudokus[1].copy()
print("This is sudoku number", 1)
print(sudoku)
your_solution = sudoku_solver(sudokus[1])
print("This is your solution for sudoku number", 1)
print(your_solution)