Sudoku

Sudoku (jap. 数独 = sūdoku) – galvosūkiai, kuriuose reikia surasti ir įrašyti skaitmenis nuo 1 iki 9 taip, kad skaitmenys nesikartotų eilutėse, stulpeliuose bei paryškintuose 9 langelių (3×3) kvadratuose. Dažniausiai sudoku sprendžiami 9 eilučių ir stulpelių galvosūkiai, kuriuose įrašyta keletas pradinių skaitmenų. Sudoku paplito Japonijoje 1986 metais, o 2005 metais pasidarė populiarūs kitose šalyse.

Žodis Sudoku, kilęs iš japonų kalbos, reiškia „vienintelis skaičius“. Pagal susitarimą galvosūkiuose naudojami skaitmenys, tačiau matematiniai ryšiai čia nėra svarbūs, taigi galimi galvosūkio variantai naudojant kitus simbolius, pavyzdžiui, abėcėlės raides ar spalvas.

Priklausomai nuo pradinių įrašytų skaitmenų, galvosūkiai gali būti skirstomi pagal sudėtingumą. Kartais įvairaus sudėtingumo sudoku galvosūkiai pateikiami mokyklose kaip loginio mąstymo pratimai.

Sprendimo būdai

Paprastai sprendžiant sudoku galvosūkį, pasitelkiamas trijų strategijų derinys – skanavimas, žymėjimas ir analizavimas.

Skanuojant pasirenkamas skaitmuo ir peržiūrimos visos eilutės randant vietas, kur skaitmuo gali būti įrašytas, vėliau peržiūrimi stulpeliai ir 3×3 kvadratai. Vėliau skanuojami kiti skaitmenys. Taip pat galima iš eilės pasirinkti langelius ir atmesti negalimus skaitmenis.

Kai skanavimas nebepadeda, padeda žymėjimas, kai langeliuose pasižymimi visi galimi skaitmenys (smulkiu šriftu ar taškais atitinkamose vietose).

Sprendimas kompiuteriu

Gana nesunku parašyti programą kompiuteriui, kuri paprastu perrinkimu ras sprendimą. Taip pat galimi efektyvesni algoritmai, eliminuojantys negalimus atvejus tol, kol lieka tik po vieną variantą kiekvienam langeliui. Taip pat yra algoritmų, imituojančių rankinį sprendimą. Šie algoritmai padeda įvertinti galvosūkio sudėtingumą.

Variantai

Populiariausios yra 9×9 langelių lentelės su 3×3 regionais, tačiau egzistuoja ir kitų variantų. Pavyzdžiui, 4×4 lentelės su 2×2 langelių regionais, 5×5 langelių lentelės su netaisyklingais penkių langelių regionais (šis variantas vadinamas Logi-5), 6×6 lentelės su 2×3 regionais ir daugelis kitų. Kartais naudojamos didesnės lentelės – 16×16 ar net 25×25. Japonijoje sprendžiami Gattai 5 galvosūkiai, kur 5 9×9 lentelės sujungtos kampiniais regionais. Yra sukurtas ir trimatis sudoku variantas ([1])

Be skaitmenų galvosūkiams naudojamos raidės ar kiti simboliai. Sukurti galvosūkio variantai su raidėmis, kur išsprendus galima perskaityti tam tikrą žodį ar frazę.

Sudoku matematiškai

Matematiškai sudoku galvosūkius galima spręsti įvairiai. Vienas iš variantų – sudoku galvosūkius išreikšti kaip grafo nuspalvinimo uždavinį, žiūrint į sprendimą kaip į nuspalvinimą 9 spalvom, turint keletą pradinių spalvotų viršūnių. Toks grafas turėtų 81 viršūnę (po viršūnę langeliui)m kurias galima žymėti $(x,\,y)$ , kur x ir y yra skaičiai nuo 1 iki 9. Dvi skirtingos viršūnės sujungiamos tada ir tik tada, jei:

$x=x'\,$ arba,
$y=y'\,$ arba,
$\lceil x/3\rceil =\lceil x'/3\rceil$ ir $\lceil y/3\rceil =\lceil y'/3\rceil$

Istorija

Pirmą kartą tokio tipo galvosūkis išspausdintas Niujorke „Math Puzzles and Logic Problems“ žurnale XX amžiaus aštuntojo dešimtmečio pabaigoje, tuo metu galvosūkiai vadinti „Number Place“. 1984 balandį tokie galvosūkiai pradėti spausdinti Japonijoje pavadinimu, kiek vėliau galvosūkiai pavadinti „Sudoku“.

1989 metais sukurta pirmoji kompiuterinė versija „Commodore 64“ kompiuteriams.

2004 metų lapkričio 12 dieną Sudoku pradėti spausdinti kasdien „The Times“ dienraštyje, po trijų dienų – „The Daily Mail“, vėliau kituose laikraščiuose ir žurnaluose, taip labai išpopuliarinant galvosūkius.

Nuorodos

Sudoku Online Sudoku galvosūkiai internetu (Lietuviška versija)
Sudoku / Soduko Sudoku galvosūkiai internetu
Sudoku.lt - taisyklės
Sudoku – Sudoku galvosūkiai internetu (angl.)
Web Sudoku – daug galvosūkių (angl.)