Колку Судоку загатки има? Броеви и математика

Содржина

• Колку Судоку загатки има? Прецизен и едноставен одговор
• Што значи „единствено“ во броењето Судоку?
• Зошто прашањето „колку Судоку загатки има“ е сложено
• Како е пресметан бројот 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 загатки со единствено решение на час со брзи решавачи и дедупликација свесна за симетрија.
• Разновидност: Со случајно преименување на цифрите, мешање на редови/колони и различни редоследи на отстранување, преклопувањето е занемарливо во нормална употреба од страна на корисници.
• Курација на тежина: Додавањето систем за оценување (само singles, скриени/заклучени кандидати, X-Wing итн.) го филтрира огромниот тек во нивоа без да се исцрпи материјалот.

Според реалните резултати, оперативниот одговор на „колку Судоку загатки има“ за една платформа е „практично неисцрпно“ на човечки временски скали. Нема да останете без свежи, валидни табли за играчите.

Зошто ова е важно за играчите и креаторите на апликации

• Перцепирана новина: Дури и секојдневните играчи можат со години да наидуваат на нови структури.
• Правичност: Спроведувањето „единствено решение“ и тестирањето за решавање само со логика ја зголемува довербата.
• Стратегија за содржина: Нивоата на тежина бараат насочено генерирање, а не случајно отстранување траги.

Ако сакате да ја почувствувате комбинаторната широчина на дело, пробајте ги различните режими и нивоа на Играј Судоку онлајн. Ако правилата или тактиките ви се нови, нашиот водич Како да играте Судоку за почетници ќе ви помогне побрзо да решавате.

Како истражувачите ги намалуваат дупликатите? (Суштински различно Судоку)

Фразата „суштински различно Судоку“ формализира кога две пополнети табли се сметаат за ист образец:

• Дозволени симетрии: преименување на цифрите, пермутации на редови/колони во рамки/стогови, размена на рамки/стогови и транспонирање.
• Орбити: Сите табли до кои се стигнува со овие симетрии формираат орбита; броењето по еден претставник од секоја орбита избегнува двојно броење.
• Резултат: 5,472,730,538 орбити за 9x9. Ова е чистиот одговор на „колку Судоку мрежи има ако се игнорира површинското означување“.

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

Што го одредува растот на бројот на загатки од една мрежа?

Почнувајќи од една пополнета мрежа, можете да генерирате многу загатки со единствено решение со избор на различни множества траги:

• Стратегии за избор на траги: симетрично поставување, по рамки или отстранување водено од ентропија.
• Проверки на единственост: решавач со backtracking и праг за број на решенија обезбедува точно едно решение.
• Минималност: Понатамошно отстранување траги додека не остане повеќе ништо што може да се отстрани без да се наруши единственоста (опционално, но популарно поради елеганција).

Дури и малку различни редоследи на отстранување или различни правила за избор во решавачот даваат различни загатки со единствено решение. Затоа „колку Судоку загатки има“ е многу повеќе од „колку Судоку мрежи има“.

Податоци и извори на кои можете да им верувате

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

Стручна перспектива за практичните граници

„Да прашате ‘колку Судоку загатки има’ е како да прашате колку мелодии може да се напишат со 12 ноти“, вели Алекс Чен, водечки за системи за загатки во LogicLab. „Теоретскиот простор е конечен, но толку огромен што за човечка употреба е практично неограничен — особено кога ќе филтрирате по единственост и тежина.“

Поврзани поими и терминологија што треба да ги знаете

• Латински квадрати и ортогоналност
• Структура на рамки и стогови во 9x9 Судоку
• Идеи од теоријата на групи: орбита–стабилизатор
• Минимални загатки наспроти загатки со повеќе решенија
• Нивоа на човечка логика за решавање (singles, парови, fish обрасци, боење)

Разбирањето на овие поими помага да ги толкувате тврдењата зад „колку Судоку загатки има“, особено кога изворите ги мешаат решените мрежи со загатки со дадени траги.

Клучни заклучоци

• Постојат 6.67×10^21 пополнети 9x9 Судоку решени мрежи; 5.47 милијарди се суштински различни под симетрија.
• Точниот број на валидни 9x9 Судоку загатки со единствено решение не е познат, но е многу поголем од бројот на решени мрежи.
• Секоја валидна 9x9 загатка има најмалку 17 траги; нема загатки со 16 траги.
• За играчите и платформите, практичната понуда на свежо, уникатно Судоку е практично неисцрпна.
• Разликувајте меѓу „колку Судоку мрежи“ (решенија) и „колку Судоку загатки“ (множества траги со единствено решение) за правилно да ги толкувате броевите.