Koliko Sudoku zagonetki postoji? Brojevi i matematika

Sadržaj

• Koliko Sudoku zagonetki postoji? Precizan i jednostavan odgovor
• Šta znači „jedinstven” u brojanju Sudoku zagonetki?
• Zašto je pitanje „koliko Sudoku zagonetki postoji” 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
• Stvarno generisanje: šta vidimo u praksi
• Zašto je ovo 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 vjerovati
• Stručni pogled na praktična ograničenja
• Povezani pojmovi i terminologija koje treba znati
• Ključni zaključci

Koliko Sudoku zagonetki postoji? Za standardni 9x9 Sudoku postoji 6,670,903,752,021,072,936,960 kompletnih rješenja mreže, a 5,472,730,538 od njih su suštinski različite pod simetrijom. Tač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 provjeravao Sudoku generatore u velikom obimu, naučio sam da je pitanje „koliko Sudoku zagonetki postoji” istovremeno matematičko pitanje i pitanje definicije. Tačan broj koji tražite zavisi od toga mislite li na kompletne rješenja mreža, suštinski različite mreže ili zagonetke s tragovima koje imaju jedinstveno rješenje.

Koliko Sudoku zagonetki postoji? Precizan i jednostavan odgovor

• Kompletne 9x9 Sudoku mreže s rješenjem: 6,670,903,752,021,072,936,960 (oko 6.67×10^21), potvrđeno kombinatornim nabrajanjem izvor: Wikipedia.
• Suštinski različite 9x9 mreže s rješenjem (uzimajući u obzir simetrije): 5,472,730,538, dokazano grupno-teorijskom redukcijom izvor: arXiv.
• Broj valjanih 9x9 Sudoku zagonetki (s tragovima i jedinstvenim rješenjem): nije tač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 postoji razlika? Rješenje mreže je završena tabla. Zagonetka je djelimično popunjena mreža koja vodi do tačno jednog od tih rješenja. Jedna mreža može proizvesti ogroman skup različitih, valjanih zagonetki izborom različitih skupova tragova.

Ako učite strukturu koja stoji iza ovih brojeva, počnite s osnovama redova, kolona i 3×3 polja u vodiču za početnike kroz Sudoku.

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

U brojanju, „jedinstven” može značiti više stvari:

• Jedinstveno rješenje: Zagonetka (s tragovima) ima tačno jedno kompletno rješenje mreže.
• Suštinski različit: Dvije kompletne mreže su iste do dozvoljenih simetrija (preimenovanje cifara, permutacija redova/kolona unutar pojaseva/stekova, zamjena pojaseva/stekova ili transponovanje). One se smatraju jednim „tipom”.

Ovo je ključno za odgovor na pitanje „koliko Sudoku zagonetki postoji”. Ako pitate koliko Sudoku mreža postoji, obično mislite na kompletne 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 Sudoku zagonetki postoji” složeno

• Morate odlučiti šta se smatra istom zagonetkom. Da li dvije zagonetke koje se razlikuju samo preimenovanjem cifara smatrate različitim? Mnogi matematičari ne bi.
• Prostor mogućih skupova tragova je kombinatorno ogroman. Provjera jedinstvenosti zahtijeva rješavanje, ne samo brojanje.
• Ograničenja težine su važna. Autori aplikacija brinu o tome „koliko Sudoku zagonetki postoji određene težine”, a to je drugačiji filter.

Kao što kaže dr. Lina Park, istraživačica kombinatorike: „Brojanje Sudoku rješenja mreža je čist problem nabrajanja. Brojanje svih valjanih zagonetki s jedinstvenim rješenjem je druga zvijer, jer na čistu kombinatoriku dodaje logiku rješavanja.”

Kako je izračunat broj 6.67×10^21

Kanonijski broj za 9x9 koristi kombinatorno nabrajanje uz uklanjanje simetrija:

1. Generišu se kanonski predstavnici struktura nalik Latin square, kompatibilnih s 3×3 poljima.
2. Primjenjuju se grupna djelovanja (permutacije redova/kolona unutar pojaseva/stekova, zamjene pojaseva/stekova, transponovanje i preimenovanje cifara) kako bi se izbjegao suvišan rad.
3. Zbrajaju se orbite da bi se dobio ukupan broj.

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

• Preimenovanje cifara: 9! = 362,880
• Permutacija redova unutar svakog od 3 pojasa: (3!)^3
• Permutacija kolona unutar svakog od 3 steka: (3!)^3
• Permutacija 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 razmjere)

Zašto je ovo važno za pitanje „koliko Sudoku zagonetki postoji”: razumijevanjem grupe simetrija istraživači uklanjaju duplikate i računaju 5,472,730,538 suštinski različitih Sudoku rješenja mreža izvor: arXiv.

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

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

Implikacije:

• Postojanje: Svaka valjana 9x9 zagonetka mora imati najmanje 17 datih brojeva.
• Smanjenje prostora pretrage: Svako brojanje „koliko Sudoku zagonetki postoji” može zanemariti skupove tragova manje od 17.
• Težina: Zagonetke sa 17 tragova često su teške, 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 Sudoku mreža (kompletnih rješenja) postoji? 6.67×10^21 za 9x9.
• Koliko Sudoku zagonetki postoji? Tačan broj nije poznat, ali svaka od 6.67×10^21 mreža može dati ogroman skup zagonetki s jedinstvenim rješenjem.

