Millaisia ratkaisuja..

teillä oli?
Muunsiko kukaan ongelma exact coveriksi? Pääskö joku koodaamaan Dancing Links -algoritmia? Käytittekö aikaa paljon matalan tason optimointiin? Olis hauska tietää miten eri ideat toimi

Samuli

Kiitos Samulille onnitteluista!

Laitoin oman ratkaisuni (C++) nettiin:

http://sli.homeunix.net/~sliedes/chilion/

Lisäksi tuolla on lisäongelmia (more*.prb) sellaisilla parametreilla, jotka ovat suhteellisen hankalia (paljon hankalampia kuin Conformiqin esimerkkiongelmat problems.prb) omalle solverilleni.

Käytin ehkä vähän enemmän aikaa matalan tason kuin korkean tason optimointiin, yhteensä arvioisin käyttäneeni ehkä jotain 30-50 epämääräistä, ei täysin tehollista tuntia. Otin tämän nyt vähän siltä kannalta, että katsotaan nyt, miten tehokkaan osaan tästä tehdä, joten en hirveästi laskenut millaisille tuntipalkoille tästä pääsee. Profiloitua tuli aika paljon, jotta löytää oikean paikan optimoida. Itse suosin profilointiin callgrindiä ja visualisointiin kcachegrindiä, mutta myös Linux-ytimen mukana tuleva perf on mainio.

Algoritmini on melko suoraviivainen

1. propagoi ja tarkista, onko lopputulos ratkaisu
2. jos päätöksiä on tehty riittävästi (alkulimitiksi hyvä arvo minun ratkaisimelleni näyttäisi olevan noin 28, vaikeammilla ongelmilla vähemmän), resetoi alkutilaan ja kasvata limittiä (= "restart")
3. tee satunnainen päätös
4. siirry kohtaan 1

ja loppu on melko paljon propagointivaiheen optimointia. Conformiqin malliongelmilla algoritmini on niin nopea, että triviaalilla toteutuksella melko suureksi pullonkaulaksi nousee inputin lukeminen - ensin scanf() oli liian hidas, myöhemmin pyrin eroon myös fgets()istä; valmis ratkaisuni lukee inputin 2048 tavun blokeissa. (Tarinan opetus: profilointi...) Hämärintä koodia toteutuksessani ehkä onkin hieman paradoksaalisesti syötteenlukukoodi. Vaikeammilla ongelmilla syötteen lukemisen osuus ajoajasta on vähäisempi.

Moi!

Lähdin soitellen sotaan DL-päivänä ja keskityin liikaa propagaatiotietorakenteiden tuunaukseen. Toteutus osoitteessa . Kokeilin yhden tason look-aheadia, mutta look-aheadin laskeminen on niin raskasta, ettei siitä tullut nopeutta lisää.

Lopputuloksena oli yksinkertainen ratkaisin, joka branchaa kapeimmasta kohdasta (pienin domain). Random restartit olisivat varmaan toimineet hyvin.

Hieman jäi kaduttamaan, etten tehnyt SAT-enkoodausta ja konfliktioppivaa solveria.

Noh, eikös linkkiä saa esille. Tässä uudestaan:
http : // www . tcs . hut . fi / ~tolaiti2 / dl / sudoku.tar.gz (jos vielä katoaa)

No jos muutkin niin ehkä sitten minäkin.

Optimointipuolella tein itsekin lähinnä matalan tason jippoilua, mm. IO read/write-kutsuin; lopullinen ratkaisin muistaakseni käytti Conformiqin esimerkkiongelmasetin ratkaisuun vähemmän aikaa kuin alkuperäinen, putchar/getchar-pohjainen IO pelkästään lukemiseen.

Algoritmimielessä käytin yksinkertaista syvyyssuuntaista hakua backtrackingillä, ja sitten yksinkertaista heuristiikkaa siihen, mitä siirtoa ensin tutkia: käytännössä valitsin sen laudan ruudun, jolle pistearvo N*256+K[C] oli pienin; N on mahdollisten vaihtoehtojen määrä, C ruutuun kohdistuvien suurempi-kuin/pienempi-kuin-rajoitteiden määrä, ja K-taulukko optimoitu yksinkertaisella geneettisellä algoritmilla.

