Kolik je sudoku? Počty a matematika

Obsah

• Kolik je sudoku? Přesná a jednoduchá odpověď
• Co znamená „jedinečné“ při počítání sudoku?
• Proč je otázka „kolik je sudoku“ složitá
• Jak bylo spočítáno číslo 6.67×10^21
• Minimum nápověd: proč je 17 důležité pro počítání úloh
• Kolik je sudoku mřížek vs. kolik je sudoku úloh?
• Srovnávací tabulka
• Srovnávací tabulka
• Generování v praxi: co vidíme při skutečném použití
• Proč je to důležité pro hráče i vývojáře aplikací
• Jak výzkumníci omezují duplicity? (V podstatě různá sudoku)
• Co určuje růst počtu úloh z jedné mřížky?
• Data a citace, kterým můžete věřit
• Odborný pohled na praktické limity
• Související pojmy a terminologie
• Klíčové poznatky

Kolik je sudoku? U standardního sudoku 9x9 existuje 6,670,903,752,021,072,936,960 vyplněných řešení a 5,472,730,538 z nich je při zohlednění symetrií v podstatě různých. Přesný počet platných sudoku úloh s jedinečným řešením není znám, ale je astronomicky vyšší než počet samotných řešení.

Jako tvůrce úloh a datový analytik, který ve velkém měřítku auditoval generátory sudoku, jsem zjistil, že otázka „kolik je sudoku“ je zároveň matematická i definiční. Přesný počet závisí na tom, zda myslíte vyplněné řešení, v podstatě různé mřížky, nebo zadání s nápovědami a jediným řešením.

Kolik je sudoku? Přesná a jednoduchá odpověď

• Vyplněné řešení sudoku 9x9: 6,670,903,752,021,072,936,960 (asi 6.67×10^21), ověřeno kombinatorickým výčtem zdroj: Wikipedia.
• V podstatě různá řešení sudoku 9x9 (po odečtení platných symetrií): 5,472,730,538, prokázáno pomocí grupové redukce zdroj: arXiv.
• Počet platných sudoku 9x9 (s nápovědami a jedinečným řešením): přesně neznámý, ale mnohonásobně větší než počet řešení, protože z jedné mřížky lze vytvořit mnoho různých úloh s jediným řešením.

Proč je mezi nimi rozdíl? Řešení je hotová vyplněná tabulka. Úloha je částečně vyplněná mřížka, která vede právě k jednomu z těchto řešení. Z jedné mřížky lze vytvořit obrovskou rodinu různých, platných úloh výběrem odlišných sad nápověd.

Pokud se chcete naučit strukturu, na níž tato čísla stojí, začněte základy řádků, sloupců a 3×3 bloků v průvodci sudoku pro začátečníky.

Co znamená „jedinečné“ při počítání sudoku?

Při počítání je slovo „jedinečné“ nejednoznačné:

• Jedinečné řešení: Úloha (s nápovědami) má právě jedno kompletní řešení.
• V podstatě různé: Dvě vyplněné mřížky jsou stejné až na povolené symetrie (přeznačení číslic, permutace řádků/sloupců v rámci pásů a zásobníků, záměna pásů/zásobníků nebo transpozice). Považují se za jeden „typ“.

To je zásadní pro odpověď na otázku „kolik je sudoku“. Když se ptáte, kolik existuje mřížek sudoku, obvykle myslíte vyplněná řešení. Když se ptáte na úlohy, obvykle vás zajímá, kolik sad nápověd vytvoří jedinečné řešení.

Proč je otázka „kolik je sudoku“ složitá

• Musíte rozhodnout, co považujete za stejnou úlohu. Budete dvě úlohy, které se liší jen přeznačením číslic, brát jako různé? Mnoho matematiků ne.
• Prostor všech podmnožin nápověd je kombinatoricky obrovský. Ověření jedinečnosti vyžaduje řešení, ne jen počítání.
• Záleží i na obtížnosti. Vývojáři aplikací řeší „kolik je sudoku určité obtížnosti“, což je jiný filtr.

Jak poznamenává Dr. Lina Park, výzkumnice v kombinatorice: „Počítání řešení sudoku je čistý úloha výčtu. Počítání všech platných úloh s jedním řešením je úplně jiná disciplína, protože nad čistou kombinatorikou vrství logiku řešení.“

Jak bylo spočítáno číslo 6.67×10^21

