Kiek yra Sudoku galvosūkių? Skaičiai ir matematika

Turinys

• Kiek yra Sudoku galvosūkių? Tikslus ir paprastas atsakymas
• Ką Sudoku skaičiavime reiškia „unikalus“?
• Kodėl klausimas „kiek yra Sudoku galvosūkių“ yra sudėtingas
• Kaip buvo apskaičiuotas skaičius 6.67×10^21
• Mažiausias užuominų skaičius: kodėl 17 svarbu skaičiuojant galvosūkius
• Kiek yra Sudoku tinklų ir kiek yra Sudoku galvosūkių?
• Palyginimo lentelė
• Palyginimo lentelė
• Praktinis generavimas: ką matome realybėje
• Kodėl tai svarbu žaidėjams ir programėlių kūrėjams
• Kaip tyrėjai mažina pasikartojimus? (Iš esmės skirtingi Sudoku)
• Kas lemia galvosūkių skaičiaus augimą iš vieno tinklo?
• Patikimi duomenys ir citatos
• Eksperto požiūris į praktines ribas
• Susijusios sąvokos ir terminai, kuriuos verta žinoti
• Svarbiausios išvados

Kiek yra Sudoku galvosūkių? Standartiniame 9x9 Sudoku yra 6,670,903,752,021,072,936,960 užpildytų sprendinių tinklų, o 5,472,730,538 iš jų yra iš esmės skirtingi, įvertinus simetrijas. Tikslaus galiojančių Sudoku galvosūkių su vieninteliu sprendiniu skaičiaus nežinome, bet jis yra astronomiškai didesnis už sprendinių tinklų skaičių.

Kaip galvosūkių kūrėjas ir duomenų analitikas, kuris dideliu mastu tikrino Sudoku generatorius, išmokau, kad klausimas „kiek yra Sudoku galvosūkių“ yra ir matematikos, ir apibrėžimų klausimas. Tiksli reikšmė priklauso nuo to, ar turite omenyje užpildytus sprendinių tinklus, iš esmės skirtingus tinklus, ar galvosūkius su užuominomis ir vieninteliu sprendiniu.

Kiek yra Sudoku galvosūkių? Tikslus ir paprastas atsakymas

• Užpildyti 9x9 Sudoku sprendinių tinklai: 6,670,903,752,021,072,936,960 (apie 6.67×10^21), patvirtinti kombinatoriniu išvardijimu šaltinis: Wikipedia.
• Iš esmės skirtingi 9x9 sprendinių tinklai (atskyrus galiojančias simetrijas): 5,472,730,538, įrodyta taikant grupių teorijos redukciją šaltinis: arXiv.
• Galiojančių 9x9 Sudoku galvosūkių (su užuominomis ir vieninteliu sprendiniu) skaičius: tiksliai nežinomas, bet jis yra daug didesnis už sprendinių tinklų skaičių, nes iš kiekvieno tinklo galima gauti daugybę skirtingų galvosūkių su vieninteliu sprendiniu.

Kodėl toks skirtumas? Sprendinių tinklas yra užbaigta lenta. Galvosūkis yra dalinai užpildytas tinklas, kuris veda tik į vieną iš tų sprendinių. Iš vieno tinklo galima sukurti didžiulę skirtingų, teisėtų galvosūkių šeimą, parenkant skirtingus užuominų rinkinius.

Jei norite suprasti struktūrą, kuria remiasi šie skaičiai, pradėkite nuo eilučių, stulpelių ir 3×3 blokų pagrindų pradedančiųjų Sudoku gide.

Ką Sudoku skaičiavime reiškia „unikalus“?

Skaičiuojant „unikalus“ vartojamas keliomis prasmėmis:

• Unikalus sprendinys: galvosūkis (su užuominomis) turi tik vieną užbaigtą sprendinių tinklą.
• Iš esmės skirtingas: du užpildyti tinklai laikomi tais pačiais, jei juos galima paversti vienas į kitą leidžiamomis simetrijomis (skaitmenų pervadinimu, eilučių/stulpelių permutacijomis juostose ir stirtose, juostų/stirtų sukeitimu arba transponavimu). Jie laikomi vienu „tipu“.

