Kuinka monta Sudoku-pulmaa on? Laskenta ja matematiikka

Sisällysluettelo

• Kuinka monta Sudoku-pulmaa on? Tarkka ja yksinkertainen vastaus
• Mitä “ainutlaatuinen” tarkoittaa Sudoku-laskennassa?
• Miksi kysymys “kuinka monta Sudoku-pulmaa on” on hankala
• Miten luku 6.67×10^21 laskettiin
• Vähimmäisvihjeet: miksi 17 on tärkeä pulmien laskennassa
• Kuinka monta Sudoku-ruudukkoa vs. kuinka monta Sudoku-pulmaa?
• Vertailutaulukko
• Vertailutaulukko
• Käytännön generointi: mitä näemme oikeassa elämässä
• Miksi tällä on väliä pelaajille ja sovellussuunnittelijoille
• Miten tutkijat vähentävät duplikaatteja? (Olennaisesti erilaiset Sudoku-pulmat)
• Mikä määrää pulmien määrän kasvun yhdestä ruudukosta?
• Luotettavat datapisteet ja lähteet
• Asiantuntijan näkemys käytännön rajoista
• Aiheeseen liittyvät käsitteet ja termit
• Keskeiset huomiot

Kuinka monta Sudoku-pulmaa on? Tavallisessa 9x9 Sudoku:ssa on 6,670,903,752,021,072,936,960 valmista ratkaisuruudukkoa, ja niistä 5,472,730,538 on symmetrioiden suhteen olennaisesti erilaisia. Yksikäsitteisen ratkaisun sisältävien Sudoku-pulmien tarkkaa määrää ei tunneta, mutta se on astronomisesti suurempi kuin ratkaisuruudukkojen määrä.

Pulmasuunnittelijana ja data-analyytikkona, joka on auditoinut Sudoku-generaattoreita laajassa mittakaavassa, olen oppinut, että kysymys “kuinka monta Sudoku-pulmaa on” on sekä matematiikkaa että määritelmiä koskeva kysymys. Tarkka vastaus riippuu siitä, tarkoitatko valmiita ratkaisuruudukkoja, olennaisesti erilaisia ruudukkoja vai vihjeillä annettuja pulmia, joilla on yksikäsitteinen ratkaisu.

Kuinka monta Sudoku-pulmaa on? Tarkka ja yksinkertainen vastaus

• Valmiit 9x9 Sudoku-ratkaisuruudukot: 6,670,903,752,021,072,936,960 (noin 6.67×10^21), vahvistettu kombinatorisella luetteloinnilla lähde: Wikipedia.
• Olennaisesti erilaiset 9x9-ratkaisuruudukot (symmetriat huomioiden): 5,472,730,538, todistettu ryhmäteoreettisen pelkistyksen avulla lähde: arXiv.
• Kelvollisten 9x9 Sudoku-pulmien määrä (vihjeillä ja yksikäsitteisellä ratkaisulla): tarkkaa määrää ei tunneta, mutta se on moninkertaisesti suurempi kuin ratkaisuruudukkojen määrä, koska yhdestä ruudukosta voidaan muodostaa monia erilaisia yksikäsitteisiä pulmia.

Miksi ero on niin suuri? Ratkaisuruudukko on valmis pelilauta. Pulma on osittain täytetty ruudukko, joka johtaa täsmälleen yhteen näistä ratkaisuista. Yhdestä ruudukosta voi syntyä valtava määrä erilaisia, täysin kelvollisia pulmia valitsemalla erilaisia vihjesarjoja.

Jos haluat ymmärtää näiden lukujen taustalla olevan rakenteen, aloita perusteista: riveistä, sarakkeista ja 3×3-ruuduista aloittelijan Sudoku-oppaassa.

Mitä “ainutlaatuinen” tarkoittaa Sudoku-laskennassa?

Laskennassa sana “ainutlaatuinen” voi tarkoittaa eri asioita:

• Yksikäsitteinen ratkaisu: Pulmalla (vihjeineen) on täsmälleen yksi valmis ratkaisuruudukko.
• Olennaisesti erilainen: Kaksi valmista ruudukkoa ovat sama, jos ne eroavat vain sallittujen symmetrioiden kautta (numeroiden uudelleennimeäminen, rivien/sarakkeiden permutointi kaistojen tai pinojen sisällä, kaistojen/pinojen vaihto tai transponointi). Näitä pidetään yhtenä “tyyppinä”.