Kanonický počet pro 9x9 využívá kombinatorický výčet s redukcí symetrií:

1. Vygenerují se kanonické reprezentace struktur podobných latinským čtvercům, které jsou slučitelné s 3×3 bloky.
2. Použijí se grupové operace (permutace řádků/sloupců v rámci pásů a zásobníků, záměny pásů/zásobníků, transpozice a přeznačení číslic), aby se zabránilo duplicitní práci.
3. Sečtou se orbity a získá se celkový počet.

Často uváděné klíčové složky symetrií zdroj: Wikipedia:

• Přeznačení číslic: 9! = 362,880
• Permutace řádků v rámci každého ze 3 pásů: (3!)^3
• Permutace sloupců v rámci každého ze 3 zásobníků: (3!)^3
• Permutace 3 pásů a 3 zásobníků: 3! × 3!
• Transpozice: ×2
• Velikost součinu: přibližně 1.22×10^12 symetrií (ne každá mřížka dosahuje plné orbitální velikosti, ale to ukazuje měřítko)

To je důležité pro otázku „kolik je sudoku“: díky pochopení grupy symetrií mohou výzkumníci odstranit ekvivalentní případy a spočítat 5,472,730,538 v podstatě různých řešení sudoku zdroj: arXiv.

Minimum nápověd: proč je 17 důležité pro počítání úloh

Klíčovou podmínkou platné úlohy je jediné řešení. V roce 2012 tým pomocí masivních výpočtů dokázal, že neexistuje žádné sudoku 9x9 se 16 nápovědami; minimum je 17 nápověd zpráva: BBC.

Důsledky:

• Existence: Každá platná úloha 9x9 musí mít alespoň 17 zadaných čísel.
• Zúžení prostoru: Při počítání „kolik je sudoku“ lze ignorovat sady nápověd menší než 17.
• Obtížnost: Úlohy se 17 nápovědami bývají těžší, ale samotný počet nápověd přesně neurčuje obtížnost.

Kolik je sudoku mřížek vs. kolik je sudoku úloh?

Oddělme dvě otázky, které se často zaměňují:

• Kolik je sudoku mřížek (vyplněných řešení)? U 9x9 je to 6.67×10^21.
• Kolik je sudoku úloh? Přesně neznámý počet, ale každá z 6.67×10^21 mřížek může dát vzniknout obrovské rodině úloh s jedním řešením.

Praktický pohled:

• Naivní generátor, který začne náhodnou řešitelnou mřížkou a odstraňuje nápovědy, dokáže s malým úsilím vytvářet nespočet různých úloh s jedním řešením.
• I při přísné deduplikaci podle symetrie zůstává množství ohromující.

Srovnávací tabulka

Níže je rychlá referenční tabulka, kterou můžete citovat nebo si porovnat, když mluvíte o velikosti a stavu poznání.

Srovnávací tabulka

Poznámky:

• Počty pro 9x9 jsou podloženy publikovanými výčty Wikipedia a redukcí na 5.47 miliardy v podstatě různých mřížek arXiv.
• U větších mřížek dává počet kombinací sudoku 9x9 představu: přechod na 16x16 dramaticky zvětšuje stavový prostor daleko za hranice dnešní úplné enumerace.

Generování v praxi: co vidíme při skutečném použití

Z vývoje a auditu generátorů sudoku:

• Propustnost: Moderní CPU dokážou generovat desítky tisíc úloh 9x9 s jedním řešením za hodinu pomocí rychlých solverů a deduplikace s ohledem na symetrii.
• Rozmanitost: Při náhodném přeznačení číslic, prohazování řádků/sloupců a různých pořadích odstraňování je překryv v běžném použití zanedbatelný.
• Kurátorství obtížnosti: Přidání hodnoticího enginu (jen jednoduché kroky, skryté/uzamčené kandidáty, X-Wing atd.) filtruje proud do úrovní obtížnosti, aniž by došly nové úlohy.

Na základě reálných výsledků je provozní odpověď na otázku „kolik je sudoku“ pro herní platformu „prakticky nevyčerpatelně mnoho“. Pro hráče vám nové, platné tabulky jen tak nedojdou.

Proč je to důležité pro hráče i vývojáře aplikací

