Koľko je sudoku? Počty, čísla a matematika

Obsah

• Koľko je sudoku? Presná a jednoduchá odpoveď
• Čo znamená „jedinečné“ pri počítaní sudoku?
• Prečo je otázka „koľko je sudoku“ zložitá
• Ako bolo vypočítané číslo 6.67×10^21
• Minimum indícií: prečo je 17 dôležitých pri počítaní
• Koľko je sudoku mriežok a koľko sudoku hádaniek?
• Porovnávacia tabuľka
• Porovnávacia tabuľka
• Tvorba v praxi: čo vidíme v reálnom svete
• Prečo je to dôležité pre hráčov a tvorcov aplikácií
• Ako výskumníci znižujú duplicity? (V podstate odlišné sudoku)
• Čo určuje rast počtu hádaniek z jednej mriežky?
• Údaje a citácie, ktorým môžete veriť
• Odborný pohľad na praktické limity
• Súvisiace pojmy a terminológia
• Kľúčové zhrnutie

Koľko je sudoku? Pri štandardnom sudoku 9x9 existuje 6,670,903,752,021,072,936,960 vyplnených riešiteľných mriežok a 5,472,730,538 z nich je pri zohľadnení symetrií v podstate odlišných. Presný počet platných sudoku s jedinečným riešením nie je známy, no je astronomicky väčší než počet riešiteľných mriežok.

Ako tvorca hádaniek a dátový analytik, ktorý auditoval generátory sudoku vo veľkom meradle, som sa naučil, že otázka „koľko je sudoku“ je zároveň matematická aj definičná. Presný počet závisí od toho, či myslíte vyplnené riešiteľné mriežky, v podstate odlišné mriežky alebo zadania s indíciami a jedinečným riešením.

Koľko je sudoku? Presná a jednoduchá odpoveď

• Vyplnené riešiteľné mriežky sudoku 9x9: 6,670,903,752,021,072,936,960 (približne 6.67×10^21), overené kombinatorickým výpočtom zdroj: Wikipedia.
• V podstate odlišné riešiteľné mriežky 9x9 (po zohľadnení symetrií): 5,472,730,538, dokázané pomocou redukcie z teórie grup zdroj: arXiv.
• Počet platných sudoku 9x9 (s indíciami a jedinečným riešením): presne neznámy, ale oveľa väčší než počet riešiteľných mriežok, pretože z každej mriežky možno odvodiť mnoho rôznych hádaniek s jedným riešením.

Prečo je medzi nimi rozdiel? Riešiteľná mriežka je hotová tabuľka. Hádanka je čiastočne vyplnená mriežka, ktorá vedie presne k jednému z týchto riešení. Z jednej mriežky možno vytvoriť obrovskú rodinu odlišných, platných hádaniek výberom rôznych súborov indícií.

Ak sa chcete naučiť štruktúru, ktorá stojí za týmito počtami, začnite so základmi riadkov, stĺpcov a 3×3 blokov v sprievodcovi sudoku pre začiatočníkov.

Čo znamená „jedinečné“ pri počítaní sudoku?

Pri počítaní je slovo „jedinečné“ nejednoznačné:

• Jedinečné riešenie: Hádanka (s indíciami) má presne jedno dokončené riešenie.
• V podstate odlišné: Dve dokončené mriežky sú rovnaké až na povolené symetrie (prečíslovanie číslic, permutácie riadkov/stĺpcov v rámci pásov alebo stohov, výmena pásov/stohov alebo transpozícia). Považujú sa za jeden „typ“.

To je kľúčové pre odpoveď na otázku „koľko je sudoku“. Ak sa pýtate, koľko existuje sudoku mriežok, zvyčajne myslíte dokončené riešiteľné mriežky. Ak sa pýtate na hádanky, zvyčajne myslíte, koľko vzorov indícií vedie k jedinečnému riešeniu.

Prečo je otázka „koľko je sudoku“ zložitá

• Musíte rozhodnúť, čo sa považuje za tú istú hádanku. Považujete dve hádanky, ktoré sa líšia len prečíslovaním číslic, za odlišné? Mnohí matematici nie.
• Priestor možností pre podmnožiny indícií je kombinatoricky obrovský. Overenie jedinečnosti si vyžaduje riešenie, nie len počítanie.
• Záleží aj na náročnosti. Tvorcovia aplikácií sa zaujímajú o to, „koľko je sudoku“ danej obtiažnosti, čo je iný filter.

Ako poznamenáva Dr. Lina Park, výskumníčka v kombinatorike: „Počítanie riešiteľných mriežok sudoku je čistá úloha enumerácie. Počítanie všetkých platných hádaniek s jedným riešením je iná disciplína, pretože nad čistú kombinatoriku pridáva aj logiku riešenia.“