Tämä on keskeistä, kun vastataan kysymykseen “kuinka monta Sudoku-pulmaa on”. Jos kysyt, kuinka monta Sudoku-ruudukkoa on olemassa, tarkoitat usein valmiita ratkaisuruudukkoja. Jos taas puhut pulmista, tarkoitat yleensä sitä, kuinka monta vihjekuvioita tuottaa yksikäsitteisen ratkaisun.

Miksi kysymys “kuinka monta Sudoku-pulmaa on” on hankala

• On päätettävä, mikä lasketaan samaksi pulmaksi. Lasketaanko kaksi pulmaa, jotka eroavat vain numeroiden uudelleennimeämisessä, eri pulmiksi? Monet matemaatikot eivät laskisi.
• Vihjesubsettien hakutila kasvaa kombinatorisesti räjähdysmäisesti. Yksikäsitteisyyden testaaminen vaatii ratkaisemista, ei pelkkää laskemista.
• Vaikeusasteella on merkitystä. Sovellussuunnittelijoita kiinnostaa, “kuinka monta Sudoku-pulmaa on tietyn vaikeustason mukaisesti”, mikä on eri suodatin.

Kuten tohtori Lina Park, kombinatoriikan tutkija, toteaa: “Sudoku-ratkaisuruudukkojen laskeminen on siisti luettelointitehtävä. Kaikkien kelvollisten yksikäsitteisten pulmien laskeminen on aivan eri eläin, koska siinä yhdistyvät ratkaisulogiikka ja puhdas kombinatoriikka.”

Miten luku 6.67×10^21 laskettiin

9x9-muodon kanoninen määrä perustuu kombinatoriseen luettelointiin ja symmetrioiden karsintaan:

1. Muodostetaan kanoniset edustajat Latin square -tyyppisistä rakenteista, jotka ovat yhteensopivia 3×3-ruutujen kanssa.
2. Sovelletaan ryhmätoimintoja (rivi- ja sarakepermutoinnit kaistojen/pinojen sisällä, kaistojen/pinojen vaihdot, transponointi ja numeroiden uudelleennimeäminen), jotta vältetään turha työ.
3. Kootaan orbiteista koko määrä.

Keskeisiä symmetriakomponentteja, joihin usein viitataan lähde: Wikipedia:

• Numeroiden uudelleennimeäminen: 9! = 362,880
• Rivien permutointi kunkin 3 kaistan sisällä: (3!)^3
• Sarakkeiden permutointi kunkin 3 pinon sisällä: (3!)^3
• Kolmen kaistan ja kolmen pinon permutointi: 3! × 3!
• Transponointi: ×2
• Tulon suuruusluokka: noin 1.22×10^12 symmetriaa (kaikki ruudukot eivät saavuta täyttä orbittia, mutta tämä antaa mittakaavan)

Miksi tällä on väliä kysymyksessä “kuinka monta Sudoku-pulmaa on”: symmetriaryhmän ymmärtäminen auttaa tutkijoita poistamaan ekvivalentit tapaukset ja laskemaan 5,472,730,538 olennaisesti erilaista Sudoku-ratkaisuruudukkoa lähde: arXiv.

Vähimmäisvihjeet: miksi 17 on tärkeä pulmien laskennassa

Keskeinen ehto kelvollisille pulmille on, että niillä on yksikäsitteinen ratkaisu. Vuonna 2012 ryhmä käytti massiivista laskentaa todistaakseen, ettei 9x9 Sudoku-pulmaa ole mahdollista tehdä 16 vihjeellä; vähimmäismäärä on 17 vihjettä uutisointi: BBC.

Vaikutukset:

• Olemassaolo: Jokaisessa kelvollisessa 9x9-pulmassa on oltava vähintään 17 annettua numeroa.
• Hakutilan pienennys: Kaikissa laskelmissa, joissa kysytään “kuinka monta Sudoku-pulmaa on”, voidaan jättää huomiotta alle 17 vihjeen sarjat.
• Vaikeus: 17 vihjeen pulmat ovat usein vaikeita, mutta vihjeiden määrä ei yksin ennusta vaikeutta täydellisesti.

