Ujjak

A feladvány

1. Egy ujj a nyolc alapirány (két vízszintes, két függőleges és négy átlós) bármelyikébe mutathat, feltéve, hogy a táblának legalább egy mezőjére rámutat, és nem valamelyik főátló irányába mutat.
2. A tábla minden 0-tól 8-ig számozott mezője felé pontosan annyi ujjnak kell mutatnia, amekkora szám áll a mezőben.
3. A 9-et tartalmazó mezők felé akárhány ujj mutathat.

Az ujjakat a karakteres ábrákon a | \ - / karakterekkel jelöljük. (Ezek jelentése mindig egyértelmű, mivel az ujjak csak a tábla belsejébe mutathatnak.)

Az 1. ábra egy feladványt ábrázol, a 2. ábra ennek megoldásait mutatja.

+---+---+---+---+ | 9 | 4 | 9 | 3 | +---+---+---+---+ | 9 | 3 | 1 | 2 | +---+---+---+---+ | 2 | 4 | 9 | 1 | +---+---+---+---+ | 3 | 6 | 4 | 9 | +---+---+---+---+		\ | \ / \ | \ / +---+---+---+---+ +---+---+---+---+ \ | 9 | 4 | 9 | 3 | - \ | 9 | 4 | 9 | 3 | - +---+---+---+---+ +---+---+---+---+ \ | 9 | 3 | 1 | 2 | \ / | 9 | 3 | 1 | 2 | \ +---+---+---+---+ +---+---+---+---+ \ | 2 | 4 | 9 | 1 | \ \ | 2 | 4 | 9 | 1 | \ +---+---+---+---+ +---+---+---+---+ - | 3 | 6 | 4 | 9 | - - | 3 | 6 | 4 | 9 | - +---+---+---+---+ +---+---+---+---+ / | / \ / | \ \
1. ábra. Egy feladvány (n=4)		2. ábra. A feladvány megoldásai

A megoldandó feladat

A Prolog-eljárásnak két paramétere van. Első (bemenő) paramétere a feladványt, második (kimenő) paramétere a megoldást írja le. Az eljárásnak a visszalépések során minden megoldást pontosan egyszer kell kiadnia. Ha a feladványnak nincs megoldása, az eljárás hiúsuljon meg.

A Prolog-eljárás bemenő paramétere egy 0 és 9 közötti egész számok azonos hosszúságú listáiból álló lista, amely a tábla sorait, azon belül az egyes mezőit írja le.

Az 1. ábrán bemutatott feladvány esetén például a Prolog-eljárás bemenő paramétere:

[[9,4,9,3],   % a tábla első sora
 [9,3,1,2],
 [2,4,9,1],
 [3,6,4,9]]   % a tábla utolsó sora

A Prolog-eljárás kimenő paramétere egy u(Észak, Kelet, Dél, Nyugat) struktúra, amelynek argumentumai listák, és rendre a tábla északi, keleti, déli és nyugati szélén elhelyezett ujjak irányát adják meg. Az egyes irányokat az s, sw, w, nw, n, ne, e, se atomokkal írjuk le, ezek jelentése rendre dél, délnyugat, nyugat, északnyugat, észak, északkelet, kelet, délkelet.

A 2. ábrán látható első megoldást írja le az alábbi kifejezés:

u([se,s,se,sw],[w,nw,nw,w],[ne,n,ne,nw],[se,se,se,e])

    [se,s,se,sw]
     \  |  \  /
[                [
se, \          - w,
se, \          \ nw,
se, \          \ nw,
e   -          - w
]                ]
     /  |  /  \
    [ne,n,ne,nw]

A megírandó eljárás specifikációja

A ujjak/2 Prolog-eljárás paramétereinek típusát a következő - megjegyzésként megadott - Prolog-típusdefiníciók írják le.

% :- type mezo         ---> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9.
% :- type sor            == list(mezo).
% :- type ujjtabla       == list(sor).

% :- type ujj          ---> s | sw | w | nw | n | ne | e | se.
% :- type ujjak          == list(ujj).
% :- type peremezes    ---> u(ujjak, ujjak, ujjak, ujjak).

