Cik Sudoku uzdevumu ir? Skaits un matemātika

Satura rādītājs

• Cik Sudoku uzdevumu ir? Precīza un vienkārša atbilde
• Ko Sudoku skaitīšanā nozīmē “unikāls”?
• Kāpēc jautājums “cik Sudoku uzdevumu ir” ir sarežģīts
• Kā tika aprēķināts skaitlis 6.67×10^21
• Minimālais pavedienu skaits: kāpēc 17 ir svarīgi
• Cik ir Sudoku režģu un cik ir Sudoku uzdevumu?
• Salīdzinājuma tabula
• Salīdzinājuma tabula
• Prakse reālajā pasaulē: ko redzam ikdienā
• Kāpēc tas ir svarīgi spēlētājiem un lietotņu izstrādātājiem
• Kā pētnieki samazina dublikātus? (Būtiski atšķirīgi Sudoku)
• Kas nosaka uzdevumu skaita pieaugumu no viena režģa?
• Datu punkti un avoti, kuriem var uzticēties
• Eksperta skatījums uz praktiskajām robežām
• Saistītie jēdzieni un termini, kas jāzina
• Galvenie secinājumi

Cik Sudoku uzdevumu ir? Standarta 9x9 Sudoku ir 6,670,903,752,021,072,936,960 pabeigtu risinājuma režģu, un 5,472,730,538 no tiem ir būtiski atšķirīgi, ņemot vērā simetrijas. Precīzs derīgo Sudoku uzdevumu skaits ar viennozīmīgu risinājumu nav zināms, taču tas ir astronomiski lielāks par risinājuma režģu skaitu.

Kā puzļu veidotājs un datu analītiķis, kurš ir auditējis Sudoku ģeneratorus lielā mērogā, esmu sapratis, ka jautājums “cik Sudoku uzdevumu ir” ir gan matemātikas, gan definīciju jautājums. Precīzais skaitlis ir atkarīgs no tā, vai jūs domājat pabeigtus risinājuma režģus, būtiski atšķirīgus režģus vai uzdevumus ar dotajiem pavedieniem un vienu unikālu risinājumu.

Cik Sudoku uzdevumu ir? Precīza un vienkārša atbilde

• Pabeigti 9x9 Sudoku risinājuma režģi: 6,670,903,752,021,072,936,960 (aptuveni 6.67×10^21), pārbaudīti ar kombinatorisku enumerāciju avots: Wikipedia.
• Būtiski atšķirīgi 9x9 risinājuma režģi (ņemot vērā simetrijas): 5,472,730,538, pierādīti, izmantojot grupu teorijas reducēšanu avots: arXiv.
• Derīgo 9x9 Sudoku uzdevumu skaits (ar pavedieniem un vienu unikālu risinājumu): precīzi nav zināms, taču tas ir daudz, daudz lielāks par risinājuma režģu skaitu, jo no viena režģa var iegūt daudz dažādu unikālu uzdevumu.

Kāpēc šī atšķirība ir tik liela? Risinājuma režģis ir pabeigts laukums. Uzdevums ir daļēji aizpildīts režģis, kas ved uz tieši vienu no šiem risinājumiem. No viena režģa var izveidot milzīgu skaitu atšķirīgu, derīgu uzdevumu, izvēloties dažādus pavedienu kopumus.

Ja vēlaties saprast struktūru, uz kuras balstās šie skaitļi, sāciet ar rindām, kolonnām un 3×3 blokiem iesācēju Sudoku ceļvedī.

Ko Sudoku skaitīšanā nozīmē “unikāls”?

Skaitīšanā vārds “unikāls” tiek lietots vairākās nozīmēs:

• Unikāls risinājums: uzdevumam (ar pavedieniem) ir tieši viens pabeigts risinājuma režģis.
• Būtiski atšķirīgs: divi pabeigti režģi tiek uzskatīti par vienādiem, ja tos var pārvērst vienu otrā ar atļautām simetrijām (ciparu pārdēvēšana, rindu/kolonnu permutācijas joslu vai stabu iekšienē, joslu/stabu maiņa vai transponēšana). Šie tiek uzskatīti par vienu “tipu”.