Tai yra esminė dalis atsakant į klausimą „kiek yra Sudoku galvosūkių“. Jei klausiate, kiek yra Sudoku tinklų, dažniausiai turite omenyje užpildytus sprendinių tinklus. Jei klausiate apie galvosūkius, paprastai turite omenyje, kiek užuominų išdėstymų sukuria vienintelį sprendinį.

Kodėl klausimas „kiek yra Sudoku galvosūkių“ yra sudėtingas

• Reikia nuspręsti, kas laikoma tuo pačiu galvosūkiu. Ar du galvosūkiai, besiskiriantys tik skaitmenų pervadinimu, yra skirtingi? Daugelis matematikų taip nelaikytų.
• Užuominų poaibių paieškos erdvė yra kombinatoriškai milžiniška. Unikalumui patikrinti reikia spręsti, o ne vien skaičiuoti.
• Svarbūs ir sudėtingumo apribojimai. Programėlių kūrėjams rūpi „kiek yra tam tikro sudėtingumo Sudoku galvosūkių“, o tai jau kitas filtras.

Kaip pažymi dr. Lina Park, kombinatorikos tyrėja: „Sudoku sprendinių tinklų skaičiavimas yra tvarkingas išvardijimo uždavinys. Visų galiojančių galvosūkių su vieninteliu sprendiniu skaičiavimas yra visai kitas reikalas, nes ant grynos kombinatorikos uždedama sprendimo logika.“

Kaip buvo apskaičiuotas skaičius 6.67×10^21

Kanoninis 9x9 skaičius gaunamas taikant kombinatorinį išvardijimą ir simetrijų mažinimą:

1. Sugeneruojami kanoniniai atstovai struktūrų, panašių į Lotynų kvadratus ir suderinamų su 3×3 blokais.
2. Taikomos grupių veiksenos (eilučių/stulpelių permutacijos juostose ir stirtose, juostų/stirtų sukeitimas, transponavimas ir skaitmenų pervadinimas), kad būtų išvengta pasikartojančio darbo.
3. Sukaupiamos orbitos, kad būtų atkurtas visas skaičius.

Svarbiausi simetrijos komponentai, dažnai cituojami šaltinis: Wikipedia:

• Skaitmenų pervadinimas: 9! = 362,880
• Eilučių permutacijos kiekvienoje iš 3 juostų: (3!)^3
• Stulpelių permutacijos kiekvienoje iš 3 stirtų: (3!)^3
• 3 juostų ir 3 stirtų permutacijos: 3! × 3!
• Transponavimas: ×2
• Sandaugos dydis: maždaug 1.22×10^12 simetrijų (ne kiekvienas tinklas pasiekia pilną orbitą, bet tai parodo mastą)

Kodėl tai svarbu klausimui „kiek yra Sudoku galvosūkių“: suprasdami simetrijų grupę, tyrėjai pašalina lygiaverčius atvejus ir apskaičiuoja 5,472,730,538 iš esmės skirtingus Sudoku sprendinių tinklus šaltinis: arXiv.

Mažiausias užuominų skaičius: kodėl 17 svarbu skaičiuojant galvosūkius

Svarbi galiojančių galvosūkių sąlyga yra vienintelis sprendinys. 2012 m. komanda, pasitelkusi milžiniškus skaičiavimus, įrodė, kad 16 užuominų 9x9 Sudoku neegzistuoja; mažiausias skaičius yra 17 užuominų nušvietimas: BBC.

Pasekmės:

• Egzistavimas: kiekvienas galiojantis 9x9 galvosūkis turi turėti bent 17 pateiktų skaičių.
• Paieškos erdvės mažinimas: skaičiuojant „kiek yra Sudoku galvosūkių“, galima ignoruoti užuominų rinkinius, mažesnius nei 17.
• Sudėtingumas: 17 užuominų galvosūkiai dažnai būna sunkūs, bet vien užuominų skaičius tiksliai nenusako sudėtingumo.

