Sudoku algoritmi.

[Matti Lehtiniemi]

Tuossa kun kesällä kun pakoilin helteitä sisätiloihin tuli tehtyä parit
sudokut.Ensimmäisiin 7-päivää lehden sudokuun meni 5-7 tuntia ratkaisuun.Sen
jälkeen helpottui.
Sittemmin siirryin älypää -sivuston nettisudokuun ja ratkaisin niitä
"vaikea" -tasolla.Ja edelliset 2 tehtävää olen ratkaissut vaikeimmalla
"älypää"-tasolla.
(Mikä on tuottanut suunnattoman älyllisen tyydytyksen)
http://alypaa.com/sudoku

Moraaliongelmat vaivaa enkä kehtaa kehittää softia nettipokeriin ja ajattelin
koodata sudoku-ratkaisijan.
(näin syksyn ratoksi ja älyllisenä haasteena)

Mites jos mä koodaan tuollaisen yksinkertaisimman mahdollisen:
http://en.wikipedia.org/wiki/Sudoku_solving_algorithms

Meneekö tuolla ratkaisuun pitkä aika, jos on oikein vaikea sudoku ?
(tarkoitan vaikealla näitä maailman vaikeimpia sudokuja)
Tuostahan saisi aika lyhyen koodinpätkän jos tekisi rekursiivisen algoritmin.
Vielä lyhyemmän saisi jos tekisi geneettisen algoritmin.(Mutta se varmaan
ratkoisi kauan sitä)

Siis se suomalainen tyyppi joka on kehittänyt sudokuja helsingin sanomille,
testaa sudokun vaikeutta sillä miten kauan ratkaisuun menee ?

Eikö tuossa tarvita copy-constructoria jos haluaa kätevästi kopioida
sudoku-gridin rekursioon C++ :lla ?
Ei vaan se kopioi automaattisesti.Annan siis vaan rekursiofunktiolle parametrina
sudoku luokan(Ilman * -merkkiä tai & merkkiä, eli ilman pointtereita)

Saako tehtyä lyhyemmän algoritmin kun mitä tää viesti on ?

Matti

[Matti Lehtiniemi]

Post by Matti Lehtiniemi
http://en.wikipedia.org/wiki/Sudoku_solving_algorithms

Jaa eihän tuo yksinkertaisin algoritmi vaadi edes mitään ruudukon kopiointia.
Nyt tajusin.
Se että kannattaako tuota kaikkein yksinkertaisinta edes koodata vai tehdäkö
samantien pikkuisen fiksumpi ja nopeampi onkin eri asia.

M

[Antti Valmari]

Post by Matti Lehtiniemi

Post by Matti Lehtiniemi
http://en.wikipedia.org/wiki/Sudoku_solving_algorithms

Jaa eihän tuo yksinkertaisin algoritmi vaadi edes mitään ruudukon kopiointia.
Nyt tajusin.
Se että kannattaako tuota kaikkein yksinkertaisinta edes koodata vai
tehdäkö samantien pikkuisen fiksumpi ja nopeampi onkin eri asia.

Tein kerran yksinkertaisen backtracking-toteutuksen tavallisen
kokoisille sudokuille (laatikon koko on 3x3 ja koko sudokun 9x9). Se oli
niin nopea, että ei ollut mitään mieltä tehdä fiksumpaa.

--- Antti Valmari ---

[Matti Lehtiniemi]

Post by Antti Valmari
Tein kerran yksinkertaisen backtracking-toteutuksen tavallisen
kokoisille sudokuille (laatikon koko on 3x3 ja koko sudokun 9x9). Se oli
niin nopea, että ei ollut mitään mieltä tehdä fiksumpaa.

Jos tuosta yksinkertaisimmasta algoritmista tekee rekursiivinen, niin
backtracking tulee siihen ikään kuin automaattisesti:
http://en.wikipedia.org/wiki/Sudoku_solving_algorithms

Prkl kun en ole vuoteen koodannut. Piti käynnistää QB64 (Quick Basic 64 bittinen
freeware versio), kun en usko että c++ onnistuu tauon jälkeen.
Saiskohan tuolla QB64:lla rekursion toimimaan kunnolla ? (niin että se pystyy
ratkomaan koko sudokun)

Olisi mielenkiintoista vaan tietää että ratkooko tuo yksinkertaisin mahdollinen
algoritmi myös kaikkein vaikeimmat sudokut järjellisessä ajassa.

Asko Inkala on sen tyypin nimi:
http://www.mtv.fi/uutiset/kotimaa/artikkeli/suomalaiselta-jalleen-maailman-vaikein-sudoku-osaatko-ratkaista/1889910

Matti