Валидное судоку (LeetCode 36): решение на Python, индекс блока и граничные случаи

Valid Sudoku (LeetCode 36) даёт частично заполненное поле 9 на 9 и спрашивает, не нарушают ли заполненные клетки правила судоку. Решать головоломку не нужно. Вы только проверяете, что ни одна цифра не повторяется в строке, столбце или квадрате 3 на 3. Один проход с тремя множествами увиденных цифр делает это за O(81), то есть за константу.

Задача

Поле — это сетка 9 на 9 из символов, каждый из которых либо цифра от 1 до 9, либо . для пустой клетки. Верните true, если заполненные клетки соблюдают эти правила:

• В каждой строке нет повторяющихся цифр.
• В каждом столбце нет повторяющихся цифр.
• В каждом квадрате 3 на 3 нет повторяющихся цифр.

Поле может быть валидным, даже если у него нет решения. Проверяются только заполненные клетки.

Подход: три множества на единицу

Храните множество увиденных цифр для каждой строки, каждого столбца и каждого квадрата. Для каждой заполненной клетки проверьте цифру во всех трёх множествах и добавьте её, если она новая.

Единственное, над чем стоит подумать, — это индекс квадрата. Для клетки в строке r и столбце c номер квадрата равен (r // 3) * 3 + c // 3. Он считает квадраты слева направо, сверху вниз, от 0 до 8.

def is_valid_sudoku(board):
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    for r in range(9):
        for c in range(9):
            ch = board[r][c]
            if ch == ".":
                continue
            b = (r // 3) * 3 + c // 3
            if ch in rows[r] or ch in cols[c] or ch in boxes[b]:
                return False
            rows[r].add(ch)
            cols[c].add(ch)
            boxes[b].add(ch)
    return True

Трассировка

Предположим, в строке 0 стоит 5 в столбце 0 и ещё одна 5 в столбце 4. Первая 5 добавляется в rows[0], cols[0] и boxes[0]. В столбце 4 проверка ch in rows[0] истинна, поэтому функция сразу возвращает false. Одинаковые цифры в одном квадрате или столбце ловятся двумя другими множествами так же.

Сложность

Поле всегда 9 на 9, поэтому время постоянное — 81 посещение клеток. Если обобщить до поля n на n, это O(n в квадрате) по времени и O(n в квадрате) по памяти. Говорите оба варианта, потому что интервьюеры часто спрашивают, как это масштабируется.

Вариации, о которых спрашивают интервьюеры

Версия с битовой маской заменяет каждое множество целым числом. mask & (1 << d) проверяет цифру, а mask |= 1 << d записывает её. Это быстрее, но версию с множествами легче написать без ошибок под давлением времени, поэтому сначала пишите её.

Частые ошибки

• Проверить строки и столбцы, но забыть про квадраты.
• Неверная формула квадрата, например r // 3 + c // 3, которая даёт одинаковый индекс разным квадратам.
• Обращение с . как с цифрой, из-за чего две пустые клетки считаются повтором.
• Попытка решить поле, когда вопрос требует только проверки валидности.

Краевые случаи для проверки

Как объяснить это на интервью

1. Переформулируйте правила и скажите, что вы только проверяете, а не решаете.
2. Назовите три единицы и скажите, что каждой нужно множество увиденных цифр.
3. Дайте формулу индекса квадрата и объясните её на одном примере.
4. Напишите один проход и ранний возврат.
5. Назовите сложность и предложите версию с битовой маской, если попросят.

Перед публикацией я проверил код выше против простой проверки строк, столбцов и квадратов на 20 000 случайных полях, часть из которых была валидной, а часть намеренно сломанной. Такая быстрая случайная проверка — хорошая привычка во время практики.

Связанная практика

Смотрите нашу шпаргалку по Big O для терминов сложности, список LeetCode Blind 75 для того, что практиковать дальше, и руководство по ассистенту для собеседований по программированию для того, как практиковаться.

Проговаривайте свой подход вслух, пока пишете код. Транскрипт показывает, сформулировали ли вы ключевое наблюдение до того, как начали писать. Соблюдайте правила работодателя об AI-инструментах на любом живом ассессменте.