Noin spekulaationa epäilisin ylläolevan ratkaisun suurimman ongelman olleen liian suuri erikoistuminen tuohon Conformiqin 1365 ongelman testisettiin. Noin vertailumielessä työpaikan työasemalla 13650 ongelman (Conformiqin esimerkit kymmenen kertaa toistettuna) testisetin ratkaisuun kuluu omalla solverillani suunnilleen 0.39 sekuntia, SLi:n "chilion"illa 0.63 sekuntia; toisaalta omani itse asiassa segfaulttaa johonkin more.prb:n ongelmaan. Olisi sinänsä kiinnostava tietää, kaatuiko se Conformiqin testeissäkin...

Toisena vertailupisteenä more3.prb: oma solverini 10.7s, "chilion" 6.1s, oma solverini "robust"-asetuksilla (jotka laitoin vaihtoehtoisena "make robust"-kääntövaihtoehtona mukaan, en tiedä käyttivätkö) 4.3s. (In retrospect, olisi ehkä pitänyt tehdä näistä asetuksista se oletus.)

Ohjelma löytyy osoitteesta http://zem.fi/~fis/sudoku-kallasjoki.tar.gz ehkä. Alla vielä README-raapustelmasta vähän tarkempaa kuvausta.

Performance expectations
========================

For these benchmarks, I have used a problem set of 13650 problems:
that is, the published sample problem set, repeated ten times.

All reported numbers are averages over 100 iterations of that set;
"us" denotes microseconds, "sigma" the standard deviation.

"System A" is an Intel Core 2 Duo E8400 at 3.0 GHz, gcc 4.4.1.
"System B" is an AMD Athlon 64 X2 5600+ at 2.8 GHz, gcc 4.4.5.

Default settings, no profile-guided optimization:
- System A: 385 ms (28.2 us/problem), sigma 3.5 ms
- System B: 561 ms (41.1 us/problem), sigma 13.3 ms

Default settings, profile-guided optimization:
- System A: 388 ms (28.5 us/problem), sigma 3.5 ms
- System B: 558 ms (40.9 us/problem), sigma 6.8 ms

Robust settings, no profile-guided optimization:
- System A: 438 ms (32.1 us/problem), sigma 3.5 ms
- System B: 614 ms (45.0 us/problem), sigma 9.2 ms

Robust settings, profile-guided optimization:
- System A: 434 ms (31.8 us/problem), sigma 3.6 ms
- System B: 619 ms (45.3 us/problem), sigma 11.5 ms

The current version of the code does not seem to benefit much from
profile-guided optimization. Some earlier versions have.


Comments on the implementation
==============================

The approach taken here is rather simplistic; basically, the solver
does a heuristic-guided recursive depth-first search of valid moves,
and returns the first encountered state where the entire board has
been filled. For each board state, I use the row/column/subarea and
the greater-than constraints to determine the list of valid moves for
the unfilled squares. If there is a "sure" move (only one valid
number), that move is taken. In the (more common) case where each
empty square has multiple alternatives, a heuristic score is used to
select which position to explore. If an impossible-to-solve position
is encountered, the solver backtracks to the previous choice point.

The heuristic move scoring is based on the number of valid moves, as
well as the amount of greater-than constraints related to the
particular square. The move with the least amount of penalty points
is chosen. Each valid move is worth a fixed 256 penalty points, while
the scores for possible numbers of greater-than constraints (0 .. 4)
have been optimized with a genetic algorithm, to lead to the lowest
possible number of explored board positions when solving the provided
sample problem set.

