Koliko ima Sudoku zagonetki? Brojevi i matematika

Sadržaj

• Koliko ima Sudoku zagonetki? Precizan i jednostavan odgovor
• Što znači “jedinstven” u brojanju Sudoku zagonetki?
• Zašto je pitanje “koliko ima Sudoku zagonetki” složeno
• Kako je izračunat broj 6.67×10^21
• Minimalni broj tragova: zašto je 17 važan za brojanje zagonetki
• Koliko ima Sudoku mreža, a koliko Sudoku zagonetki?
• Usporedna tablica
• Usporedna tablica
• Stvarno generiranje: što vidimo u praksi
• Zašto je to važno za igrače i dizajnere aplikacija
• Kako istraživači smanjuju duplikate? (Bitno različit Sudoku)
• Što određuje rast broja zagonetki iz jedne mreže?
• Podaci i izvori kojima možete vjerovati
• Stručni pogled na praktična ograničenja
• Povezani pojmovi i terminologija koje vrijedi znati
• Ključni zaključci

Koliko ima Sudoku zagonetki? Za standardni Sudoku 9x9 postoji 6,670,903,752,021,072,936,960 dovršenih rješenja mreže, a 5,472,730,538 od njih su bitno različite pod simetrijom. Točan broj valjanih Sudoku zagonetki s jedinstvenim rješenjem nije poznat, ali je astronomski veći od broja rješenja mreža.

Kao dizajner zagonetki i analitičar podataka koji je u velikom opsegu provjeravao Sudoku generatore, naučio sam da je pitanje “koliko ima Sudoku zagonetki” istodobno matematičko pitanje i pitanje definicije. Točan broj koji tražite ovisi o tome mislite li na dovršene rješenja mreža, bitno različite mreže ili zagonetke s tragovima koje imaju jedinstveno rješenje.

Koliko ima Sudoku zagonetki? Precizan i jednostavan odgovor

• Dovršene Sudoku mreže 9x9: 6,670,903,752,021,072,936,960 (oko 6.67×10^21), potvrđeno kombinatornim nabrajanjem izvor: Wikipedia.
• Bitno različite mreže 9x9 (uz uzimanje u obzir valjanih simetrija): 5,472,730,538, dokazano grupno-teorijskom redukcijom izvor: arXiv.
• Broj valjanih Sudoku zagonetki 9x9 (s tragovima i jedinstvenim rješenjem): nije točno poznat, ali je mnogo veći od broja rješenja mreža jer svaka mreža može dati mnogo različitih zagonetki s jedinstvenim rješenjem.

Zašto je razlika tolika? Rješenje mreže je dovršena ploča. Zagonetka je djelomično ispunjena mreža koja vodi do točno jednog od tih rješenja. Jedna mreža može proizvesti golemo mnoštvo različitih, valjanih zagonetki odabirom različitih skupova tragova.

Ako učite strukturu koja stoji iza tih brojki, krenite od osnova redaka, stupaca i 3×3 polja u vodiču za početnike u Sudokuu.

Što znači “jedinstven” u brojanju Sudoku zagonetki?

U brojanju se riječ “jedinstven” koristi u više značenja:

• Jedinstveno rješenje: Zagonetka (s tragovima) ima točno jedno dovršeno rješenje mreže.
• Bitno različit: Dvije dovršene mreže iste su do dopuštenih simetrija (preimenovanje znamenki, permutacije redaka/stupaca unutar pojaseva/stogova, zamjena pojaseva/stogova ili transponiranje). One se smatraju jednom “vrstom”.

To je ključno za odgovor na pitanje “koliko ima Sudoku zagonetki”. Ako pitate koliko Sudoku mreža postoji, obično mislite na dovršene rješenja mreža. Ako pitate za zagonetke, obično mislite na to koliko obrazaca tragova daje jedinstveno rješenje.

Zašto je pitanje “koliko ima Sudoku zagonetki” složeno

• Morate odlučiti što se smatra istom zagonetkom. Smatrate li dvije zagonetke koje se razlikuju samo preimenovanjem znamenki različitima? Mnogi matematičari ne bi.
• Prostor mogućih podskupova tragova kombinatorno eksplodira. Provjera jedinstvenosti zahtijeva rješavanje, a ne samo brojanje.
• Važna su i ograničenja težine. Dizajneri aplikacija brinu o tome “koliko ima Sudoku zagonetki određene težine”, što je zaseban filter.

Kako napominje dr. Lina Park, istraživačica kombinatorike: “Brojanje Sudoku rješenja mreža čist je problem nabrajanja. Brojanje svih valjanih zagonetki s jedinstvenim rješenjem sasvim je druga priča jer na čistu kombinatoriku nadograđuje logiku rješavanja.”

