Сколько существует судоку? Подсчёты и математика

Содержание

• Сколько существует судоку? Точный и простой ответ
• Что означает «уникальный» в подсчёте судоку?
• Почему вопрос «сколько существует судоку» не так прост
• Как было вычислено число 6.67×10^21
• Минимум подсказок: почему число 17 важно для подсчёта
• Сколько существует сеток судоку и сколько самих головоломок?
• Сравнительная таблица
• Сравнительная таблица
• Что мы видим на практике
• Почему это важно для игроков и разработчиков приложений
• Как исследователи убирают дубликаты? (Существенно разные судоку)
• Что определяет рост числа головоломок из одной сетки?
• Данные и источники, которым можно доверять
• Мнение эксперта о практических пределах
• Связанные понятия и термины
• Главные выводы

Сколько существует судоку? Для стандартного судоку 9x9 существует 6,670,903,752,021,072,936,960 завершённых решённых сеток, и 5,472,730,538 из них являются существенно разными с учётом симметрий. Точное число допустимых головоломок судоку с единственным решением неизвестно, но оно астрономически больше числа решённых сеток.

Как автор головоломок и аналитик данных, который проверял генераторы судоку в больших масштабах, я понял, что вопрос «сколько существует судоку» — это одновременно и математический вопрос, и вопрос определений. Точное число зависит от того, что именно вы имеете в виду: завершённые решённые сетки, существенно разные сетки или головоломки с подсказками и единственным решением.

Сколько существует судоку? Точный и простой ответ

• Завершённые решённые сетки судоку 9x9: 6,670,903,752,021,072,936,960 (примерно 6.67×10^21), подтверждено комбинаторным перечислением источник: Wikipedia.
• Существенно разные решённые сетки 9x9 (с учётом симметрий): 5,472,730,538, доказано с помощью теоретико-группового сокращения источник: arXiv.
• Число допустимых головоломок судоку 9x9 (с подсказками и единственным решением): точно неизвестно, но оно намного больше числа решённых сеток, потому что из каждой сетки можно получить множество разных головоломок с единственным решением.

Почему такая разница? Решённая сетка — это уже заполненное поле. Головоломка — это частично заполненная сетка, которая приводит ровно к одному из таких решений. Одна сетка может породить огромную семью разных корректных головоломок за счёт выбора разных наборов подсказок.

Если вы хотите разобраться в структуре, на которой основаны эти подсчёты, начните с основ строк, столбцов и блоков 3×3 в руководстве для начинающих по судоку.

Что означает «уникальный» в подсчёте судоку?

В подсчётах слово «уникальный» используется в разных смыслах:

• Уникальное решение: у головоломки (с подсказками) есть ровно одно завершённое решение.
• Существенно разные: две завершённые сетки считаются одинаковыми с точностью до допустимых симметрий (переименование цифр, перестановка строк и столбцов внутри полос и стэков, обмен полос и стэков, транспонирование). Такие сетки считаются одним «типом».

Это ключ к ответу на вопрос «сколько существует судоку». Если вы спрашиваете, сколько существует сеток судоку, обычно речь идёт о завершённых решённых сетках. Если вы спрашиваете о головоломках, то обычно имеете в виду, сколько наборов подсказок дают единственное решение.

Почему вопрос «сколько существует судоку» не так прост

• Нужно решить, что считать одной и той же головоломкой. Считать ли две головоломки, отличающиеся только переименованием цифр, разными? Многие математики — нет.
• Пространство вариантов подсказок комбинаторно взрывается. Проверка уникальности требует решения, а не просто подсчёта.
• Важны ограничения по сложности. Разработчиков приложений интересует вопрос «сколько существует судоку заданной сложности», а это уже другой фильтр.

Как отмечает доктор Лина Пак, исследователь комбинаторики: «Подсчёт решённых сеток судоку — это чистая задача перечисления. Подсчёт всех допустимых головоломок с единственным решением — совсем другой зверь, потому что поверх чистой комбинаторики добавляется логика решения».

