Mitu Sudoku mõistatust on? Arvud ja matemaatika

Sisukord

• Mitu Sudoku mõistatust on? Täpne ja lihtne vastus
• Mida tähendab Sudoku loendamisel „unikaalne“?
• Miks on küsimus „mitu Sudoku mõistatust on“ keeruline?
• Kuidas arvutati number 6.67×10^21
• Miinimumvihjed: miks 17 on mõistatuste loendamisel oluline
• Mitu on Sudoku ruudustikke vs mitu on Sudoku mõistatusi?
• Võrdlustabel
• Võrdlustabel
• Praktiline genereerimine: mida näeme päriselus
• Miks see on oluline mängijatele ja rakenduste loojatele
• Kuidas teadlased duplikaate vähendavad? (Sisuliselt erinevad Sudoku)
• Mis määrab mõistatuste arvu kasvu ühest ruudustikust?
• Usaldusväärsed andmepunktid ja viited
• Ekspertvaade praktilistele piiridele
• Seotud mõisted ja terminid, mida tasub teada
• Peamised järeldused

Mitu Sudoku mõistatust on? Tavalise 9x9 Sudoku puhul on 6,670,903,752,021,072,936,960 täidetud lahendusruudustikku ning neist 5,472,730,538 on sümmeetria mõttes sisuliselt erinevad. Kehtivate, ainulahendusega Sudoku mõistatuste täpset arvu ei teata, kuid see on lahendusruudustike arvust astronoomiliselt suurem.

Mõistatuste looja ja andmeanalüütikuna, kes on suurel skaalal Sudoku generaatorid üle vaadanud, olen õppinud, et küsimus „mitu Sudoku mõistatust on“ on ühtaegu nii matemaatika- kui ka definitsiooniküsimus. Täpne arv sõltub sellest, kas pead silmas täidetud lahendusruudustikke, sisuliselt erinevaid ruudustikke või vihjetega mõistatusi, millel on ainulahendus.

Mitu Sudoku mõistatust on? Täpne ja lihtne vastus

• Täidetud 9x9 Sudoku lahendusruudustikud: 6,670,903,752,021,072,936,960 (umbes 6.67×10^21), kinnitatud kombinatoorse loendamisega allikas: Wikipedia.
• Sisuliselt erinevad 9x9 lahendusruudustikud (kehtiva sümmeetria arvestamisel): 5,472,730,538, tõestatud rühmateoreetilise vähenduse abil allikas: arXiv.
• Kehtivate 9x9 Sudoku mõistatuste arv (vihjetega ja ainulahendusega): täpselt teadmata, kuid palju suurem kui lahendusruudustike arv, sest ühest ruudustikust saab tuletada väga palju erinevaid ainulahendusega mõistatusi.

Miks see vahe? Lahendusruudustik on valmis laud. Mõistatus on osaliselt täidetud ruudustik, mis viib täpselt ühe sellise lahenduseni. Ühest ruudustikust saab valida erinevaid vihjekogumeid ja nii luua tohutu hulga eristuvaid, kuid kehtivaid mõistatusi.

Kui õpid nende arvude taga olevat struktuuri, alusta ridade, veergude ja 3×3 plokkide põhitõdedest algaja Sudoku juhendis.

Mida tähendab Sudoku loendamisel „unikaalne“?

Loendamisel on sõnal „unikaalne“ mitu tähendust:

• Ainulahendus: mõistatusel (koos vihjetega) on täpselt üks täidetud lahendusruudustik.
• Sisuliselt erinev: kaks täidetud ruudustikku on samad kuni lubatud sümmeetriateni (numbrite ümbernimetamine, ridade/veergude permutatsioon ribade või virnade sees, ribade/virnade vahetamine või transpositsioon). Neid käsitletakse ühe „tüübina“.

See on keskne, kui vastata küsimusele „mitu Sudoku mõistatust on“. Kui küsid, mitu Sudoku ruudustikku eksisteerib, pead sageli silmas täidetud lahendusruudustikke. Kui küsid mõistatuste kohta, mõtled tavaliselt, kui palju vihjemustreid annab ainulahenduse.

Miks on küsimus „mitu Sudoku mõistatust on“ keeruline?

• Tuleb otsustada, mis loetakse samaks mõistatuseks. Kas kaks mõistatust, mis erinevad ainult numbrite ümbernimetamise poolest, on erinevad? Paljud matemaatikud ei käsitleks neid eraldi.
• Vihjekogumite otsinguruum kasvab kombinatoorselt meeletult. Ainulahenduse kontrollimiseks tuleb lahendada, mitte lihtsalt loendada.
• Raskusastme piirangud on olulised. Rakenduste loojad hoolivad küsimusest „mitu Sudoku mõistatust on kindla raskusastmega“, mis on hoopis teine filter.

Nagu märgib dr Lina Park, kombinatoorika uurija: „Sudoku lahendusruudustike loendamine on puhas loendusülesanne. Kõigi kehtivate ainulahendusega mõistatuste loendamine on hoopis teine loom, sest see lisab puhtale kombinatoorikale lahendamisloogika.“

