Sudoku

Sudoku (japonsko 数独: sūdoku) je logična uganka, katere cilj je zapolniti kvadratno mrežo, običajno velikosti 9 × 9, s števili od 1 do 9. Vsako število se lahko pojavi točno enkrat v vsakem stolpcu, vsaki vrstici in vsakem manjšem kvadratu velikosti 3 × 3. V mreži so nekatera števila že podana. Namesto števil lahko nastopajo tudi kakšni drugi različni simboli. Za rešitev uganke je potreben logičen razmislek in malo potrpežljivosti, pri težjih pa tudi nekoliko kombinatorike, oziroma poskušanja in vračanja.

Lažja uganka sudoku

V Sloveniji že od leta 1999 to uganko pod imenom »Devet« redno objavljajo v slovenski ugankarski reviji Modro razvedrilo (v vsaki izdaji objavijo pet ugank). Istega leta se je uganka pod imenom »Magični kvadrat« pojavila v reviji Logika in razvedrilna matematika. V juniju 2005 pa se je pojavila tudi v Slovenskih novicah. V avgustu 2006 se je pojavila tudi v Nedeljskem dnevniku, kjer so tudi omenili del članka iz Wikipedije.

Uganke so lahko sestavljene ročno ali pa s pomočjo računalniškega programa. Zahtevnost uganke je načeloma obratno sorazmerna s številom že vpisanih števil, lažje uganke jih imajo preko 30, težje pa med 20 in 30. Japonska različica igre običajno zahteva simetrično postavitev podanih števil.

Zgodovina sudokuja

Sudoku je sestavil Howard Garns, upokojen arhitekt in sestavljavec križank, in ga prvič objavil leta 1979. Čeprav ga je predvidoma navdihnil latinski kvadrat Leonharda Eulerja, je Garns dodal tretjo razsežnost tej matematični konstrukciji in jo predstavil kot križanko, ki je delno izpolnjena in zahteva, da se vstavi še manjkajoče števke tako, da so v vsaki vrstici, stolpcu in kvadratu 3 × 3 števke od 1 do 9, ne da bi se ponovile. Sudoku je bil prvič objavljen v založbi Dell Magazines, v njihovi reviji Dell Pencil Puzzles and Word Games, pod naslovom Number Place (Številčni prostor) v New Yorku.

Na Japonskem je bil sudoku prvič predstavljen v reviji Monthly Nikolist, aprila 1984, pod naslovom Suuji wa dokushin ni kagiru, kar se lahko prevede kot »števke morajo biti edine« ali »števke se morajo pojaviti le enkrat«. Naslov križanke si je izmislil Kaji Maki, predstavnik Nikolija. Pozneje so ga preimenovali v sudoku; na Japonskem je običajno, da se vzame samo prve zloge in se naredi krajšo besedo. Leta 1986 je Nikoli predstavil dve inovaciji, ki sta zagotavljali priljubljenost sudokuja:

• število danih števk je bilo predpisano na ne več kot 32,
• križanke so postale simetrične (dane števke so bile razporejene v simetrične oblike).

Danes sudoku objavljajo velike japonske revije, kot je Asahi Shimbun. Znotraj Japonske ima Nikoli še vedno avtorske pravice za ime sudoku; druge publikacije na Japonskem uporabljajo alternativna imena. Leta 1989 je Loadstar/Softdisk Publishing predstavil DigitHunt na računalniku Commodore 64 in tako naredil prvo domačo računalniško različico sudokuja. Tak naslov nekateri uporabljajo še danes. Yoshimitsu Kanai je leta 1995 predstavil svoj računalniški generator sudokujev pod imenom Single Number za računalnik Apple Macintosh [11] v japonščini in angleščini.

Da bi celotno stvar zaokrožili, Dell Magazines, ki objavlja izvirno križanko Number Place, sedaj izdaja še dve sudoku reviji.

Trenutno ga objavlja kar 55 različnih časopisov po vsem svetu (New York Post, USA Today, The Boston Globe, Washington Post, San Francisco Chronicle, ...), obiskovalce spletne strani www.soduku.com, kjer je moč kupiti progam za osebno uporabo in izvedeti veliko reševalnih trikov, pa štejejo v milijonih.

Vrste sudokuja

Geometrijski sudoku

Ko je sudoku postal priljubljena miselna igra, so si ljudje začeli izmišljati drugačne in težje vrste sudokuja:

• sudoku-X,
• sodo - lihi sudoku,
• geometrijski sudoku,
• sudoku z drugačnimi razsežnostmi.

Sudoku-X

Sudoku-X (diagonalni sudoku) je sudoku, pri katerem je treba upoštevati, da se morajo števke od 1 do 9 v diagonalah pojaviti le enkrat – tako nekateri sudokuji pridobijo enolično rešitev.

Sodo - lihi sudoku

Tak sudoku ima določena polja osenčena. Vpisane števke povedo, ali se v osenčena polja vpisuje sode ali lihe števke.

Geometrijski sudoku

Kvadrat tega sudokuja je sestavljen iz različnih geometrijskih likov, imenovanih nonomine. Razmejeni so z debelejšo črto. Sestavlja jih 9 polj, v katere je potrebno vpisati števke od 1 do 9. Pri tem lahko nastopajo nonomine brez ali z vsemi simetrijami.

Sudoku z drugačnimi razsežnostmi

Seveda pa se lahko spreminja tudi razsežnost sudokuja. Najbolj poznan je sudoku 3 × 3 (saj ima manjša področja sestavljena iz 3 × 3 kvadratkov), obstaja pa tudi veliko drugih velikosti (2 × 3, 2 × 4, 2 × 5, 3 × 4, ...).

Načini reševanja

Postopek črtanja

Eden najbolj enostavnih in uporabih postopkov je črtanje (glej sliko). Zgornji desni mali (3 × 3) kvadrat mora vsebovati 5. Če se (navidezno) prečrta prvi dve vodoravni vrstici (ki že drugje vsebujeta petico) in zadnji navpični stolpec, ostane za petico v malem kvadratu samo še zeleno označeno polje.

Kasneje se ta postopek običajno ustavi in se lahko z manjšimi številkami na robu kvadratkov označuje možna števila, ki se tam lahko pojavijo. Pri težjih ugankah pa je treba izbrati eno od možnosti in preveriti ali se pride do rešitve, sicer pa se vrne nekaj korakov in izbere drugo možnost (postopek se v programiranju imenuje sestopanje ali backtracking).

Za reševanje se lahko uporabi tudi kakega od računalniških programov.

Matematika sudokuja

Pravilna mreža sudoku je tudi latinski kvadrat, seveda pa obratno ne velja, ker so pri sodukuju dodatne omejitve. Število vseh možnih mrež pri velikosti 9 × 9 je 6.670.903.752.021.072.936.960 [1] Arhivirano 2005-07-14 na Wayback Machine.. V latinskem kvadratu 9 × 9 je možnih še dodatnih 5.524.744.825.253.140.821.458.288.640 kombinacij, ki v sudokuju niso možne.

Kolikšno je najmanjše število podanih števil, da je rešitev še vedno enolična, ni znano, trenutni minumum je 17, glejte [2] Arhivirano 2016-10-12 na Wayback Machine. in [3] Arhivirano 2006-11-26 na Wayback Machine..

Glej tudi

• križanka vsot
• KenKen

Zunanje povezave

• Sredin seminar (slovensko)
• http://sudoku.sourceforge.net/ (angleško)