Решение судоку

Решение судоку через Backtracking

Понимание задачи

Судоку - классическая задача на поиск с возвратом (backtracking). Идея: перебираем все возможные числа для каждой пустой ячейки, проверяем ограничения (строка, столбец, блок), и возвращаемся назад если попали в тупик.

Оптимальное решение: Backtracking

def solve_sudoku(board: list[list[int]]) -> bool:
    """
    Решает судоку методом backtracking.
    
    Args:
        board: Сетка 9x9, 0 = пустая ячейка
    
    Returns:
        True если решение найдено (board изменяется на месте)
    """
    
    # Находим следующую пустую ячейку
    for i in range(9):
        for j in range(9):
            if board[i][j] == 0:
                # Пробуем каждое число от 1 до 9
                for num in range(1, 10):
                    if is_valid(board, i, j, num):
                        # Положим число и рекурсивно решаем
                        board[i][j] = num
                        
                        if solve_sudoku(board):
                            return True
                        
                        # Возвращаемся: это число не подошло
                        board[i][j] = 0
                
                # Если ни одно число не подошло - возвращаемся
                return False
    
    # Все ячейки заполнены - решение найдено
    return True

def is_valid(board: list[list[int]], row: int, col: int, num: int) -> bool:
    """Проверяет, можно ли поставить num в board[row][col]."""
    
    # 1. Проверка строки
    if num in board[row]:
        return False
    
    # 2. Проверка столбца
    if num in [board[i][col] for i in range(9)]:
        return False
    
    # 3. Проверка блока 3x3
    block_row, block_col = 3 * (row // 3), 3 * (col // 3)
    for i in range(block_row, block_row + 3):
        for j in range(block_col, block_col + 3):
            if board[i][j] == num:
                return False
    
    return True

Сложность:

• Время: O(9^n) в худшем случае, где n = кол-во пустых ячеек (обычно ~40-50). На практике быстро благодаря constraints.
• Память: O(n) для рекурсивного стека

Оптимизация: Constraint Propagation

class SudokuSolver:
    def __init__(self, board: list[list[int]]):
        self.board = board
        # Возможные значения для каждой ячейки
        self.possibilities = [[set(range(1, 10)) for _ in range(9)] for _ in range(9)]
        self.init_possibilities()
    
    def init_possibilities(self):
        """Инициализируем возможные значения на основе существующих чисел."""
        for i in range(9):
            for j in range(9):
                if self.board[i][j] != 0:
                    self.eliminate(i, j, self.board[i][j])
    
    def eliminate(self, row: int, col: int, num: int):
        """Удаляем num из всех связанных ячеек (строка, столбец, блок)."""
        # Из строки
        for j in range(9):
            self.possibilities[row][j].discard(num)
        
        # Из столбца
        for i in range(9):
            self.possibilities[i][col].discard(num)
        
        # Из блока 3x3
        block_row, block_col = 3 * (row // 3), 3 * (col // 3)
        for i in range(block_row, block_row + 3):
            for j in range(block_col, block_col + 3):
                self.possibilities[i][j].discard(num)
    
    def solve(self) -> bool:
        """Решает с учётом constraint propagation."""
        # Находим ячейку с минимальным кол-вом возможностей (эвристика)
        min_count = 10
        min_cell = None
        
        for i in range(9):
            for j in range(9):
                if self.board[i][j] == 0:
                    count = len(self.possibilities[i][j])
                    if count == 0:
                        return False  # Противоречие
                    if count < min_count:
                        min_count = count
                        min_cell = (i, j)
        
        if min_cell is None:
            return True  # Решено
        
        i, j = min_cell
        for num in list(self.possibilities[i][j]):
            # Делаем копию состояния
            board_copy = [row[:] for row in self.board]
            poss_copy = [[cell.copy() for cell in row] for row in self.possibilities]
            
            # Пробуем это число
            self.board[i][j] = num
            self.possibilities[i][j] = {num}
            self.eliminate(i, j, num)
            
            if self.solve():
                return True
            
            # Откатываемся
            self.board = board_copy
            self.possibilities = poss_copy
        
        return False

Тест решения

def test_sudoku():
    board = [
        [5, 3, 0, 0, 7, 0, 0, 0, 0],
        [6, 0, 0, 1, 9, 5, 0, 0, 0],
        [0, 9, 8, 0, 0, 0, 0, 6, 0],
        [8, 0, 0, 0, 6, 0, 0, 0, 3],
        [4, 0, 0, 8, 0, 3, 0, 0, 1],
        [7, 0, 0, 0, 2, 0, 0, 0, 6],
        [0, 6, 0, 0, 0, 0, 2, 8, 0],
        [0, 0, 0, 4, 1, 9, 0, 0, 5],
        [0, 0, 0, 0, 8, 0, 0, 7, 9]
    ]
    
    if solve_sudoku(board):
        print("Судоку решено!")
        for row in board:
            print(row)
    else:
        print("Решения не существует")

Ключевые оптимизации

1. Выбор ячейки: Выбираем ячейку с минимальным кол-вом возможностей (Most Constrained Variable)
2. Constraint Propagation: Сразу исключаем невозможные значения
3. Ранний выход: Если возможностей нет - возвращаемся назад

Сравнение подходов

Интересный факт

Оптимальное судоку с минимальным кол-вом подсказок имеет ровно 17 заполненных ячеек. Судоку с 16 и менее подсказками либо имеет несколько решений, либо невозможно.

Для интервью

Дай простой backtracking решение, потом предложи оптимизацию с constraint propagation если останется время.