Valid Sudoku: проверка доски за один проход хеш-множествами и битмасками

Коротко

Valid Sudoku (LeetCode 36) — задача уровня medium, которую на деле решают за пять минут, если знать один приём: как по координатам клетки получить номер квадрата 3×3. Всё остальное сводится к уже знакомой проверке на дубликаты, только не в одном массиве, а сразу в 27.

Условие

Дана доска 9×9, клетки — строки "1"–"9" или "." для пустой клетки. Нужно вернуть True, если заполненные клетки не нарушают правил судоку:

• в каждой строке цифры не повторяются;
• в каждом столбце цифры не повторяются;
• в каждом из девяти квадратов 3×3 цифры не повторяются.

board = [
    ["5", "3", ".", ".", "7", ".", ".", ".", "."],
    ["6", ".", ".", "1", "9", "5", ".", ".", "."],
    [".", "9", "8", ".", ".", ".", ".", "6", "."],
    ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
    ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
    ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
    [".", "6", ".", ".", ".", ".", "2", "8", "."],
    [".", ".", ".", "4", "1", "9", ".", ".", "5"],
    [".", ".", ".", ".", "8", ".", ".", "7", "9"],
]
# Ответ: True

Самое важное в условии — то, чего в нём нет. Доска не обязана быть решаемой. Проверяем только то, что уже стоит на доске. Об этом подробнее в конце, а на собеседовании этот вопрос стоит задать вслух в первую же минуту.

Сводим к знакомой задаче

Если убрать сетку, задача звучит так: есть 27 групп по 9 клеток, в каждой группе не должно быть повторов среди непустых клеток. А «есть ли повтор в наборе» — это Contains Duplicate: кладём элементы в множество и смотрим, не встречался ли элемент раньше. Потренироваться на чистой версии можно в задаче про дубликаты.

Значит, вопрос только в том, как организовать обход этих 27 групп. Есть два пути: три отдельных прохода или один общий.

Решение в три прохода

Самый прямолинейный вариант: отдельно проверить строки, столбцы и квадраты. Код длиннее, но ошибиться в нём сложно, и это хорошая отправная точка на собеседовании.

def has_duplicates(cells):
    digits = [c for c in cells if c != "."]
    return len(digits) != len(set(digits))


def is_valid_sudoku_naive(board):
    for r in range(9):
        if has_duplicates(board[r]):
            return False
    for c in range(9):
        if has_duplicates([board[r][c] for r in range(9)]):
            return False
    for br in range(0, 9, 3):
        for bc in range(0, 9, 3):
            box = [board[r][c] for r in range(br, br + 3) for c in range(bc, bc + 3)]
            if has_duplicates(box):
                return False
    return True

has_duplicates выбрасывает точки и сравнивает длину списка с размером множества: если какие-то цифры совпали, множество окажется короче. Квадраты перебираем по левым верхним углам (0, 0), (0, 3), ..., (6, 6).

Каждая клетка читается ровно три раза — по разу на строку, столбец и квадрат. Для доски 9×9 это 243 чтения, то есть константа. Плохого в этом решении ничего нет, но интервьюер почти наверняка спросит: «А можно за один проход?»

Решение в один проход

Идея: идём по клеткам один раз и для каждой цифры сразу проверяем три множества — её строки, её столбца и её квадрата. Строку и столбец знаем из координат (r, c). Остаётся понять, в каком квадрате клетка.