Tas ir centrālais jautājums, atbildot uz “cik Sudoku uzdevumu ir”. Ja jautājat, cik Sudoku režģu pastāv, parasti domājat pabeigtus risinājuma režģus. Ja jautājat par uzdevumiem, parasti interesē, cik pavedienu izkārtojumu dod vienu unikālu risinājumu.

Kāpēc jautājums “cik Sudoku uzdevumu ir” ir sarežģīts

• Jāizlemj, kas tiek uzskatīts par vienu un to pašu uzdevumu. Vai divi uzdevumi, kas atšķiras tikai ar ciparu pārdēvēšanu, ir atšķirīgi? Daudzi matemātiķi tā nedomātu.
• Pavedienu apakškopu meklēšanas telpa ir kombinatoriski milzīga. Unikalitātes pārbaude prasa risināšanu, nevis tikai skaitīšanu.
• Svarīgi ir arī grūtības kritēriji. Lietotņu izstrādātājiem rūp, “cik Sudoku uzdevumu ir noteiktā grūtības līmenī”, un tas ir cits filtrs.

Kā norāda Dr. Lina Park, kombinatorikas pētniece: “Sudoku risinājuma režģu skaitīšana ir tīrs enumerācijas uzdevums. Visu derīgo unikālā risinājuma uzdevumu skaitīšana ir pavisam cita lieta, jo tā uz tīras kombinatorikas virsū uzliek arī risināšanas loģiku.”

Kā tika aprēķināts skaitlis 6.67×10^21

Kanoniskais 9x9 skaits tiek iegūts ar kombinatorisku enumerāciju un simetriju samazināšanu:

1. Ģenerē kanoniskos pārstāvjus struktūrām, kas līdzīgas Latīņu kvadrātiem un ir saderīgas ar 3×3 blokiem.
2. Pielieto grupu darbības (rindu/kolonnu permutācijas joslu un stabu iekšienē, joslu/stabu maiņu, transponēšanu un ciparu pārdēvēšanu), lai izvairītos no lieka darba.
3. Apkopo orbītas, lai atgūtu pilno skaitu.

Bieži minētās galvenās simetrijas sastāvdaļas avots: Wikipedia:

• Ciparu pārdēvēšana: 9! = 362,880
• Rindu permutācijas katrā no 3 joslām: (3!)^3
• Kolonnu permutācijas katrā no 3 stabiem: (3!)^3
• 3 joslu un 3 stabu permutācija: 3! × 3!
• Transponēšana: ×2
• Kopējais mērogs: aptuveni 1.22×10^12 simetriju (ne katram režģim ir pilna orbīta, taču tas parāda mērogu)

Kāpēc tas ir svarīgi, runājot par “cik Sudoku uzdevumu ir”: izprotot simetriju grupu, pētnieki var atfiltrēt ekvivalentus gadījumus un aprēķināt 5,472,730,538 būtiski atšķirīgos Sudoku risinājuma režģus avots: arXiv.

Minimālais pavedienu skaits: kāpēc 17 ir svarīgi

Svarīgs nosacījums derīgiem uzdevumiem ir tas, ka tiem jābūt ar vienu unikālu risinājumu. 2012. gadā komanda, izmantojot milzīgus aprēķinus, pierādīja, ka 9x9 Sudoku ar 16 pavedieniem nepastāv; minimums ir 17 pavedieni ziņots: BBC.

Sekas:

• Eksistence: katram derīgam 9x9 uzdevumam jābūt vismaz 17 dotajiem skaitļiem.
• Meklēšanas telpas samazināšana: jebkurā skaitījumā par “cik Sudoku uzdevumu ir” var ignorēt pavedienu kopas, kas ir mazākas par 17.
• Grūtība: 17 pavedienu uzdevumi bieži ir grūtāki, taču pavedienu skaits viens pats ne vienmēr precīzi prognozē grūtību.

