BME Villamosmérnöki és Informatikai Kar
Műszaki informatika szak

Nappali tagozat

2002/2003-es tanév, őszi félév

Nagyhatékonyságú logikai programozás

Házi feladat, 1.0. változat

Bűvös csiga

Ez a leírás a Nagyhatékonyságú logikai programozás c. tárgyból kiadott féléves házi feladatot ismerteti.

A feladvány

Adott egy n*n mezőből álló négyzet alakú tábla, amelynek egyes mezőiben 1 és m közötti számok szerepelnek. A feladat az, hogy további 1 és m közötti számokat helyezzünk el a táblában úgy, hogy az alábbi feltételek teljesüljenek:

Minden sorban és minden oszlopban az 1..m számok mindegyike pontosan egyszer szerepel.
A bal felső sarokból induló csigavonal mentén a számok rendre az1,2,...m,1,2,...,m,...sorrendben követik egymást.

A csigavonalat a következőképpen definiáljuk. Először a négyzet első sorában haladunk balról jobbra, majd az utolsó oszlopban felülről lefelé. Ezután az utolsó sorban megyünk jobbról balra, majd az első oszlopban alulról felfelé, egészen a 2. sor 1. mezőjéig. Miután így bejártuk a négyzetes tábla szélső sorait és oszlopait, rekurzívan folytatjuk a bejárást a 2. sor 2. mezőjében kezdődő

 (n-2)*(n-2)

mezőből álló négyzettel.

Az 1. ábra egy feladványt ábrázol, a 2. ábra ennek (egyetlen) megoldását mutatja.

-----------------------\
                  2     |
/-------------------\   |
|     1             |   |
|   /-----------\   |   |
|   |           |   |   |
|   |   /---\   |   |   |
|   |   |       |   | 1 |
|   |   \-------/   |   |
|   |               |   |
|   \---------------/   |
|                       |
\-----------------------/

-----------------------\
  1   -   -   -   2   3 |
/-------------------\   |
| -   1   2   3   - | - |
|   /-----------\   |   |
| - | 3   1   2 | - | - |
|   |   /---\   |   |   |
| - | 2 | 3   - | - | 1 |
|   |   \-------/   |   |
| 3 | -   -   -   1 | 2 |
|   \---------------/   |
| 2   -   -   1   3   - |
\-----------------------/

1. ábra. Egy feladvány(n=6, m=3) 2. ábra. A feladvány megoldása

A megoldandó feladat

Írjon buvos_csiga néven olyan Prolog-eljárást, amely egy feladvány összes megoldását előállítja!

Az 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

     csiga(N, M, As)

felépítésű struktúra, ahol

N a négyzetes tábla mérete, azaz sorainak, ill. oszlopainak a száma ( N >= 1);
M a csigavonal ciklusa, azaz az egy sorban/oszlopban levő nem-üres mezők száma; minden sorban és oszlopban az 1..M számok pontosan egyszer fordulnak elő (1 <= M <= N)
As az előre kitöltött mezőket leíró lista. A lista egyes elemei i(Sor,Oszlop,Érték) alakú struktúrák. Egy ilyen elem azt írja elő, hogy a tábla Sor számú soránakOszlopszámú oszlopában az Érték szám áll. AzAslista a (Sor,Oszlop) párok szerint lexikografikusan rendezett.

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

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

A Prolog-eljárás kimenő paramétere a kitöltött tábla. Ezt sorok listájaként kell előállítani, ahol az egyes sorok egész számokból álló listák. Ez utóbbi lista minden eleme a tábla egy mezőjét írja le: a 0 számérték jelenti az üres helyet, míg a nem-nulla I érték azt jelenti, hogy az adott helyen az I szám áll.

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

     [[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]]

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

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

% :- type feladvany_leiro ---> csiga(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 csigatabla        == list(sor).
% :- type sor               == list(ertek_vagy_ures).
% :- type ertek_vagy_ures   == integer.

% :- pred buvos_csiga(feladvany_leiro::in, csigatabla::out).

A buvos_csiga/2 eljárás első,

 feladvany_leiro

típusú paramétere mindenképpen kielégíti az alábbi feltételt:

helyes_feladvany_leiro(csiga(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.

A megoldásban tehát feltételezheti, hogy a bemenő argumentumra a


helyes_feladvany_leiro/1

eljárás sikeresen lefut (csak ilyen adattal teszteljük majd a programot).

A keretprogram

Programjait keretprogramok segítségével próbálhatja ki. A keretprogramot és 95 tesztfeladatot tartalmazó csomagot innen letöltheti.

A keretprogram bemenete egy olyan szöveges állomány, amelynek első két sora a feladványtábla mérete és a csigavonal ciklusa. Az ezt követő sorok mindegyikében három szám áll, amelyek az adott elemek sorszámát, oszlopszámát ill. értékét írják le (ld. 3. ábra, vö. 1. ábra).

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 keretprogram három eljárást exportál:

csiga_be(file::in, feladvany_leiro::out): A megnevezett szöveges állományból beolvassa a feladványleírót, és visszaadja a második argumentumban.
csiga_ki(file::in, csigatabla::in): A megnevezett szöveges állományba kiírja az adott megoldást.
megold(file::in, file::in): Beolvas egy feladványleírót 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 buvos_csiga/2 eljárásra.

A keretprogram felhasználja a file típust:

     % :- type file == atom.

A file típusú paraméterben a user atomot megadva a terminálról vihetünk be, ill. a terminálra irathatunk ki adatokat. Egyébként a megadott nevű állományba írunk, ill. állományból olvasunk.

Dokumentációs követelmények

Mindkét programot úgy írja meg (választása szerint vagy magyarul, vagy angolul), hogy a szövegük jól olvasható legyen: válasszon értelmes neveket, specifikálja a paraméterek és más azonosítók szerepét és értelmezési tartományát, magyarázza meg az egyes eljárások ill. függvények feladatát és működését! Írjon minden eljáráshoz és függvényhez fejkommentet!

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

Tervezés, az egyes eljárások specifikálása
Kódolás, az algoritmusok ismertetése
Tesztelési megfontolások
Kipróbálási tapasztalatok

Fogalmazzon világosan és tömören, ügyeljen a helyes nyelvhasználatra és a helyesírási szabályok betartására! Az indokoltan elvárható formai követelmények be nem tartását, a gondatlan kivitelt szankcionáljuk.

A dokumentációt elektronikus formában adja be, HTML, esetleg ASCII formátumban, ill. azt a beadott program szövegében is elhelyezheti kommentárként.

A beadás módja

A beadás módját később ismertetjük.

szeredi@inf.bme.hu

Utolsó módosítás: 2002. 11. 4.