Kuinka monta Sudoku-ruudukkoa vs. kuinka monta Sudoku-pulmaa?

Erotetaan kaksi usein sekoittuvaa kysymystä:

• Kuinka monta Sudoku-ruudukkoa (valmista ratkaisua) on? 6.67×10^21 9x9-muodossa.
• Kuinka monta Sudoku-pulmaa on? Tarkkaa määrää ei tunneta, mutta jokaisesta 6.67×10^21 ruudukosta voidaan muodostaa valtava määrä yksikäsitteisen ratkaisun pulmia.

Käytännön näkökulma:

• Yksinkertainen generaattori, joka aloittaa satunnaisista ratkaisuruudukkoista ja poistaa vihjeitä, tuottaa valtavan määrän erilaisia yksikäsitteisiä pulmia melko vähällä vaivalla.
• Jopa tiukka symmetrioihin perustuva deduplikointi jättää jäljelle häkellyttävän suuren joukon.

Vertailutaulukko

Alla on nopea viite, johon voit viitata tai katsoa vertailun, kun puhutaan koosta ja tilasta.

Vertailutaulukko

Huomautukset:

• 9x9-lukemat perustuvat julkaistuihin luetteloihin Wikipedia ja pelkistykseen 5.47 miljardiin olennaisesti erilaiseen ruudukkoon arXiv.
• Suuremmissa ruuduissa 9x9 Sudoku-yhdistelmien määrä antaa suuntaa: siirtyminen 16x16-muotoon räjäyttää tilan paljon nykyistä täyttä luettelointia suuremmaksi.

Käytännön generointi: mitä näemme oikeassa elämässä

Sudoku-generaattoreita rakentaessa ja auditoidessa:

• Läpäisykyky: Nykyaikaiset prosessorit voivat tuottaa kymmeniä tuhansia yksikäsitteisen ratkaisun 9x9-pulmia tunnissa nopeilla ratkaisijoilla ja symmetriat huomioivalla deduplikoinnilla.
• Monipuolisuus: Satunnainen numeroiden uudelleennimeäminen, rivi- ja sarakevaihdot sekä vaihtelevat poistojärjestykset johtavat tavallisessa kuluttajakäytössä käytännössä olemattomaan päällekkäisyyteen.
• Vaikeustason kuratointi: Arviointimoottorin lisääminen (vain yksinkertaiset, piilotetut/suljetut kandidaatit, X-Wing jne.) suodattaa virran tasoitetuiksi kokonaisuuksiksi ilman että sisältö loppuu kesken.

Käytännön tulosten perusteella operatiivinen vastaus kysymykseen “kuinka monta Sudoku-pulmaa on” pelialustalle on “käytännössä ehtymätön” ihmisen aikaskaalassa. Pelaajilta ei lopu uudet, kelvolliset ruudukot kesken.

Miksi tällä on väliä pelaajille ja sovellussuunnittelijoille

• Koettu uutuus: Jopa päivittäin pelaavat voivat kohdata uusia rakenteita vuosien ajan.
• Reiluus: “Yksikäsitteisen ratkaisun” varmistaminen ja logiikkaratkaisun testaaminen lisäävät luottamusta.
• Sisältöstrategia: Vaikeusluokat vaativat kohdennettua generointia, eivät satunnaista vihjeiden poistoa.

Jos haluat kokea kombinatorisen laajuuden itse, kokeile eri pelitiloja ja tasoja sivustolla Pelaa Sudoku verkossa. Jos säännöt tai taktiikat ovat sinulle uusia, Kuinka pelata Sudoku aloittelijoille -oppaamme auttaa sinut alkuun nopeammin.

Miten tutkijat vähentävät duplikaatteja? (Olennaisesti erilaiset Sudoku-pulmat)

Ilmaus “olennaisesti erilaiset Sudoku-pulmat” määrittelee, milloin kaksi valmista ruudukkoa katsotaan samaksi kuvioksi:

• Sallittuja symmetrioita: numeroiden uudelleennimeäminen, rivien/sarakkeiden permutointi kaistojen/pinojen sisällä, kaistojen/pinojen vaihto ja transponointi.
• Orbitit: Kaikki näillä symmetrioilla saavutettavat ruudukot muodostavat orbittin; yhden edustajan laskeminen orbittia kohti estää ylikertymän.
• Tulos: 5,472,730,538 orbittia 9x9-muodossa. Tämä on siisti vastaus kysymykseen “kuinka monta Sudoku-ruudukkoa on, jos jätetään pinnalliset nimikkeet huomiotta”.

