Sudoku Solver

Q: Какова временная сложность решателя судоку с возвратом?

Экспоненциальная сложность в худшем случае, O(9^m) для m пустых клеток, поскольку для каждой клетки возможно до 9 вариантов цифр. В реальных головоломках правила строк, столбцов и блоков отсекают большинство ветвей, а заполнение сначала самой пустой клетки отсекает большую часть остальных.

СложноПоиск с возвратом

+10

Поле судоку — это сетка 9 × 9, разделённая на девять квадратов 3 × 3. В решённом поле в каждой строке, каждом столбце и каждом квадрате каждая цифра от 1 до 9 встречается ровно один раз.

Головоломка представлена в виде 9 строк, по одной на каждую строку поля, начиная сверху; . обозначает пустую клетку. Заполните все пустые клетки и верните решённое поле в том же формате. У поля есть ровно одно решение.

Функция

solveSudoku(board: string-array) → string-array

boardstring-array: 9 строк головоломки, точка в каждой пустой ячейке
Возвращаетstring-array: 9 строк решённой доски

Ограничения

board содержит 9 строк длиной 9 символов.
Каждый символ — это . или одна из цифр от 1 до 9.
Заданные цифры никогда не повторяются в строке, столбце или блоке.
У этой доски ровно одно решение.

Примеры

Ввод: board = ["9.7.....6", "824.3....", "..1..9..2", ".9...2.18", "...4....5", "1325.8...", "...687...", "......8.9", ".4.9...5."]
Вывод: ["957214386", "824736591", "361859742", "495372618", "786491235", "132568974", "519687423", "273145869", "648923157"]
Пояснение: В верхней строке 9.7.....6 уже стоят 9, 7 и 6, поэтому в шести пустых ячейках должны быть 1, 2, 3, 4, 5 и 8. Столбцы и блоки определяют, куда поставить каждую цифру, и строка становится такой: 957214386.

Дополнительный вопрос

В судоку-киллере суммы чисел в группах клеток должны совпадать с заданными. Как добавить это правило в поиск и использовать его, чтобы раньше отсекать ветви?

Решение

Реши её с помощью поиска с возвратом: поставь подходящую цифру, продолжай, а если доску нельзя заполнить — отмени этот ход. Порядок клеток определяет скорость. На сложной доске при обходе в порядке чтения могут посещаться сотни миллионов частично заполненных досок; если сначала заполнять клетку с наименьшим числом вариантов, их будет около сотни.

Возвратный поиск в порядке чтения

Верно, но не успевает на самых больших тестах

Идея

Заполняй пустые клетки в порядке чтения, каждый раз ставя наименьшую подходящую цифру. Если для клетки больше не осталось цифр, вернись к предыдущей клетке и попробуй следующую цифру. По очереди проверяются все комбинации, соответствующие правилам, поэтому поиск находит решение.

Три таблицы позволяют проверять каждую цифру за O(1): rowUsed[r][d], colUsed[c][d] и boxUsed[b][d], где b = (r / 3) * 3 + c / 3. При размещении цифры задаются три значения, а при её удалении они очищаются.

Фиксированный порядок — слабое место: поиск может заполнить целую строку цифрами, которые подходят на своём месте, и лишь позже выяснить, что для многих клеток они не оставляют места. На доске, в верхних строках которой почти нет подсказок, а ответами служат большие цифры, поиск перебирает более 300 миллионов частично заполненных досок.

Алгоритм

Считай доску в сетку, используя 0 для пустой ячейки, заполни rowUsed, colUsed и boxUsed и перечисли пустые ячейки в порядке чтения.
backtrack(k): если k равно количеству пустых ячеек, верни true.
Для каждой цифры d от 1 до 9, которая ещё не используется в строке, столбце и блоке ячейки k, помести её в ячейку, отметь её и верни true, если это сделает backtrack(k+1); в противном случае сними отметку.
Если ни одна цифра не подходит, очисти ячейку и верни false. Вызови backtrack(0) и преобразуй сетку обратно в строки.