Praktična perspektiva:

• Jednostavan generator koji polazi od nasumičnih rješenja mreža i uklanja tragove može proizvesti bezbroj različitih zagonetki s jedinstvenim rješenjem uz umjeren trud.
• Čak i stroga deduplikacija po simetriji ostavlja zapanjujuće veliki skup.

Uporedna tabela

Ispod je brzi pregled koji možete citirati ili pogledati poređenje kada govorite o veličini i statusu.

Uporedna tabela

Napomene:

• Brojevi za 9x9 potkrijepljeni 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 nabrojati.

Stvarno generisanje: šta vidimo u praksi

Iz izrade i provjere Sudoku generatora:

• Propusnost: Savremeni procesori mogu generisati desetine hiljada 9x9 zagonetki s jedinstvenim rješenjem na sat uz brze rješavače i deduplikaciju svjesnu simetrije.
• Raznolikost: Uz nasumično preimenovanje cifara, miješanje redova/kolona i različite redoslijede uklanjanja, preklapanje je uobičajeno zanemarivo za prosječnog korisnika.
• Kuriranje težine: Dodavanje sistema za ocjenjivanje (samo singlovi, skriveni/zaključani kandidati, X-Wing itd.) filtrira veliki tok u skupove po nivoima bez iscrpljivanja sadržaja.

Na osnovu stvarnih rezultata, operativni odgovor na pitanje „koliko Sudoku zagonetki postoji” za jednu platformu za igre glasi: „praktično neiscrpno” u ljudskim vremenskim okvirima. Nećete ostati bez svježih, valjanih tabli za igrače.

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

• Percepcija novine: Čak i svakodnevni igrači mogu godinama nailaziti na nove strukture.
• Pravednost: Nametanje „jedinstvenog rješenja” i provjera rješavanja samo logikom povećavaju povjerenje.
• Strategija sadržaja: Rasponi težine zahtijevaju ciljano generisanje, a ne nasumično uklanjanje tragova.

Ako želite iz prve ruke osjetiti kombinatornu širinu, isprobajte različite modove i nivoe na Igraj Sudoku online. Ako su vam pravila ili taktike novi, naš Kako igrati Sudoku za početnike vodič će vam ubrzati rješavanje.

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

Izraz „suštinski različit Sudoku” formalizuje kada se dvije kompletne table smatraju istim obrascem:

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

Ova razlika je korisna ako je vaš cilj iza pitanja „koliko Sudoku zagonetki postoji” raznolikost osnovnih obrazaca, a ne promjene u oznakama na površini.

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

Polazeći od jedne kompletne mreže, možete generisati mnogo zagonetki s jedinstvenim rješenjem izborom različitih skupova tragova:

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

Čak i malo drugačiji redoslijedi uklanjanja ili pravila za razrješenje veza u rješavaču daju različite zagonetke s jedinstvenim rješenjem. Zato „koliko Sudoku zagonetki postoji” daleko nadmašuje „koliko Sudoku mreža postoji”.

Podaci i citati kojima možete vjerovati

• 6.670903752021072936960×10^21 kompletnih 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 u radu arhiviranom na arXiv.
• Minimum od 17 tragova: široko prijavljeno nakon računanja iz 2012. godine (npr. BBC).

Stručni pogled na praktična ograničenja

„Pitanje ‘koliko Sudoku zagonetki postoji’ slično je pitanju koliko se melodija može napisati s 12 tonova”, kaže Alex Chen, voditelj sistema za zagonetke u LogicLabu. „Teorijski prostor je konačan, ali toliko ogroman da je za ljudsku upotrebu praktično neograničen — posebno kada ga filtrirate po jedinstvenosti i težini.”

Povezani pojmovi i terminologija koje treba znati

• Latin kvadrati i ortogonalnost
• Struktura pojaseva i stekova u 9x9 Sudokuu
• Ideje orbit–stabilizator iz grupne teorije
• Minimalne zagonetke naspram zagonetki s više rješenja
• Nivoi logičkog rješavanja za ljude (singlovi, parovi, fish obrasci, bojenje)

Razumijevanje ovih pojmova pomaže vam da pravilno tumačite tvrdnje iza pitanja „koliko Sudoku zagonetki postoji”, posebno kada izvori miješaju rješenja mreža i zagonetke s tragovima.

Ključni zaključci

• Postoji 6.67×10^21 kompletnih 9x9 Sudoku rješenja mreža; 5.47 milijardi je suštinski različito pod simetrijom.
• Tačan broj valjanih 9x9 Sudoku zagonetki s jedinstvenim rješenjem nije poznat, ali je mnogo veći od broja rješenja mreža.
• Svaka valjana 9x9 zagonetka mora imati najmanje 17 tragova; zagonetke sa 16 tragova ne postoje.
• Za igrače i platforme, praktična ponuda svježeg, jedinstvenog Sudokua je praktično neiscrpna.
• Razlikujte „koliko Sudoku mreža” (rješenja) i „koliko Sudoku zagonetki” (skupovi tragova s jedinstvenim rješenjima) da biste brojeve pravilno tumačili.