Разобран алгоритм, ориентированный главным образом на решение неправильных судоку (9×9), и на примерах показано, как можно их «подправить».
Правильное судоку имеет единственное решение, которое печатается, например, в газетах в виде одной заполненной цифрами таблицы. Но многие генераторы судоку из интернета, да и газеты (см. далее ссылку на архив газет) часто приводят головоломки судоку с одним (но вовсе не единственным) ответом на судоку. Получить нетривиальное правильное судоку непросто. Поэтому уместно, взяв за основу опубликованные неправильные судоку, «подправить» их, дополнив некоторыми условиями, и получить подправленные судоку с одним решением, которое можно представить (и напечатать) в виде одной таблицы как ответ на судоку.
Предыстория
Как-то мне на глаза попалась распространяемая у нас в ВАО газета «Восточный округ» за октябрь 2023 с судоку. Решил проверить — как у меня с логикой? Стал решать головоломку. Не помогла и очевидная газетная рекомендация «в сложных случаях можно вписать в клетку цифры‑кандидаты»: не удалось найти такой же ОТВЕТ НА СУДОКУ, как напечатанная на 10-й странице таблица с цифрами. Но у меня, не посвященного в тайны жанра, возникло подозрение, что для данного судоку возможны и иные варианты ответов. Тогда я решил поупражняться в программировании и найти все решения этой задачки.
Описание алгоритма
Полный перебор цифр‑кандидатов в свободных клетках таблицы судоку компьютер не потянет. Надо уменьшить число клеток для перебора. Возможен и полезен простейший предварительный анализ, при котором цифры сразу явно определяются. Более тонкий анализ для уменьшения числа цифр‑кандидатов сложен и неэффективен. Существенного сокращения числа клеток с перебираемыми значениями можно добиться использованием системы ограничений на цифры в строках, столбцах и 3*3-квадратах (секциях). Ориентируясь на поиск многих решений одного судоку, планирую предварительно составить систему ограничений и подготовить её для быстрых финальных вычислений каждого из решений. Имея в виду реализацию (удобную для матричных вычислений с системой ограничений) на Fortran 90 (стандарта 90 и выше), где есть функции работы с битами, буду представлять цифры 1,..,9 соответственно единицами в битах 0,..,8 двухбайтовой переменной. При этом цифрам 1,..,k,..,9 ставятся в однозначное соответствие числа 1,..,2k-1,..,256. Пронумерую подряд, обходя по строкам, свободные от цифр‑подсказок клетки, а потом запишу систему уравнений соответственно для строк, столбцов и секций. Для соответствующих пустых (без цифр) клеток проставлю единицы в матрицу системы, а в правые части уравнений системы помещу числа 511 — [ 2k1–1,.., 2kN-1], где k1,..,kN — цифры в клетках, уже известные на момент составления системы условий, а целое 511=512–1 даёт единицы во всех 9 младших битах, т. е. соответствует полному набору цифр {1,..,9}. Получится система линейных алгебраических уравнений (СЛАУ) с разреженной прямоугольной расширенной матрицей (с единицами), имеющей (для судоку без дополнительных условий) 27 строк и M столбцов, в последнем из которых содержатся правые части уравнений.
Произведу декомпозицию системы до верхней треугольной матрицы LT и оставшейся прямоугольной матрицы H. Для выполнения декомпозиции можно применить, например, метод Гаусса с выбором главного элемента по матрице. Причём, поскольку СЛАУ должно решаться в целых числах, то исключаю операцию деления и ищу не максимальный по модулю элемент (как обычно принято), а преимущественно единичный. Завершается декомпозиция при получении главного элемента равного нулю. При этом определяется количество верхних непустых строк матриц LT и H.
Рассмотрим для примера исходную таблицу СУДОКУ из номера № 36(513) упомянутой выше газеты. В ней 56 клеток с неизвестными пока цифрами. После простейшего предварительного анализа число таких клеток уменьшилось до 50. Верхняя треугольная матрица LT (с непустой главной диагональю) имеет размер 21*21, то есть перебор можно организовать уже только для остальных 50–21=29 ячеек (клеток) с неизвестными пока цифрами (обозначим их как вектор Y). Перебор допустимых цифр‑кандидатов в этих 29 ячейках, с учётом сразу исключаемых комбинаций, представляется приемлемым по времени. Цифры для первых 21 ячеек (обозначим их как вектор X) можно определить обратной подстановкой из системы LT *X=z, где z = b — H*Y, а вектор b — это столбец правых частей матрицы после декомпозиции. Компоненты полученного вектора X должны проверяться на принадлежность битам 0,..,8. Если все компоненты подходят, то решение найдено.
Перебор среди компонент вектора Y удобно реализовать в виде рекурсивной процедуры от 21 до 50-ой компоненты. При успешном назначении последней как раз и производятся упомянутые выше вычисления векторов z, X и контроль компонент вектора X. Подходящий вектор X вместе с назначенным при переборе вектором Y определяет решение судоку. Перебор кодов цифр в массиве Y представлен далее как «Код рекурсивной процедуры Perebor». В процедуре массив (вектор) Y = jV(kX+1:M-1) является частью всего массива jV(1:M-1), где jVT=[XT YT].
Анализ решенного судоку
Оказалось, что рассмотренное выше судоку имеет не одно, а 101 отличающееся друг от друга решение. Приведу для сравнения полученный Ответ номер 61 и Ответ на судоку из газетного номера № 36(513). Цифры разнятся в 38 ячейках — они в Ответе номер 61 закрашены розовым цветом.
Конечно, можно привести (и напечатать) как вариант решения Ответ на судоку и ещё одну таблицу с решением, максимально отличающимся от Ответа на судоку. Но вообще таких решений тоже может оказаться несколько. Так что лучше иметь судоку с единственным решением и печатать одну заполненную таблицу с ответом на него. Кроме того, единственность решения может существенно влиять на способ и время решения судоку.
Примеры «подправленных» судоку
Пример от sudoku.bestcrosswords.ru/generator
Рассмотрим на примерах то, как можно «подправлять» неправильные головоломки для получения судоку с единственным решением. Следующий пример под номером № 149 сгенерирован на sudoku.bestcrosswords.ru/generator как «самый сложный судоку».
Генератор выдал таблицу с цифрами‑подсказками (они проставлены на рисунке на жёлтом фоне) и по запросу ОТВЕТ мгновенно выдал цифры решения. Программное решение этого действительно сложного судоку показало, что у него есть 26 918 отличающихся друг от друга ответов. Также как и в предыдущем примере, среди них найдётся решение с наибольшим числом клеток с цифрами, отличающимися от выданных генератором в качестве «ответа» на судоку. Это будет единственное решение, у которого 58 цифр в ячейках не совпадают со сгенерированным «ответом».
Но можно программно проанализировать таблицы с полученными решениями и выбрать дополнительные условия, выделяющие отдельные из них. Оказалось, что если потребовать, чтобы на главной и побочной диагоналях матрицы судоку располагались все различные цифры множества {1,..,9}, составляющие Полный Набор Цифр (ПНЦ), то в трёх вариантах решений ПНЦ лежал на главной диагонали и в одном случае — на побочной. Клетки с требованием ПНЦ (лежащие, как в данном случае, на побочной диагонали) будем обводить в таблицах жирным контуром. Выбрав этот случай, получаем головоломку с дополнительным условием («подправленное» судоку) и единственным решением. Программная проверка показала, что единственность решения может существенно сократить время поиска ответа на это судоку.
Примеры из архива газет на newsvostok.ru
Далее рассматриваются судоку из последних номеров 2023 года газеты «Восточный округ». Архив этих номеров можно найти на сайте newsvostok.ru. Приводятся условия, «подправляющие» эти неправильные судоку к виду, имеющему единственное решение.
Для судоку № 36(513), имеющего, как отмечалось выше, 101 решение, дополнительное требование — обеспечить ПНЦ на побочной диагонали таблицы — даёт единственное решение. Такое «подправленное» судоку представлено на рисунке.
Судоку № 37(514) имеет 1553 отличающихся друг от друга решения. Дополнительное требование — обеспечить ПНЦ на клетках, изображающих перевёрнутую букву W (см. рисунок) — существенно уменьшает количество решений. Дополнительная цифра‑подсказка 9 в клетке, выделенной коричневым цветом, даёт судоку с единственным решением.
Исходное судоку № 38(515) имеет 826 решений. ПНЦ на главной диагонали снижает их количество до 17, а три дополнительные цифры‑подсказки 7, 4, 4 в клетках, выделенных коричневым цветом (см. рисунок), дают судоку с единственным решением.
Судоку из номера № 39(516) имеет 615 решений. Требование обеспечить ПНЦ на ячейках фигуры, представляющих собой перевёрнутую букву V (см. рисунок), выделяет из множества решений единственное.
Судоку № 40(517) имеет изначально 66 решений. Дополнительное требование (обеспечить ПНЦ на побочной диагонали таблицы) даёт единственное решение. Такое «подправленное» судоку представлено на рисунке.
Судоку № 41(518) имеет изначально 65 решений. Дополнительное условие — иметь ПНЦ на ячейках фигуры, показанной на рисунке — выделяет единственное из множества всех решений исходного судоку.
Судоку из газеты ВО № 42(519) изначально имеет 108 не совпадающих друг с другом решений. Условие — обеспечить ПНЦ на ячейках фигуры, представляющих перевёрнутую букву V (см. рисунок) — выделяет из множества три несовпадающих решения. А введение дополнительно ещё двух цифр‑подсказок 7 и 1 в ячейках, выделенных на рисунке коричневым цветом, обеспечит для данного судоку одно-единственное.
Судоку из № 43(520) имеет 21 не совпадающее друг с другом решение. Для него не удалось подобрать условие с требованием иметь дополнительное ПНЦ. Лишь пять дополнительных цифр‑подсказок (они указаны на рисунке в коричневых ячейках) позволили получить правильное судоку с единственным решением.
Судоку из № 44(521) имеет 4651 не совпадающее друг с другом решение. Дополнительное условие — обеспечить ПНЦ на клетках, изображающих латинскую букву W (см. рисунок) — уменьшает количество решений. Три дополнительные цифры‑подсказки 5, 5 и 9 в клетках, закрашенных коричневым цветом, дают судоку с единственным решением.
Судоку из номера № 45(522) имеет 26 153 не совпадающих друг с другом решений. Дополнительное условие с ПНЦ в виде области ячеек, образующих букву V, сокращает до двух число решений головоломки. Из рисунка следует, что в двух верхних ячейках крайних столбцов должны стоять две цифры, меняющиеся друг с другом местами. Одна дополнительная цифра‑подсказка 6 в «коричневой» ячейке выделяет единственное решение данного судоку.
Для судоку № 46(523) существует 918 отличающихся друг от друга решений. Выделение дополнительной области с ПНЦ на главной диагонали таблицы уменьшает до трёх число не совпадающих друг с другом решений. Дополнительная цифра‑подсказка 1 в ячейке, закрашенной на рисунке коричневым цветом, позволяет выделить единственное решение для данного судоку.
Резюме
Нередко публикуют головоломки, в которых единственная заполненная цифрами таблица даётся как ОТВЕТ НА СУДОКУ, но для них обнаруживается множество иных решений. А публикуемый ОТВЕТ НА СУДОКУ всего лишь показывает, что головоломка вообще имеет решение. В этом случае можно найти все решения судоку, проанализировать их и введением дополнительных условий «подправить» так, что оно будет иметь только один ответ. Рассмотренные здесь примеры судоку специально не подбирались, но для них оказалось возможным прийти к единственному решению. Ответы на них приведены ниже. Эти «подправленные» судоку вполне можно использовать, в том числе, и как задачи для осваивающих программирование.
ОТВЕТЫ на «подправленные» судоку
В таблицах ответов ячейки дополнительных областей с Полным Набором Цифр (ПНЦ) закрашены зелёным цветом. Ячейки с цифрами‑подсказками закрашены жёлтым цветом. Синим цветом закрашены ячейки, которые содержат цифры‑подсказки и одновременно являются ячейками дополнительных областей с ПНЦ.