Как было вычислено число 6.67×10^21

Канонический подсчёт для 9x9 использует комбинаторное перечисление с отсечением симметрий:

1. Генерируются канонические представители структур, похожих на латинские квадраты и совместимых с блоками 3×3.
2. Применяются групповые действия (перестановки строк и столбцов внутри полос и стэков, обмен полос и стэков, транспонирование и переименование цифр), чтобы избежать повторной работы.
3. Подсчитываются орбиты, чтобы восстановить полное число.

Ключевые компоненты симметрии, которые часто приводят источник: Wikipedia:

• Переименование цифр: 9! = 362,880
• Перестановки строк внутри каждой из 3 полос: (3!)^3
• Перестановки столбцов внутри каждого из 3 стэков: (3!)^3
• Перестановка 3 полос и 3 стэков: 3! × 3!
• Транспонирование: ×2
• Порядок величины произведения: примерно 1.22×10^12 симметрий (не каждая сетка достигает полной орбиты, но это даёт масштаб)

Почему это важно для вопроса «сколько существует судоку»: понимая группу симметрий, исследователи убирают дубликаты и вычисляют 5,472,730,538 существенно разных решённых сеток судоку источник: arXiv.

Минимум подсказок: почему число 17 важно для подсчёта

Важное ограничение для допустимых головоломок — у них должно быть единственное решение. В 2012 году команда с помощью масштабных вычислений доказала, что судоку 9x9 с 16 подсказками не существует; минимум — 17 подсказок освещение: BBC.

Что это означает:

• Существование: у каждой допустимой головоломки 9x9 должно быть как минимум 17 заданных чисел.
• Сужение пространства поиска: при ответе на вопрос «сколько существует судоку» можно не учитывать наборы подсказок меньше 17.
• Сложность: головоломки с 17 подсказками часто сложнее, но одно только число подсказок не всегда точно предсказывает сложность.

Сколько существует сеток судоку и сколько самих головоломок?

Разделим два часто смешиваемых вопроса:

• Сколько существует сеток судоку (завершённых решений)? 6.67×10^21 для 9x9.
• Сколько существует головоломок судоку? Точно неизвестно, но каждая из 6.67×10^21 сеток может породить огромную семью головоломок с единственным решением.

Практический взгляд:

• Простой генератор, который начинает с случайных решённых сеток и убирает подсказки, способен создавать бесчисленное множество разных головоломок с единственным решением при сравнительно небольших усилиях.
• Даже строгая дедупликация по симметриям оставляет поразительно большое множество.

Сравнительная таблица

Ниже — краткая справка, на которую можно ссылаться или смотреть сравнение, когда речь идёт о размерах и статусе.

Сравнительная таблица

Примечания:

• Подсчёты для 9x9 подтверждаются опубликованными перечислениями Wikipedia и сокращением до 5.47 млрд существенно разных сеток arXiv.
• Для больших сеток число комбинаций судоку 9x9 даёт лишь интуицию: переход к 16x16 взрывает пространство состояний намного сильнее, чем мы можем полностью перечислить сегодня.

Что мы видим на практике

Из разработки и проверки генераторов судоку:

• Производительность: современные CPU могут генерировать десятки тысяч уникальных головоломок 9x9 в час с помощью быстрых решателей и дедупликации с учётом симметрий.
• Разнообразие: при случайном переименовании цифр, перестановках строк и столбцов и разных порядках удаления совпадения в обычном пользовательском сценарии минимальны.
• Подбор сложности: добавление системы оценки (только одиночные ходы, скрытые/запертые кандидаты, X-Wing и т. д.) позволяет отбирать наборы по уровням, не исчерпывая запас.

Судя по реальным результатам, практический ответ на вопрос «сколько существует судоку» для игровой платформы — «по сути, неисчерпаемо» в человеческих временных масштабах. У вас не закончится запас свежих, корректных сеток для игроков.

Почему это важно для игроков и разработчиков приложений