To reduce the amount of backtracking further, during the move
candidate scoring I also optionally take into account further
constraints imposed by a square's siblings (other squares of the same
row/column/subarea). This is done by computing the union of valid
moves for the unfilled siblings and set-subtracting that from the list
of numbers that the row/column/subarea is still missing. The
resulting set of numbers need to be filled in the square under
consideration. If the set is empty, we do nothing, as we have gained
no new information. Alternatively, if the set has multiple numbers in
it, or if a single number would not be valid for the current square,
we backtrack immediately, as the current position is impossible to
solve. Finally, if there is a single, valid move, we immediately
perform that move.

The above-described checks take a significant amount of computation.
Therefore it is only performed during the early parts of the solving,
while 35 or less squares on the board contain filled-in numbers.
Additionally, it is only performed for moves that have at most 1.25
times the number of penalty points of the current best candidate.
Both of these tests are omitted in the "robust" mode, however.

Some amount of low-level optimization has also been done. Sets of
numbers are represented by 9-bit bitsets. To find the first (or last)
number in such a set, inline-asm "bsf"/"bsr" opcodes are used; they
seem faster than GCC's "ffs" built-in. Problem input and solution
output are done with a reasonably optimized read/write syscall
solution. (A naive getchar/putchar solution took something like 75 ms
for the 1365-problem set; for contrast, the current solver takes about
a half of that time to actually solve all the problems.)

fizzie kirjoitti:

Olisi sinänsä kiinnostava tietää, kaatuiko se Conformiqin testeissäkin...

Ei kaatunut.

fizzie kirjoitti:Olisi sinänsä kiinnostava tietää, kaatuiko se Conformiqin testeissäkin...

Muita kiinnostavia asioita tietää olisi osallistujoiden lukumäärä ja se, miten paljon toiseksi tullut hävisi. Tätä foorumia lukemalla tulee sellainen olo että mulla on ollut vähän onneakin mukana, taso on ilmeisesti ollut yllättävän kova.

Moi!

Osallistuin kilpailuun C++ -ohjelmalla, joka perustuu useita vuosia sitten huvikseen tehtyyn Java-koodiin.

Lisärajoitusten toteuttaminen jo olemassa olevaan algoritmiin oli helppoa. Haku perustuu mielestäni kaikista ilmeisimpään algoritmiin eli päätellään ensin yksikäsitteiset ruudut, jonka jälkeen arvataan rekursiivisesti vähiten monikäsitteisen ruudun arvot (käsittääkseni tämä vastaa Teron kuvaamaa algoritmia). Päättelyn ei edes tarvitse olla kovin pitkälle menevää --- riittää, että se toimii nopeasti.

Oma ratkaisijani tekee turhaa työtä yksikäsitteisten ruutujen ratkaisemisessa, koska se ei pidä kirjaa muuttuneista ruuduista / riveistä / sarakkeista / lohkoista. Kaikki tarvittava tilatieto on koodattu yhteen 9x9-kokonaislukutaulukkoon pyrkimyksenä mahdollisimman hyvä tehokkuus. Esimerkiksi ruudun kielletty tila voidaan tunnistaa suoraan '>='-operaattorilla.

Java-ohjelman muuttaminen C++ -ohjelmaksi oli hyvin suoraviivaista, koska ohjelma oli alunperinkin kirjoitettu tätä mahdollisuutta silmällä pitäen. Ainoat ongelmat olivat tiedoston lukemisen kanssa. Tein sen aluksi C++ stream:llä, mikä osoittautui hyvin hitaaksi tavaksi lukea syötettä. Vanhat C-funktiot toimivat paremmin ja muutenkin ratkaisijan lopullinen versio on pikemminkin C:tä kuin C++:aa. Bitinnypläykseen en ymmärtänyt käyttää bsf/bsr-käskyjä (x86-asm) tai edes gcc:n ffs-funktiota --- kävi kyllä mielessä että jotain tällaista voisi olla olemassa.

