Max Home IndustryСудоку — забавная задача, но насколько сложна конкретная головоломка? Теперь у нас есть ответ, основанный на измерении хаоса, присущего сетке. Это дает шкалу Рихтера для судоку.
Пара компьютерных ученых из Университета Бабе с-Бойяи (Румыния) и Университета Нотр-Дам (США) установила замечательную связь между судоку, классической задачей k-SAT и еще более классической нелинейной непрерывной динамикой. .
Но прежде чем мы углубимся в детали, давайте посмотрим, что это значит для энтузиастов судоку. Мария Эрче-Равас и Золт ан Торочкай изобрели шкалу, которая позволяет точно определять сложность головоломки Судоку. Итак, когда вы сталкиваетесь с головоломкой, помеченной как сложная, и находите ее простой, все, что вам нужно сделать, это вычислить ее коэффициент η, который измеряет сложность задачи.
Легкая головоломка должна попадать в диапазон 0 <η <1, средняя - в 1 <η <2, сложная - в 2 <η <3, а для сверхтвердых головоломок - η> 3 с самая сложная головоломка: пресловутый платиновый блонд оказался на вершине шкалы с η = 3,6. Нам придется подождать, чтобы увидеть, начнут ли газеты и веб-сайты использовать эту меру сложности.
Возвращаясь к теории, лежащей в основе этого прорыва, поскольку k-SAT является проблемой NP-Complete, любая проблема NP может быть преобразована в конкретную задачу k-SAT — это то, что означает NP Complete.
На всякий случай, если вы не знаете, проблему k-SAT очень легко описать. У вас есть логическое выражение в n логических переменных, и каждое предложение включает только k из них за раз. Все, что вам нужно сделать, это найти набор присваиваний переменным, которые делают выражение истинным. Например, задача 2-SAT для 3 переменных x, y, z выглядит примерно так:
(x OR y) AND (z OR x)
и вам нужно найти значения x, y и z, чтобы выражение было истинным. Этот k-SAT прост, но если k> 2 и чем больше N, проблема становится намного сложнее.
Задача k-SAT (k> 2) — это NP. То есть поиск решения занимает больше времени, чем полиномиальное время, но для проверки решения требуется полиномиальное время. Другими словами, решения трудно найти, но их легко проверить.
Так что преобразование судоку в k-SAT не является большим сюрпризом, но это сложная задача. Например, простая головоломка с 34 подсказками содержит 126 переменных и 717 предложений в логическом выражении. Преобразование данного судоку в форму k-SAT происходит автоматически, но сложно.
Следующий шаг, пожалуй, самый замечательный.
Вы можете настроить функцию «энергии», которая показывает, насколько далеко от решения находится данная конфигурация. Энергетическая функция равна нулю, когда конфигурация является решением. Тонкая часть состоит в том, что функция энергии является непрерывной функцией переменных решения в диапазоне от -1 до 1. Это превращает задачу из дискретного поиска в непрерывный.
В классической динамике движение тела управляется функцией энергии, и система эволюционирует, чтобы найти наименьшую энергию — в основном вещи катятся под гору. Любая задача k-SAT может быть решена с использованием того же подхода «градиентного спуска» для ее энергетической функции. Проще говоря, вы запускаете систему из случайной конфигурации и перемещаете ее в направлении уменьшения энергии. Когда система достигла нулевой энергии, у вас есть решение.
Этот подход является мостом между алгоритмами дискретного поиска и классической непрерывной динамикой. Вы можете увидеть, насколько сложна задача поиска, по тому, насколько быстро система движется вниз по энергетической поверхности до минимума. Простые задачи судоку легко решаются. Более сложные проблемы означают, что поверхность энергии также более сложна, а путь, используемый для минимизации энергии, запутан и занимает больше времени.
Вы можете убедиться в этом, сравнив, сколько времени требуется переменным решения, чтобы успокоиться в двух случаях — простом и сложном судоку.
нажмите, чтобы увеличить
Поведение динамики системы можно использовать для определения сложности проблемы. Чем дольше система успокаивается и чем более хаотичным является поведение на пути к решению, тем сложнее проблема. Это позволяет определить судоку шкалу Рихтера η, измеряющую сложность задачи, при этом простые головоломки попадают в диапазон 0 <η <1, средние - в 1 <η <2, сложные - в 2 <η <3 и для сверхсложных головоломок η> 3.
Похоже, что оценки соответствуют примерам головоломок, проанализированных на веб-сайте Sudoku of the Day: легкая — 0,8, средняя — 1,4, сложная — 1,78 и «абсурдная» — 1,8.
Чтобы найти головоломки в верхней части шкалы, вы должны искать примеры, которые были объявлены «самыми сложными». Например, самая сложная головоломка Guardian 2010 получила всего 2,8 балла по шкале Судоку по шкале Рихтера. Другие «самые сложные» головоломки также оказались не такими сложными — самая сложная головоломка USA Today в 2006 году набрала всего 2,17 балла.
Так какие головоломки самые сложные?
Пять самых сложных головоломок настолько известны, что у них есть названия: Platinum Blond, Golden Nugget, Red Dwarf, coly013 и tarx0134. Их коэффициент твердости находится в диапазоне от 3 до 3,6, причем Platinum Blond является самым твердым на уровне 3,6.
Куда мы пойдем дальше?
Возможность измерить сложность головоломки судоку может показаться мелочью, но связь между дискретным поиском и непрерывной нелинейной динамикой интригует — она заслуживает большего внимания.
Больше мультяшных забав на xkcd, веб-комиксе о романтике, сарказме, математике и языке