Näytä kirjoitukset
1
Ohjelmointi, palvelimet ja muu edistyneempi käyttö / Vs: Sudoku ja evoluutio/geneerinen algoritmi
« : 09.12.25 - klo:20.25 »
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.
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.
ja aika moneen muuhunkin asiaan. Tuollaiselle on kyllä paikkansa, jos kääntelee suuria projekteja tai tarvitsee useita virtuaalikoneita, mutta ehkä peruskäyttöön sopivana näkisin selkeästi edullisemman kokoonpanon, jos käyttö on tosiaan peruskäyttöä. 