Откуда берётся (r // 3) * 3 + c // 3

Пронумеруем квадраты так же, как читаем текст: слева направо, сверху вниз.

 0 | 1 | 2
---+---+---
 3 | 4 | 5
---+---+---
 6 | 7 | 8

Целочисленное деление на 3 сжимает координату 0–8 в номер полосы 0–2: клетки 0, 1, 2 попадают в полосу 0, клетки 3, 4, 5 — в полосу 1, клетки 6, 7, 8 — в полосу 2. Значит, r // 3 — номер «строки квадратов», c // 3 — номер «столбца квадратов».

Дальше обычный перевод двумерного индекса в одномерный, как при хранении матрицы в плоском массиве: строка * ширина + столбец. Ширина сетки квадратов — 3, отсюда (r // 3) * 3 + c // 3. Если вывести формулу для каждой клетки, получится ровно картинка выше:

for r in range(9):
    print(" ".join(str((r // 3) * 3 + c // 3) for c in range(9)))

0 0 0 1 1 1 2 2 2
0 0 0 1 1 1 2 2 2
0 0 0 1 1 1 2 2 2
3 3 3 4 4 4 5 5 5
3 3 3 4 4 4 5 5 5
3 3 3 4 4 4 5 5 5
6 6 6 7 7 7 8 8 8
6 6 6 7 7 7 8 8 8
6 6 6 7 7 7 8 8 8

Например, клетка (4, 7): 4 // 3 = 1, 7 // 3 = 2, номер квадрата 1 * 3 + 2 = 5 — средний ряд, правый квадрат. Сходится.

Код

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):
            d = board[r][c]
            if d == ".":
                continue
            b = (r // 3) * 3 + c // 3
            if d in rows[r] or d in cols[c] or d in boxes[b]:
                return False
            rows[r].add(d)
            cols[c].add(d)
            boxes[b].add(d)
    return True

Порядок важен: сначала проверить все три множества, потом добавить. Если добавить раньше проверки, цифра найдёт сама себя.

Обратите внимание на [set() for _ in range(9)]. Запись [set()] * 9 создала бы список из девяти ссылок на одно и то же множество, и все строки «видели» бы цифры друг друга. Это классическая ловушка Python, о ней ниже.

Разбор на примере

Испортим доску из условия: поставим "3" в клетку (2, 0). В строке 2 тройки нет (. 9 8 . . . . 6 .), в столбце 0 тоже (5 6 . 8 4 7 . . .). А вот в квадрате 0 тройка уже есть — в клетке (0, 1).

Обход идёт построчно, поэтому к моменту, когда дойдём до (2, 0), клетка (0, 1) уже обработана:

Строка и столбец конфликта не дали, поймал его только квадрат. Именно поэтому формула индекса квадрата — сердце решения.

Вариант с одним множеством

Иногда пишут ещё короче: одно множество, в которое кладут кортежи-«факты» вида «в строке 4 есть пятёрка».

def is_valid_sudoku_keys(board):
    seen = set()
    for r in range(9):
        for c in range(9):
            d = board[r][c]
            if d == ".":
                continue
            keys = (("row", r, d), ("col", c, d), ("box", r // 3, c // 3, d))
            if any(k in seen for k in keys):
                return False
            seen.update(keys)
    return True

Здесь квадрат описан парой (r // 3, c // 3), и формула «развернуть в один индекс» вообще не нужна: кортеж и так хешируется. Метка "row"/"col"/"box" нужна, чтобы факт «строка 2, цифра 5» не совпал с «столбец 2, цифра 5». Тот же трюк с кортежем как составным ключом встречается в Group Anagrams.

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

Вариант с битмасками

Множество из цифр 1–9 — это просто девять флажков «было / не было». Девять флажков помещаются в одно целое число: бит $k$ равен 1, если цифра $k + 1$ уже встречалась. Подробно про такие операции — в статье о битовых манипуляциях.

Пусть в строке уже стоят 2, 3, 5 и 9. Маска строки:

Проверяем пятёрку: её бит — 1 << 4 = 10000₂. Пересечение mask & bit = 10000₂ не равно нулю, значит, пятёрка уже есть.

def is_valid_sudoku_bits(board):
    rows = [0] * 9
    cols = [0] * 9
    boxes = [0] * 9

    for r in range(9):
        for c in range(9):
            if board[r][c] == ".":
                continue
            bit = 1 << (int(board[r][c]) - 1)
            b = (r // 3) * 3 + c // 3
            if (rows[r] | cols[c] | boxes[b]) & bit:
                return False
            rows[r] |= bit
            cols[c] |= bit
            boxes[b] |= bit
    return True

Здесь [0] * 9 безопасно: числа неизменяемы, и |= создаёт новое число вместо изменения общего объекта.

Строчка (rows[r] | cols[c] | boxes[b]) & bit склеивает три проверки в одну: объединяем три маски и смотрим, есть ли в объединении нужный бит.

Что даёт битовый вариант:

• Память. 27 целых чисел вместо 27 хеш-множеств. На доске 9×9 это мелочь, но если судоку проверяют миллионы раз (генератор головоломок, солвер), разница заметна.
• Скорость. Никакого хеширования, только побитовые операции. В Python выигрыш скромный из-за накладных расходов интерпретатора, в C++, Java и JavaScript — ощутимый.
• Переносимость. Маска — обычное число, её легко скопировать, сравнить или сохранить. Солверам это особенно удобно.

Та же логика на JavaScript:

function isValidSudoku(board) {
  const rows = new Array(9).fill(0)
  const cols = new Array(9).fill(0)
  const boxes = new Array(9).fill(0)

  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      const ch = board[r][c]
      if (ch === '.') continue
      const bit = 1 << (ch.charCodeAt(0) - 49) // '1' -> 0
      const b = Math.floor(r / 3) * 3 + Math.floor(c / 3)
      if ((rows[r] | cols[c] | boxes[b]) & bit) return false
      rows[r] |= bit
      cols[c] |= bit
      boxes[b] |= bit
    }
  }
  return true
}

В JavaScript нет целочисленного деления, поэтому Math.floor(r / 3). Вместо parseInt берём код символа: '1'.charCodeAt(0) равно 49.

Сложность

Для фиксированной доски 9×9 любое из решений работает за $O(1)$: клеток всегда 81. Но интервьюеры часто просят оценить в общем виде, для доски $n \times n$ с квадратами $\sqrt{n} \times \sqrt{n}$.

Асимптотически один проход ничем не лучше трёх. Выигрыш практический: меньше кода обхода, раньше выходим при ошибке, и решение легче расширить — например, превратить в основу солвера.

Типичные ошибки

Неправильная формула квадрата

Самая частая ошибка — r // 3 + c // 3 без умножения на 3. Такая формула выдаёт числа от 0 до 4, и разные квадраты слипаются:

0 0 0 1 1 1 2 2 2
0 0 0 1 1 1 2 2 2
0 0 0 1 1 1 2 2 2
1 1 1 2 2 2 3 3 3
1 1 1 2 2 2 3 3 3
1 1 1 2 2 2 3 3 3
2 2 2 3 3 3 4 4 4
2 2 2 3 3 3 4 4 4
2 2 2 3 3 3 4 4 4

Верхний средний и левый средний квадраты получили один номер 1. Поставим пятёрку в (0, 3) и ещё одну в (3, 0): доска корректна, они в разных строках, столбцах и квадратах. А код с неправильной формулой вернёт False. Проверяйте формулу на картинке, а не в уме.

Встречается и обратная путаница — (r // 3) * 3 + c % 3 или r % 3 * 3 + c % 3. Последняя формула даёт позицию клетки внутри квадрата, а не номер квадрата. Она тоже полезна, но не здесь.

Общее множество на все строки

rows = [set()] * 9  # девять ссылок на один объект
rows[0].add("5")
print(rows[8])  # {'5'}

Ошибка подлая: на маленьких примерах может случайно пройти. Создавайте множества генератором списка.

Забыли пропустить точки

Если не пропустить ".", вторая пустая клетка в строке вызовет «дубликат». На примере из условия функция сразу вернёт False. В битовом варианте будет ещё хуже: int(".") бросит ValueError.

Добавили до проверки

rows[r].add(d)
if d in rows[r]:  # всегда True
    return False

Сначала проверяем, потом добавляем. Или проверяем по возвращаемому значению, если язык это позволяет: в Java Set.add возвращает false, если элемент уже был.

Проверяют решаемость

Некоторые кандидаты, услышав «судоку», начинают писать перебор. Это лишняя работа и другая задача, о ней — следующий раздел.

Валидация и решение: в чём разница

У Valid Sudoku есть парная задача — Sudoku Solver (LeetCode 37, hard): заполнить все пустые клетки так, чтобы доска стала правильной. Звучит похоже, но устроено иначе.

Валидация отвечает на вопрос «нарушены ли правила прямо сейчас». Это один проход по 81 клетке без вариантов и откатов.

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

Связь между задачами прямая: структуры из этой статьи — сердце солвера. Он проверяет каждую цифру-кандидата теми же rows, cols, boxes, только теперь их приходится ещё и откатывать.

def solve(board):
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    empty = []
    for r in range(9):
        for c in range(9):
            d = board[r][c]
            if d == ".":
                empty.append((r, c))
            else:
                rows[r].add(d)
                cols[c].add(d)
                boxes[(r // 3) * 3 + c // 3].add(d)

    def backtrack(i):
        if i == len(empty):
            return True
        r, c = empty[i]
        b = (r // 3) * 3 + c // 3
        for d in "123456789":
            if d in rows[r] or d in cols[c] or d in boxes[b]:
                continue
            board[r][c] = d
            rows[r].add(d)
            cols[c].add(d)
            boxes[b].add(d)
            if backtrack(i + 1):
                return True
            rows[r].remove(d)
            cols[c].remove(d)
            boxes[b].remove(d)
            board[r][c] = "."
        return False

    return backtrack(0)

Этот солвер справляется с доской из условия мгновенно. Для по-настоящему трудных головоломок его ускоряют: заменяют множества битмасками и выбирают сначала клетку с наименьшим числом кандидатов. Число кандидатов клетки — это количество нулевых битов в rows[r] | cols[c] | boxes[b], и битовый вариант тут снова выигрывает.

А вот пример, который хорошо показывает разницу между задачами:

trap = [["."] * 9 for _ in range(9)]
trap[0][:8] = list("12345678")
trap[5][8] = "9"

print(is_valid_sudoku(trap))  # True
print(solve(trap))            # False

В первой строке стоят цифры от 1 до 8, а в правом столбце, ниже, уже есть 9. Правила не нарушены, поэтому валидатор честно отвечает True. Но в клетку (0, 8) нельзя поставить ни одну цифру, и решения нет. Valid Sudoku такие доски должен пропускать: это прямо сказано в условии.

Где встречается на собеседованиях

Valid Sudoku регулярно попадается в подборках задач по хеш-таблицам и матрицам. Интервьюеры любят её, потому что она проверяет сразу несколько вещей:

• умеете ли вы свести задачу к уже известной (поиск дубликатов);
• можете ли аккуратно работать с индексами в матрице;
• задаёте ли уточняющие вопросы (решаемость, формат входа);
• знаете ли, когда множество можно заменить битовой маской.

Частые продолжения:

1. «А если доска 16×16 или $n^2 \times n^2$?» Формула обобщается: (r // k) * k + c // k, где $k = \sqrt{n}$. Цифр становится больше, но маска на 16 бит по-прежнему влезает в одно число.
2. «Сделайте без дополнительной памяти». Строго $O(1)$ памяти для произвольного $n$ не получится, но для 9×9 любая версия уже константная. Хорошо сказать это прямо, а затем показать битмаски как самый экономный вариант.
3. «Найдите все конфликтующие клетки, а не просто ответ». Вместо множеств храним словари «цифра → список координат» и не выходим досрочно.
4. «Теперь решите судоку». Переход к бэктрекингу из предыдущего раздела.

Если хочется закрепить базу, начните с разбора хеш-таблиц: вся задача держится на том, что проверка d in set работает за $O(1)$ в среднем.

Итог

• Valid Sudoku — это 27 проверок на дубликаты, упакованные в один проход.
• Номер квадрата: (r // 3) * 3 + c // 3. Деление на 3 даёт номер полосы, умножение на 3 переводит двумерный индекс в одномерный.
• Сначала проверяем все три множества, потом добавляем цифру.
• Битмаски заменяют множества: бит $k$ означает цифру $k + 1$, проверка — mask & bit.
• Валидатор не ищет решение. Корректная доска может быть нерешаемой, и это нормально.