Koliko ima Sudoku zagonetki? Brojevi i matematika

Sadržaj

• Koliko ima Sudoku zagonetki? Precizan i jednostavan odgovor
• Šta 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 tragovi: zašto je 17 važno za brojanje zagonetki
• Koliko ima Sudoku mreža, a koliko Sudoku zagonetki?
• Uporedna tabela
• Uporedna tabela
• Generisanje u praksi: šta vidimo u stvarnom svetu
• Zašto je to važno za igrače i dizajnere aplikacija
• Kako istraživači smanjuju duplikate? (Suštinski različit Sudoku)
• Šta određuje rast broja zagonetki iz jedne mreže?
• Podaci i citati kojima možete verovati
• Stručni pogled na praktična ograničenja
• Povezani pojmovi i terminologija koje treba znati
• Ključni zaključci

Koliko ima Sudoku zagonetki? Za standardni 9x9 Sudoku postoji 6,670,903,752,021,072,936,960 popunjenih rešenih mreža, a 5,472,730,538 od njih su suštinski različite pod simetrijom. Tačan broj važećih Sudoku zagonetki sa jedinstvenim rešenjem nije poznat, ali je astronomski veći od broja rešenih mreža.

Kao dizajner zagonetki i analitičar podataka koji je proveravao Sudoku generatore u velikom obimu, naučio sam da je pitanje „koliko ima Sudoku zagonetki“ istovremeno matematičko pitanje i pitanje definicije. Tačan broj koji tražite zavisi od toga da li mislite na popunjene rešenje mreže, suštinski različite mreže ili zagonetke sa tragovima koje imaju jedinstveno rešenje.

Koliko ima Sudoku zagonetki? Precizan i jednostavan odgovor

• Popunjene 9x9 Sudoku rešenje mreže: 6,670,903,752,021,072,936,960 (oko 6.67×10^21), potvrđeno kombinatornim nabrajanjem izvor: Wikipedia.
• Suštinski različite 9x9 rešenje mreže (uzimajući u obzir simetrije): 5,472,730,538, dokazano grupno-teorijskom redukcijom izvor: arXiv.
• Broj važećih 9x9 Sudoku zagonetki (sa tragovima i jedinstvenim rešenjem): nije tačno poznat, ali je daleko veći od broja rešenih mreža, jer jedna mreža može dati mnogo različitih zagonetki sa jedinstvenim rešenjem.

Zašto postoji tolika razlika? Rešenje mreža je završena tabla. Zagonetka je delimično popunjena mreža koja vodi do tačno jednog od tih rešenja. Jedna mreža može da proizvede ogroman skup različitih, potpuno ispravnih zagonetki izborom različitih skupova tragova.

Ako učite strukturu koja stoji iza ovih brojeva, počnite od osnova redova, kolona i 3×3 polja u vodiču za početnike u Sudokuu.

Šta znači „jedinstven“ u brojanju Sudoku zagonetki?

U brojanju, „jedinstven“ može da znači više stvari:

• Jedinstveno rešenje: Zagonetka (sa tragovima) ima tačno jedno završeno rešenje mreže.
• Suštinski različit: Dve završene mreže su iste do dozvoljenih simetrija (preimenovanje cifara, permutovanje redova/kolona unutar pojaseva/stekova, zamena pojaseva/stekova ili transponovanje). One se smatraju jednim „tipom“.

Ovo je ključno za odgovor na pitanje „koliko ima Sudoku zagonetki“. Ako pitate koliko postoji Sudoku mreža, obično mislite na popunjene rešenje mreže. Ako pitate za zagonetke, obično mislite na to koliko rasporeda tragova daje jedinstveno rešenje.

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

• Morate da odlučite šta se smatra istom zagonetkom. Da li dve zagonetke koje se razlikuju samo po preimenovanju cifara smatrate različitim? Mnogi matematičari ne bi.
• Prostor mogućih skupova tragova je kombinatorno ogroman. Provera jedinstvenosti zahteva rešavanje, ne samo brojanje.
• Ograničenja težine su važna. Dizajneri aplikacija brinu o tome „koliko ima Sudoku zagonetki određene težine“, što je drugačiji filter.

Kako primećuje dr Lina Park, istraživač kombinatorike: „Brojanje Sudoku rešenje mreža je čist problem nabrajanja. Brojanje svih važećih zagonetki sa jedinstvenim rešenjem je sasvim druga priča, jer na čistu kombinatoriku dodaje logiku rešavanja.“