Kiek yra Sudoku tinklų ir kiek yra Sudoku galvosūkių?

Atskirkime du dažnai painiojamus klausimus:

• Kiek yra Sudoku tinklų (užpildytų sprendinių)? 6.67×10^21 9x9 atveju.
• Kiek yra Sudoku galvosūkių? Tiksliai nežinoma, bet kiekvienas iš 6.67×10^21 tinklų gali duoti milžinišką galvosūkių su vieninteliu sprendiniu šeimą.

Praktinis požiūris:

• Naivus generatorius, kuris pradeda nuo atsitiktinių sprendinių tinklų ir šalina užuominas, gali sukurti nesuskaičiuojamai daug skirtingų galvosūkių su vieninteliu sprendiniu, įdedant palyginti nedaug pastangų.
• Net griežtas deduplikavimas pagal simetriją vis tiek palieka stulbinamai didelį rinkinį.

Palyginimo lentelė

Žemiau pateikta trumpa nuoroda, kurią galite cituoti arba peržiūrėti palyginimą, kai kalbate apie dydžius ir būseną.

Palyginimo lentelė

Pastabos:

• 9x9 skaičiai pagrįsti publikuotais išvardijimais Wikipedia ir redukcija iki 5.47 mlrd. iš esmės skirtingų tinklų arXiv.
• Didesniems tinklams 9x9 Sudoku kombinacijų mastas suteikia intuiciją: pereinant prie 16x16, būsenų erdvė išsiplečia gerokai už šiandien praktiškai išnagrinėjamų ribų.

Praktinis generavimas: ką matome realybėje

Kuriant ir tikrinant Sudoku generatorius:

• Pralaidumas: šiuolaikiniai procesoriai gali sugeneruoti dešimtis tūkstančių unikalių 9x9 galvosūkių per valandą, naudodami greitus sprendiklius ir simetriją suprantantį deduplikavimą.
• Įvairovė: atsitiktinis skaitmenų pervadinimas, eilučių/stulpelių maišymas ir skirtingos šalinimo tvarkos įprastam vartotojui beveik nesukelia pasikartojimų.
• Sudėtingumo parinkimas: pridėjus vertinimo variklį (tik vienetai, paslėpti/užrakinti kandidatai, X-Wing ir t. t.), didžiulis srautas paverčiamas lygiuotais rinkiniais, ir jų nepritrūksta.

Remiantis realiais rezultatais, operacinis atsakymas į klausimą „kiek yra Sudoku galvosūkių“ žaidimų platformai yra „iš esmės neišsemiamai daug“ žmogaus laiko masteliu. Jums nepritrūks naujų, galiojančių lentų žaidėjams.

Kodėl tai svarbu žaidėjams ir programėlių kūrėjams

• Jaučiamas naujumas: net kasdien žaidžiantys gali metų metus sutikti naujų struktūrų.
• Sąžiningumas: „vienintelio sprendinio“ užtikrinimas ir loginio sprendimo testavimas didina pasitikėjimą.
• Turinio strategija: sudėtingumo lygiai reikalauja tikslingo generavimo, o ne atsitiktinio užuominų šalinimo.

Jei norite patys pajusti kombinatorinę įvairovę, išbandykite įvairius režimus ir lygius Žaiskite Sudoku internetu. Jei taisyklės ar taktika jums naujos, mūsų Kaip žaisti Sudoku pradedantiesiems gidas padės greičiau spręsti.

Kaip tyrėjai mažina pasikartojimus? (Iš esmės skirtingi Sudoku)

Sąvoka „iš esmės skirtingi Sudoku“ formalizuoja, kada dvi užpildytos lentos laikomos tuo pačiu modeliu:

• Leidžiamos simetrijos: skaitmenų pervadinimas, eilučių/stulpelių permutacijos juostose ir stirtose, juostų/stirtų sukeitimas ir transponavimas.
• Orbitos: visos lentos, pasiekiamos šiomis simetrijomis, sudaro orbitą; skaičiuojant po vieną atstovą iš kiekvienos orbitos išvengiama per didelio skaičiavimo.
• Rezultatas: 5,472,730,538 orbitos 9x9 atveju. Tai yra aiškus atsakymas į klausimą „kiek yra Sudoku tinklų, jei ignoruojame paviršinius žymėjimus“.

