Банк головоломок
Сайт головоломок каждое утро выпускает свежие судоку, а перед выпуском редактор прогоняет новые задачи через программу: решение должно найтись быстро, иначе на проверку пачки уйдёт весь день. Задачи берутся из настоящего банка Sudoku Exchange — того же, что в статье о переборе с возвратом: лёгкие, средние, трудные и дьявольские вперемешку, и среди них есть такие, на которых бесхитростный перебор пишет десятки миллионов цифр.
Судоку — поле 9 × 9, разбитое на девять квадратов 3 × 3. Нужно вписать в пустые клетки цифры от 1 до 9 так, чтобы в каждой строке, каждом столбце и каждом квадрате все девять цифр были разными.
Вход
В первой строке число головоломок T (1 ≤ T ≤ 200). Дальше T строк по 81 цифре — поле, прочитанное по строкам сверху вниз, каждая строка слева направо; 0 обозначает пустую клетку. У каждой головоломки ровно одно решение. Бывают и поля без пустых клеток.
Выход
Для каждой головоломки в отдельной строке — решённое поле в том же формате, 81 цифра без нулей.
Примеры
Пример 1
2 902006053180000020000970008700104300006000500008203007800037000030000071270600904 000000230037000090050940700000500049020080070540007000009052080070000460082000000
942816753187345629563972418729154386316798542458263197891437265634529871275681934 894175236137268594256943718763521849921384675548697123619452387375819462482736951
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Перебор с возвратом здесь годится: ставим цифру, проверяем строку, столбец и квадрат, при противоречии стираем. Но в каком порядке обходить пустые клетки? Попробуйте обходить их по порядку чтения на седьмом тесте и посчитайте, сколько цифр пишет программа.
2Подсказка 2
Если в какой-то клетке разрешена одна цифра, с этой клеткой и думать нечего. А если ни одной — текущая ветка уже мертва, и лучше узнать об этом сейчас, чем через двадцать уровней.
3Идея
Каждый раз заполняем клетку, где разрешено меньше всего цифр. Вынужденные ходы делаются без ветвления, а противоречие обнаруживается на той глубине, где оно возникло, а не после долгого перебора всего, что ниже.
4Разбор
Маски. Для каждой строки, столбца и квадрата храним девятибитную маску занятых цифр: цифра d — бит 1 << d. Разрешённые в клетке цифры — ALL & ~(row | col | box), их число — количество единичных битов. Поставить цифру — три операции «или», стереть — три «исключающих или».
Выбор клетки. Пустые клетки лежат в списке; первые k уже заполнены. На шаге k просматриваем остальные, находим клетку с наименьшим числом вариантов и меняем её местами с k-й. Если нашлась клетка с одним вариантом, искать дальше незачем; с нулём вариантов — ветка мертва, возвращаемся.
Почему так быстрее. Седьмой тест собран из головоломок, на которых обход по порядку оказался самым долгим во всём банке из 893 916 задач: до 36,5 миллиона записанных цифр на одну. Выбор самой стеснённой клетки решает каждую из них за несколько сотен цифр. Это не гарантия: в банке есть головоломка, которой он стоит почти 18 тысяч цифр, но и это в тысячи раз меньше худших случаев обхода по порядку.
4+Решение
5Сложность
В худшем случае перебор экспоненциален, и для судоку произвольного размера быстрого алгоритма не знают: задача NP-полна. На поле 9 × 9 с выбором стеснённой клетки медиана по банку — 97 записанных цифр на головоломку, а работа на каждую — просмотр не более 81 клетки. Двести головоломок — доли секунды даже на Python.
6Типичные ошибки
- Обход по порядку. Верное решение, и на большинстве головоломок быстрое, но на седьмом тесте пишет десятки миллионов цифр и не укладывается во время.
- Проверка «в конце». Заполнить все клетки и только потом проверять поле — это 950 вариантов и больше. Проверять нужно после каждой цифры.
- Забытый возврат. Если, стирая цифру, не убрать её из масок строки, столбца и квадрата, перебор начнёт считать клетки занятыми и потеряет решение.
- Поле без пустых клеток. Второй тест начинается с полностью заполненного поля: решение — само поле.