Ubuntu Suomen keskustelualueet
Ubuntun käyttö => Ohjelmointi, palvelimet ja muu edistyneempi käyttö => Aiheen aloitti: Jere Sumell - 09.12.25 - klo:11.19
-
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.
-
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.
-
Puhutaanko tässä nyt Sudokujen ratkaisemisesta vai niiden luomisesta? Nuohan ovat kaksi eri ongelmaa. Kirjoitan alla olemassa olevien Sudokujen ratkaisemisesta
No lähinnä lähdin siitä, että molemmat tulevat samalla kertaa, jos ensin luo valmiin validin vaikka 9x9 -taulukon ja sitten sen jälkeen vasta lähtee koneen tekemään valintoja, mitkä ruudukot poistaisi tietyn vaikeusasteen ratkojalle tarjottavaksi.
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.)
Juu, netistä löytyy tutoriaaleja ihan riittävästi joka tasolle. Ratkaisu-palveluitakin löytyy maailmalta todella paljon, jossa syötetään alkutilanne ja sitten verkkosovellus lisää kandidaatit eri ruudukoihin ja ulostulona on ratkaisu.
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.
Itsekin selailin jotain paperia netissä, missä oli käsiteltynä alkuun 0 ja 1 binääreinä matriisi-taulukko, ja vielä pitää syventyä enemmän tähän aiheeseen, että lähtisi mitään ohjelmoimaan. Oivalsin heti, että 0 ja 1:llä toimiminen lienee mielenkiintoisempaa, kun 0-9 arvoilla ainakin alkutilanteen syöteparametrina ratkaisijalle annettuna. Se on se tie, jos päädyn itse ja miettisin Pythonia, että se voisi olla mielekäs kieli, jos päädyn ohjelmoimaan.
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.
Juu, ei BF ole kovin kustannustehokas sen lisäksi, että se on hitain. Lähinnä mitä itselläni jonkinlaiset äärityypit joko-tai (0 tai 1), mitä kaksitila -periaattella tajuan tietokoneen toimintaa, niin jotenkin mielsin aluksi verrattain suuren joukon erilaisia sudokupohjia/pelitilanteita ja ratkaisut samalla ajokerralla. On totta, että yksittäisen tehtävän pohja/ratkaisu ei nyt kauaa aikaa vie edes raalla laskentateholla.
En muista lähdettä, mutta Sudokuun on liitettävissä vissiin heuristisia hakumenetelmiäkin.