Как измеряют сложность судоку?

Сложность головоломки определяется одной самой трудной логической техникой, необходимой, чтобы решить её без угадывания. Солверы вроде Sudoku Explainer проходят головоломку по фиксированной лестнице техник — от голых одиночек до форсирующих цепочек — и сообщают самую высокую ступень, которую пришлось задействовать, в виде числа — оценки SE. Поскольку метод фиксирован и воспроизводим, одна и та же головоломка всегда получает одну и ту же оценку — поэтому мы оцениваем каждую сетку именно так, а не расплывчатыми словами вроде «легко» или «эксперт».

Не обязательно. Минимальное число заданных цифр, при котором корректное судоку сохраняет ровно одно решение, — 17; это доказано полным компьютерным перебором (McGuire, Tugemann и Civario, 2012). Но число заданных цифр лишь слабо связано со сложностью: головоломка с 17 заданными цифрами может быть мягкой, а с 30 — требовать продвинутых цепочек. Важна техника, которую навязывает расстановка, а не количество пустых клеток.

Полностью решённых сеток судоку — 6,670,903,752,021,072,936,960, то есть около 6.67 × 10²¹ (Felgenhauer и Jarvis, 2005); после отбрасывания симметрий их остаётся 5,472,730,538 по существу различных. На практике это значит, что свежие, никогда прежде не встречавшиеся головоломки любой сложности не закончатся никогда.

Знаменитые «монстры» вроде AI Escargot (Arto Inkala, 2006) когда-то рекламировались как самые сложные из когда-либо созданных. Оценка SE позволяет сравнивать их объективно, а не по репутации: самые сложные из известных головоломок находятся около оценки SE 11 и выше.

Посмотрите, как работает оценка SE или самые сложные судоку-головоломки — чтобы увидеть весь список монстров.