Cik ir Sudoku režģu un cik ir Sudoku uzdevumu?

Atdalīsim divus jautājumus, kurus cilvēki bieži sajauc:

• Cik ir Sudoku režģu (pabeigtu risinājumu)? 6.67×10^21 9x9 gadījumā.
• Cik ir Sudoku uzdevumu? Precīzi nav zināms, taču katrs no 6.67×10^21 režģiem var radīt milzīgu unikālu uzdevumu kopu ar vienu risinājumu.

Praktiskais skatījums:

• Naivs ģenerators, kas sāk ar nejaušiem risinājuma režģiem un pēc tam noņem pavedienus, var radīt neskaitāmi daudz atšķirīgu unikālu uzdevumu ar salīdzinoši nelielu piepūli.
• Pat stingra deduplikācija pēc simetrijas joprojām atstāj satriecoši lielu kopu.

Salīdzinājuma tabula

Zemāk ir īsa atsauce, ko varat citēt vai apskatīt salīdzinājumu, runājot par izmēriem un statusu.

Salīdzinājuma tabula

Piezīmes:

• 9x9 skaitļus apstiprina publicētas enumerācijas Wikipedia un reducēšana līdz 5.47 miljardiem būtiski atšķirīgu režģu arXiv.
• Lielākiem režģiem 9x9 Sudoku kombināciju skaits dod tikai intuīciju: pāreja uz 16x16 šodien eksplodē stāvokļu telpu daudz tālāk par praktiski pilnīgu enumerāciju.

Prakse reālajā pasaulē: ko redzam ikdienā

No Sudoku ģeneratoru izstrādes un audita pieredzes:

• Caurlaidība: mūsdienu CPU var ģenerēt desmitiem tūkstošu unikāla risinājuma 9x9 uzdevumu stundā, izmantojot ātrus risinātājus un simetriju apzinātu deduplikāciju.
• Dažādība: ar nejaušu ciparu pārdēvēšanu, rindu/kolonnu sajaukšanu un dažādiem noņemšanas secību variantiem pārklāšanās parastā lietotāju lietojumā ir niecīga.
• Grūtības kurēšana: vērtēšanas dzinējs (tikai vieninieki, slēptie/fiksētie kandidāti, X-Wing u. c.) ļauj atlasīt līmeņotus komplektus, neizsīkstot uzdevumu krājumam.

Balstoties uz reāliem rezultātiem, operatīvā atbilde uz “cik Sudoku uzdevumu ir” spēļu platformai ir “praktiski neizsmeļami” cilvēka laika mērogā. Jums nepietrūks svaigu, derīgu laukumu spēlētājiem.

Kāpēc tas ir svarīgi spēlētājiem un lietotņu izstrādātājiem

• Uztveramā novitāte: pat ikdienas spēlētāji var sastapt jaunus izkārtojumus gadiem ilgi.
• Godīgums: “viena unikāla risinājuma” nodrošināšana un loģikas risinājuma pārbaude vairo uzticību.
• Satura stratēģija: grūtības līmeņi prasa mērķētu ģenerēšanu, nevis nejaušu pavedienu noņemšanu.

Ja vēlaties paši izjust kombinatorisko plašumu, izmēģiniet dažādos režīmus un līmeņus vietnē Spēlēt Sudoku tiešsaistē. Ja noteikumi vai taktikas jums vēl ir jaunas, mūsu Kā spēlēt Sudoku iesācējiem pamācība palīdzēs ātrāk sākt risināt.

Kā pētnieki samazina dublikātus? (Būtiski atšķirīgi Sudoku)

Frāze “būtiski atšķirīgi Sudoku” formalizē to, kad divi pabeigti laukumi tiek uzskatīti par vienu un to pašu modeli:

• Atļautās simetrijas: ciparu pārdēvēšana, rindu/kolonnu permutācijas joslu un stabu iekšienē, joslu/stabu maiņa un transponēšana.
• Orbītas: visi laukumi, ko var sasniegt ar šīm simetrijām, veido vienu orbītu; viena pārstāvja skaitīšana katrai orbītai novērš pārskaitīšanu.
• Rezultāts: 5,472,730,538 orbītas 9x9 gadījumā. Tā ir skaidrā atbilde uz “cik ir Sudoku režģu, ja ignorē virspusēju marķējumu”.