Kako je izračunat broj 6.67×10^21

Kanonski broj za 9x9 dobija se kombinatornim nabrajanjem uz uklanjanje simetrija:

1. Generišu se kanonski predstavnici struktura nalik Latin square, kompatibilnih sa 3×3 poljima.
2. Primene se grupna dejstva (permutacije redova/kolona unutar pojaseva/stekova, zamena pojaseva/stekova, transponovanje i preimenovanje cifara) da bi se izbegao suvišan rad.
3. Sabiraju se orbite kako bi se dobio ukupan broj.

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

• Preimenovanje cifara: 9! = 362,880
• Permutovanje redova unutar svakog od 3 pojasa: (3!)^3
• Permutovanje kolona unutar svakog od 3 steka: (3!)^3
• Permutovanje 3 pojasa i 3 steka: 3! × 3!
• Transponovanje: ×2
• Veličina proizvoda: približno 1.22×10^12 simetrija (ne postiže svaka mreža punu orbitu, ali ovo daje razmeru)

Zašto je to važno za „koliko ima Sudoku zagonetki“: razumevanjem grupe simetrija istraživači uklanjaju duplikate i računaju 5,472,730,538 suštinski različitih Sudoku rešenje mreža izvor: arXiv.

Minimalni tragovi: zašto je 17 važno za brojanje zagonetki

Ključno ograničenje za važeće zagonetke jeste da moraju imati jedinstveno rešenje. Godine 2012. tim je uz ogromnu računarsku obradu dokazao da ne postoji 9x9 Sudoku sa 16 tragova; minimum je 17 tragova izveštaj: BBC.

Implikacije:

• Postojanje: Svaka važeća 9x9 zagonetka mora imati najmanje 17 datih brojeva.
• Smanjenje prostora pretrage: Svako brojanje „koliko ima Sudoku zagonetki“ može da zanemari skupove tragova manje od 17.
• Težina: Zagonetke sa 17 tragova često su teške, ali sam broj tragova ne predviđa savršeno težinu.

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

Razdvojimo dva pitanja koja ljudi često mešaju:

• Koliko ima Sudoku mreža (završenih rešenja)? 6.67×10^21 za 9x9.
• Koliko ima Sudoku zagonetki? Tačan broj nije poznat, ali svaka od 6.67×10^21 mreža može da proizvede ogroman skup zagonetki sa jedinstvenim rešenjem.

Praktična perspektiva:

• Naivan generator koji polazi od nasumičnih rešenih mreža i uklanja tragove može da proizvede bezbroj različitih zagonetki sa jedinstvenim rešenjem uz skroman napor.
• Čak i stroga deduplikacija po simetriji i dalje ostavlja zapanjujuće veliki skup.

Uporedna tabela

Ispod je brza referenca koju možete citirati ili pogledati poređenje kada govorite o veličinama i statusu.

Uporedna tabela

Napomene:

• Brojevi za 9x9 potkrepljeni su objavljenim nabrajanjem Wikipedia i redukcijom na 5.47 milijardi suštinski različitih mreža arXiv.
• Za veće mreže, broj 9x9 Sudoku kombinacija daje intuiciju: prelazak na 16x16 dramatično povećava prostor stanja daleko iznad onoga što je danas moguće potpuno izbrojati.

Generisanje u praksi: šta vidimo u stvarnom svetu

Iz izrade i provere Sudoku generatora:

• Propusnost: Savremeni procesori mogu da generišu desetine hiljada 9x9 zagonetki sa jedinstvenim rešenjem na sat uz brze rešavače i deduplikaciju svesnu simetrije.
• Raznolikost: Uz nasumično preimenovanje cifara, mešanje redova/kolona i različite redoslede uklanjanja, preklapanje je uobičajeno zanemarljivo u svakodnevnoj upotrebi.
• Uređivanje težine: Dodavanje sistema za ocenjivanje (samo jednostavna polja, skriveni/zatvoreni kandidati, X-Wing itd.) filtrira veliki tok u nivoe bez iscrpljivanja sadržaja.

Na osnovu stvarnih rezultata, operativni odgovor na pitanje „koliko ima Sudoku zagonetki“ za jednu platformu za igre glasi: „praktično neiscrpno“ u ljudskim vremenskim razmerama. Nećete ostati bez novih, važećih tabli za igrače.

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

