Колко судоку пъзела има? Брой и математика

Съдържание

• Колко судоку пъзела има? Точен и прост отговор
• Какво означава „уникален“ при броенето на судоку?
• Защо „колко судоку пъзела има“ е труден въпрос
• Как е изчислено числото 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 взривява пространството на състоянията далеч отвъд днешната възможност за пълно изброяване.

Генериране в реалния свят: какво виждаме на практика

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

• Пропускателна способност: Съвременните процесори могат да генерират десетки хиляди пъзели 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 судоку
• Идеи за орбита–стабилизатор от груповата теория
• Минимални пъзели срещу пъзели с повече от едно решение
• Нива на логика за човешко решаване (единични, двойки, fish модели, оцветяване)

Разбирането на тези термини ви помага да тълкувате твърденията зад „колко судоку пъзела има“, особено когато източниците смесват решетки с решения и пъзели с подсказки.

Основни изводи

• Има 6.67×10^21 завършени 9x9 решетки с решения на судоку; 5.47 милиарда от тях са съществено различни след отчитане на симетриите.
• Точният брой валидни 9x9 судоку пъзели с уникално решение не е известен, но е многократно по-голям от броя на решетките с решения.
• Всеки валиден 9x9 пъзел трябва да има поне 17 подсказки; пъзели с 16 подсказки не съществуват.
• За играчите и платформите практическото предлагане на ново, уникално судоку е на практика неизчерпаемо.
• Разграничете „колко судоку решетки“ (решения) от „колко судоку пъзела“ (набори от подсказки с уникални решения), за да тълкувате числата правилно.