Raidinis Wordoku spausdinimui A4 / PDF (Galvosūkiai su raidėmis)

Begalinio Sudoku iliuzija: kodėl dauguma generatorių internete yra apgavystė

Užsukite į bet kurį oro uosto spaudos kioską ar prekybos centrą ir lentynose pamatysite aštuonis eurus kainuojančias minkštais viršeliais knygutes, kuriose ant pigaus gelsvo popieriaus atspausdinti seni, dešimtis kartų perspausdinti galvosūkiai. Dar blogiau internete: devyniasdešimt procentų nemokamų „Sudoku generatorių“ tėra pigi klastotė. Jie serveryje laiko dvidešimt paruoštų PDF failų iš 2008 metų ir tiesiog maišo puslapių numerius, arba aklai trina skaičius iš tinklelio, net netikrindami, ar gautas rezultatas apskritai turi logišką sprendimą.

Kiekvienas patyręs žaidėjas yra patyręs didžiausią Sudoku tragediją: praleidi keturiasdešimt penkias minutes preciziškai analizuodamas langelius, kol prieini aklavietę – 2×2 bloką, kuriame du skaičiai tinka į abi vietas vienodai teisingai. Tai nėra loginis iššūkis – tai brokuota matematinė klaida. Mūsų generatorius naršyklėje vykdo tikrą procedūrinį atgalinio sekimo (Backtracking) algoritmą su unikalumo garantija: kiekvienas sugeneruotas galvosūkis turi griežtai vieną ir tik vieną teisingą sprendinį.

Sudoku kombinatorika ir 17 skaičių minimumas: nuo Eulerio iki superkompiuterių

Matematiniu požiūriu Sudoku yra specialus apribotas Lotyniškųjų kvadratų (Latin Squares) atvejis, kurį dar 1783 metais sistemingai ištyrė šveicarų matematikas Leonhardas Euleris. Šiuolaikinį Sudoku XX a. pabaigoje Japonijoje išpopuliarino Maki Kaji (leidykla „Nikoli“) su filosofiniu šūkiu „Sūji wa dokushin ni kagiru“ („skaičiai turi likti vieniši“), pridėdamas nesikertančių 3×3 blokų taisyklę.

Klasikinio 9×9 tinklelio galimų sprendinių kombinatorinė erdvė yra sunkiai suvokiama. 2005 m. matematikai Felgenhaueris ir Jarvis apskaičiavo tikslų teisingai išspręstų tinklelių skaičių:

N = 6,670,903,752,021,072,936,960 ≈ 6.67 × 10²¹

Atmetus rotacines simetrijas, veidrodinius atspindžius ir skaitmenų perkeitimus, lieka 5,472,730,538 iš esmės skirtingi galvosūkiai. Negana to, 2012 m. matematikas Gary McGuire Dublino universitete panaudojo 7.1 milijono procesoriaus valandų „Blue Gene“ superkompiuteryje, kad įrodytų dešimtmečio teoremą: joks teisingas Sudoku negali turėti mažiau nei 17 atverstų skaičių. Turint 16 ar mažiau skaičių, galvosūkis matematiškai garantuotai turi mažiausiai du konkuruojančius sprendimus.

Kaip veikia mūsų algoritminis generatorius be jokių šablonų

Paspaudus mygtuką „Generuoti naujus“, mūsų variklis nesikreipia į jokią serverio duomenų bazę. Jis sukuria naują galvosūkį iš grynos matematikos per mažiau nei 30 milisekundžių, pasitelkdamas trijų etapų konvejerį:

• 1 etapas – Įstrižainių atsitiktinis užpildymas: Trys nepriklausomi 3×3 įstrižiniai blokai (viršuje kairėje, centre, apačioje dešinėje) užpildomi atsitiktinėmis skaitmenų 1–9 permutacijomis. Kadangi jie nesidalina eilutėmis ar stulpeliais, juos galima inicializuoti be jokių konfliktų tikrinimo.
• 2 etapas – Rekursyvus Backtracking užpildymas: Atsitiktinės tvarkos sprendėjas užpildo likusius 54 langelius, akimirksniu sukonstruodamas tobulą 81 langelio Lotyniškąjį kvadratą.
• 3 etapas – Simetrinis skaičių šalinimas su unikalumo įrodymu: Algoritmas trina skaičių poras taikydamas 180° rotacinę simetriją (kad lapas atrodytų estetiškai subalansuotas). Po kiekvieno skaičiaus ištrynimo išsamus šakų ir rėžių tikrintuvas patikrina, ar tinklelis vis dar turi lygiai vieną sprendimą. Jei atsiranda antras sprendimo kelias – skaičius akimirksniu grąžinamas atgal.

Tikras žmogaus mąstymo sunkumas: daugiau nei atverstų skaičių kiekis

Pigiose galvosūkių knygutėse sunkumas matuojamas tik skaičių kiekiu. Tai klaidinga: galvosūkis su 28 skaičiais gali būti išspręstas vien akimis, o su 32 skaičiais – reikalauti grandininių loginių schemų. Mūsų generatorius sunkumą kalibruoja pagal būtinas dedukcijos technikas:

• Lengvas (~40 skaičių): Išsprendžiamas vien tiesioginiu vizualiniu skenavimu: Naked Singles ir Hidden Singles. Nereikia jokių pieštuko žymų. Idealu pradedantiesiems ir smagiam laiko praleidimui.
• Vidutinis (~34 skaičiai): Reikalauja atmetimo logikos bloke: Pointing Pairs ir Box-Line Reductions. Žaidėjas turi pastebėti, kad kandidatas yra „užrakintas“ 3×3 bloke.
• Sunkus (~28 skaičiai): Įtraukia porų ir trejetų eliminavimą keliuose sektoriuose: Hidden Pairs ir Naked Triples.
• Ekspertas (~24 skaičiai): Reikalauja gilių geometrinių grandinių, tokių kaip X-Wing (dvi lygiagrečios eilutės su kandidatais sutampančiuose stulpeliuose) ir Swordfish modeliai.

Rašalą taupantis vektorinis spausdinimas ir atsakymų lapas

Spausdinant rastrinius interneto paveikslėlius, rašalas dažnai peršlampa per ploną 80 g/m² popierių ir be reikalo eikvoja juodą kasetę. Mūsų generatorius naudoja procedūrinius vektorinius SVG kelius, sukalibruotus ISO A4 standartui. Galite pasirinkti 1, 2, 4 arba 6 galvosūkius viename lape savaitgalio kelionei, stovyklai ar senjorų laisvalaikiui. Pažymėjus varnelę „Pridėti atsakymų lapą“, naršyklė automatiškai suformuoja antrąjį puslapį su miniatiūriniais teisingai išspręstais tinkleliais pasitikrinimui.