A számtekercs feladvány

Az 2. nagy házi feladat

Az eljárás első, bemenő paramétere a feladványt írja le, a második, kimenő paraméter a feladvány egy megoldása. 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 második, kimenő paraméterben kell előállítani a kitöltött táblát, egész számokból álló listák listájaként. Minden egyes szám a tábla egy-egy mezőjének az értéket adja meg: ha a szám 0, akkor a mező üres, egyébként pedig egy i egész szám, ahol 1 =< i =< m.

Az 1. ábrán bemutatott feladvány esetén például a tekercs/2 predikátum első (bemenő) paramétere ez kell legyen:

     szt(6,3,[i(1,5,2),i(2,2,1),i(4,6,1)])

Az eljárás feladata, hogy (visszalépések során) állítsa elő a feladvány összes megoldását. A 2. ábrán látható (egyetlen) megoldást írja le az alábbi, listák listájaként ábrázolt mátrix:

      [[1,0,0,0,2,3],
       [0,1,2,3,0,0],
       [0,3,1,2,0,0],
       [0,2,3,0,0,1],
       [3,0,0,0,1,2],
       [2,0,0,1,3,0]]

Prolog-specifikációk

A szamtekercs/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 feladvany_leiro ---> szt(meret, ciklus, list(adott_elem)).
% :- type meret             == integer.
% :- type ciklus            == integer.
% :- type adott_elem      ---> i(sorszam, oszlopszam, ertek).
% :- type sorszam           == integer.
% :- type oszlopszam        == integer.
% :- type ertek             == integer.
		          
% :- type megoldas          == list(sor).
% :- type sor               == list(ertek).
% :- type ertek             == integer.

% :- pred szamtekercs(feladvany_leiro::in, megoldas::out).

helyes_feladvany_leiro(szt(Meret,Ciklus,Adottak)) :-
	integer(Meret), integer(Ciklus),
	Meret >= 1, Ciklus >= 1,
	Ciklus =< Meret,
        % nincs nem helyes eleme az Adottak listának:
	\+ (   member(Adott, Adottak), 
	       \+ helyes_adott_elem(Meret, Ciklus, Adott)
	   ),  
	% az Adottak lista lexikografikusan rendezett:
	sort(Adottak, Adottak),
	% Az Adottak lista minden eleme különböző (Sor,Oszlop) 
	% koordinátára vonatkozik (a rendezettség miatt elegendő a
        % szomszédos elemekre kikötni ezt):
	\+ append(_, [i(S,O,_),i(S,O,_)|_], Adottak).

helyes_adott_elem(Meret, Ciklus, i(Sor,Oszlop,Ertek)) :-
	integer(Sor), integer(Oszlop), integer(Ertek),
	1 =< Sor, Sor =< Meret,
	1 =< Oszlop, Oszlop =< Meret,
	1 =< Ertek, Ertek =< Ciklus.

Példa

Az alábbi Prolog hívás az 1. ábrán látható feladványt oldja meg, az Mx változóban sorolva fel a megoldásokat. Mivel a feladványnak csak egy megoldása van, az alábbi tekercs/2 hívás csak egy sikeres választ ad, amely a 2. ábrán látható megoldásnak felel meg:

  | ?- tekercs(szt(6,3,[i(1,5,2),i(2,2,1),i(4,6,1)]), Mx).
  Mx = [[1,0,0,0,2,3],
        [0,1,2,3,0,0],
        [0,3,1,2,0,0],
        [0,2,3,0,0,1],
        [3,0,0,0,1,2],
        [2,0,0,1,3,0]] ? ;
  no

Egyéb követelmények

Megoldásában tetszőleges Prolog-könyvtárakat használhat, kivéve a clpfd, clpq, clpr, clpb, chr és atts könyvtárakat: az ezeket felhasználó megoldásokat nem fogadjuk el, így a létraversenyben sem vehetnek részt, és megajánlott jegyet sem kaphatnak. Hasonlóképpen tiltott a mellékhatásos beépített eljárások, így az assert, retract, bb_put, bb_get stb. használata.

A beadott programokat Linux környezetben SICStus Prolog 4 rendszerrel teszteljük.

Dokumentációs követelmények

Egyéb tudnivalók