Судоку 9*9

class Sudoku:
    sudoku_digits = set('123456789')
    block_size    = 3
    grid_size     = block_size * block_size
 
    rows_sets     = []
    cols_sets     = []
    blocks_sets   = []
 
    cells_arr     = [0] * grid_size * grid_size
    task_cells    = set()
    #==========================================================================
    def __init__(self):
        for k in range(Sudoku.grid_size):
            self.rows_sets.append(set())
            self.cols_sets.append(set())
            self.blocks_sets.append(set())
    #==========================================================================
    def get_block_row(i):
        return i // Sudoku.block_size
    #==========================================================================
    def get_block_col(j):
        return j // Sudoku.block_size
    #==========================================================================
    def get_block_ind(i, j):
        return Sudoku.get_block_row(i) * Sudoku.block_size + Sudoku.get_block_col(j)
    #==========================================================================
    def good_add_task_row(self, row, i):
        row = row.replace(' ', '')
        row = row.replace('\t', '')
        if len(row) == 0:
            return True
        res = row.isdigit()
        if not res:
            print('Строка должна содержать только цифры и пробелы.')
            return res
        res = len(row) == Sudoku.grid_size
        if not res:
            print('Строка должна содержать', Sudoku.grid_size, 'цифр.')
            return res
 
        row_without_zeros = row.replace('0','')
        set_without_zeros = set(row_without_zeros)
        res = len(row_without_zeros) == len(set_without_zeros)
        if not res:
            print('Ненулевые цифры в строке не должны повторяться.')
            return res
 
        for j in range(Sudoku.grid_size):
            if row[j] == '0':
                continue
 
            res = row[j] not in self.cols_sets[j]
            if not res:
                print('В столбце', j + 1, 'уже есть цифра', row[j])
                return res
 
            block_ind = Sudoku.get_block_ind(i, j)
            res = row[j] not in self.blocks_sets[block_ind]
            if not res:
                block_row_begin = Sudoku.get_block_row(i) * Sudoku.block_size + 1
                block_row_end   = block_row_begin + Sudoku.block_size - 1
                block_col_begin = Sudoku.get_block_col(j) * Sudoku.block_size + 1
                block_col_end   = block_col_begin + Sudoku.block_size - 1
 
                print('В блоке со строками', block_row_begin, '-', block_row_end,\
                      'и столбцами', block_col_begin, '-', block_col_end, 'уже есть цифра', row[j], '.')
                return res
 
        for jj in range(Sudoku.grid_size):
            if row[jj] != '0':
                self.cols_sets[jj].add(row[jj])
                self.blocks_sets[Sudoku.get_block_ind(i, jj)].add(row[jj])
 
                self.task_cells.add((i, jj))
                self.cells_arr[Sudoku.get_cells_arr_ind(i, jj)] = '\033[4m' + row[jj] + '\033[0m'
 
        self.rows_sets[i] = set_without_zeros
        return res
    #==========================================================================
    def input_task(self):
        print('Введите строки-задания из 9 цифр (можно с пробелами), на месте пустых клеток ставьте нули,')
        print('например: 400 803 001. \nЕсли строка с каким-то номером не содержит цифр-заданий - просто нажмите Enter.')
        i = 0
        while i < self.grid_size:
            s = 'строка ' + str(i + 1) + ': '
            row = input(s)
            if not self.good_add_task_row(row, i):
                print('Повторите ввод.')
            else:
                i += 1
            print()
    #==========================================================================
    def get_cells_arr_ind(i, j):
        return i * Sudoku.grid_size + j
    #==========================================================================
    def remove_and_get_dig_from_cell(self, i, j):
        old_dig = self.cells_arr[Sudoku.get_cells_arr_ind(i, j)]
        self.cells_arr[Sudoku.get_cells_arr_ind(i, j)] = 0
 
        self.rows_sets[i].remove(old_dig)
        self.cols_sets[j].remove(old_dig)
        self.blocks_sets[Sudoku.get_block_ind(i, j)].remove(old_dig)
        return old_dig
    #==========================================================================
    def insert_dig_in_cell(self, dig, i, j):
        self.cells_arr[Sudoku.get_cells_arr_ind(i, j)] = dig
        self.rows_sets[i].add(dig)
        self.cols_sets[j].add(dig)
        self.blocks_sets[Sudoku.get_block_ind(i, j)].add(dig)
    #==========================================================================
    def good_insert_min_dig_in_cell_greater_than(self, old_dig, i, j):
        cell_dig_set = \
            Sudoku.sudoku_digits - \
            (self.rows_sets[i] | self.cols_sets[j] | self.blocks_sets[Sudoku.get_block_ind(i, j)])
 
        res = len(cell_dig_set) != 0
        if res:
            cell_dig_list = list(cell_dig_set)
            cell_dig_list.sort()
            for dig in cell_dig_list:
                res = dig > old_dig
                if res:
                    self.insert_dig_in_cell(dig, i, j)
                    break
        return res
    #==========================================================================
    def good_inc_dig_in_cell_or_remove(self, i, j):
        old_dig = self.remove_and_get_dig_from_cell(i, j)
        return self.good_insert_min_dig_in_cell_greater_than(old_dig, i, j)
    #==========================================================================
    def good_insert_min_dig_in_cell(self, i, j):
        cell_dig_set = \
            Sudoku.sudoku_digits - \
            (self.rows_sets[i] | self.cols_sets[j] | self.blocks_sets[Sudoku.get_block_ind(i, j)])
 
        res = len(cell_dig_set) != 0
        if res:
            cell_dig_list = list(cell_dig_set)
            min_good_dig  = min(cell_dig_list)
            self.insert_dig_in_cell(min_good_dig, i, j)
        return res
    #==========================================================================
    def create_solution(self):
        cell_ind         = 0
        inserting_digits = True
        while 0 <= cell_ind < Sudoku.grid_size * Sudoku.grid_size:
            i, j = divmod(cell_ind, Sudoku.grid_size)
            if inserting_digits:
                if (i, j) not in self.task_cells and not self.good_insert_min_dig_in_cell(i, j):
                    inserting_digits = False
                    cell_ind -= 1
                    continue
                else:
                    cell_ind += 1
                    continue
            else: #Увеличиваем цифры в клетках.
                if (i, j) not in self.task_cells and self.good_inc_dig_in_cell_or_remove(i, j):
                    inserting_digits = True
                    cell_ind += 1
                    continue
                else:
                    cell_ind -= 1
    #==========================================================================
    def print_solution(self):
        print('РЕШЕНИЕ (заданные цифры подчеркнуты):')
 
        for i in range(Sudoku.grid_size):
            cells_arr_row = self.cells_arr[ i * Sudoku.grid_size : (i + 1) * Sudoku.grid_size ]
            cells_arr_row.insert(Sudoku.block_size * 2, '|')
            cells_arr_row.insert(Sudoku.block_size * 1, '|')
            cells_arr_row.insert(Sudoku.block_size * 0, '|')
 
            str_row = '  '.join(cells_arr_row)
            str_row = 'Строка ' + str(i + 1) + ':\t' + str_row
            if i > 0 and i % Sudoku.block_size == 0:
                print('----------------------------------------------')
            print(str_row)
#=============================================================================
def main():
    sudoku = Sudoku()
    sudoku.input_task()
    sudoku.create_solution()
    sudoku.print_solution()
#=============================================================================
main()