def solveSudoku(board):
    grid = [[0 if ch == "." else int(ch) for ch in row] for row in board]
    # row_used[r][d] is True when digit d already sits in row r; same for
    # columns and boxes. Box b holds the cells with (r // 3) * 3 + c // 3 == b.
    row_used = [[False] * 10 for _ in range(9)]
    col_used = [[False] * 10 for _ in range(9)]
    box_used = [[False] * 10 for _ in range(9)]
    empties = []
    for r in range(9):
        for c in range(9):
            d = grid[r][c]
            if d:
                row_used[r][d] = col_used[c][d] = box_used[(r // 3) * 3 + c // 3][d] = True
            else:
                empties.append((r, c))

    def backtrack(k):
        if k == len(empties):
            return True
        r, c = empties[k]
        b = (r // 3) * 3 + c // 3
        for d in range(1, 10):
            if not row_used[r][d] and not col_used[c][d] and not box_used[b][d]:
                grid[r][c] = d
                row_used[r][d] = col_used[c][d] = box_used[b][d] = True
                if backtrack(k + 1):
                    return True
                row_used[r][d] = col_used[c][d] = box_used[b][d] = False
        grid[r][c] = 0
        return False

    backtrack(0)
    return ["".join(str(d) for d in row) for row in grid]

Сначала заполните самую пустую ячейку

Идея

Решение не зависит от порядка заполнения, поэтому выбирайте такой порядок, который сокращает перебор: на каждом шаге заполняйте пустую ячейку, в которую можно вписать наименьшее число цифр. Ячейка, в которую можно вписать только одну цифру, заполнена принудительно и не создаёт дополнительной ветви перебора. Если нельзя вписать ни одной цифры, ячейку выбирают сразу, поэтому ошибочная доска обнаруживается немедленно.

Чтобы быстро подсчитывать допустимые цифры для 81 ячейки на каждом шаге, храните каждую строку, столбец и блок в виде битовой маски: бит d в rows[r] установлен, если цифра d есть в строке r. Для ячейки допустимы цифры, заданные выражением ~(rows[r] | cols[c] | boxes[b]) & 0x3FE, где 0x3FE сохраняет биты с 1-го по 9-й, а количество цифр равно числу установленных битов. При размещении d установите бит d в трёх масках; исключающее ИЛИ удаляет его.

Алгоритм

Постройте сетку и маски rows, cols и boxes по заданным цифрам.
backtrack(): просмотрите все ячейки, вычислите допустимые цифры для каждой пустой ячейки и выберите первую ячейку с наименьшим количеством вариантов. Если пустых ячеек нет, верните true.
Для каждой допустимой цифры этой ячейки установите её, установите соответствующий бит в трёх масках и верните true, если backtrack() вернёт true; иначе сбросьте биты.
Если ни одна цифра не подходит, очистите ячейку и верните false. Вызовите backtrack() и снова преобразуйте сетку в строки.

def solveSudoku(board):
    grid = [[0 if ch == "." else int(ch) for ch in row] for row in board]
    # Bit d of rows[r] is set when digit d already sits in row r; same for
    # columns and boxes. Box b holds the cells with (r // 3) * 3 + c // 3 == b.
    rows, cols, boxes = [0] * 9, [0] * 9, [0] * 9
    for r in range(9):
        for c in range(9):
            d = grid[r][c]
            if d:
                rows[r] |= 1 << d
                cols[c] |= 1 << d
                boxes[(r // 3) * 3 + c // 3] |= 1 << d

    def backtrack():
        # Pick the empty cell with the fewest digits left (the first one on a tie).
        best_r, best_c, best_allowed, best_count = -1, -1, 0, 10
        for r in range(9):
            for c in range(9):
                if grid[r][c] == 0:
                    # Bits 1 to 9 of 0x3FE are the nine digits.
                    allowed = ~(rows[r] | cols[c] | boxes[(r // 3) * 3 + c // 3]) & 0x3FE
                    count = bin(allowed).count("1")
                    if count < best_count:
                        best_r, best_c, best_allowed, best_count = r, c, allowed, count
        if best_r == -1:
            return True  # no empty cell is left: the board is solved
        r, c = best_r, best_c
        b = (r // 3) * 3 + c // 3
        for d in range(1, 10):
            bit = 1 << d
            if best_allowed & bit:
                grid[r][c] = d
                rows[r] |= bit
                cols[c] |= bit
                boxes[b] |= bit
                if backtrack():
                    return True
                rows[r] ^= bit
                cols[c] ^= bit
                boxes[b] ^= bit
        grid[r][c] = 0
        return False

    backtrack()
    return ["".join(str(d) for d in row) for row in grid]

Ловушки и крайние случаи

Забыть удалить цифру из записей строки, столбца и блока при отмене хода. Тогда последующие клетки будут считать, что цифра уже использована, и поиск не найдёт решение.
Использовать r / 3 + c / 3 для блока. Клетки (0, 4) и (4, 0) обе попадают в 1, поэтому два блока используют одну запись, и доску невозможно заполнить. Используйте (r / 3) * 3 + c / 3 с целочисленным делением.
Не останавливаться на первом решении. Тогда шаги отмены снова очистят доску, прежде чем вы её прочитаете.

Частые вопросы3

Какова временная сложность решателя судоку с возвратом?

Экспоненциальная сложность в худшем случае, O(9^m) для m пустых клеток, поскольку для каждой клетки возможно до 9 вариантов цифр. В реальных головоломках правила строк, столбцов и блоков отсекают большинство ветвей, а заполнение сначала самой пустой клетки отсекает большую часть остальных.

Как проверить, что у судоку ровно одно решение?

Выполните тот же поиск с возвратом, но подсчитывайте решения и остановитесь, когда их количество достигнет 2. Количество 1 означает, что у головоломки единственное решение, 0 — что решения нет. Генераторы головоломок выполняют эту проверку после удаления каждой подсказки.

Есть ли способ решать судоку быстрее, чем с помощью возврата с отсечением?

Большинство быстрых решателей по-прежнему используют возврат, но перед каждой догадкой делают больше выводов. Распространение ограничений заполняет все ячейки, в которых остался только один вариант, а также размещает каждую цифру, которая подходит только для одной ячейки в своей строке, столбце или блоке, после чего повторяет этот процесс. Судоку также можно представить как задачу точного покрытия и решить с помощью алгоритма X Кнута.

def solveSudoku(board):
    # Напишите код здесь

Тест #1

Аргумент

board = ["9.7.....6", "824.3....", "..1..9..2", ".9...2.18", "...4....5", "1325.8...", "...687...", "......8.9", ".4.9...5."]

Ожидаемый вывод

["957214386", "824736591", "361859742", "495372618", "786491235", "132568974", "519687423", "273145869", "648923157"]