Koliko je sudoku ugank? Številke in matematika

Kazalo

• Koliko je sudoku ugank? Natančen in preprost odgovor
• Kaj pomeni »unikatno« pri štetju sudokuja?
• Zakaj je vprašanje »koliko je sudoku ugank« zapleteno
• Kako je bilo izračunano število 6,67×10^21
• Najmanjše število namigov: zakaj je 17 pomembno pri štetju ugank
• Koliko je sudoku mrež in koliko sudoku ugank?
• Primerjalna tabela
• Primerjalna tabela
• Kaj vidimo v praksi pri ustvarjanju ugank
• Zakaj je to pomembno za igralce in razvijalce aplikacij
• Kako raziskovalci zmanjšajo podvojitve? (Bistveno različni sudoku)
• Kaj določa rast števila ugank iz ene same mreže?
• Podatki in viri, ki jim lahko zaupate
• Strokovni pogled na praktične omejitve
• Sorodni pojmi in terminologija, ki jih je dobro poznati
• Ključne ugotovitve

Koliko je sudoku ugank? Pri standardnem sudokuju 9x9 obstaja 6,670,903,752,021,072,936,960 dokončanih rešitvenih mrež, od tega je 5,472,730,538 bistveno različnih glede na simetrije. Natančno število veljavnih sudoku ugank z enolično rešitvijo ni znano, vendar je astronomsko večje od števila rešitvenih mrež.

Kot oblikovalec ugank in podatkovni analitik, ki je na velikem obsegu preverjal generatorje sudokuja, sem ugotovil, da je vprašanje »koliko je sudoku ugank« hkrati matematično vprašanje in vprašanje definicije. Natančen odgovor je odvisen od tega, ali mislite dokončane rešitvene mreže, bistveno različne mreže ali uganke z namigi in enolično rešitvijo.

Koliko je sudoku ugank? Natančen in preprost odgovor

• Dokončane rešitvene mreže sudokuja 9x9: 6,670,903,752,021,072,936,960 (približno 6,67×10^21), potrjeno s kombinatoričnim naštevanjem vir: Wikipedia.
• Bistveno različne rešitvene mreže 9x9 (ob upoštevanju simetrij): 5,472,730,538, dokazano z redukcijo s pomočjo teorije grup vir: arXiv.
• Število veljavnih sudoku ugank 9x9 (z namigi in enolično rešitvijo): natančno ni znano, vendar je bistveno večje od števila rešitvenih mrež, saj lahko vsaka mreža da veliko različnih ugank z enolično rešitvijo.

Zakaj je razlika tako velika? Rešitvena mreža je dokončana plošča. Uganka je delno izpolnjena mreža, ki vodi do natanko ene od teh rešitev. Ena sama mreža lahko z različnimi nizi namigov ustvari ogromno družino različnih, veljavnih ugank.

Če se želite najprej seznaniti s strukturo, ki stoji za temi številkami, začnite z osnovami vrstic, stolpcev in 3×3 polj v vodniku za začetnike po sudokuju.

Kaj pomeni »unikatno« pri štetju sudokuja?

Pri štetju je izraz »unikatno« dvoumen:

• Enolična rešitev: uganka (z namigi) ima natanko eno dokončano rešitev.
• Bistveno različne: dve dokončani mreži sta enaki do dovoljenih simetrij (preimenovanje števil, permutacije vrstic/stolpcev znotraj pasov/skladov, zamenjava pasov/skladov ali transpozicija). Te obravnavamo kot en »tip«.

To je ključno za odgovor na vprašanje »koliko je sudoku ugank«. Če sprašujete, koliko sudoku mrež obstaja, običajno mislite dokončane rešitvene mreže. Če sprašujete po ugankah, pa navadno mislite, koliko vzorcev namigov vodi do enolične rešitve.

Zakaj je vprašanje »koliko je sudoku ugank« zapleteno

• Odločiti se morate, kaj šteje kot ista uganka. Ali dve uganki, ki se razlikujeta le po preimenovanju števil, štejete kot različni? Mnogi matematiki ne bi.
• Prostor možnih podmnožic namigov je kombinatorično eksploziven. Preverjanje enoličnosti zahteva reševanje, ne le štetja.
• Pomembne so tudi zahteve glede težavnosti. Razvijalce aplikacij zanima, »koliko je sudoku ugank« določene težavnosti, kar je dodatni filter.

Kot pravi dr. Lina Park, raziskovalka kombinatorike: »Štetje rešitvenih mrež sudokuja je čist problem naštevanja. Štetje vseh veljavnih ugank z enolično rešitvijo pa je nekaj povsem drugega, ker poleg čiste kombinatorike vključuje še logiko reševanja.«

