Sudoku

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje
Lažja sudoku uganka

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 kaki 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.

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[uredi | uredi kodo]

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 dimenzijo tej matematični konstrukciji in jo predstavil kot križanko, ki je delno izpolnjena in zahteva, da 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 lahko prevedemo 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 vzameš samo prve zloge in 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[uredi | uredi kodo]

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 dimenzijami,

Sudoku-X[uredi | uredi kodo]

Sudoku-X je sudoku, pri katerem moramo 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[uredi | uredi kodo]

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

Geometrijski sudoku[uredi | uredi kodo]

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 dimenzijami[uredi | uredi kodo]

Seveda pa lahko spreminjamo tudi dimenzijo sudokuja. Nam 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[uredi | uredi kodo]

Postopek črtanja

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

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

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

Matematika sudokuja[uredi | uredi kodo]

Pravilna sudoku mreža je tudi latinski kvadrat, seveda pa obratno ne velja, ker imamo pri sodukuju dodatne omejitve. Število vseh možnih mrež pri velikosti 9 × 9 je 6.670.903.752.021.072.936.960 [1]. 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] in [3].

Glej tudi[uredi | uredi kodo]

Zunanje povezave[uredi | uredi kodo]

V slovenščini

V angleščini