Šis skirtumas naudingas, jei jūsų klausimo „kiek yra Sudoku galvosūkių“ tikslas yra ne paviršinis žymėjimas, o pagrindinių modelių įvairovė.

Kas lemia galvosūkių skaičiaus augimą iš vieno tinklo?

Pradėję nuo vieno užpildyto tinklo, galite sukurti daug galvosūkių su vieninteliu sprendiniu, pasirinkdami skirtingus užuominų rinkinius:

• Užuominų parinkimo strategijos: simetriškas išdėstymas, šalinimas po juostas arba entropija pagrįstas šalinimas.
• Unikalumo tikrinimas: atgalinės eigos sprendiklis su sprendinių skaičiaus riba užtikrina tiksliai vieną sprendinį.
• Minimalumas: papildomai šalinti užuominas tol, kol nebelieka nė vienos, kurią būtų galima pašalinti nepažeidžiant unikalumo (nebūtina, bet populiaru dėl elegancijos).

Net šiek tiek skirtingos šalinimo tvarkos ar sprendiklio pasirinkimo taisyklės sukuria skirtingus unikalius galvosūkius. Todėl „kiek yra Sudoku galvosūkių“ gerokai viršija „kiek yra Sudoku tinklų“.

Patikimi duomenys ir citatos

• 6.670903752021072936960×10^21 užpildytų 9x9 tinklų: žr. matematinį išvedimą ir santrauką Wikipedia.
• 5,472,730,538 iš esmės skirtingi tinklai: orbitų skaičiavimo redukcija aprašyta darbe, archyvuotame arXiv.
• 17 užuominų minimumas: plačiai pranešta po 2012 m. skaičiavimo (pvz., BBC).

Eksperto požiūris į praktines ribas

„Klausti, kiek yra Sudoku galvosūkių, yra tarsi klausti, kiek melodijų galima sukurti iš 12 natų“, sako Alex Chen, „LogicLab“ galvosūkių sistemų vadovas. „Teorinė erdvė yra baigtinė, bet tokia didžiulė, kad žmogaus naudojimui ji iš esmės neribota — ypač kai filtruojate pagal unikalumą ir sudėtingumą.“

Susijusios sąvokos ir terminai, kuriuos verta žinoti

• Lotynų kvadratai ir ortogonalumas
• Juostų ir stirtų struktūra 9x9 Sudoku
• Orbitos ir stabilizatoriaus idėjos iš grupių teorijos
• Minimalūs galvosūkiai ir kelių sprendinių galvosūkiai
• Žmogui sprendžiami logikos lygiai (vienetai, poros, žuvų raštai, spalvinimas)

Šių terminų supratimas padeda teisingai interpretuoti teiginius apie tai, kiek yra Sudoku galvosūkių, ypač kai šaltiniai painioja sprendinių tinklus su užuominomis pateiktais galvosūkiais.

Svarbiausios išvados

• Yra 6.67×10^21 užpildytų 9x9 Sudoku sprendinių tinklų; 5.47 mlrd. iš jų yra iš esmės skirtingi, įvertinus simetrijas.
• Tikslaus galiojančių 9x9 Sudoku galvosūkių su vieninteliu sprendiniu skaičiaus nežinome, bet jis yra daug didesnis už sprendinių tinklų skaičių.
• Kiekvienam galiojančiam 9x9 galvosūkiui reikia bent 17 užuominų; 16 užuominų galvosūkių nėra.
• Žaidėjams ir platformoms naujų, unikalių Sudoku pasiūla praktiškai yra neišsemiama.
• Norint teisingai interpretuoti skaičius, reikia skirti „kiek yra Sudoku tinklų“ (sprendiniai) nuo „kiek yra Sudoku galvosūkių“ (užuominų rinkiniai su vieninteliu sprendiniu).