Kako je izračunat broj 6.67×10^21

Kanonijski broj za Sudoku 9x9 dobiven je kombinatornim nabrajanjem uz uklanjanje simetrija:

1. Generiraju se kanonski predstavnici struktura nalik latinskim kvadratima koje su kompatibilne s poljima 3×3.
2. Primjenjuju se grupne akcije (permutacije redaka/stupaca unutar pojaseva/stogova, zamjene pojaseva/stogova, transponiranje i preimenovanje znamenki) kako bi se izbjegao suvišan rad.
3. Zbrajaju se orbite kako bi se dobio puni broj.

Ključne komponente simetrije koje se često navode izvor: Wikipedia:

• Preimenovanje znamenki: 9! = 362,880
• Permutacije redaka unutar svakog od 3 pojasa: (3!)^3
• Permutacije stupaca unutar svakog od 3 stoga: (3!)^3
• Zamjena 3 pojasa i 3 stoga: 3! × 3!
• Transponiranje: ×2
• Veličina produkta: približno 1.22×10^12 simetrija (ne postiže svaka mreža punu orbitu, ali to daje mjerilo)

Zašto je to važno za pitanje “koliko ima Sudoku zagonetki”: razumijevanjem grupe simetrija istraživači uklanjaju duplikate kako bi izračunali 5,472,730,538 bitno različitih Sudoku rješenja mreža izvor: arXiv.

Minimalni broj tragova: zašto je 17 važan za brojanje zagonetki

Važno ograničenje za valjane zagonetke jest da moraju imati jedinstveno rješenje. Godine 2012. tim je uz golemo računanje dokazao da ne postoji Sudoku 9x9 s 16 tragova; minimum je 17 tragova prikaz: BBC.

Implikacije:

• Postojanje: Svaka valjana zagonetka 9x9 mora imati najmanje 17 zadanih brojeva.
• Smanjenje prostora pretraživanja: Svako brojanje “koliko ima Sudoku zagonetki” može zanemariti skupove tragova manje od 17.
• Težina: Zagonetke s 17 tragova često su teže, ali broj tragova sam po sebi ne predviđa savršeno težinu.

Koliko ima Sudoku mreža, a koliko Sudoku zagonetki?

Razdvojimo dva pitanja koja ljudi često miješaju:

• Koliko ima Sudoku mreža (dovršenih rješenja)? 6.67×10^21 za 9x9.
• Koliko ima Sudoku zagonetki? Točan broj nije poznat, ali svaka od 6.67×10^21 mreža može dati golemo mnoštvo zagonetki s jedinstvenim rješenjem.

Praktična perspektiva:

• Naivan generator koji krene od slučajnih rješenja mreža i uklanja tragove može proizvesti bezbroj različitih zagonetki s jedinstvenim rješenjem uz relativno malo truda.
• Čak i stroga deduplikacija po simetriji ostavlja zapanjujuće velik skup.

Usporedna tablica

Ispod je brzi pregled koji možete citirati ili pogledati usporedbu kada raspravljate o veličinama i statusu.

Usporedna tablica

Napomene:

• Brojke za 9x9 potkrijepljene su objavljenim nabrajanjem Wikipedia i redukcijom na 5.47 milijardi bitno različitih mreža arXiv.
• Za veće mreže, broj Sudoku kombinacija 9x9 daje intuiciju: prelazak na 16x16 eksplodira prostor stanja daleko iznad onoga što je danas moguće potpuno nabrojati.

Stvarno generiranje: što vidimo u praksi

Iz izrade i provjere Sudoku generatora:

• Propusnost: Moderni procesori mogu generirati desetke tisuća Sudoku zagonetki 9x9 s jedinstvenim rješenjem na sat uz brze rješavače i deduplikaciju svjesnu simetrija.
• Raznolikost: Uz nasumično preimenovanje znamenki, miješanje redaka/stupaca i različite redoslijede uklanjanja, preklapanje je u uobičajenoj potrošačkoj uporabi zanemarivo.
• Uređivanje težine: Dodavanje sustava za ocjenjivanje (samo jednostavni, skriveni/zaključani kandidati, X-Wing itd.) filtrira golemi tok u razine bez da ponestane sadržaja.

Na temelju stvarnih rezultata, operativni odgovor na pitanje “koliko ima Sudoku zagonetki” za platformu za igre glasi: “praktički neiscrpno” u vremenskim razmjerima čovjeka. Nećete ostati bez svježih, valjanih ploča za igrače.

Zašto je to važno za igrače i dizajnere aplikacija

