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]

> Mites jos m� koodaan tuollaisen yksinkertaisimman mahdollisen:
> 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]

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]

> 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