Šī atšķirība ir noderīga, ja jūsu nodoms aiz jautājuma “cik Sudoku uzdevumu ir” ir pamatstruktūru dažādība, nevis virspusējas marķējuma izmaiņas.

Kas nosaka uzdevumu skaita pieaugumu no viena režģa?

Sākot no viena pabeigta režģa, var izveidot daudz unikāla risinājuma uzdevumu, izvēloties dažādas pavedienu kopas:

• Pavedienu izvēles stratēģijas: simetriska izvietošana, joslu pa joslai pieeja vai entropijas vadīta noņemšana.
• Unikalitātes pārbaudes: atpakaļgaitas risinātājs ar risinājumu skaita slieksni nodrošina tieši vienu risinājumu.
• Minimālisms: var turpināt noņemt pavedienus, līdz vairs nav iespējams neko noņemt, nezaudējot unikālo risinājumu (pēc izvēles, bet populāri estētikas dēļ).

Pat nedaudz atšķirīgas noņemšanas secības vai risinātāja izvēles rada atšķirīgus unikālus uzdevumus. Tāpēc “cik Sudoku uzdevumu ir” ir daudz vairāk nekā “cik Sudoku režģu ir”.

Datu punkti un avoti, kuriem var uzticēties

• 6.670903752021072936960×10^21 pabeigtu 9x9 režģu: skatiet matemātisko atvasinājumu un kopsavilkumu Wikipedia.
• 5,472,730,538 būtiski atšķirīgi režģi: orbītu skaita samazināšana aprakstīta darbā, kas arhivēts arXiv.
• 17 pavedienu minimums: plaši ziņots pēc 2012. gada aprēķina (piem., BBC).

Eksperta skatījums uz praktiskajām robežām

“Jautāt ‘cik Sudoku uzdevumu ir’ ir kā jautāt, cik melodiju var uzrakstīt ar 12 notīm,” saka Alex Chen, Puzzle Systems Lead uzņēmumā LogicLab. “Teorētiskā telpa ir galīga, bet tik milzīga, ka cilvēku lietojumam tā ir praktiski neierobežota — īpaši tad, ja filtrē pēc unikāla risinājuma un grūtības.”

Saistītie jēdzieni un termini, kas jāzina

• Latīņu kvadrāti un ortogonalitāte
• Joslu un stabu struktūra 9x9 Sudoku
• Orbītas–stabilizatora idejas no grupu teorijas
• Minimālie uzdevumi pret uzdevumiem ar vairākiem risinājumiem
• Cilvēkam risināmu loģikas līmeņi (vieninieki, pāri, zivju raksti, krāsošana)

Šo terminu izpratne palīdz interpretēt apgalvojumus par to, “cik Sudoku uzdevumu ir”, īpaši tad, ja avoti sajauc risinājuma režģus ar uzdevumiem, kuros ir dotie pavedieni.

Galvenie secinājumi

• Ir 6.67×10^21 pabeigtu 9x9 Sudoku risinājuma režģu; 5.47 miljardi no tiem ir būtiski atšķirīgi, ņemot vērā simetriju.
• Precīzs derīgo 9x9 Sudoku uzdevumu skaits ar vienu unikālu risinājumu nav zināms, taču tas ir daudz lielāks par risinājuma režģu skaitu.
• Katram derīgam 9x9 uzdevumam vajag vismaz 17 pavedienus; 16 pavedienu uzdevumu nav.
• Spēlētājiem un platformām svaigu, unikālu Sudoku piedāvājums praktiski ir neizsmeļams.
• Lai pareizi interpretētu skaitļus, atšķiriet “cik ir Sudoku režģu” (risinājumi) no “cik ir Sudoku uzdevumu” (pavedienu kopas ar unikālu risinājumu).