Как «подправить» неправильные судоку. Алгоритм решения судоку, использующий систему ограничений

Разобран алгоритм, ориентированный главным образом на решение неправильных судоку (9×9), и на примерах показано, как можно их «подправить».
Правильное судоку имеет единственное решение, которое печатается, например, в газетах в виде одной заполненной цифрами таблицы. Но многие генераторы судоку из интернета, да и газеты (см. далее ссылку на архив газет) часто приводят головоломки судоку с одним (но вовсе не единственным) ответом на судоку. Получить нетривиальное правильное судоку непросто. Поэтому уместно, взяв за основу опубликованные неправильные судоку, «подправить» их, дополнив некоторыми условиями, и получить подправленные судоку с одним решением, которое можно представить (и напечатать) в виде одной таблицы как ответ на судоку.

Предыстория

  Как-то мне на глаза попалась распространяемая у нас в

Анализ решенного судоку

Оказалось, что рассмотренное выше судоку имеет не одно, а 101 отличающееся друг от друга решение. Приведу для сравнения полученный Ответ номер 61 и Ответ на судоку из газетного номера № 36(513). Цифры разнятся в 38 ячейках — они в Ответе номер 61 закрашены розовым цветом.

Конечно, можно привести (и напечатать) как вариант решения Ответ на судоку и ещё одну таблицу с решением, максимально отличающимся от Ответа на судоку. Но вообще таких решений тоже может оказаться несколько. Так что лучше иметь судоку с единственным решением и печатать одну заполненную таблицу с ответом на него. Кроме того, единственность решения может существенно влиять на способ и время решения судоку.

Примеры «подправленных» судоку

Пример от sudoku.bestcrosswords.ru/generator

 Рассмотрим на примерах то, как можно «подправлять» неправильные головоломки для получения судоку с единственным решением. Следующий пример под номером № 149 сгенерирован на sudoku.bestcrosswords.ru/generator как «самый сложный судоку».

Генератор выдал таблицу с цифрами‑подсказками (они проставлены на рисунке на жёлтом фоне) и по запросу ОТВЕТ мгновенно выдал цифры решения. Программное решение этого действительно сложного судоку показало, что у него есть 26 918 отличающихся друг от друга ответов. Также как и в предыдущем примере, среди них найдётся решение с наибольшим числом клеток с цифрами, отличающимися от выданных генератором в качестве «ответа» на судоку. Это будет единственное решение, у которого 58 цифр в ячейках не совпадают со сгенерированным «ответом».

Но можно программно проанализировать таблицы с полученными решениями и выбрать дополнительные условия, выделяющие отдельные из них. Оказалось, что если потребовать, чтобы на главной и побочной диагоналях матрицы судоку располагались все различные цифры множества {1,..,9}, составляющие Полный Набор Цифр (

Судоку № 37(514) имеет 1553 отличающихся друг от друга решения. Дополнительное требование — обеспечить

Судоку из номера № 39(516) имеет 615 решений. Требование обеспечить

Судоку № 41(518) имеет изначально 65 решений. Дополнительное условие — иметь

Судоку из № 43(520) имеет 21 не совпадающее друг с другом решение. Для него не удалось подобрать условие с требованием иметь дополнительное

Судоку из номера № 45(522) имеет 26 153 не совпадающих друг с другом решений. Дополнительное условие с