Как «подправить» неправильные судоку, сохранив их классическую структуру
Рассмотрен способ приведения судоку: неправильного (со множеством решений) к правильному, то есть к судоку с единственным решением − . (9×9)-матрицей цифр, назначенной для неправильного судоку в качестве «Ответов на судоку». «Правка» неправильного судоку состоит в назначении для него минимального количества дополнительных цифр-подсказок, что не нарушает классической структуры судоку.
Предыстория и казус газетных судоку
Как и прежде, ближе к Новому году в почтовых ящиках жителей нашего городского округа чаще стали появляется номера газеты «Восточный округ» (ВО). И традиционно в конце каждого номера приводится головоломка судоку. И наверное, тоже уже традиционно, эти судоку ̶ неправильные, то есть имеют много решений (ответов), и только одно из них назначено в виде заполненной цифрами таблицы как «Ответы на судоку». На этот раз судоку, попавшееся на глаза (в номере ВО №40 (563)), побило все прежние рекорды по числу решений (их оказалось 83 132), из которых уважаемому читателю предложено как-то угадать единственное, приведённое в газете как «Ответы на судоку». На такой казус газетных судоку я прежде обращал внимание редакции газеты ВО. И на этот раз я не удержался, и не внял просьбе близких: «перестать заниматься ерундой» не тратить время на публикацию в сети. Год назад, анализируя последние номера газеты ВО 2023 года, я предлагал (см. habr.com/ru/articles/787496) «подправлять» подобные неправильные судоку так, чтобы они имели единственное решение. Но предлагаемая тогда «правка» налагала на судоку дополнительные ограничения, меняя их классическую структуру. Например, для судоку №149 из sudoku.bestcrosswords.ru/generator, имеющего 26 918 отличных друг от друга решений, предлагалось дополнительно потребовать, чтобы на побочной диагонали матрицы располагался полный набор цифр от 1 до 9. Это дополнительное требование меняло классическую структуру судоку и усложняло восприятие привычной головоломки.
А как дополнить исходную таблицу судоку минимальным числом новых цифр-подсказок, чтобы получилось судоку с классической структурой и единственным решением, например, с тем, что приведено в газете как «Ответы на судоку»? В этом и состоит задача, решение которой позволит преодолеть казус газетных судоку.
Способ преодоление казуса или как «править» неправильные
классические судоку
Для «правки» возьмём судоку из семи последних номеров газеты ВО за 2024 год (см. архив газет на newsvostok.ru/archive) и упомянутый выше судоку №149.
Вряд ли «подправленные» судоку будут отличаться особым изяществом, но они дадут единственный честный «Ответ на судоку», напечатанный в упомянутой газете или выданный упомянутым генератором судоку.
Рассмотрим этапы предлагаемой «правки».
После получения множества всех решений неправильного судоку (например, по алгоритму, рассмотренному в habr.com/ru/articles/787496) произведём их анализ. Определим частоту появления каждой цифры из «Ответа на судоку» в полученных решениях.
В сформированной при этом таблице частот находим клетку с минимальным значением (количеством повторений). А в ячейке, соответствующей этой клетке, в матрице с «Ответами на судоку» выбираем цифру, которую назначаем как новую дополнительную
цифру-подсказку для корректируемого судоку. Затем снова получаем решения (или они выбираются из ранее найденных) для судоку с новой, дополнительно принятой
цифрой-подсказкой. Число таких решений сокращается. Далее снова выполняем процедуры вычисления таблицы частот повторений, выбора минимального их числа и назначения новой цифры-подсказки для коррекции неправильного судока до получения единственного решения.
Отметим, что если в таблице частот окажется несколько одинаковых значений с минимальным числом повторений, то выбираем любой вариант или просто берём вариант с первой клеткой, встречаемой, например, при обходе этой таблицы по строкам .
Представленный способ позволит назначить дополнительные цифры-подсказки к матрицам, которые изначально задают неправильные судоку. Алгоритм представленного способа несложно реализовать программно.
Пример для иллюстрации
Поясним рассмотренный способ на примере судоку №46(569) в последнем номере газеты ВО за 2024 год. На рисунке 1 представлены исходная матрица этого судоку и единственная матрица «Ответы на судоку», хотя это судоку имеет 27 отличающихся друг от друга решений (27 матриц с цифрами).
Рисунок 1. Матрица исходного судоку (слева) и «Ответы на судоку» (справа).
Цифры из матрицы «Ответы на судоку» сравнивалась с цифрами из этих 27 решений и определялось количество повторений цифр из «Ответы на судоку» в одинаково расположенных ячейках матриц решений. Получена следующая таблица числа повторений, показанная слева на рисунке 2.
Рисунок 2. Таблицы частот повторений для решений: 27 (слева) и 3 (справа).
Выбор из таблицы частот (слева) клетки 3B с минимальным числом 3 повторений и цифры 9 из ячейки 3B матрицы «Ответы на судоку» как дополнительной цифры-подсказки даст 3 решения дополненного судоку. А для этих 3 решений выбор из таблицы частот (справа) клетки 5B и цифры 4 из ячейки 5B матрицы «Ответы на судоку» в качестве следующей дополнительной цифры-подсказки приведёт к единственному решению, совпадающему с «Ответами на судоку».
Отметим, что для 27 решений альтернативный выбор из таблицы частот (слева) клетки 8D с таким же минимальным числом 3 повторений и цифры 8 из ячейки 8D матрицы «Ответы на судоку» приведёт к такой же таблице частот (справа) и затем к единственному решению, совпадающему с «Ответами на судоку». То есть дополненные матрицы судоку будут отличаться на одну ячейку, но количество 2 дополнительных цифр-подсказок (к исходному неправильному судоку) не изменится.
Рассмотренное из газеты ВО судоку №46(569) с 27 решениями и с 2-мя альтернативами выбора первой дополнительной цифры-подсказки, каждая из которых ведёт к безальтернативному (то есть альтернатива равна 1) выбору из 3-х решений второй
цифры-подсказки, схематически можно записать как ВО №46(569) 27(2), 3(1), 1.
Здесь число дополнительных цифр-подсказок равно двум и равно количеству стадий понижения чисел рассматриваемых решений без последней единицы. Опираясь на такую схему записи представим «правку» всех рассмотренных судоку.
Схемы «правки» и результаты «правки»
Рассмотренные судоку:
Источник_судоку Число_решений (вариантов_выбора_доп._цифры), … , 1
ВО №46(569) 27(2), 3(1), 1
ВО №45(568) 584(2), 32(4×3), 2(10), 1 *
ВО №44(567) 92(1), 7(1), 1
ВО №43(566) 179(1), 6(1), 1
ВО №42(565) 1316(1), 51(15), 1
ВО №41(564) 17709(1), 1132(1), 128(1), 21(1), 4(1), 1
ВО №40(564) 83132(1), 7097(1), 438(1), 21(1), 4(8), 2(8×4|2), 1
sudoku.bestcrosswords.ru/generator №149, 26819(1), 851(1), 62(1), 12(1), 4(1), 2(10), 1
* Запись (4×3) означает, что одному из 2-ух вариантов назначения предыдущей цифры-подсказки соответствует 4 или 3 варианта назначения следующей цифры-подсказки.
Приведём далее (на рисунках слева) исходные неправильные судоку с решениями, максимально отличающимися от «Ответов на судоку». Ячейки с отличающимися цифрами закрашены оранжевым цветом. На рисунках справа показаны полученные правильные судоку с добавленными цифрами-подсказками, а в ячейках каждого из этих судоку указано единственное решение, которое и есть «Ответы на судоку». Добавленные цифры-подсказки указаны в раскрашенных в цвета спектра ячейках − красный, оранжевый, жёлтый, светло-зелёный, зелёный, голубой − в порядке их назначения и следования стадий понижения числа рассматриваемых решений.
Рисунок 3. Исходный судоку №46(569) с решением №22 из 27 (слева)
и исправленный судоку с единственным «Ответом на судоку» (справа).
Рисунок 4. Исходный судоку №45(568) с решением №120 из 584 (слева) и исправленный судоку с единственным «Ответом на судоку» (справа).
Рисунок 5. Исходный судоку №44(567) с решением №62 из 92 (слева)
и исправленный судоку с единственным «Ответом на судоку» (справа).
Рисунок 6. Исходный судоку №43(566) с решением №63 из 179 (слева)
и исправленный судоку с единственным «Ответом на судоку» (справа).
/Рисунок 7. Исходный судоку №42(565) с решением №517 из 1316 (слева)
и исправленный судоку с единственным «Ответом на судоку» (справа).
Рисунок 8. Исходный судоку №41(564) с решением №13945 из 17709 (слева) и исправленный судоку с единственным «Ответом на судоку» (справа).
Рисунок 9. Исходный судоку №40(563) с решением №15000 из 83132 (слева) и исправленный судоку с единственным «Ответом на судоку» (справа).
Рисунок 10. Исходный судоку №149 с решением №20098 из 26918 (слева)
и исправленный судоку с единственным «Ответом на судоку» (справа).
Анализ полученных правильных судоку
Рассмотрение для судоку №43(566), №45(568), №41(564) альтернативных назначений клеток таблиц частот и путей следования по ним показало, что общее число дополнительных цифр-подсказок при этом для судоку не изменялось.
Отметим, что сложность получившихся правильных судоку невелика.
Все они, кроме судоку №43(566), решаются с помощью простейшего анализа.
Опишем проверки, используемые в таком анализе. Поскольку при анализе применялись функции работы с битами, используем обозначение zk=2k-1 — двоичный код цифры k, и обозначим как Hi, j, Vi, j, Si, j логическую сумму двоичных кодов цифр членов группы (соответственно строки, столбца и 3×3-сектора) с исключённой из неё ячейкой (i, j) − её код можно задать значением zk=[2k-1]=[20–1]=0.
Простейший анализ включает следующие две проверки (1) и (2):
1. Если для пустой ячейки (i, j) (ячейки с нулём) отрицание логической суммы двоичных кодов цифр-подсказок для группы (строки Hi, j, столбца Vi, j , сектора Si, j), содержащей эту ячейку, даёт только один бит zk (см. формулу (1)) для одной цифры, то цифра k назначается как цифра-подсказка.
2. Если для пустой ячейки логическая сумма двоичных кодов всех цифр-кандидатов членов её группы не содержит единственный бит zk, который присутствует среди двоичных кодов цифр-кандидатов данной ячейки, то этот код zk цифры (см. формулу (2)) принимается как код цифры-подсказки (и цифра k назначается как цифра-подсказка). Другими словами: если для пустой ячейки нет повторений допустимой цифры z среди допустимых цифр в строке, столбце или секции для других ячеек, то эту цифру z следует оформить как новую
цифру-подсказку.
Правильное судоку, полученное на основе судоку ВО №43(566), оказалось более сложным. В нём при решении кроме упомянутого выше анализа надо задействовать исключение из списков цифр-кандидатов, а также назначение наугад из цифр-кандидатов с дальнейшим следованием или до обнаружения противоречия, или до получения правильного набора цифр.
Заключение
Представленный способ, позволяющий переводить неправильное судоку с выбранным одним из множества решений в правильное судоку с этим единственным решением «Ответом на судоку», можно использовать не только для устранения казусов газетных судоку, но и вообще для получения иных правильных судоку по первоначально заданной системе цифр-подсказок.
При программной реализации алгоритма представленного способа назначение дополнительных цифр-подсказок на основе выбора из частотных таблиц альтернативных клеток с минимальным значением может выполняться как в интерактивном режиме, так и в автоматическом: при конкретном задании пути просмотра частотных таблиц. Рассмотренные примеры показали, что количество необходимых дополнительных ячеек не меняется − не зависит от выбора пути просмотра.
Хотя случай судоку ВО №43(566) даёт пример получения относительно сложной головоломки, но сложность остальных правильных судоку, полученных в результате «правки», невысока. Впрочем, она соответствует уровню кроссвордов и головоломок, публикуемых вместе с этими судоку. Во всяком случае эти «подправленные» головоломки лучше тех неправильных судоку, для которых невозможно с помощью нормальной логики определить, какое из множества решений было опубликовано как «Ответы на судоку».