% :- pred ujjak(ujjtabla::in, peremezes::out).

helyes_feladvany(Tabla) :-
        %% négyzet alakú
        length(Tabla, N),
        all_same_length(Tabla, N),
        %% nem üres
        N \= 0,
        %% nincs nem helyes eleme a Tabla ujjtáblának
        \+ (   member(Sor, Tabla),
               member(Mezo, Sor),
               \+ helyes_mezo(Mezo)
           ).

% all_same_length(Ls, L): az Ls elemei listák, hosszuk azonosan L.
all_same_length([], _).
all_same_length([L|Ls], N) :-
        length(L, N),
        all_same_length(Ls, N).

% helyes_mezo(+Mezo): Mezo egy helyes mezőt ír le
helyes_mezo(D) :- number(D), 0 =< D, D =< 9.

A keretprogram

A keretprogram bemenete egy olyan szöveges állomány, amelynek minden sora a tábla egy-egy sorát írja le. Ezekben a sorokban 0 és 9 közötti számjegyek fordulhatnak elő, szóközökkel elválasztva (ld. 3. ábra, vö. 1. ábra).

9 4 9 3 9 3 1 2 2 4 9 1 3 6 4 9

3. ábra. A bemenő állomány tartalma az 1. ábrán látható feladvány esetén

A keretprogram kimenete a 2. ábrán bemutatotthoz hasonló tartalmú szöveges állomány.

A Prolog-keretprogram

helyes_feladvany(ujjtabla::in)

A fent ismertetett feladvány-ellenőrző eljárás.

ujjak_be(file::in, ujjtabla::out)

A megnevezett szöveges állományból beolvassa az ujjtáblát, és visszaadja a második argumentumban.

ujjak_ki(file::in, ujjtabla::in, peremezes::in)

A megnevezett szöveges állományba kiírja az adott megoldást.

megold(file::in, file::in)

Beolvas egy feladványt az első paraméterként kapott állományból, és kiírja az ahhoz tartozó összes megoldást a második paraméterben megadott állományba. Ehhez természetesen szüksége van a ujjak/2 eljárásra.

stopper(file::in, file::in)

Mint megold/2, de a futás végén kiírja a futási időt is.

A keretprogram felhasználja a file típust:

% :- type file == atom.

Használat: a saját programját a ujjak.pl nevű állományba tegye, különben a keretprogram nem találja meg. Ezután futtassa a SICStus interpretert, és töltse be a keretprogramot:

SICStus 3.11.2 (x86-linux-glibc2.2): Thu Jun 27 22:46:49 CEST 2002
Licensed to BUTE DP course
| ?- [kujjak].
% consulting /home/david/uni/dp/02a/nhf/kujjak.pl...
%  module ujjak_keret imported into user
%  loading /usr/local/lib/sicstus-3.11.2/library/lists.po...
%  module lists imported into ujjak_keret
%  loaded /usr/local/lib/sicstus-3.11.2/library/lists.po in module lists, 0 msec 11656 bytes
% consulted /home/david/uni/dp/02a/nhf/kujjak.pl in module ujjak_keret, 20 msec 29168 bytes
yes
| ?- stopper(..., ...).

Dokumentációs követelmények

A programhoz készítsen dokumentációt; vagy magyarul, vagy angolul. A dokumentáció tartalma legalább a következő legyen:

• Követelmények elemzése
• Modellezés: korlát-változók és tartományaik, valamint a korlátok megválasztása
• Esetleges felhasználói korlátok (globális korlátok, FD-predikátumok) ismertetése
• Címkézési módszerek (pl. borotválás) bemutatása
• Kipróbálási tapasztalatok

A dokumentációt elektronikus alakban adja be, HTML, PS, PDF, esetleg ASCII formátumban.

Egyéb követelmények és tudnivalók

A programok készülhetnek MS DOS vagy MS Windows alatt is, de Unix (linux) alatt is működniük kell. A beadott programokat Unix környezetben a SICStus Prolog 3.12.2, rendszerrel teszteljük.

A beadás módja