Halusin myös kokeilla, kuinka nopeaksi saan ohjelman omalla koneellani, joten toteutin siihen tuen säikeistykselle. Lopuksi tuli vielä ihmeteltyä gcc:n profilointityökaluja ja optimointioptioita, joihin en ole aikaisemmin juurikaan tutustunut. Lopputuloksena Java-ohjelma ottaa C-ohjelmalta turpaansa 4.9:1 yhdellä säikeellä ja neljällä säikeellä ero on vieläkin suurempi 7.4:1.

Onnittelut SLi:lle kisan voitosta ja kiitokset chilionin lähdekoodin julkaisemisesta! Muita kommentteja lukiessa luulin jo, että tehokkaaseen ratkaisuun tarvitaan läjä tieteellisiä julkaisuja ja jokin tolkuttoman hieno algoritmi. Voittaja kuitenkin osoitti, että yksinkertainen on kaunista tässäkin asiassa.

chilionin lähdekoodi on kiinnostavaa luettavaa, siinä on periaatteessa ihan samat asiat kuin omassakin koodissani, tosin paljon paremmin toteutettuna. Monet operaatiot esilasketaan ja taulukoidaan jo käännösaikana. Itse pelkäsin turhaan, että taulukoista tulee liian suuria, jotta niistä olisi hyötyä (cache misses). Toinen koodista mieleen jäänyt asia on asserttien systemaattinen ja runsas käyttö.

Eniten kuitenkin ihmetyttää itse algoritmi. Miten satunnaisesti etenevä ja itsensä välillä kokonaan resetoiva algoritmi voikin olla näin tehokas? Kokeilin nopeasti vastaavaa (ainakin käsittääkseni) muutosta ja Java-version nopeus liki kolminkertaistui. Minua kiinnostaisi tietää, miten ratkaisuun on päädytty, koska ratkaisu on mielestäni kaikkea muuta kuin intuitiivisesti selvä.

Jotenkin tuntuu myös siltä, että näennäisesti pienet muutokset tehtävänannossa voisivat muuttaa merkittävästi koko tehtävän luonnetta. Esimerkiksi, jos tehtävätiedosto voisi sisältää myös huonostilaadittuja (ratkeamattomia) tehtäviä, niin satunnaisesti etenevät algoritmit olisivat vaikeuksissa?

MOX kirjoitti:chilionin lähdekoodi on kiinnostavaa luettavaa, siinä on periaatteessa ihan samat asiat kuin omassakin koodissani, tosin paljon paremmin toteutettuna. Monet operaatiot esilasketaan ja taulukoidaan jo käännösaikana. Itse pelkäsin turhaan, että taulukoista tulee liian suuria, jotta niistä olisi hyötyä (cache misses). Toinen koodista mieleen jäänyt asia on asserttien systemaattinen ja runsas käyttö.

Hyvä että jollekin on ollut koodista iloa. Assertit ovat ystävä. Viljelen niitä itse aika paljonkin varsinkin kun koodi on yhtään vaikeampaa, jolloin suurin osa virheistä tulee havaittua lähellä sitä paikkaa, jossa ne ovat syntyneet, eikä vasta lopussa vastauksen ollessa virheellinen. Jos niitä ei halua mukaan lopulliseen versioon (itse yleensä mieluummin jätän jos sovellus ei ole nopeuskriittinen), -DNDEBUGilla saa ne jätettyä kääntämättä mukaan. Tällöin kannattaa huomata kuitenkin, ettei assert()in sisällä sovi olla sivuvaikutuksia, muuten tulos saattaa olla hämmentävä kun se koodi jää pois :)

Cache missejä pelätään minun havaintoni mukaan nykyään vähän liikaa. On niitäkin, jotka sanovat, että kaikki koodi pitäisi kääntää GCC:n -Os-vivulla (optimize for size), koska cache missit ovat niin paljon tärkeämpiä kuin mikään muu. Oma havaintoni on, että -O2 on pääsääntöisesti paljon nopeampi, ja (looppien unrollauksen ym. kautta) isompaa koodia tuottava -O3 yleensä vielä nopeampi. Järkeä -Os:ssä on minusta lähinnä sellaisen koodin ollessa kyseessä, jota oikeasti kutsutaan harvoin, koska tällöin kutsuvalla mahdollisesti kriittisemmällä koodilla on parempi mahdollisuus pysyä cachessa. (Esim. kerneli voi laajalti olla tällaista koodia.)

