Дорешать судоку

Сложная

Дана доска судоку grid размером 9 × 9. В каждой клетке стоит цифра от '1' до '9' или точка '.' — пустая клетка. Заполните все пустые клетки так, чтобы: - в каждой строке каждая цифра от 1 до 9 встречалась ровно один раз; - в каждом столбце — тоже; - в каждом из девяти квадратов 3 × 3, на которые делится доска, — тоже. Верните заполненную доску. Гарантируется, что решение у доски ровно одно.

Пример 1

grid=[['.', '.', '.', '9', '7', '2', '.', '8', '5'], ['.', '.', '2', '.', '.', '.', '6', '.', '4'], ['.', '.', '.', '.', '.', '.', '3', '.', '.'], ['.', '8', '.', '.', '9', '.', '.', '5', '.'], ['4', '5', '.', '2', '.', '3', '.', '7', '6'], ['.', '7', '.', '.', '6', '.', '.', '1', '.'], ['.', '.', '6', '.', '.', '.', '.', '.', '.'], ['9', '.', '5', '.', '.', '.', '2', '.', '.'], ['8', '2', '.', '6', '1', '4', '.', '.', '.']] → [['3', '6', '4', '9', '7', '2', '1', '8', '5'], ['7', '1', '2', '3', '5', '8', '6', '9', '4'], ['5', '9', '8', '1', '4', '6', '3', '2', '7'], ['6', '8', '3', '7', '9', '1', '4', '5', '2'], ['4', '5', '1', '2', '8', '3', '9', '7', '6'], ['2', '7', '9', '4', '6', '5', '8', '1', '3'], ['1', '3', '6', '5', '2', '9', '7', '4', '8'], ['9', '4', '5', '8', '3', '7', '2', '6', '1'], ['8', '2', '7', '6', '1', '4', '5', '3', '9']]

В возвращённой доске все точки заменены цифрами, и в каждой строке, столбце и квадрате 3 × 3 цифры от 1 до 9 стоят без повторов.

Пример 2

grid=[['.', '.', '.', '9', '7', '2', '.', '8', '5'], ['.', '.', '2', '.', '.', '.', '6', '.', '4'], ['.', '.', '.', '.', '.', '.', '3', '.', '.'], ['.', '8', '.', '.', '9', '.', '.', '5', '.'], ['4', '5', '.', '2', '.', '3', '.', '7', '6'], ['.', '7', '.', '.', '6', '.', '.', '1', '.'], ['.', '.', '6', '.', '.', '.', '.', '.', '.'], ['9', '.', '5', '.', '.', '.', '2', '.', '.'], ['8', '2', '.', '6', '1', '4', '.', '.', '.']] → [['3', '6', '4', '9', '7', '2', '1', '8', '5'], ['7', '1', '2', '3', '5', '8', '6', '9', '4'], ['5', '9', '8', '1', '4', '6', '3', '2', '7'], ['6', '8', '3', '7', '9', '1', '4', '5', '2'], ['4', '5', '1', '2', '8', '3', '9', '7', '6'], ['2', '7', '9', '4', '6', '5', '8', '1', '3'], ['1', '3', '6', '5', '2', '9', '7', '4', '8'], ['9', '4', '5', '8', '3', '7', '2', '6', '1'], ['8', '2', '7', '6', '1', '4', '5', '3', '9']]

Ограничения

grid — 9 строк по 9 клеток
Каждая клетка — цифра от '1' до '9' или '.'
Заполненные клетки не противоречат правилам
У доски ровно одно решение

Встречал эту задачу на настоящем собесе?

Решили0

Пробовали0

Отправок0

Принято—

Темы

Array Hash Table Backtracking Matrix

Вход

grid=[['.', '.', '.', '9', '7', '2', '.', '8', '5'], ['.', '.', '2', '.', '.', '.', '6', '.', '4'], ['.', '.', '.', '.', '.', '.', '3', '.', '.'], ['.', '8', '.', '.', '9', '.', '.', '5', '.'], ['4', '5', '.', '2', '.', '3', '.', '7', '6'], ['.', '7', '.', '.', '6', '.', '.', '1', '.'], ['.', '.', '6', '.', '.', '.', '.', '.', '.'], ['9', '.', '5', '.', '.', '.', '2', '.', '.'], ['8', '2', '.', '6', '1', '4', '.', '.', '.']]

Ожидается

[['3', '6', '4', '9', '7', '2', '1', '8', '5'], ['7', '1', '2', '3', '5', '8', '6', '9', '4'], ['5', '9', '8', '1', '4', '6', '3', '2', '7'], ['6', '8', '3', '7', '9', '1', '4', '5', '2'], ['4', '5', '1', '2', '8', '3', '9', '7', '6'], ['2', '7', '9', '4', '6', '5', '8', '1', '3'], ['1', '3', '6', '5', '2', '9', '7', '4', '8'], ['9', '4', '5', '8', '3', '7', '2', '6', '1'], ['8', '2', '7', '6', '1', '4', '5', '3', '9']]

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 30 тестов на сервере, включая скрытые.