Valid Sudoku

Средняя№36три множества

Дана доска судоку 9 × 9, заполненная не до конца. Нужно проверить, что правила не нарушены: цифра не повторяется ни в строке, ни в столбце, ни в одном из девяти квадратов 3 × 3. Решать судоку не нужно. На нашей доске 17 цифр, ответ false: две семёрки стоят в правом нижнем квадрате, хотя строки и столбцы у них разные.

36 Valid SudokuРазбор · 1×

Пример: наша доска из 17 цифр. Рамка показывает, с чем сверяем текущую цифру: со строкой и столбцом, потом с квадратом.

00112233445566778853761984283657297
ещё не проверенытекущая цифрауже в множествахтакая же цифра

По девять пустых множеств: для строк, для столбцов и для квадратов

01/86
сначала · назад · пуск · шаг
Скорость
1function isValidSudoku(board):
2 rows, cols, boxes = 9 empty sets each
3 for each digit d at (r, c) on board:
4 b = (r / 3) * 3 + c / 3 // round down
5 if d in rows[r] or d in cols[c]:
6 return false
7 if d in boxes[b]:
8 return false
9 add d to rows[r], cols[c], boxes[b]
10 return true
состояние
r
–
c
–
d
–
b
–
rows[r]
–
cols[c]
–
boxes[b]
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. У каждой строки, столбца и квадрата есть множество цифр, которые в нём уже стоят. Множество сразу отвечает «есть тут такая цифра?», поэтому цифра сверяется со всеми тремя без нового просмотра доски.
  2. Квадрат получается из строки и столбца: r / 3 и c / 3 с округлением вниз дают ряд и колонку квадратов, от 0 до 2, а (r / 3) × 3 + c / 3 нумерует квадраты от 0 до 8 по рядам.
  3. Хватает одного прохода: повтор ловится, когда встречается вторая копия, потому что первая уже лежит в множестве. Пустые клетки не участвуют.

Сложность

Время O(1): на доске всегда 81 клетка, и каждая цифра один раз ищется в трёх множествах; для доски n × n было бы O(n²). Память O(1) по той же причине: 27 множеств, в каждом не больше 9 цифр.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.