Tämä ero on hyödyllinen, jos tarkoituksesi kysymyksessä “kuinka monta Sudoku-pulmaa on” liittyy taustalla olevien kuvioiden monipuolisuuteen eikä vain pintatason nimeämismuutoksiin.

Mikä määrää pulmien määrän kasvun yhdestä ruudukosta?

Yhdestä valmiista ruudukosta voidaan tuottaa monia yksikäsitteisen ratkaisun pulmia valitsemalla erilaisia vihjesarjoja:

• Vihjeiden valintastrategiat: symmetrinen sijoittelu, kaista kerrallaan tai entropiaan perustuva poisto.
• Yksikäsitteisyystarkistukset: takaisinkytkentään perustuva ratkaisija, jossa ratkaisujen määrä katkaistaan tietyn rajan jälkeen, varmistaa täsmälleen yhden ratkaisun.
• Minimaalisuus: Vihjeitä poistetaan edelleen, kunnes mitään ei voi enää poistaa rikkomatta yksikäsitteisyyttä (valinnainen mutta suosittu eleganssin vuoksi).

Jopa hieman erilaiset poistojärjestykset tai ratkaisijan tasatilanteiden purkamiset tuottavat eri yksikäsitteisiä pulmia. Siksi “kuinka monta Sudoku-pulmaa on” on paljon suurempi luku kuin “kuinka monta Sudoku-ruudukkoa on”.

Luotettavat datapisteet ja lähteet

• 6.670903752021072936960×10^21 valmista 9x9-ruudukkoa: katso matemaattinen johdanto ja yhteenveto Wikipediasta.
• 5,472,730,538 olennaisesti erilaista ruudukkoa: orbittien laskentaan perustuva pelkistys on kuvattu arXivissa arkistoidussa työssä.
• 17 vihjeen vähimmäismäärä: raportoitu laajasti vuoden 2012 laskennan jälkeen (esim. BBC).

Asiantuntijan näkemys käytännön rajoista

“Kysymys ‘kuinka monta Sudoku-pulmaa on’ on kuin kysyisi, kuinka monta melodiaa voidaan kirjoittaa 12 sävelellä,” sanoo Alex Chen, Puzzle Systems Lead LogicLabissa. “Teoreettinen tila on äärellinen mutta niin valtava, että ihmiskäytössä se on käytännössä rajaton — etenkin kun suodatetaan yksikäsitteisyyden ja vaikeustason mukaan.”

Aiheeseen liittyvät käsitteet ja termit

• Latin squaret ja ortogonaalisuus
• 9x9 Sudoku:n kaista- ja pino-rakenne
• Orbit–stabilizer-ajatukset ryhmäteoriasta
• Minimaaliset pulmat vs. moniratkaisu-pulmat
• Ihmisen ratkaistavuuden logiikkatasot (yksinkertaiset, parit, fish-kuviot, väritys)

Näiden termien ymmärtäminen auttaa tulkitsemaan väitteitä siitä, “kuinka monta Sudoku-pulmaa on”, etenkin kun lähteet sekoittavat ratkaisuruudukot ja vihjeillä annetut pulmat.

Keskeiset huomiot

• 9x9 Sudoku-ratkaisuruudukkoja on 6.67×10^21; niistä 5.47 miljardia on symmetrioiden suhteen olennaisesti erilaisia.
• Tarkkaa määrää kelvollisille 9x9 Sudoku-pulmille, joilla on yksikäsitteinen ratkaisu, ei tunneta, mutta se on paljon suurempi kuin ratkaisuruudukkojen määrä.
• Jokaisessa kelvollisessa 9x9-pulmassa on oltava vähintään 17 vihjettä; 16 vihjeen pulmia ei ole olemassa.
• Pelaajille ja alustoille uusien, yksikäsitteisten Sudoku-pulmien tarjonta on käytännössä ehtymätön.
• Erota toisistaan “kuinka monta Sudoku-ruudukkoa” (ratkaisut) ja “kuinka monta Sudoku-pulmaa” (vihjesarjat, joilla on yksikäsitteinen ratkaisu), jotta luvut tulkitaan oikein.