Egyikotok irta:
A gyorsítás viszont nem nagyon megy...Kipróbáltam
minden trükköt, amit anno
deklapónál használtam, de csak lassítottak rajta.
Van egy olyan, hogy ha egy oszlopban (sorban stb.) csak egy elem domainjében
szerepel pl. a 4-es, akkor behelyettesíti arra. Ezt megírtam globális
korlátként, de csak lassított a futáson. Elképzelhetõ, hogy a clpfd (az
all_different hatására mondjuk) már észreveszi ezt az esetet?
Az all_different csak akkor, ha megfelelo opciot adsz neki, de az
all_distinct alapertelmezesben tartomanykonzisztenciat biztosit, tehat
annak hasznalatakor biztosan felesleges ez a plusz globalis korlat.
Ami fontos tehat:
1. Hasznaljatok tartomany-szukito korlatokat:
a. all_distinct (es nem all_different)
b. az s es w infoknak megfelelo tavolsag-korlatokhoz is erdemes egy
tartomany-szukito megoldast talalni.
2. Hasznaljatok borotvalast.
3. Hasznaljatok redundans korlatokat.
Az en viszonylag egyszeru megoldasom futasa a kovetkezokeppen alakul:
1. megvalositasa eseten (2. es 3. nelkul) lefut 6 teszteset (tehat mar boven
ervenyes a nagyhazi).
1.+2. megvalositasa eseten lefut 8 teszteset.
1.+2.+3. megvalositasa eseten lefut mind a 10 teszteset.
(A fenti "lefutott" tesztesetek eseten legalabb 3-szoros az en futasi
idomhoz kepest a idokorlat.)
Nikhazy Laci programjaval az osszes teszteset lefutott szumma 20 mp
korul. Laci, nyugodtan ird meg a listara, hogy milyen *jellegu*
optimalizaciokat hasznaltal (persze reszletek nelkul).
Kicsit reszletesebben irok meg a 2. es 3. "tanacsokrol".
A borotvalasban talan az a legosszetetebb, hogy hogyan agyazzuk be a
cimkezesbe. Ket lehetoseg:
- nem hasznaljuk a konyvtari labeling eljarast, helyette egy sajat cimkezot
irunk. Ebben a cimkezoben minden n. cimkezesi lepes utan meghivjuk a
borotvalast (ahol n egy kiserletileg megallapitando konstans -- az en
programomnal 2 vagy 3 latszott a legjobbnak).
Hatrany: elveszitjuk a konyvtari cimkezes elonyeit (pl. a hatekony
valtozo-kivalasztas), vagy ezeket be kell programoznunk.
- a konyvtari labeling eljarast hasznaljuk, es a myval opcioval vesszuk at
a vezerlest minden cimkezesi lepes elott. Persze ilyenkor is erdemes csak
minden n. cimkezesi lepesben hajtani vegre a borotvalast, de most ezt
csak globalis valtozok hasznalataval tudjuk elerni (lasd bb_put, bb_get
beepitett eljarasok).
Hatrany: ezeket a speci dolgokat (myval, bb_*) fel kell deriteni.
Maga a borotvalas ugye abbol all, hogy vegigmegyunk a sudoku tablan, es
megprobalunk egyes -- meg be nem helyettesitett -- mezoket szukiteni oly
modon, hogy kivalasztunk egy lehetseges erteket, es megnezzuk, hogy ha erre
helyettesitunk, akkor ez meghiusulast okoz-e. Ha igen, akkor nyertunk, ezt
az erteket kizarhatjuk az adott valtozo lehetseges ertekei kozul. Ha nem,
akkor nem volt szerencsenk, es nem tudunk szukiteni (es a behelyettesites
miatt felebresztett demonok munkaja karba veszett).
A fenti eljarast erdemes lehet nem az osszes mezore elvegezni, mert az sok
karbaveszett munkahoz vezethet. Egy lehetseges korlatozas, hogy csak azokat
a mezoket borotvaljuk, ahol mar keves lehetseges ertek van. Ha pl. egy
olyan mezot borotvalunk, ahol mar csak ket ertek van, es szerencsenk van,
akkor be is tudjuk helyettesiteni az adott mezo erteket.
Ami a redundans korlatokat illeti, szobajohetnek:
- a klasszikus (tavolsagkorlatok nelkuli) sudokura vonatkozo redundans
korlatok.
- a tavolsaginfokra vonatkozo redundans korlatok.
Nyugodtan kerdezzetek, ha valami nem vilagos.
-Peter