Как «подправить» неправильные судоку, сохранив их классическую структуру

info@vsetut.pro

О проекте

Вернуться

14.01.2025 14:29:44 | Хабр

Хабы: Занимательные задачки, Алгоритмы

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

Предыстория и казус газетных судоку

Как и прежде, ближе к Новому году в почтовых ящиках жителей нашего городского округа чаще стали появляется номера газеты «Восточный округ» (ВО). И традиционно в конце каждого номера приводится головоломка судоку. И наверное, тоже уже традиционно, эти судоку ̶ неправильные, то есть имеют много решений (ответов), и только одно из них назначено в виде заполненной цифрами таблицы как «Ответы на судоку». На этот раз судоку, попавшееся на глаза (в номере ВО №40 (563)), побило все прежние рекорды по числу решений (их оказалось 83 132), из которых уважаемому читателю предложено как-то угадать единственное, приведённое в газете как «Ответы на судоку». На такой казус газетных судоку я прежде обращал внимание редакции газеты ВО. И на этот раз я не удержался, и не внял просьбе близких: ~~«перестать заниматься ерундой»~~ не тратить время на публикацию в сети. Год назад, анализируя последние номера газеты ВО 2023 года, я предлагал (см. habr.com/ru/articles/787496) «подправлять» подобные неправильные судоку так, чтобы они имели единственное решение. Но предлагаемая тогда «правка» налагала на судоку дополнительные ограничения, меняя их классическую структуру. Например, для судоку №149 из sudoku.bestcrosswords.ru/generator, имеющего 26918 отличных друг от друга решений, предлагалось дополнительно потребовать, чтобы на побочной диагонали матрицы располагался полный набор цифр от 1 до 9. Это дополнительное требование меняло классическую структуру судоку и усложняло восприятие привычной головоломки.
А как дополнить исходную таблицу судоку минимальным числом новых цифр-подсказок, чтобы получилось судоку с классической структурой и единственным решением, например, с тем, что приведено в газете как «Ответы на судоку»? В этом и состоит задача, решение которой позволит преодолеть казус газетных судоку.

Подробнее