• Doživljaj novosti: Čak i svakodnevni igrači mogu godinama nailaziti na nove strukture.
• Poštenje: Provjera “jedinstvenog rješenja” i testiranje logičkog rješavanja povećavaju povjerenje.
• Strategija sadržaja: Razine težine zahtijevaju ciljano generiranje, a ne nasumično uklanjanje tragova.

Ako želite iz prve ruke doživjeti kombinatornu širinu, isprobajte razne načine i razine na Igraj Sudoku online. Ako su vam pravila ili taktike novi, naš Kako igrati Sudoku za početnike vodič ubrzat će vaše rješavanje.

Kako istraživači smanjuju duplikate? (Bitno različit Sudoku)

Izraz “bitno različit Sudoku” formalizira kada se dvije dovršene ploče smatraju istim obrascem:

• Dopuštene simetrije: preimenovanje znamenki, permutacije redaka/stupaca unutar pojaseva/stogova, zamjena pojaseva/stogova i transponiranje.
• Orbite: Sve ploče do kojih se može doći tim simetrijama čine orbitu; brojanje jednog predstavnika po orbiti sprječava dvostruko brojanje.
• Rezultat: 5,472,730,538 orbita za 9x9. To je jasan odgovor na pitanje “koliko ima Sudoku mreža ako zanemarimo površinsko označavanje”.

Ova je razlika korisna ako je vaš cilj iza pitanja “koliko ima Sudoku zagonetki” raznolikost temeljnih obrazaca, a ne promjene u površinskom označavanju.

Što određuje rast broja zagonetki iz jedne mreže?

Polazeći od jedne dovršene mreže, možete generirati mnogo zagonetki s jedinstvenim rješenjem odabirom različitih skupova tragova:

• Strategije odabira tragova: simetrično postavljanje, uklanjanje po pojasevima ili uklanjanje vođeno entropijom.
• Provjera jedinstvenosti: rješavač s povratnim pretraživanjem i ograničenjem broja rješenja osigurava točno jedno rješenje.
• Minimalnost: dodatno uklanjanje tragova dok se više nijedan ne može ukloniti bez gubitka jedinstvenosti (opcionalno, ali popularno zbog elegancije).

Čak i umjereno različiti redoslijedi uklanjanja ili tie-break pravila u rješavaču daju različite zagonetke s jedinstvenim rješenjem. Zato je odgovor na “koliko ima Sudoku zagonetki” daleko veći od odgovora na “koliko ima Sudoku mreža”.

Podaci i izvori kojima možete vjerovati

• 6.670903752021072936960×10^21 dovršenih mreža 9x9: pogledajte matematičko izvođenje i sažetak na Wikipedia.
• 5,472,730,538 bitno različitih mreža: redukcija brojanja orbita opisana je u radu arhiviranom na arXiv.
• Minimum od 17 tragova: široko je prijavljen nakon izračuna iz 2012. (npr. BBC).

Stručni pogled na praktična ograničenja

“Pitati ‘koliko ima Sudoku zagonetki’ slično je kao pitati koliko se melodija može napisati s 12 nota,” kaže Alex Chen, voditelj sustava zagonetki u LogicLabu. “Teorijski prostor je konačan, ali toliko golem da je za ljudsku uporabu praktički neograničen — osobito kada ga filtrirate po jedinstvenosti i težini.”

Povezani pojmovi i terminologija koje vrijedi znati

• Latinski kvadrati i ortogonalnost
• Struktura pojaseva i stogova u Sudokuu 9x9
• Ideje orbitno-stabilizatorskog teorema iz teorije grupa
• Minimalne zagonetke nasuprot zagonetkama s više rješenja
• Razine logike za ljudsko rješavanje (jednostavni, parovi, riblji obrasci, bojanje)

Razumijevanje ovih pojmova pomaže vam protumačiti tvrdnje iza pitanja “koliko ima Sudoku zagonetki”, osobito kada izvori miješaju rješenja mreža sa zagonetkama koje imaju tragove.

Ključni zaključci

• Postoji 6.67×10^21 dovršenih Sudoku rješenja mreža 9x9; 5.47 milijardi je bitno različito pod simetrijom.
• Točan broj valjanih Sudoku zagonetki 9x9 s jedinstvenim rješenjem nije poznat, ali je mnogo veći od broja rješenja mreža.
• Svaka valjana zagonetka 9x9 treba imati najmanje 17 tragova; zagonetke s 16 tragova ne postoje.
• Za igrače i platforme, praktična ponuda svježih, jedinstvenih Sudoku zagonetki praktički je neiscrpna.
• Razlikujte “koliko ima Sudoku mreža” (rješenja) i “koliko ima Sudoku zagonetki” (skupovi tragova s jedinstvenim rješenjem) kako biste ispravno tumačili brojke.