Sudoku

Wikipedia

Tavallinen ratkaisematon klassikkosudoku

Sudoku (japaniksi: 数独, sūdoku) on hiljattain Euroopassa suurta suosiota saanut logiikkapeli. Pelissä tehtävänä on täyttää vajaa ruudukko merkeillä, jotka pitää päätellä jo valmiina olevien merkkien avulla. Yleisimmin tehtävissä on käytetty numeroita, mutta myös kirjaimia, värejä ja muita symboleita.

[muokkaa] Historiaa

Sveitsiläinen matemaatikko Leonhard Euler tutki 1783 latinalaisia neliöitä, NxN-taulukoita, joissa luvut 1–N esiintyivät jokaisella rivillä ja sarakkeella.

Yleisesti uskotaan, että ensimmäisen nykyisen muotoisen sudoku-tehtävän (nimellä Number Place) laati Howard Garnes vuonna 1979. Tämä tehtävä julkaistiin yhdysvaltalaisessa tehtävälehdessä nimeltään Dell Pencil Puzzles and Word Games. Japanissa ensimmäinen sudoku julkaistiin huhtikuussa 1984 nimellä "Sūji wa dokushin ni kagiru (数字は独身に限る)". Myöhemmin nimi lyhennettiin nykyiseen muotoonsa.

Brittiläinen The Times -lehti alkoi julkaista päivittäin sudoku-tehtäviä 12. marraskuuta 2004, ja seuraavien viikkojen aikana muutkin brittiläiset lehdet ryhtyivät julkaisemaan sudoku-tehtäviä. Sudokun suosiota Britanniassa kuvaa, että nykyisin brittiläisessä televisiossa lähetetään päivittäin Sudoku Live! -nimistä ohjelmaa, jossa kilpaillaan sudoku-tehtävien ratkomisessa. Suomessa Helsingin Sanomat alkoi julkaista arkipäivisin sudoku-tehtäviä 17. syyskuuta 2005. Aiemmin sudoku-tehtäviä on Suomessa julkaistu mm. muutamissa ristikkolehdissä, iltapäivälehtien viikkoliitteissä sekä Hufvudstadsbladetissa. Myös Suomessa useat lehdet julkaisevat nykyisin tehtäviä.

[muokkaa] Yleistä

Sana sūdoku on japania ja se koostuu sanoista sū, joka tarkoittaa lukua (tai numeroa) ja doku, joka tarkoittaa yksinäistä, yksin olevaa.

Numeroita käytetään sudoku-tehtävissä pelkästään helppouden takia; numeroiden välisillä aritmeettisilla suhteilla ei ole tehtävien kannalta mitään merkitystä. Mitä tahansa yhdeksää toisistaan helposti erotettavaa symbolia kuten kirjaimia, muotoja tai värejä voidaan käyttää numeroiden sijasta.

Sudokun suosiota selittää se, että pelin säännöt ovat hyvinkin yksinkertaiset, mutta tehtävien ratkaisuun vaadittava päättely voi olla hyvinkin vaikeaa.

Sudoku on NP-täydellinen, joten sitä ei voida ratkaista puhtaasti laskennallisesti (Ei todistettu lausetta P=NP): eri vaihtoehtojen testaaminen on siksi välttämätöntä. Sudokujen ratkaiseminen ei testaa niinkään matemaattista lahjakkuutta vaan paremminkin loogista päättelykykyä. Sudokut on usein lajiteltu vaikeusasteikoltaan asteikolla 1-4 tai 1-5.

[muokkaa] Sudokun variaatiot

Yleisin ja tunnetuin sudokun versio on klassikkosudoku, joka koostuu 9x9-ruudukosta, joka on jaettu yhdeksään 3x3-ruudukkoon. Tämäntyyppisessä tehtävässä jokaisessa rivissä, sarakkeessa ja 3x3-ruudukossa tulee olla numerot 1-9. Klassikkosudokun perusohje voisi kuulua näin: "Täytä tyhjät ruudut siten, että jokainen vaaka- ja pystysuora rivi sekä 3x3-ruudun laatikko sisältää numerot yhdestä yhdeksään".

Muita variaatioita:

minisudokussa on 4x4-ruudukko, joka on jaettu neljään pienempään 2x2-ruudukkoon. Säännöt ovat samat kuin klassikkosudokussa, tässä variaatossa käytetään yleisesti numeroita 1-4.
salamasudokussa on 6x6-ruudukko, joka on jaettu kuuteen pienempään 2x3-ruudukkoon. Säännöt ovat samat kuin klassikkosudokussa, tässä variaatossa käytetään yleisesti numeroita 1-6.
supersudokussa on 12x12-ruudukko, joka on jaettu 12 pienempään 4x3-ruudukkoon. Yleisesti tässä tehtävässä käytetään numeroita 1-12.
mestarisudokussa on 16x16-ruudukko, joka on jaettu 16 pienempään 4x4-ruudukkoon. Yleisesti tässä tehtävässä käytetään joko numeroita 1-16 tai numeroita 1-9 ja kirjaimia A-G.
palapelisudokussa on klassikkosudokun tapaan 9x9-ruudukko, mutta se on jaettu yhdeksään epäsäännöllisen muotoiseen 9 ruudun laatikkoon, joihin vastaavasti sijoitetaan numerot 1-9. Perussääntö koko ruudukkoon on sama.

Lisäksi on olemassa ns. kaksikko-, kolmikko- ja viisikkosudokuja. Niissä on nimensä mukainen määrä klassikkosudokuja, jotka ovat kiinni toisissaan eli joilla on yhteisiä pienempiä 3x3-ruudukoita.

[muokkaa] Vaikeustaso

Sudokutehtävän vaikeustason kannalta ei ole paljonkaan merkitystä annettujen numeroiden määrällä vaan annettujen numeroiden sijoittuminen ratkaisee. Tehtävän vaikeustaso määräytyy sen ratkaisemiseen tarvittavien tekniikoiden ja päättelyketjujen pituuden perusteella. Maailman vaikeimpia tehtäviä on pisteytetty muun muassa seuraavilla ohjelmilla; Sudoku Explainer, gsfr ja suexrat9.