MOX kirjoitti:Eniten kuitenkin ihmetyttää itse algoritmi. Miten satunnaisesti etenevä ja itsensä välillä kokonaan resetoiva algoritmi voikin olla näin tehokas? Kokeilin nopeasti vastaavaa (ainakin käsittääkseni) muutosta ja Java-version nopeus liki kolminkertaistui. Minua kiinnostaisi tietää, miten ratkaisuun on päädytty, koska ratkaisu on mielestäni kaikkea muuta kuin intuitiivisesti selvä.

Idea tulee SAT-solvereiden (lauselogiikan toteutuvuustarkastimien) maailmasta, joka on minulle jonkin verran tuttu. Kyllä kai sitä tämäntapaisessa haussa käytetään usein muutenkin. "rapid restarts" lienee oikea hakusana, jos tuosta haluaa hakea lisätietoa.

Ideaa voisi yrittää perustella ainakin sillä, että ei-satunnaisille algoritmeille on olemassa sellaisia syötteitä, joissa rekursion alkuvaiheessa tehdyt ratkaisut käytännössä sulkevat oikean ratkaisun pois, mutta eivät johda nopeaan ristiriitaan ja sitä myötä backtrackäämiseen. Rapid restarttien kanssa kun tila välillä nollataan, tällaisesta umpikujasta päästään pois eikä siellä tuhlata kohtuutonta määrää aikaa.

MOX kirjoitti:Jotenkin tuntuu myös siltä, että näennäisesti pienet muutokset tehtävänannossa voisivat muuttaa merkittävästi koko tehtävän luonnetta. Esimerkiksi, jos tehtävätiedosto voisi sisältää myös huonostilaadittuja (ratkeamattomia) tehtäviä, niin satunnaisesti etenevät algoritmit olisivat vaikeuksissa?

Kyllä sellaisenkin haun voi toteuttaa samaan tyyliin, erona se, ettei restartissa nollata tilaa täysin. Tämä itse asiassa on se keino, jota näissä mainitsemissani SAT-solvereissa käytetään. Tällöin tila nollataan muuten, mutta haun aikana tallennetaan tehtyjä päätelmiä, joita sitten hyödynnetään myöhemmillä kierroksilla. Sudokun kyseessä ollessa tallennettavat päätelmät saattaisivat olla esimerkiksi muotoa "ruudussa 16 ei voi olla numeroa 6", tai "jos ruudussa 18 on numero 2, ruudussa 14 täytyy olla/ei voi olla numeroa 9". Harkitsin kyllä tällaisen toteuttamista omaankin ratkaisuuni, mutta tuntuu, että tässä siitä ei vielä välttämättä olisi ollut juuri hyötyä - melko iso osa ratkaisuista kuitenkin löytyy joko ilman restarttia tai vain muutaman restartin jälkeen.

SLi kirjoitti:

Muita kiinnostavia asioita tietää olisi osallistujoiden lukumäärä ja se, miten paljon toiseksi tullut hävisi. Tätä foorumia lukemalla tulee sellainen olo että mulla on ollut vähän onneakin mukana, taso on ilmeisesti ollut yllättävän kova.

Osallistujia oli reilut puoli tusinaa mutta osallistujien taso yllätti. Aikaeroja löytyi mutta kaikki olivat kuitenkin selkeästi panostaneet ratkaisuihinsa jonkin verran. Mitään täydellisiä räpellyksiä ei löytynyt lainkaan. Eroa toiseksi tulleeseen tuli useita sekunteja mutta loppupelissä noin tehokkailla toteutuksilla nämä jutut ovat aika pienestäkin kiinni kuten juuri tuosta syötteen lukemisesta.

Jos joku on kiinnostunut omasta suoritusajastaan niin voin kyllä laittaa niitä näkyviin.