Sudoku ja evoluutio/geneerinen algoritmi

[Jere Sumell]

Olen viime pari viikkoa viettänyt perinteisen lyijykynä/humaanin ajanvietteen parissa, johon myös liittyy Sudokun ratkaiseminen perinteisen printtimedian välityksellä vuorovaikutuksen tapahtuessa.

En ole mikään expertti enää aivotärähdyksen jäljiltä enkä koskaan ole ollut, vaikka matematiikka oli paras alani esim. ylppäreissä kuulakärkikynällä vastaukset kirjottaen.

Alkoi kiinnostamaan kombinatoriikan osalta Sudoku-tehtävän ratkaisu, niin päädyin lukemaan geneerisestä algoritmistä kyseisen ristikkotehtävän ratkaisun osalta.

Tuttuja on jo yhteissumma 1-9 -tehtävässä, mutta ohjelmoinnin osalta se ei riitä. Lisäksi "Killer sudoku solver" -videoita olen katsonut ja ymmärrän eri strategioita, mitä esim. raalla laskentateholla (brute force) on mahdotonta ratkaista kotiläppärillä tai luoda kaikkia sextiljoonaa Sudoku-mallia ratkaistavaksi asiakkaille, mitä suoritus kestäisi enemmän varmaan mitä elinaikaa jäljellä ihmisellä.

Mielenkiintoista on myös se, että tämä nyt paljastaa amatöörimäisyyteni Sudoku-tyypin osalta,, mitä pidin aiemmin jopa tietokoneshakkia ihmisen elinaikana kaikkia pelitilanteita koneen luovutettaveen ratkaistavaksi, mitä Sudokussa on vielä enemmän niitä alkutilanne -vaihtoehtoja, ja itse humaanin harrastuksen osalta kynä/paperi -ratkaisuvaihtoehtoja, vielä vähemmän ehtii universumin kaikkia Sudokuja ratkaisemaan.

Päädyin nettisession jälkeen siihen, että ainakin permutaatiosta liikkeelle lähtiessä voisi karsia pois alkutilanne-vaihtoehtoja, mitä onko se 16/17 -alkuasetelmassa numeroita antamalla ollaan globaalisti päästy minimiin tällä "Sudoku patterns permutation -approached way" -to do-it.

Onko palstalla muita Sudoku-harrastajia, ja jos on niin näkemys ja myös esimerkki Geneerisestä algoritmistä olisi kiinnostava. BF - on mahdoton ihmisen elinajan puitteissa.

[Tomin]

Puhutaanko tässä nyt Sudokujen ratkaisemisesta vai niiden luomisesta? Nuohan ovat kaksi eri ongelmaa. Kirjoitan alla olemassa olevien Sudokujen ratkaisemisesta.

Sudokun voi kyllä ratkaista aika helposti ihan ohjelmallisestikin. Siinähän ei tarvitse kuin käydä soluja läpi vuoronperään ja tarkistaa, mitkä numerot ovat mahdollisia. Jos mahdollisuuksia on yksi, niin sen täytyy olla oikein. Sitten jos ei sillä löydy ratkaisua vaikka kierroksella on käyty kaikki ruudut läpi, täytyy etsiä ruutu, jossa on mahdollisimman vähän mahdollisuuksia, ja ratkaista nämä vaihtoehdot erikseen (eräänlainen brute force -ratkaisu tämäkin). Jos päätyy umpikujaan, niin jatkaa toista vaihtoehtoa. Sehän voi sitten haarautua useammankin kerran, mitä voi potentiaalisesti vähän optimoida laittamalla haarautumiset jonoon ja ratkaisemalla nämä mahdolliset myöhemmin tapahtuvat haarautumiset vasta ns. helpompien jälkeen. Toki myös voi toteuttaa kaikenlaisia muitakin kikkoja, mitä paperillakin käyttäisi, kuten ruutujen ryhmittelyä käypien numeroiden avulla, mikä poissulkee muita numeroita, mutta koodi alkaa sitten mennä monimutkaiseksi. (Selitin tuon varmaan huonosti, mutta jos katsoo vaikka YouTubesta sudokunratkaisukikkoja, niin siellä on kaikenlaista edistyneemmille ratkaisijoille.)

Olen parit ratkaisijat kirjoittanut Pythonilla ja yhden myös C:llä joskus opiskeluaikoina, ja paperilla noita tulee aina välillä ratkaistua. Yksi kiva kikka C:n kanssa on esittää ruutujen arvot bittivektoreina, jolloin niitä voi yhdistellä bittioperaatioilla ja siten varsin nopeasti tarkistaa, mitkä numerot sopivat tyhjään ruutuun. Tuo haarautuminen on myös verrattain helppo rinnakkaistaa.

Mitä tulee tuohon brute forceen, niin ei kai tuollaisen normaalin 9x9-ruudukon ratkaisu niin kauan voi viedä, vaikka sen toteuttaisi huonostikin. Toki jos yleistää sudokun ratkaisun mielettömän suurelle ruudukolle, niin se alkaa viedä paljonkin aikaa tietenkin. Geneettisiä algoritmeja en ole tähän ongelmaan koskaan koittanut, enkä oikein näe, että Sudokujen ratkaisemiseen se auttaisi paljoakaan. Sen sijaan Sudokujen luomiseen sellainen voisi olla ihan paikallaankin.