Ako bolo vypočítané číslo 6.67×10^21

Kanonický počet pre 9x9 používa kombinatorickú enumeráciu so znižovaním symetrií:

1. Vytvoria sa kanonické reprezentácie štruktúr podobných latinským štvorcom, ktoré sú kompatibilné s 3×3 blokmi.
2. Použijú sa grupové operácie (permutácie riadkov/stĺpcov v rámci pásov/stohov, výmeny pásov/stohov, transpozícia a prečíslovanie číslic), aby sa zabránilo redundantnej práci.
3. Započítajú sa orbity a získa sa úplný počet.

Kľúčové zložky symetrie, ktoré sa často uvádzajú zdroj: Wikipedia:

• Prečíslovanie číslic: 9! = 362,880
• Permutácie riadkov v rámci každého z 3 pásov: (3!)^3
• Permutácie stĺpcov v rámci každého z 3 stohov: (3!)^3
• Výmena 3 pásov a 3 stohov: 3! × 3!
• Transpozícia: ×2
• Veľkosť súčinu: približne 1.22×10^12 symetrií (nie každá mriežka dosiahne plnú orbitu, ale toto ukazuje mierku)

Prečo je to dôležité pri otázke „koľko je sudoku“: pochopením symetrickej grupy výskumníci odstraňujú duplicity a vypočítali 5,472,730,538 v podstate odlišných riešiteľných mriežok sudoku zdroj: arXiv.

Minimum indícií: prečo je 17 dôležitých pri počítaní

Kľúčovou podmienkou platných hádaniek je, že musia mať jedinečné riešenie. V roku 2012 tím pomocou masívneho výpočtu dokázal, že neexistuje sudoku 9x9 so 16 indíciami; minimum je 17 indícií správa: BBC.

Dôsledky:

• Existencia: Každá platná hádanka 9x9 musí mať aspoň 17 zadaných čísel.
• Zúženie priestoru: Pri počítaní „koľko je sudoku“ možno ignorovať súbory indícií menšie ako 17.
• Obtiažnosť: Hádanky so 17 indíciami bývajú náročné, no samotný počet indícií presne neurčuje obtiažnosť.

Koľko je sudoku mriežok a koľko sudoku hádaniek?

Rozdeľme si dve otázky, ktoré si ľudia často mýlia:

• Koľko je sudoku mriežok (dokončených riešení)? Pre 9x9 je to 6.67×10^21.
• Koľko je sudoku hádaniek? Presne neznáme, no každá z 6.67×10^21 mriežok môže vytvoriť obrovskú rodinu hádaniek s jedným riešením.

Praktický pohľad:

• Jednoduchý generátor, ktorý začne náhodnou riešiteľnou mriežkou a odstraňuje indície, dokáže s malým úsilím vytvoriť nespočetné množstvo odlišných hádaniek s jedným riešením.
• Aj prísna deduplikácia podľa symetrie stále ponecháva ohromne veľký súbor.

Porovnávacia tabuľka

Nižšie je rýchla referenčná tabuľka, ktorú môžete citovať alebo si pozrieť porovnanie, keď hovoríte o veľkostiach a stave poznania.

Porovnávacia tabuľka

Poznámky:

• Počty pre 9x9 sú podložené publikovanými enumeráciami Wikipedia a redukciou na 5.47 miliardy v podstate odlišných mriežok arXiv.
• Pri väčších mriežkach dáva počet kombinácií sudoku 9x9 predstavu o tom, ako dramaticky sa pri prechode na 16x16 zväčší stavový priestor nad rámec dnešnej možnosti úplnej enumerácie.

Tvorba v praxi: čo vidíme v reálnom svete

Pri tvorbe a audite generátorov sudoku:

• Priepustnosť: Moderné CPU dokážu generovať desiatky tisíc hádaniek 9x9 s jedným riešením za hodinu pomocou rýchlych riešičov a deduplikácie s ohľadom na symetriu.
• Rozmanitosť: Pri náhodnom prečíslovaní číslic, miešaní riadkov/stĺpcov a rôznych poradí odstraňovania je v bežnom spotrebiteľskom použití prekryv zanedbateľný.
• Kurátorovanie obtiažnosti: Pridanie hodnotiaceho enginu (iba jednoduché čísla, skryté/zamknuté kandidáty, X-Wing atď.) filtruje prúd do úrovňových sád bez toho, aby sa obsah minul.

Na základe reálnych výsledkov je prevádzková odpoveď na otázku „koľko je sudoku“ pre hernú platformu „prakticky nevyčerpateľne veľa“ v ľudských časových mierkach. O nové, platné tabuľky pre hráčov len tak neprídete.

Prečo je to dôležité pre hráčov a tvorcov aplikácií

