Почему это работает
- У каждой строки, столбца и квадрата есть множество цифр, которые в нём уже стоят. Множество сразу отвечает «есть тут такая цифра?», поэтому цифра сверяется со всеми тремя без нового просмотра доски.
- Квадрат получается из строки и столбца: r / 3 и c / 3 с округлением вниз дают ряд и колонку квадратов, от 0 до 2, а (r / 3) × 3 + c / 3 нумерует квадраты от 0 до 8 по рядам.
- Хватает одного прохода: повтор ловится, когда встречается вторая копия, потому что первая уже лежит в множестве. Пустые клетки не участвуют.
Сложность
Время O(1): на доске всегда 81 клетка, и каждая цифра один раз ищется в трёх множествах; для доски n × n было бы O(n²). Память O(1) по той же причине: 27 множеств, в каждом не больше 9 цифр.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