Kuidas arvutati number 6.67×10^21

9x9 standardarv kasutab kombinatoorset loendamist koos sümmeetria kärpimisega:

1. Genereeritakse kanoonilised esindajad 3×3 plokkidega ühilduvatest Latin square’i-laadsetest struktuuridest.
2. Rakendatakse rühmatehteid (ridade/veergude permutatsioonid ribade ja virnade sees, ribade/virnade vahetus, transpositsioon ja numbrite ümbernimetamine), et vältida korduvat tööd.
3. Kogutakse orbiidid, et taastada täielik arv.

Olulised sümmeetriaelemendid, mida sageli tsiteeritakse allikas: Wikipedia:

• Numbrite ümbernimetamine: 9! = 362,880
• Ridade permutatsioon igas kolmest ribast: (3!)^3
• Veergude permutatsioon igas kolmest virnast: (3!)^3
• Kolme riba ja kolme virna vahetamine: 3! × 3!
• Transpositsioon: ×2
• Korrutise suurusjärk: umbes 1.22×10^12 sümmeetriat (mitte iga ruudustik ei anna täpselt sama orbiiti, kuid see näitab mastaapi)

Miks see on oluline küsimuse „mitu Sudoku mõistatust on“ jaoks: sümmeetriarühma mõistmine aitab teadlastel samaväärseid juhtumeid eemaldada ja arvutada 5,472,730,538 sisuliselt erinevat Sudoku lahendusruudustikku allikas: arXiv.

Miinimumvihjed: miks 17 on mõistatuste loendamisel oluline

Üks oluline tingimus kehtivatele mõistatustele on see, et neil peab olema ainulahendus. 2012. aastal tõestas meeskond suure arvutuse abil, et 16 vihjega 9x9 Sudoku’t ei eksisteeri; miinimum on 17 vihjet kajastus: BBC.

Järeldused:

• Olemasolu: igal kehtival 9x9 mõistatusel peab olema vähemalt 17 etteantud arvu.
• Otsinguruumi vähendamine: küsimuse „mitu Sudoku mõistatust on“ puhul võib kõik alla 17 vihjega kogumid kõrvale jätta.
• Raskus: 17-vihjega mõistatused kipuvad olema raskemad, kuid vihjete arv üksi ei ennusta raskust täiuslikult.

Mitu on Sudoku ruudustikke vs mitu on Sudoku mõistatusi?

Eraldame kaks küsimust, mida sageli segamini aetakse:

• Mitu Sudoku ruudustikku (täidetud lahendust) on? 9x9 puhul 6.67×10^21.
• Mitu Sudoku mõistatust on? Täpselt teadmata, kuid iga 6.67×10^21 ruudustik võib anda tohutu hulga ainulahendusega mõistatusi.

Praktiline vaade:

• Naivne generaator, mis alustab juhuslikest lahendusruudustikest ja eemaldab vihjeid, suudab luua lugematul hulgal erinevaid ainulahendusega mõistatusi üsna väikese pingutusega.
• Isegi range sümmeetriapõhine deduplikatsioon jätab alles jahmatavalt suure hulga.

Võrdlustabel

Allpool on kiire ülevaade, mida saad tsiteerida või võrdlust vaadata, kui räägid suurusest ja staatusest.

Võrdlustabel

Märkused:

• 9x9 arvud põhinevad avaldatud loendustel Wikipedia ja vähendusel 5.47 miljardi sisuliselt erineva ruudustikuni arXiv.
• Suuremate ruudustike puhul annab 9x9 Sudoku kombinatsioonide arv aimu: 16x16 peale liikumine paisutab olekuruumi tänapäeval täielikust loendamisest palju kaugemale.

Praktiline genereerimine: mida näeme päriselus

Sudoku generaatorite loomise ja auditeerimise kogemusest:

• Läbilase: tänapäevased protsessorid suudavad kiirete lahendajate ja sümmeetriateadliku deduplikatsiooniga genereerida kümneid tuhandeid ainulahendusega 9x9 mõistatusi tunnis.
• Mitmekesisus: juhusliku numbrite ümbernimetamise, ridade/veergude segamise ja erinevate eemaldusjärjestuste korral on kattuvus tavakasutuses tühine.
• Raskusastme kureerimine: hindamismootori lisamine (ainult üksikud, peidetud/lukustatud kandidaadid, X-Wing jne) filtreerib voolu tasemete kaupa, ilma et mõistatused otsa saaksid.

Päriseluliste tulemuste põhjal on operatiivne vastus küsimusele „mitu Sudoku mõistatust on“ mänguplatvormi jaoks „praktiliselt ammendamatu“ inimaja skaalal. Mängijatele ei saa värsked, kehtivad ruudustikud otsa.

Miks see on oluline mängijatele ja rakenduste loojatele

