Kígyó

A feladvány

1. A kígyó az éleik mentén érintkező mezőkből áll, amelyek az előre meghatározott kezdőpontot és végpontot kötik össze.
2. A számozott mezők nyolc él- és sarokszomszédja közül pontosan annyi mezőnek kell a kígyóhoz tartoznia, amekkora szám szerepel az adott mezőn. (Ez a feltétel hasonló a közismert aknakereső feladványban szereplő feltételhez.)
3. Számmal jelzett mezőn nem lehet kígyó.
4. A kígyó nem keresztezheti önmagát. A kígyóhoz tartozó, nem szomszédos mezők legfeljebb a sarkukkal érinthetik egymást, az éleik nem lehetnek közösek. (Tehát a kígyó nem teheti meg, hogy például megy felfele 2 mezőt, azután 1-et jobbra, majd 1-et lefele.)
5. A kezdő- és a végpont is csak a sarkukkal érintkezhetnek, emiatt nem szerepelhet 8-as a mezőkben.

Az 1. ábra egy feladványt ábrázol, a 2. ábra ennek (egyetlen) megoldását mutatja. (K: Kezdőpont, V: Végpont, @: a kígyó további mezői.)

  +---+---+---+---+---+
  | K |   | V |   |   |
  +---+---+---+---+---+
  |   |   | 5 |   |   |
  +---+---+---+---+---+
  | 4 |   |   |   |   |
  +---+---+---+---+---+
  |   |   |   |   |   |
  +---+---+---+---+---+
  |   |   |   | 3 |   |
  +---+---+---+---+---+

  +---+---+---+---+---+
  | K |   | V | @ |   |
  +---+---+---+---+---+
  | @ | @ | 5 | @ | @ |
  +---+---+---+---+---+
  | 4 | @ |   |   | @ |
  +---+---+---+---+---+
  |   | @ | @ | @ | @ |
  +---+---+---+---+---+
  |   |   |   | 3 |   |
  +---+---+---+---+---+

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

    k(S-O,KS-KO,VS-VO,RefPL)

• S és O a tábla mérete, azaz sorainak és oszlopainak a száma (a tábla bal felső mezője az első sor első oszlopában van);
• KS és KO a kezdőpont koordinátái.
• VS és VO a végpont koordinátái.
• RefPL a referenciapontok listája, ahol a lista p(Sor,Oszlop,Érték) alakú elemekből áll. Ezek határozzák meg a számot tartalmazó mezők pozícióját és értékét. A lista lexikografikusan rendezett.

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

    k(5-5, 1-1, 1-3, [p(2,3,5),p(3,1,4),p(5,4,3)]) 

A Prolog-eljárás kimenő paramétere a kezdőponttól a végpontig vezető mezők koordinátáinak a listája (a kezdő és a végpontokat is beleértve).

A 2. ábrán látható megoldást írja le az alábbi lista:

    [1-1,2-1,2-2,3-2,4-2,4-3,4-4,4-5,3-5,2-5,2-4,1-4,1-3] 

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

A kigyo/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 kigyotabla      ---> k(meret, pont, pont, list(ref_pont)). 
% :- type ref_pont        ---> p(sor, oszlop, ertek). 
% :- type sor               == integer. 
% :- type oszlop            == integer. 
% :- type ertek             == integer. 
% :- type pont            ---> sor-oszlop.
% :- type meret           ---> sor-oszlop.
% :- type kigyovonal        == list(pont).

% :- pred kigyo(kigyotabla::in, kigyovonal::out).

helyes_feladvany(k(Meret,KPont,VPont,RefPL)) :-
	% a tábla mérete helyes:
	helyes_pont(Meret,inf-inf),
	% a kezdő és a végpont helyesek:
	helyes_pont(KPont, Meret),
	helyes_pont(VPont, Meret),
	% a kezdő és a végpont nem lehet ugyanaz a pont,
	% és nem lehetnek élszomszédosak sem,
	% azaz távolságuk nagyobb 1-nél
	tavolsaga(KPont, VPont, Tav), Tav > 1,
        % nincs nem helyes eleme a RefPL listának:
 	\+ (   member(Ref, RefPL),  
	       \+ helyes_referencia(Ref, Meret) 
	   ),   
	% a RefPL lista lexikografikusan rendezett:
 	sort(RefPL, RefPL), 
	% A RefPL lista minden eleme különböző (Sor,Oszlop)
  	% koordinátára vonatkozik (a rendezettség miatt elegendő ezt a
        % szomszédos elemekre kikötni):
 	\+ append(_, [i(S,O,_),i(S,O,_)|_], RefPL). 
 
helyes_pont(S-O, MaxS-MaxO) :-
	integer(S), S >=1, S =< MaxS,
	integer(O), O >=1, O =< MaxO.

tavolsaga(S1-O1, S2-O2, T) :-
	T is sqrt( (S1-S2)**2 + (O1-O2)**2 ).

helyes_referencia(p(Sor,Oszlop,Ertek), Meret) :-
	helyes_pont(Sor-Oszlop, Meret),
	0 =< Ertek, Ertek =< 7.

A keretprogram

A keretprogram bemenete egy olyan szöveges állomány, amelynek első sorában a sor- és oszlopszám szerepel, második sorában a kezdősor és kezdőoszlop, harmadik sorában a végsor és végoszlop. Az ezt követő sorok mindegyikében három szám áll, amelyek az adott referenciapont sor- és oszlopszámát, valamint értékét adják meg. Ezekre a számokra a már fent említett korlátok vonatkoznak, tehát a sor- és oszlopszámok a táblán belüli mezőt azonosítanak, a referenciapont értéke pedig 0 és 7 közé esik (ld. 3. ábra, vö. 1. ábra).

 5 5
 1 1
 1 3
 2 3 5
 3 1 4
 5 4 3

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

A Prolog-keretprogram

helyes_feladvany(kigyotabla::in)

A fent ismertetett feladványellenőrző eljárás.

kigyó_be(file::in, kigyotabla::out)

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

kigyo_ki(file::in, kigyotabla::in, kigyovonal::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 kigyo/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 kigyo.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.10.0 (x86-linux-glibc2.2): Thu Jun 27 22:46:49 CEST 2002
Licensed to BUTE DP course
| ?- compile(kkigyo).
% consulting /home/david/uni/dp/03s/nhf/kkigyo.pl...
%  module kigyo_keret imported into user
%  loading /usr/local/lib/sicstus-3.9.1/library/lists.po...
%  module lists imported into kigyo_keret
%  loaded /usr/local/lib/sicstus-3.9.1/library/lists.po in module lists, 0 msec 11656 bytes
% consulted /home/david/uni/dp/03s/nhf/kkigyo.pl in module kigyo_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
• Tervezés, az egyes eljárások, ill. függvények specifikálása
• Kódolás Prolog-nyelven, az algoritmusok ismertetése
• Tesztelési megfontolások
• Kipróbálási tapasztalatok

A dokumentációt elektronikus alakban adja be, HTML, 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.10.1 rendszerrel teszteljük.

A beadás módja