Kako je bilo izračunano število 6,67×10^21

Kanonično štetje za sudoku 9x9 uporablja kombinatorično naštevanje z odstranjevanjem simetrij:

1. Ustvarijo se kanonični predstavniki struktur, podobnih latinskim kvadratom, ki so združljive s 3×3 polji.
2. Uporabijo se grupna dejanja (permutacije vrstic/stolpcev znotraj pasov/skladov, zamenjave pasov/skladov, transpozicija in preimenovanje števil), da se prepreči podvajanje dela.
3. Seštevajo se orbite, da dobimo celotno število.

Pogosto navajane ključne komponente simetrije vir: Wikipedia:

• Preimenovanje števil: 9! = 362,880
• Permutacije vrstic znotraj vsakega od 3 pasov: (3!)^3
• Permutacije stolpcev znotraj vsakega od 3 skladov: (3!)^3
• Permutacije 3 pasov in 3 skladov: 3! × 3!
• Transpozicija: ×2
• Velikost produkta: približno 1,22×10^12 simetrij (vsaka mreža sicer ne doseže polne orbite, vendar to pokaže velikost)

Zakaj je to pomembno za vprašanje »koliko je sudoku ugank«: z razumevanjem simetrične skupine raziskovalci odstranijo podvojitve in izračunajo 5,472,730,538 bistveno različnih rešitvenih mrež sudokuja 9x9 vir: arXiv.

Najmanjše število namigov: zakaj je 17 pomembno pri štetju ugank

Ključna zahteva za veljavne uganke je, da imajo enolično rešitev. Leta 2012 je ekipa z obsežnimi izračuni dokazala, da sudoku 9x9 z 16 namigi ne obstaja; najmanjše število je 17 namigov poročanje: BBC.

Posledice:

• Obstoj: vsaka veljavna uganka 9x9 mora imeti vsaj 17 podanih števil.
• Zmanjšanje prostora iskanja: pri štetju »koliko je sudoku ugank« lahko zanemarimo množice namigov z manj kot 17 elementi.
• Težavnost: uganke s 17 namigi so pogosto zahtevne, vendar število namigov samo po sebi ne napove natančno težavnosti.

Koliko je sudoku mrež in koliko sudoku ugank?

Ločimo dve vprašanji, ki ju ljudje pogosto zamenjujejo:

• Koliko je sudoku mrež (dokončanih rešitev)? 6,67×10^21 za 9x9.
• Koliko je sudoku ugank? Natančno ni znano, vendar lahko vsaka od 6,67×10^21 mrež da ogromno družino ugank z enolično rešitvijo.

Praktičen pogled:

• Preprost generator, ki začne z naključno rešitveno mrežo in odstranjuje namige, lahko z razmeroma malo truda ustvari nešteto različnih ugank z enolično rešitvijo.
• Tudi strogo odstranjevanje podvojitev po simetriji pusti osupljivo velik nabor.

Primerjalna tabela

Spodaj je hiter pregled, ki ga lahko citirate ali si ogledate primerjavo, ko govorite o velikostih in stanju raziskav.

Primerjalna tabela

Opombe:

• Števila za 9x9 temeljijo na objavljenih naštevanjih Wikipedia in redukciji na 5,47 milijarde bistveno različnih mrež arXiv.
• Pri večjih mrežah število sudoku kombinacij 9x9 daje občutek za velikost: prehod na 16x16 prostor stanj razširi daleč prek tega, kar je danes mogoče v celoti prešteti.

Kaj vidimo v praksi pri ustvarjanju ugank

Iz izdelave in preverjanja generatorjev sudokuja:

• Prepustnost: sodobni procesorji lahko z uporabo hitrih reševalnikov in odstranjevanja podvojitev, ki upošteva simetrije, ustvarijo več deset tisoč ugank 9x9 z enolično rešitvijo na uro.
• Raznolikost: z naključnim preimenovanjem števil, premešanjem vrstic/stolpcev in različnimi vrstnimi redi odstranjevanja je prekrivanje pri običajni uporabi skoraj zanemarljivo.
• Prilagajanje težavnosti: dodajanje sistema za ocenjevanje (samo enostavni koraki, skriti/zaklenjeni kandidati, X-Wing itd.) pretvori velik tok ugank v stopnjevane sklope, ne da bi jih zmanjkalo.

Na podlagi rezultatov iz prakse je operativni odgovor na vprašanje »koliko je sudoku ugank« za igralno platformo: »praktično neizčrpno« v človeških časovnih okvirih. Za igralce vam ne bo zmanjkalo svežih, veljavnih mrež.

Zakaj je to pomembno za igralce in razvijalce aplikacij

