Gatavs spēlei?

Spēlēt sudoku!

Sudoku matemātika: režģi, doti cipari, unikāli atrisinājumi

4 min lasīšanas

Pastāv 6 670 903 752 021 072 936 960 derīgi pilnībā aizpildīti 9x9 sudoku režģi, aptuveni 6.67 x 10^21. Nevienai mīklai nevar būt mazāk par 17 dotajiem cipariem, lai tai joprojām būtu viens atrisinājums, un labi izveidotai mīklai vienmēr ir tieši viens. Šī lapa sniedz skaitļus, to, kas tos pierādīja, un to, ko mūsu pašu katalogs rāda par dotajiem cipariem un grūtību. Tā der spēlētājiem, kurus interesē skaitļi aiz režģa. (Angliski runājošie meklē „sudoku math“ vai „sudoku maths“.)

Cik sudoku režģu ir?

„Režģis“ šeit nozīmē pilnībā aizpildītu laukumu, kas ievēro rindu, kolonnu un bloku noteikumus. Bertram Felgenhauer un Frazer Jarvis tos saskaitīja rakstā „Enumerating possible Sudoku grids“ (2005) un atrada 6 670 903 752 021 072 936 960.

Daudzi no šiem režģiem ir viens un tas pats laukums pārģērbies. Pārdēvē ciparus (samaini katru 1 ar katru 2), pagriez vai atspoguļo laukumu, vai samaini rindas 3 rindu joslas iekšienē, un iegūsti citādi izskatīgu režģi ar identisku struktūru. Ed Russell un Frazer Jarvis saskaitīja režģus, kas paliek pēc šo simetriju noņemšanas, rakstā „There are 5,472,730,538 essentially different Sudokus“ (2006). Atbilde ir skaitlis nosaukumā: 5 472 730 538.

Cik sudoku mīklu ir?

Vairāk nekā režģu, un neviens nenosauc vienu vienotu skaitli. Mīkla ir režģis ar paslēptiem dažiem cipariem, tāpēc viens režģis dod milzīgu skaitu mīklu. Pareizas mīklas ir tikai tās, kurām joprojām ir tieši viens atrisinājums, un šī pārbaude jāveic katrai mīklai atsevišķi. Spēlei praktiskā atbilde ir „daudz vairāk, nekā kāds spēj atrisināt mūžā“. Mūsu katalogs ir paraugs, nevis visas telpas skaitījums: tajā ir līdz 1 000 mīklu katram līmenim un režīmam, sakārtotas pēc grūtības.

Kāds ir minimālais doto ciparu skaits sudoku?

    1. gadā Gary McGuire, Bastian Tugemann un Gilles Civario pierādīja, ka nevienai mīklai ar 16 dotajiem nav unikāla atrisinājuma, darbā „There is no 16-clue Sudoku: solving the Sudoku minimum number of clues problem“. Viņu meklēšana bija izsmeļoša un prasīja ļoti daudz datora laika, tāpēc jautājums gadiem palika atvērts.

Pirms tam 17 doto mīklas jau bija zināmas. Gordon Royle uzturēja publisku to kolekciju, un neviena ar 16 nekad netika atrasta. Pierādījums slēdza jautājumu: 17 ir grīda.

17 ir matemātiska robeža, nevis spēles standarts. Tik retas mīklas ir retums un galvenokārt interesē pētniekus. Mūsu klasiskajai mīklai ar vismazāk dotajiem cipariem to ir 19, bet tipiskām mīklām ir nedaudz virs 20 (tabula zemāk).

Vai katram sudoku ir unikāls atrisinājums?

Nē. Jebkurš režģis ar izņemtiem cipariem ir „mīkla“ brīvā nozīmē, bet daudziem šādiem laukumiem ir 2 vai vairāki derīgi pabeigumi. Pareizi izveidotam sudoku ir tieši viens, un tā ir standarta konvencija: Nikoli, izdevējs, kas popularizēja mīklu Japānā, to prasīja (skati sudoku vēsturi).

Unikalitāte ir svarīga praktisku iemeslu dēļ. Ja mīklai ir viens atrisinājums, katrs tīras loģikas solis ved uz to, un tev nekad nav jāmin. Ja ir 2, risinātājs var būt pareizs katrā solī un tomēr pabeigt ar „nepareizo“ atbildi.

Kā mēs to pārbaudām: katra šīs vietnes mīkla ir pierādīta ar tieši vienu atrisinājumu, pirms tā tiek publicēta. Risinātājs meklē atrisinājumu, tad meklē otru, un mīkla tiek noraidīta, ja otrs pastāv. Katra mīkla tiek arī vērtēta ar mūsu Sudoku Explainer portu, kas reģistrē grūtāko nepieciešamo loģisko soli. Tā pati unikalitātes pārbaude attiecas uz Killer un 16x16 mīklām.

Vai sudoku ir matemātika?

Klasiskais sudoku neizmanto aritmētiku. Cipari ir tikai 9 dažādi simboli: tos varētu nomainīt pret 9 burtiem vai 9 krāsām, un nekas nemainītos. Risināšana ir loģika, iespēju izslēgšana, tāpēc tā ir tuvāka dedukcijas mīklai nekā summai. Tāpēc 16x16 laukumi pēc 9 var izmantot A līdz G.

Matemātika ir aiz mīklas, nevis tajā: režģu skaitīšana, simetrija un minimālā doto skaita pierādīšana ir kombinatorika un datorizēta meklēšana. 17 doto rezultāts ir trāpījuma kopas (hitting set) problēmas piemērs, kas atrisināta ar izsmeļošu aprēķinu.

Aritmētika parādās variantos. Killer sudoku katras zonas cipariem jāsummējas līdz mērķim, tāpēc tu spried par summām un to, kuras ciparu kombinācijas tās var dot.

Vai mazāk doto cipari padara sudoku grūtāku?

Ne uzticami. Doto skaits norāda, cik daudz tev tiek pateikts, nevis cik dziļa ir loģika. Šeit ir mūsu pašu klasisko 9x9 mīklu doto skaits pa līmeņiem no mūsu kataloga uz 2026. gada 29. septembri:

LīmenisVismazāk dotieVidējiVisvairāk dotie
Viegls3034.536
Vidējs2227.840
Grūts2227.044
Eksperts2124.729
Meistars1924.428
Leģendārs2025.331

Izceļas 2 lietas. Vidējais doto skaits krītas no Viegla līdz Meistaram, bet Leģendārs vidēji ir vairāk doto (25.3) nekā Meistaram (24.4), kaut arī tas ir vērtēts grūtāks. Un Grūtai mīklai var būt 44 doti. Grūtību nosaka grūtākais paņēmiens, ko mīkla piespiež, mērīts Sudoku Explainer skalā, nevis doto skaits. Ko prasa katra josla, skati grūtības līmeņos.

Killer to izceļ vēl asāk. Mūsu Eksperta, Meistara un Leģendārām Killer mīklām vispār nav doto ciparu: atrisinājumu nosaka tikai zonas.

Ja gribi sajust efektu pats, izmēģini Leģendāru mīklu un redzi, cik maz doto tev dod, tad cik daudz loģikas tās joprojām prasa. Grūtākās sudoku mīklas to pavirza vēl tālāk. Jauns noteikumos? Sāc ar to, kā spēlēt sudoku.