Példaként mutatunk egy egyszerű 4x4-es feladványt és megadjuk egy megoldását (a megoldásban az egy ,,szélrózsához'' tartozó mezőket azonos betűkkel jeleztük):
. . . . . . . . . .
4 a-- 4 --a b
. . . . . . . | . . | .
0 c a 0 b
. . . . . . | . | . . | .
4 c a b-- 4
. . . . . . | . . . | .
4 4 --c---c b
. . . . . . . . . .
A feladványt a következő szemléletes módon is lehet értelmezni. A számokkal
jelzett mezőkön adott számú korongból álló tornyok vannak. A feladat az,
hogy az adott tornyot alkotó korongokat folytonosan leterítsük a négy égtáj
irányába, úgy hogy a tábla minden eredetileg üres mezőjére pontosan egy
korong kerüljön. A játék ilyen szemléltetésű változatának képekkel
illusztrált leírása megtalálható a
http://www.rubiksgames.com/coverup.html címen.
a/3 struktúrával ábrázoljuk, amelynek argumentumai a
tábla függőleges és vízszintes méretei (sorok és oszlopok száma),
valamint a tornyokat leíró lista:
% tábla ---> a(sor_max, oszlop_max, list(torony)). % sor_max == sorszám. % oszlop_max == oszlopszám.Egy tornyot egy
t/3 struktúrával adunk meg, ennek argumentumai a
torony elhelyezkedését megadó sor- ill. oszlopszám, valamint a torony
magassága:
% torony ---> t(sorszám, oszlopszám, magasság). % sorszám == int. % 1,2,... % oszlopszám == int. % 1,2,... % magasság == int. % 0,1,...A fenti példa Prolog alakja tehát:
a(4,4, % 4 soros, 4 oszlopos tábla
[t(1,2,4), % az 1. sor 2. oszlopában egy 4 magas torony
t(2,3,0), % a 2. sor 3. oszlopában egy 0 magas torony, stb.
t(3,4,4),t(4,1,4)])
A megoldást szélrózsák listájaként várjuk, az i. szélrózsa a
torony-lista i.-edik elemének felel meg. Egy szélrózsa egy s/4
struktúra, amelynek argumentumai rendre az északi, nyugati, déli és
keleti irányba lerakandó korongok számát (vagyis a rajzolandó vonal
hosszát) adják meg. Ezek a számok természetesen lehetnek 0 értékűek,
ha az adott irányba nem kell korongot lerakni.
% megoldás == list(szélrózsa). % szélrózsa ---> s(észak, nyugat, dél, kelet). % észak == int. % 0,1,... % nyugat == int. % 0,1,... % dél == int. % 0,1,... % kelet == int. % 0,1,...A megadott példafeladat korábban felrajzolt megoldását tehát a következő formában kell előállítani:
[s(0,1,2,1), % észak: 0, nyugat: 1, dél: 2, kelet: 1 korong, stb.
s(0,0,0,0),s(2,1,1,0),s(2,0,0,2)],
% :- pred szelrozsa(tábla::in, megoldás::out). % szelrozsa(+Tábla, -Szélrózsák): Szélrózsák hézagmentesen % és helyesen lefedik a Táblát.A
szelrozsa/2 eljárásnak a feladat minden megoldását elő kell állítania,
mindegyiket pontosan egyszer. A megoldások sorrendje érdektelen.
A megoldásnak CLP-módszerekre kell épülnie. Bármelyik SICStus CLP könyvtár használható. Nem elfogadható olyan program, amelyben a megoldó algoritmus lényege Prolog-ban van és CLP könyvtárat egyáltalán nem, vagy csak kisebb részfeladatokra használ!
Hiányos dokumentáció esetén a megoldás nem bírálható el.
szelrozsak.pl nevű allományban kell elhelyezni. Megengedett
Prolog modulok használata, ekkor a szelrozsak.pl szövegében el kell
helyezni a többi állomány betöltését végző direktívákat. Az összes
állományt egy VezeteknevKeresztnev nevű könyvtárban kell elhelyezni.
(Pl. Nagy Péter Sándor a saját megoldását a NagyPeterSandor könyvtárba
helyezze el. A könyvtárnév ékezeteket ne tartalmazzon!)
A megoldást tartalmazó könyvtárat kérem zip vagy tar.gz formában a
szeredi-nlp-hf@iqsoft.hu
címre beküldeni. A beadás folyamatos, végső határideje a vizsgaidőpont
előtti 3. nap 24:00, azaz január 23., kedd 24:00.
Egy ilyen feladat esetén az összes megoldás előállítása nem igényelhet többet néhány másodpercnél.
Nagyobb példa-feladatok találhatók itt. Ezekhez hasonló méretű feladatokat használunk majd a beadott megoldások tesztelésére. A tesztelést a kempelen.iit.bme.hu gépen végezzük majd, 30 másodperces idő-korláttal (az összes megoldás előállítására).
Megjegyzéseket a szeredi@iqsoft.hu címre várunk.
Utoljára Szeredi Péter módosította 2000. november 6-án.