• Vnímaná novota: Aj denní hráči môžu roky stretávať nové štruktúry.
• Férovosť: Vynucovanie „jedinečného riešenia“ a testovanie logického riešenia zvyšuje dôveru.
• Obsahová stratégia: Úrovne obtiažnosti si vyžadujú cielenú generáciu, nie náhodné odstraňovanie indícií.

Ak chcete na vlastnej koži zažiť kombinatorickú rozmanitosť, vyskúšajte rôzne režimy a úrovne na Hrajte sudoku online. Ak sú pre vás pravidlá alebo taktiky nové, náš návod Ako hrať sudoku pre začiatočníkov vám pomôže zrýchliť riešenie.

Ako výskumníci znižujú duplicity? (V podstate odlišné sudoku)

Pojem „v podstate odlišné sudoku“ formalizuje, kedy sa dve dokončené tabuľky považujú za rovnaký vzor:

• Povolené symetrie: prečíslovanie číslic, permutácie riadkov/stĺpcov v rámci pásov/stohov, výmena pásov/stohov a transpozícia.
• Orbity: Všetky tabuľky dosiahnuteľné týmito symetriami tvoria orbitu; počítanie jedného zástupcu za orbitu zabraňuje nadhodnoteniu.
• Výsledok: 5,472,730,538 orbit pre 9x9. To je čistá odpoveď na otázku „koľko je sudoku mriežok, ak ignorujete povrchové označenie“.

Toto rozlíšenie je užitočné, ak je vaším zámerom pri otázke „koľko je sudoku“ rozmanitosť základných vzorov, nie len zmeny v označení na povrchu.

Čo určuje rast počtu hádaniek z jednej mriežky?

Z jednej dokončenej mriežky môžete vytvoriť mnoho hádaniek s jedným riešením výberom rôznych súborov indícií:

• Stratégie výberu indícií: symetrické umiestnenie, po pásoch alebo odstraňovanie riadené entropiou.
• Kontrola jedinečnosti: spätnoväzbový riešič s limitom počtu riešení zabezpečí presne jedno riešenie.
• Minimalita: Ďalšie odstraňovanie indícií, kým už žiadnu nemožno odstrániť bez porušenia jedinečnosti (voliteľné, ale obľúbené pre eleganciu).

Aj mierne odlišné poradia odstraňovania alebo rozdielne pravidlá pri výbere riešení vedú k odlišným hádankám s jedným riešením. Preto „koľko je sudoku“ výrazne presahuje „koľko je sudoku mriežok“.

Údaje a citácie, ktorým môžete veriť

• 6.670903752021072936960×10^21 vyplnených mriežok 9x9: pozrite si matematické odvodenie a zhrnutie na Wikipedia.
• 5,472,730,538 v podstate odlišných mriežok: redukcia počtu orbit opísaná v práci archivovanej na arXiv.
• Minimum 17 indícií: široko uvádzané po výpočte z roku 2012 (napr. BBC).

Odborný pohľad na praktické limity

„Pýtať sa, koľko je sudoku, je ako pýtať sa, koľko melódií sa dá vytvoriť z 12 tónov,“ hovorí Alex Chen, vedúci systémov hádaniek v LogicLab. „Teoretický priestor je konečný, ale taký obrovský, že pre ľudské použitie je v podstate neobmedzený — najmä keď ho filtrujete podľa jedinečnosti a obtiažnosti.“

Súvisiace pojmy a terminológia

• Latinské štvorce a ortogonalita
• Štruktúra pásov a stohov v sudoku 9x9
• Myšlienky orbit–stabilizátor z teórie grup
• Minimálne hádanky vs. viacriešiteľné hádanky
• Úrovne logiky ľudského riešenia (jednoduché čísla, dvojice, fish vzory, farbenie)

Pochopenie týchto pojmov vám pomôže správne interpretovať tvrdenia o tom, „koľko je sudoku“, najmä keď zdroje miešajú riešiteľné mriežky s hádankami so zadanými indíciami.

Kľúčové zhrnutie

• Existuje 6.67×10^21 vyplnených riešiteľných mriežok sudoku 9x9; 5.47 miliardy z nich je pri zohľadnení symetrie v podstate odlišných.
• Presný počet platných sudoku 9x9 s jedinečným riešením nie je známy, ale je oveľa väčší než počet riešiteľných mriežok.
• Každá platná hádanka 9x9 potrebuje aspoň 17 indícií; 16-indíciové hádanky neexistujú.
• Pre hráčov a platformy je praktická zásoba nových, jedinečných sudoku v podstate nevyčerpateľná.
• Rozlišujte medzi „koľko je sudoku mriežok“ (riešení) a „koľko je sudoku hádaniek“ (súborov indícií s jedinečným riešením), aby ste čísla interpretovali správne.