• Osećaj novine: Čak i svakodnevni igrači mogu godinama nailaziti na nove strukture.
• Pravednost: Primena pravila „jedinstveno rešenje“ i provera rešivosti logikom povećavaju poverenje.
• Strategija sadržaja: Nivoi težine zahtevaju ciljano generisanje, a ne nasumično uklanjanje tragova.

Ako želite da iz prve ruke iskusite kombinatornu širinu, isprobajte različite režime i nivoe na Igraj Sudoku onlajn. Ako su vam pravila ili taktike nove, naš vodič Kako igrati Sudoku za početnike ubrzaće vam rešavanje.

Kako istraživači smanjuju duplikate? (Suštinski različit Sudoku)

Izraz „suštinski različit Sudoku“ formalizuje kada se dve završene table smatraju istim obrascem:

• Dozvoljene simetrije: preimenovanje cifara, permutacije redova/kolona unutar pojaseva/stekova, zamena pojaseva/stekova i transponovanje.
• Orbite: Sve table do kojih se može doći ovim simetrijama čine orbitu; brojanje jednog predstavnika po orbiti sprečava prebrojavanje.
• Rezultat: 5,472,730,538 orbita za 9x9. Ovo je čist odgovor na pitanje „koliko ima Sudoku mreža ako zanemarite površinsko označavanje“.

Ova razlika je korisna ako je vaša namera iza pitanja „koliko ima Sudoku zagonetki“ raznolikost osnovnih obrazaca, a ne promene u površinskom označavanju.

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

Polazeći od jedne popunjene mreže, možete da generišete mnogo zagonetki sa jedinstvenim rešenjem izborom različitih skupova tragova:

• Strategije izbora tragova: simetrično raspoređivanje, uklanjanje po pojasevima ili uklanjanje vođeno entropijom.
• Provere jedinstvenosti: rešavač sa povratnim pretraživanjem i ograničenjem broja rešenja obezbeđuje tačno jedno rešenje.
• Minimalnost: Dodatno uklanjajte tragove dok više nijedan ne može da se ukloni bez narušavanja jedinstvenosti (opciono, ali popularno zbog elegancije).

Čak i malo drugačiji redosledi uklanjanja ili različita pravila rešavača daju različite zagonetke sa jedinstvenim rešenjem. Zato je odgovor na „koliko ima Sudoku zagonetki“ daleko veći od odgovora na „koliko ima Sudoku mreža“.

Podaci i citati kojima možete verovati

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

Stručni pogled na praktična ograničenja

„Pitati ‘koliko ima Sudoku zagonetki’ isto je kao pitati koliko melodija može da se napiše sa 12 tonova“, kaže Aleks Čen, vođa sistema za zagonetke u LogicLabu. „Teorijski prostor je konačan, ali toliko ogroman da je za ljudsku upotrebu praktično neograničen — naročito kada filtrirate po jedinstvenosti i težini.“

Povezani pojmovi i terminologija koje treba znati

• Latin square i ortogonalnost
• Struktura pojaseva i stekova u 9x9 Sudokuu
• Ideje orbit–stabilizator iz teorije grupa
• Minimalne zagonetke naspram zagonetki sa više rešenja
• Nivoi logike za ljudsko rešavanje (jednostavna polja, parovi, riblje šeme, bojenje)

Razumevanje ovih pojmova pomaže vam da pravilno tumačite tvrdnje iza pitanja „koliko ima Sudoku zagonetki“, naročito kada izvori mešaju rešenje mreže i zagonetke sa tragovima.

Ključni zaključci

• Postoji 6.67×10^21 popunjenih 9x9 Sudoku rešenje mreža; 5.47 milijardi je suštinski različito pod simetrijom.
• Tačan broj važećih 9x9 Sudoku zagonetki sa jedinstvenim rešenjem nije poznat, ali je daleko veći od broja rešenih mreža.
• Svaka važeća 9x9 zagonetka mora imati najmanje 17 tragova; zagonetke sa 16 tragova ne postoje.
• Za igrače i platforme, praktična ponuda novih, jedinstvenih Sudoku zagonetki je praktično neiscrpna.
• Razlikujte „koliko ima Sudoku mreža“ (rešenja) i „koliko ima Sudoku zagonetki“ (skupovi tragova sa jedinstvenim rešenjem) da biste pravilno tumačili brojeve.