Решён
Какой самый сложный судоку в мире?

Олег Ферзёв • Шахматы •
816
3

Занимаюсь судоку уже лет пять, перешел на задачки уровня "expert" и "evil". Начал интересоваться темой глубже.

Нашел упоминания про "AI Escargot" от Инкалы и про задачу, которую составил финский математик Арто Инкала специально как самую трудную. Но в разных источниках называют разные задачи "самыми сложными в мире".

Есть ли вообще объективный критерий сложности судоку? Как эту сложность измеряют? И что считается абсолютным рекордом?

ГоловоломкиМатематикаРекордыСудоку

3 ответа

Лучшие Новые Старые
Решение
33
Эксперт • 12 ответов

"AI Escargot" - это и есть то, что ты ищешь. Составил Арто Инкала в 2006 году. По шкале сложности, которую используют решатели типа Gordon Royle и других исследователей, она оценивается в 11 баллов из 11 - максимум по большинству алгоритмических метрик.

Критерий сложности объективный: количество шагов логического вывода, которые нельзя заменить простым перебором. Чем больше задача требует применения продвинутых техник (X-Wing, Swordfish, XY-Chain) - тем выше рейтинг. Простой перебор не считается.

Гриды с минимальным количеством подсказок (17 - доказанный минимум для единственного решения) не обязательно самые сложные. AI Escargot имеет 21 подсказку, но решается несравнимо тяжелее большинства 17-подсказочных головоломок.

Аватар Олег Ферзёв
Олег Ферзёв Автор

Спасибо! Именно про шкалу и хотел понять. Про 17 подсказок как минимум знал, но не понимал почему это не равно сложности.

15
Участник • 6 ответов

Небольшое уточнение к ответу выше. Арто Инкала - финн, но AI Escargot как название придумал не он. Название дали в сообществе за форму улитки, которую образует расположение подсказок. Сам Инкала называл её просто своей "наисложнейшей задачей".

Есть еще "Golden Nugget" - тоже претендент на звание сложнейшей, и между фанатами идут споры что из двух тяжелее. Зависит от того, какой решатель и метрику брать за эталон.

16
Участник • 3 ответа

Если интересна тема с формальной стороны - есть статья на arXiv про вычислительную сложность судоку в обобщенном виде (n x n). Доказано что это NP-полная задача. Для классической 9x9 это не так страшно звучит, но математически объясняет почему "сложность" не имеет одного универсального определения.

Написать ответ

Визуальный редактор (WYSIWYG)
Премодерация гостей

Вы отвечаете как гость. Ваш ответ будет скрыт до проверки модератором. Чтобы ответ появился сразу и вы получали репутацию — войдите в аккаунт.

Или войдите в систему
Будьте вежливы и соблюдайте правила платформы.