Sudoku (数独, sūdoku) (joskus kirjoitetaan Su Doku, mutta sitä kutsutaan myös nimellä Number Place tai Nanpure) on pulmapeli, joka on hyvin suosittu Japanissa. Sen loi Indianapolisissa vuonna 1979 Howard Garns, ja se ilmestyi sen jälkeen Dell Magazines -lehdessä.

Sudoku-palapelit ratkaistaan logiikan avulla, eikä matematiikkaa tarvita. Kuten oikealla näkyy, se koostuu ruudukosta, joka koostuu yleensä yhdeksästä rivistä, yhdeksästä sarakkeesta ja yhdeksästä laatikosta, jotka on erotettu toisistaan paksummilla, tummemmilla viivoilla. Joissakin näistä laatikoista on numeroita 1-9. Palapelin ratkaisemiseksi henkilön on täytettävä kaikki tyhjät ruudut käyttämättä samaa numeroa kahdesti kussakin sarakkeessa, rivillä tai laatikossa ja muuttamatta ruudukossa jo olevia numeroita.

Nämä palapelit on luotu tehtäväksi kynällä ja paperilla, ja monet kirjat sisältävät kokoelmia näistä palapeleistä sekä vinkkejä ja strategioita niiden ratkaisemiseen. Niitä julkaistaan myös sanoma- ja aikakauslehdissä: yleensä joka päivä ilmestyy erilainen arvoitus, jonka ratkaisu on painettu jonnekin muualle tai seuraavaan numeroon. Myöhemmin kehitettiin pieniä kannettavia koneita, jotka tuottavat Sudoku-palapelejä käyttäjän ratkaistavaksi. Viime aikoina peliä on kuitenkin voitu pelata internetissä tai mobiilisovelluksissa.

Lyhyesti säännöistä

  • Tavallinen Sudoku on 9×9-ruudukko, ja se on jaettu yhdeksään 3×3-alueeseen (laatikoihin).
  • Tavoitteena on täyttää ruudukko numeroilla 1–9 siten, että jokainen rivi, sarake ja 3×3-laatikko sisältää kaikki numerot 1–9 täsmälleen kerran.
  • Annetut numerot (ns. "givens") eivät saa muuttua. Useimmat julkaistut pulmat on suunniteltu niin, että niillä on täsmälleen yksi ratkaisu.

Lyhyt historiikki ja suosio

Alkuperäisen "Number Place" -version kehitti Howard Garns vuonna 1979. Puzzle sai uuden elämän Japanissa, jossa julkaisijat kuten Nikoli toivat sitä laajemman yleisön tietoisuuteen ja antoivat sille lyhennetyn nimen sudoku (ajatus: numerot yksinään). 2000-luvulla Sudoku-innostus levisi laajasti Eurooppaan ja muualle maailmaan, ja erityisesti sanomalehdet ja nettipalvelut tekivät pelistä arkipäiväisen ajanvietenimen.

Varianssit ja vaikeusasteet

  • Perinteinen 9×9 on yleisin, mutta sudokua on myös pienempänä (4×4, 6×6) ja suurempana (12×12, 16×16).
  • Erilaisia muunnelmia: Killer Sudoku (ryhmät ja summat), Jigsaw/Irregular Sudoku (ei säännöllisiä 3×3-laatikoita), Hyper Sudoku (ylimääräisiä alueita), Samurai Sudoku (moniristikot), Sudoku X (diagonaalit myös unik), ja Wordoku (kirjaimet numeroiden sijaan).
  • Vaikeusaste määräytyy annettujen numeromäärän, niiden sijoittelun ja tarvittavien ratkaisustrategioiden mukaan. Helppoihin riittää peruslogiikka; vaikeissa voidaan tarvita edistyneempiä ketjumenetelmiä tai systemaattista koe- ja virhettä (backtracking).

Ratkaisustrategioita — alkeista edistyneisiin

