Keskustelu: Yleinen keskustelu: Sudokut

Merri kirjoitti:

Uh... ja nyt voisi ehkä jo harkita ihan omaa topikkiaan sudokulle, kun tätä asiaa on jo useamman viestin verran tullut.

Vaikka näin. Eli tämä ketju on jatkoa taannoisille Sudoku-aiheisille viesteille.

lainaus:

Käytännössä siis Dancing Links on juuri sellainen algoritmi, jota en tarkoittanut, koska se pohjautuu "arvailuun" :)

Käsitin sitten väärin: luulin, että puhuit Sudokujen ratkaisemisesta ylipäätään, etkä vain "logiikkapohjaisista" algoritmeistä.

lainaus:

"Oikeat" sudokuohjelmoijat ovat varsin... hmm... mielenkiintoisia tapauksia. He ovat ehkäpä hieman elitistisiä. Siellä on joukossa sellaisia, joilla on todella paljon älyä algoritmien ymmärtämisessä ja he sitten rankkaavat onko jokin tietty tapa "soveliasta" vaiko ei. -- He rankkaavat jotenkin, kuuluuko jokin algoritmi arvaajakastiin vaiko logiikkakastiin.

Näinhän he tekevät. Käytännössä se on kuitenkin aika helppoa nähdä: logiikka-algoritmit toimivat yleensä niin, että etsitään tiettyjä kuvioita, joiden perusteella jokin ehto on aina tosi. Yksinkertaisimmillaan siis esim. jos rivissä voi olla jokin luku vain yhdessä kohtaa, luvun on tultava siihen kohtaan. Ne monimutkaisimmat menevätkin sitten minulta yli hilseen, ellei niitä mieti pitkään, kohta kohdalta, läpi. (Yleensä vielä tuppaan unohtamaan seuraavaan päivään mennessä, miten se tekniikka oikein toimikaan. :-P)

Tavallaanhan kaikki logiikka-algoritmit ovat loppupeleissä vain "hienostuneempaa brute-forcea": ollaan voitu kokeilla tietyssä tilanteessa kaikki mahdolliset siirtovaihtoehdot ja todeta, että siinä tilanteessa vain yksi siirto toimii (tai jokin siirto ei toimi). Eli ylläolevassa yksinkertaisessa esimerkissä voidaan kokeilla kaikkia lukuja, ja todeta sen yhden olevan ainoa oikea vaihtoehto.

Käsittääkseni osa (ettei peräti suurin osa) tekniikoista onkin keksitty tuolla tavalla, ja varsinainen looginen tai matemaattinen todistus, joka selittää, miksi tekniikat toimivat, tulee paljon myöhemmin, jos ollenkaan.

Vielä yksi rankkaus, jota tehdään, on sellainen, että olettaako tekniikka vain yhden ratkaisun olevan olemassa. Eli algoritmissa voi olla perusoletuksena, että Sudokussa on vain yksi ratkaisu, ja sen pohjalta voidaan tehdä jotain eliminointeja. Joidenkin mielestä tällainen ei ole varsinaisesti oikein, sillä virheellisessä Sudokussa voi olla useampia ratkaisuja, ja tällaisella tavalla sellainen Sudoku "muutetaan" oikeaoppiseksi, eikä sen virheellisyyttä noteerata. Itse ajattelen juuri näin.

Eri algoritmien rankkauksista keskustellaan paljon; tehdään eroa "yritys-erehdyksen" ja "brute forcen" välillä, ym. Yhteismielisyyttä ei löydy, jokainen päättää sen itse kunkin algoritmin kohdalla.

Kaksi hyvää foorumia Sudokuihin, ja erityisesti niihin liittyvään ohjelmointiin sekä monimutkaisempiin ratkaisutekniikoihin, liittyen: Sudoku Programmers ja Sudoku Players' Forums.