Nagyhatékonyságú logikai programozás

Házi feladat, 1.4. változat

Sátrak

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

Egy téglalap alakú kert négyzet alakú, egyforma parcellákra van felosztva. Kezdetben a parcellák többsége üres, egyes parcellákon egy-egy fa áll. Az üres parcellákon - egy-egy szomszédos fához kötve - sátrakat állíthatunk fel, az alábbi feltételekkel:

egy parcellán legfeljebb egy fa vagy egy sátor lehet,
minden fához pontosan egy sátrat kell kötni,
egy sátor akkor köthető egy fához, ha a parcellák, amelyeken állnak, oldalszomszédok,
olyan parcellák, amelyeken sátrak állnak, sem oldal-, sem sarokszomszédok nem lehetnek.

Összesen n*m parcella van a kertben (hosszában n, széltében m). Ismerjük a fák pontos helyét, továbbá a sátrak számát soronként és oszloponként. A fát, amelyhez a sátor hozzá van kötve, a sátor saját fájának nevezzük. Meghatározandó a sátrak helyzete a saját fájukhoz képest. Példa:


      1 --------> m
      1  0  2  0  2 
1   +--+--+--+--+--+
  1 |  |F |  |  |  |
|   +--+--+--+--+--+
| 1 |  |  |  |  |  |
|   +--+--+--+--+--+
| 0 |  |  |F |  |F |
|   +--+--+--+--+--+
v 3 |  |  |  |  |  |
    +--+--+--+--+--+
n 0 |F |  |  |  |F |
    +--+--+--+--+--+



    1  0  2  0  2
  +--+--+--+--+--+
1 |  | F-S |  |  |
  +--+--+--+--+--+
1 |  |  |  |  |S |
  +--+--+--+--+|-+
0 |  |  |F |  |F |
  +--+--+|-+--+--+
3 |S |  |S |  |S |
  +|-+--+--+--+|-+
0 |F |  |  |  |F |
  +--+--+--+--+--+

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

Előfordulhat, hogy egyes sorokban, ill. oszlopokban nem írjuk elő a sátrak számát: ezt a megfelelő sor, ill. oszlop elején álló negatív szám jelzi. Példa:


      1 --------> m
      1  0 -1  0  2 
1   +--+--+--+--+--+
  1 |  |F |  |  |  |
|   +--+--+--+--+--+
| 1 |  |  |  |  |  |
|   +--+--+--+--+--+
|-1 |  |  |F |  |F |
|   +--+--+--+--+--+
v 3 |  |  |  |  |  |
    +--+--+--+--+--+
n 0 |F |  |  |  |F |
    +--+--+--+--+--+

3. ábra. Negatív szám jelzi, ha nem írjuk elő a sátrak számát egy-egy sorban vagy oszlopban

A megoldandó feladat

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

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

satrak(Ss, Os, Fs)

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

Ss a sátrak soronkénti számát tartalmazó lista,
Os a sátrak oszloponkénti számát tartalmazó lista és
Fs a fák sorát és oszlopát azonosító (i,j) párok lexikografikusan rendezett listája.

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

satrak([1,1,0,3,0], [1,0,2,0,2], [1-2,3-3,3-5,5-1,5-5])

ahol az (i,j) párt i-j alakú Prolog-struktúrával írjuk le.

A Prolog-eljárás kimenő paramétere egy olyan lista, amely - a fák Fs-beli megadási sorrendjét követve - a sátrak saját fájukhoz viszonyított helyzetét írja le. Egy sátor helyzetét a megfelelő égtájat jelölő betűvel adjuk meg:

w (west) - a sátor a saját fájától nyugatra áll, n (north) - a sátor a saját fájától északra áll,

e (east) - a sátor a saját fájától keletre áll, s (south) - a sátor a saját fájától délre áll.

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

[e,s,n,n,n]

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

A satrak/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 fLeiro  ---> satrak(sSzS, sSzO, list(parc)).
% :- type sSzS    == list(int).
% :- type sSzO    == list(int).
% :- type parc    == int-int.
% :- type irany   ---> n    % észak
%                 ;    e    % kelet
%                 ;    s    % dél
%                 ;    w.   % nyugat
% :- type sHelyek   == list(irany).
% :- pred satrak(fLeiro::in, sHelyek::out).

A keretprogram

Programját keretprogram segítségével próbálhatja ki. A keretprogramot egy 32 mintapéldából álló tesztsorral együtt innen letöltheti.

A keretprogram bemenete egy olyan szöveges állomány, amelynek soraiban a feladványmátrix sorai vannak; az üres parcellákat "-" jel jelöli.

1 0 2 0 2 1 - F - - - 1 - - - - - 0 - - F - F 3 - - - - - 0 F - - - F

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

satrak_be(file::in, fLeiro::out): A megnevezett szöveges állományból beolvassa a feladványleírót, és visszaadja a második argumentumban.
satrak_ki(file::in, sHelyek::in, fLeiro::in): A megnevezett szöveges állományba kiírja az adott megoldást a sátorhelyek és a feladványleíró alapján.
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 satrak/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

A programot úgy írja meg (választása szerint vagy magyarul, vagy angolul), hogy a szövege 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 feladatát és működését! Írjon minden eljáráshoz fejkommentet!

A programhoz készítsen dokumentációt - 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 Prolog-nyelven, 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 programot egy satrak.pl nevű állományban kell elhelyezni. Megengedett Prolog modulok használata, ekkor a satrak.pl állomány 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 2002. január 27., vasárnap 24:00.

szeredi@inf.bme.hu

Utolsó módosítás: 2002. 01. 10.

`w` (west) - a sátor a saját fájától nyugatra áll,	`n` (north) - a sátor a saját fájától északra áll,
`e` (east) - a sátor a saját fájától keletre áll,	`s` (south) - a sátor a saját fájától délre áll.