Sudoku FlowMiten tietokoneet ratkaisevat sudokun
Päivitetty 2026-10-05
Peruuttava haku
Ratkaisija kokeilee tyhjään soluun sääntöjen sallimaa numeroa ja jatkaa eteenpäin. Jos mikään numero ei johda ratkaisuun, se peruu aiemman valinnan ja kokeilee toista. Haku lyhenee usein huomattavasti, kun ensin valitaan solu, johon on vähiten mahdollisia numeroita.
Lähteet: Wikipedia: Sudoku solving algorithms, Peter Norvig: Solving Every Sudoku Puzzle
Täsmällinen peitto ja Dancing Links
Sudoku voidaan muotoilla täsmällisen peitteen ongelmaksi: valitaan numeroiden sijoitukset siten, että jokainen solu sekä jokainen numero jokaisella rivillä, sarakkeessa ja lohkossa katetaan täsmälleen kerran. Donald Knuth kuvasi marraskuussa 2000 julkaistussa artikkelissaan Dancing Linksin, tehokkaan tavan suorittaa hänen peruuttavaa hakua käyttävä Algorithm X -algoritminsa. Sudokun täsmällisen peitteen malliin sovellettuna se löytää tehtävän kaikki ratkaisut nopeasti.
Lähteet: Wikipedia: Sudoku solving algorithms, Knuth, Dancing links (arXiv cs/0011047, 2000)
Satunnaishaku
Jotkin ohjelmat täyttävät ruudukon satunnaisesti ja järjestävät sitten numeroita uudelleen vähentääkseen ristiriitojen määrää esimerkiksi simuloidun jäähdytyksen tai geneettisten algoritmien avulla. Näitä on tutkittu vaihtoehtoisina lähestymistapoina. Niiden toimivuus riippuu ohjelmasta ja tehtävästä.
Lähteet: Wikipedia: Sudoku solving algorithms
Ihmisten tavoin ajattelevat ratkaisijat
Vihjemoottorin tehtävä on erilainen: sen pitää paitsi löytää vastaus myös näyttää seuraava askel, jota ihminen voi seurata. Sovelluksemme moottori kokeilee ihmisten käyttämiä tekniikoita kiinteässä järjestyksessä helpoimmista, kuten piilotetusta ainoasta ehdokkaasta, vaikeimpiin, kuten ketjuihin ja lähes lukittuihin joukkoihin, ja käyttää ensimmäistä tekniikkaa, joka johtaa numeron sijoittamiseen. Vaikeammat tekniikat toimivat karsimalla ensin ehdokkaita. Vaikein tekniikka, jota moottori käyttää tehtävän ratkaisemiseen, määrittää tehtävän tason sovelluksessa.
Lähteet: Mitä kukin sudokun vaikeustaso vaatii sinulta