• Tajutav uudsus: isegi igapäevased mängijad võivad aastaid kohata uusi struktuure.
• Õiglus: „ainulahenduse“ jõustamine ja loogikapõhise lahenduse kontroll suurendab usaldust.
• Sisu strateegia: raskusastme vahemikud vajavad sihipärast genereerimist, mitte juhuslikku vihjete eemaldamist.

Kui tahad kogeda kombinatoorset mitmekesisust ise, proovi erinevaid režiime ja tasemeid lehel Mängi Sudoku’t veebis. Kui reeglid või võtted on sulle uued, aitab meie Kuidas Sudoku’t algajale mängida juhend lahendamist kiiremini selgeks saada.

Kuidas teadlased duplikaate vähendavad? (Sisuliselt erinevad Sudoku)

Väljend „sisuliselt erinevad Sudoku“ formaliseerib, millal kahte täidetud lauda käsitletakse sama mustrina:

• Lubatud sümmeetriad: numbrite ümbernimetamine, ridade/veergude permutatsioonid ribade/virnade sees, ribade/virnade vahetamine ja transpositsioon.
• Orbiidid: kõik nende sümmeetriatega saavutatavad lauad moodustavad orbiidi; ühe esindaja loendamine orbiidi kohta väldib topeltarvestust.
• Tulemus: 5,472,730,538 orbiiti 9x9 puhul. See on puhas vastus küsimusele „mitu Sudoku ruudustikku on, kui eirata pealispindset märgistust“.

See eristus on kasulik, kui sinu küsimuse „mitu Sudoku mõistatust on“ tegelik eesmärk on aluseks olevate mustrite mitmekesisus, mitte ainult pealispinna märgistuse muutused.

Mis määrab mõistatuste arvu kasvu ühest ruudustikust?

Ühest täidetud ruudustikust saab luua palju ainulahendusega mõistatusi, valides erinevaid vihjekogumeid:

• Vihjete valimise strateegiad: sümmeetriline paigutus, riba kaupa eemaldamine või entroopial põhinev eemaldus.
• Ainulahenduse kontroll: tagasijälitusega lahendaja koos lahenduste arvu piiranguga tagab täpselt ühe lahenduse.
• Miinimumsus: eemaldatakse veel vihjeid, kuni rohkem ei saa ilma ainulahendust rikkumata (valikuline, kuid esteetiliselt populaarne).

Isegi veidi erinevad eemaldusjärjestused või lahendaja murdepunktid annavad erinevaid ainulahendusega mõistatusi. Sellepärast ületab küsimus „mitu Sudoku mõistatust on“ kaugelt küsimuse „mitu Sudoku ruudustikku on“.

Usaldusväärsed andmepunktid ja viited

• 6.670903752021072936960×10^21 täidetud 9x9 ruudustikku: vaata matemaatilist tuletust ja kokkuvõtet Wikipedia lehelt.
• 5,472,730,538 sisuliselt erinevat ruudustikku: orbiitide loenduse vähendus on kirjeldatud töös, mis on arhiveeritud arXivis.
• 17-vihje miinimum: laialdaselt teatatud pärast 2012. aasta arvutust (nt BBC).

Ekspertvaade praktilistele piiridele

„Küsimus ‘mitu Sudoku mõistatust on’ on nagu küsida, mitu meloodiat saab kirjutada 12 noodiga,“ ütleb Alex Chen, LogicLabi mõistatussüsteemide juht. „Teoreetiline ruum on lõplik, kuid nii tohutu, et inimkasutuses on see sisuliselt piiramatu — eriti kui filtreerida ainulahenduse ja raskusastme järgi.“

Seotud mõisted ja terminid, mida tasub teada

• Latin square’id ja ortogonaalsus
• 9x9 Sudoku riba- ja virnastruktuur
• Orbiit-stabilisaatori ideed rühmateoorias
• Miinimum-mõistatused vs mitme lahendusega mõistatused
• Inimesele lahendatava loogika tasemed (üksikud, paarid, kalamustrid, värvimine)

Nende terminite mõistmine aitab tõlgendada väiteid küsimuse „mitu Sudoku mõistatust on“ kohta, eriti kui allikad ajavad segi lahendusruudustikud ja vihjetega mõistatused.

Peamised järeldused

• 9x9 Sudoku täidetud lahendusruudustikke on 6.67×10^21; 5.47 miljardit neist on sümmeetria mõttes sisuliselt erinevad.
• Kehtivate 9x9 Sudoku mõistatuste täpne arv ainulahendusega on teadmata, kuid see on lahendusruudustike arvust palju suurem.
• Igal kehtival 9x9 mõistatusel peab olema vähemalt 17 vihjet; 16-vihjega mõistatusi ei ole.
• Mängijate ja platvormide jaoks on värske, ainulahendusega Sudoku praktiliselt ammendamatu.
• Arvude õigeks tõlgendamiseks erista „mitu Sudoku ruudustikku“ (lahendused) ja „mitu Sudoku mõistatust“ (ainulahendusega vihjekogumid).