Tässä käytetään muutamia yleisimpiä tekniikoita aloittelijasta etenevälle:

  • Muistiinpanot (pencil marks): merkitse kuhunkin tyhjään ruutuun mahdolliset numerot pienennä kirjoitettuna.
  • Naked single: ruudussa vain yksi mahdollinen numero — täytä se.
  • Hidden single: tietyllä rivillä/sarakkeessa/alueella vain yhdessä ruudussa voi tietty numero esiintyä, vaikka ruudussa olisi muitakin merkintöjä.
  • Naked pair/triple: jos kahdessa ruudussa alueella on täsmälleen samat kaksi mahdollisuutta, ne voidaan poistaa muista alueen ruuduista.
  • Locked candidates (pointing): jos tietyn numeron ehdokkaat tietyssä laatikossa rajoittuvat yhdelle riville tai sarakkeelle, kyseistä numeroa ei voi olla muissa saman rivin/sarakkeen ruuduissa laatikon ulkopuolella.
  • X-wing, Swordfish: ritilämalliset ketjut, joilla voidaan eliminoida ehdokkaita rivien ja sarakkeiden leikkausten perusteella.
  • Väri- ja ketjutekniikat (coloring, chains): loogisia ketjuja ja väritystä käytetään ristiriitojen etsimiseen ja ehdokkaiden poissulkemiseen.
  • Koe- ja virhe (trial and error): joskus käytetään systemaattista olettamista ja takaisinperuutusta (backtracking) varsinkin vaikeissa pulmissa tai tietokoneavusteisissa ratkaisuissa.

Teknologia ja laskenta

  • Sovellukset ja nettisivut tarjoavat automaattista tarkistusta, vihjeitä ja eri vaikeustasoja. Monet antavat mahdollisuuden kytkeä päälle muistiinpanot ja tasoittaa käytön.
  • Tietokoneet voivat ratkaista sudokun tehokkaasti. Tunnettu menetelmä on Donald Knuthin Algorithm X yhdessä Dancing Links (DLX) -tekniikan kanssa, mutta myös backtracking ja muitakin algoritmeja käytetään.
  • Yleistetty Sudoku-ongelma on laskennallisesti vaikea: täydellisenä ongelmana (parametrisoituna) se kuuluu NP-täydellisiin ongelmiin.

Erityistietoja ja kiinnostavia faktoja

  • Useimpiin sanomalehtipulmiin pyritään suunnittelemaan yksi ainutlaatuinen ratkaisu. Pääosin julkaistavat pulmat ovat sellaisia.
  • Tutkijat ovat löytäneet, että on olemassa Sudoku-pulmia, joissa on vain 17 alussa annettua numeroa ja jotka silti säilyttävät yksiselitteisen ratkaisun — 16 numerolla ei ole löydetty toimivaa tapausta (tämä on tutkitusti vakiintunut tieto).
  • Sudokussa voi kehittyä loogista päättelyä, kärsivällisyyttä ja tarkkuutta — siksi monet pitävät sitä aivojumppana.

Vinkkejä aloittelijalle

  • Aloita helposta vaikeustasosta ja käytä muistiinpanoja.
  • Tarkista aina rivit, sarakkeet ja laatikot järjestelmällisesti — etsi ensin naked- ja hidden-singles.
  • Poista ehdokkaita aina kun huomaat varmoja rajoituksia; pieni muutos voi johtaa ketjureaktioon ja ratkaisuun.
  • Älä arvaa ensin — kokeile vasta, kun kaikki loogiset vaihtoehdot on käytetty loppuun. Jos arvauksesta syntyy ristiriita, palaa siihen takaisin ja kokeile vaihtoehtoa.

Sudoku on yksinkertaisilta sääntöjensä puolesta helposti lähestyttävä mutta monitasoinen haaste, joka soveltuu sekä lyhyisiin aamuhetkiin että tuntien uppoutumiseen monimutkaisiin logiikkaketjuihin. Jos haluat, voin lisätä esimerkkiratkaisun vaihe vaiheelta yhdelle sudokun strategialle tai luoda harjoituspähkinän eri vaikeustasolle.