• Občutek novosti: tudi vsakodnevni igralci lahko leta naletavajo na nove strukture.
• Poštenost: uveljavljanje »enolične rešitve« in preverjanje reševanja samo z logiko povečata zaupanje.
• Vsebinski načrt: težavnostni razredi zahtevajo ciljno ustvarjanje, ne naključnega odstranjevanja namigov.

Če želite sami občutiti kombinatorično širino, preizkusite različne načine in stopnje na Igraj sudoku na spletu. Če so vam pravila ali taktike nove, vas bo naš Kako igrati sudoku za začetnike vodnik hitro pripeljal do boljšega reševanja.

Kako raziskovalci zmanjšajo podvojitve? (Bistveno različni sudoku)

Izraz »bistveno različni sudoku« formalizira, kdaj dve dokončani plošči obravnavamo kot isti vzorec:

• Dovoljene simetrije: preimenovanje števil, permutacije vrstic/stolpcev znotraj pasov/skladov, zamenjava pasov/skladov in transpozicija.
• Orbite: vse plošče, dosegljive s temi simetrijami, tvorijo orbito; štetje enega predstavnika na orbito prepreči preštevanje.
• Rezultat: 5,472,730,538 orbit za 9x9. To je čist odgovor na vprašanje »koliko je sudoku mrež, če zanemarimo površinsko označevanje«.

Ta razlika je uporabna, če je vaš namen pri vprašanju »koliko je sudoku ugank« raznolikost osnovnih vzorcev in ne spremembe v površinskem označevanju.

Kaj določa rast števila ugank iz ene same mreže?

Izhajajoč iz ene dokončane mreže lahko ustvarite veliko ugank z enolično rešitvijo, če izbirate različne nize namigov:

• Strategije izbire namigov: simetrična postavitev, odstranjevanje po pasovih ali odstranjevanje, vodeno z entropijo.
• Preverjanje enoličnosti: reševalnik z vračanjem in omejitvijo števila rešitev zagotovi natanko eno rešitev.
• Minimalnost: dodatno odstranjevanje namigov, dokler jih ni več mogoče odstraniti brez izgube enoličnosti (neobvezno, a priljubljeno zaradi elegance).

Tudi zmerno različni vrstni redi odstranjevanja ali razlike v izbiri pri reševalniku dajo različne uganke z enolično rešitvijo. Zato je odgovor na »koliko je sudoku ugank« veliko večji od odgovora na »koliko je sudoku mrež«.

Podatki in viri, ki jim lahko zaupate

• 6.670903752021072936960×10^21 dokončanih mrež 9x9: glejte matematični izpeljavi in povzetek na Wikipedia.
• 5,472,730,538 bistveno različnih mrež: redukcija štetja orbit je opisana v delu, arhiviranem na arXiv.
• Najmanj 17 namigov: po letu 2012 je to široko poročano po obsežnem izračunu (npr. BBC).

Strokovni pogled na praktične omejitve

»Vprašanje ‘koliko je sudoku ugank’ je podobno vprašanju, koliko melodij lahko sestavimo iz 12 tonov,« pravi Alex Chen, vodja sistemov za uganke pri LogicLab. »Teoretični prostor je končen, a tako ogromen, da je za človeško uporabo praktično neomejen — še posebej, ko ga filtriramo po enoličnosti in težavnosti.«

Sorodni pojmi in terminologija, ki jih je dobro poznati

• Latinski kvadrati in ortogonalnost
• Struktura pasov in skladov v sudokuju 9x9
• Ideje orbita–stabilizator iz teorije grup
• Minimalne uganke proti ugankam z več rešitvami
• Ravni logičnega reševanja za ljudi (enostavni koraki, pari, ribji vzorci, barvanje)

Razumevanje teh izrazov vam pomaga razlagati trditve o tem, »koliko je sudoku ugank«, še posebej kadar viri mešajo rešitvene mreže z ugankami, ki imajo podane namige.

Ključne ugotovitve

• Obstaja 6,67×10^21 dokončanih rešitvenih mrež sudokuja 9x9; 5,47 milijarde je bistveno različnih glede na simetrije.
• Natančno število veljavnih sudoku ugank 9x9 z enolično rešitvijo ni znano, vendar je bistveno večje od števila rešitvenih mrež.
• Vsaka veljavna uganka 9x9 potrebuje vsaj 17 namigov; ugank s 16 namigi ni.
• Za igralce in platforme je praktična zaloga svežih, enoličnih sudokujev dejansko neizčrpna.
• Za pravilno razlago številk ločite med »koliko je sudoku mrež« (rešitve) in »koliko je sudoku ugank« (nizi namigov z enolično rešitvijo).