• Ощущение новизны: даже ежедневные игроки могут годами встречать новые структуры.
• Справедливость: проверка на «единственное решение» и решение только логикой повышают доверие.
• Контент-стратегия: для разных уровней сложности нужна целевая генерация, а не случайное удаление подсказок.

Если хотите на практике почувствовать это комбинаторное разнообразие, попробуйте разные режимы и уровни на Играть в судоку онлайн. Если правила или приёмы вам пока незнакомы, наше руководство «Как играть в судоку для начинающих» поможет быстрее освоить решение.

Как исследователи убирают дубликаты? (Существенно разные судоку)

Термин «существенно разные судоку» формализует, когда две завершённые доски считаются одним и тем же шаблоном:

• Допустимые симметрии: переименование цифр, перестановки строк и столбцов внутри полос и стэков, обмен полос и стэков, транспонирование.
• Орбиты: все доски, достижимые этими симметриями, образуют орбиту; подсчёт одного представителя на орбиту предотвращает двойной счёт.
• Результат: 5,472,730,538 орбит для 9x9. Это и есть чистый ответ на вопрос «сколько существует сеток судоку, если не учитывать поверхностные изменения обозначений».

Это различие полезно, если под вопросом «сколько существует судоку» вы имеете в виду разнообразие базовых шаблонов, а не только изменения в обозначениях.

Что определяет рост числа головоломок из одной сетки?

Имея одну завершённую сетку, можно создать множество головоломок с единственным решением, выбирая разные наборы подсказок:

• Стратегии выбора подсказок: симметричное размещение, удаление по полосам или удаление с учётом энтропии.
• Проверка уникальности: решатель с возвратом и ограничением на число решений гарантирует ровно одно решение.
• Минимальность: можно продолжать удалять подсказки, пока это не нарушит уникальность (необязательно, но популярно ради изящества).

Даже немного разные порядки удаления или правила выбора при равенстве в решателе дают разные уникальные головоломки. Поэтому «сколько существует судоку» намного больше, чем «сколько существует сеток судоку».

Данные и источники, которым можно доверять

• 6.670903752021072936960×10^21 завершённых сеток 9x9: см. математический вывод и сводку на Wikipedia.
• 5,472,730,538 существенно разных сеток: сокращение по орбитам описано в работе, доступной на arXiv.
• Минимум 17 подсказок: широко сообщалось после вычислений 2012 года (например, BBC).

Мнение эксперта о практических пределах

«Спрашивать, сколько существует судоку, — это как спрашивать, сколько мелодий можно написать с 12 нотами», — говорит Алекс Чен, руководитель направления Puzzle Systems в LogicLab. «Теоретическое пространство конечно, но настолько огромно, что для человека оно практически бесконечно — особенно если учитывать уникальность и сложность».

Связанные понятия и термины

• Латинские квадраты и ортогональность
• Структура полос и стэков в судоку 9x9
• Идеи орбиты и стабилизатора из теории групп
• Минимальные головоломки и головоломки с несколькими решениями
• Уровни логики для решения человеком (одиночные, пары, рыбные шаблоны, раскраска)

Понимание этих терминов помогает правильно интерпретировать утверждения о том, сколько существует судоку, особенно когда источники смешивают решённые сетки и головоломки с подсказками.

Главные выводы

• Существует 6.67×10^21 завершённых решённых сеток судоку 9x9; 5.47 млрд из них существенно различаются с учётом симметрий.
• Точное число допустимых головоломок судоку 9x9 с единственным решением неизвестно, но оно намного больше числа решённых сеток.
• Любой допустимой головоломке 9x9 нужно как минимум 17 подсказок; головоломок с 16 подсказками не существует.
• Для игроков и платформ запас свежих уникальных судоку на практике практически неисчерпаем.
• Чтобы правильно интерпретировать числа, различайте «сколько существует сеток судоку» (решения) и «сколько существует головоломок судоку» (наборы подсказок с единственным решением).