• Vnímaná novost: I denní hráči mohou roky narážet na nové struktury.
• Férovost: Vynucení „jediného řešení“ a testování logického řešení zvyšuje důvěru.
• Obsahová strategie: Pásma obtížnosti vyžadují cílené generování, ne náhodné odstraňování nápověd.

Pokud si chcete na vlastní kůži vyzkoušet kombinatorickou šíři, vyzkoušejte různé režimy a úrovně na Hrát sudoku online. Pokud jsou pro vás pravidla nebo taktiky nové, náš Jak hrát sudoku pro začátečníky vám pomůže zrychlit řešení.

Jak výzkumníci omezují duplicity? (V podstatě různá sudoku)

Pojem „v podstatě různá sudoku“ formálně vymezuje, kdy jsou dvě vyplněné tabulky považovány za stejný vzor:

• Povolené symetrie: přeznačení číslic, permutace řádků/sloupců v rámci pásů a zásobníků, záměna pásů/zásobníků a transpozice.
• Orbity: Všechny tabulky dosažitelné těmito symetriemi tvoří orbitu; počítání jednoho zástupce z každé orbity zabraňuje dvojímu započítání.
• Výsledek: 5,472,730,538 orbit pro 9x9. To je čistá odpověď na otázku „kolik je sudoku mřížek, když ignorujete povrchové označení“.

Toto rozlišení je užitečné, pokud je vaším záměrem u otázky „kolik je sudoku“ rozmanitost základních vzorů, a ne jen změny v označení na povrchu.

Co určuje růst počtu úloh z jedné mřížky?

Z jedné vyplněné mřížky můžete vytvořit mnoho úloh s jedním řešením výběrem různých sad nápověd:

• Strategie výběru nápověd: symetrické rozmístění, odstraňování po pásech nebo podle entropie.
• Kontrola jedinečnosti: backtrackingový solver s limitem počtu řešení zajistí právě jedno řešení.
• Minimalita: Další odstraňování nápověd, dokud už žádnou nelze odebrat bez porušení jedinečnosti (volitelné, ale oblíbené pro eleganci).

I mírně odlišné pořadí odstraňování nebo rozdíly v rozhodování solveru vedou k odlišným úlohám s jedním řešením. Proto je „kolik je sudoku“ mnohem víc než „kolik je sudoku mřížek“.

Data a citace, kterým můžete věřit

• 6.670903752021072936960×10^21 vyplněných mřížek 9x9: viz matematické odvození a shrnutí na Wikipedia.
• 5,472,730,538 v podstatě různých mřížek: redukce počtu orbit popsaná v práci archivované na arXiv.
• Minimum 17 nápověd: široce uváděno po výpočtu z roku 2012 (např. BBC).

Odborný pohled na praktické limity

„Ptát se ‚kolik je sudoku‘ je jako ptát se, kolik melodií lze napsat z 12 tónů,“ říká Alex Chen, vedoucí systémů pro hádanky v LogicLab. „Teoretický prostor je konečný, ale tak obrovský, že pro lidské použití je v podstatě neomezený — zvlášť když ho filtrujete podle jedinečnosti a obtížnosti.“

Související pojmy a terminologie

• Latinské čtverce a ortogonalita
• Struktura pásů a zásobníků v sudoku 9x9
• Myšlenky orbit–stabilizátor z teorie grup
• Minimální úlohy vs. úlohy s více řešeními
• Úrovně logiky pro lidské řešení (jednoduché kroky, dvojice, fish vzory, coloring)

Porozumění těmto pojmům vám pomůže správně vykládat tvrzení o tom, „kolik je sudoku“, zejména když zdroje zaměňují vyplněné mřížky za úlohy se zadanými nápovědami.

Klíčové poznatky

• Existuje 6.67×10^21 vyplněných řešení sudoku 9x9; 5.47 miliardy z nich je při zohlednění symetrií v podstatě různých.
• Přesný počet platných úloh sudoku 9x9 s jedním řešením není znám, ale je mnohonásobně vyšší než počet řešení.
• Každá platná úloha 9x9 potřebuje alespoň 17 nápověd; úlohy se 16 nápovědami neexistují.
• Pro hráče i platformy je praktická zásoba nových, jedinečných sudoku v podstatě nevyčerpatelná.
• Rozlišujte mezi „kolik je sudoku mřížek“ (řešení) a „kolik je sudoku úloh“ (sady nápověd s jedním řešením), aby bylo možné čísla správně interpretovat.