A feladat

Ez a leírás a Deklaratív programozás c. tárgyból kiadott 5., Prolog nyelven megirandó kis házi feladatot ismerteti, amely a Prolog nagy házi feladathoz kapcsolódik, de itt most önállóan, a nagy házi feladattól függetlenül ismertetjük.

A Prolog nagy házi feladatban egy logikai feladványt kell megoldani:

Egy téglalap alakú kert négyzet alakú, egyforma parcellákra (vagy mezőkre) van felosztva, egy n sorból és m oszlopból álló mátrixot alkotva. 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:

1. egy parcellán legfeljebb egy fa vagy egy sátor lehet,
2. minden fához pontosan egy sátrat kell kötni, és minden sátor pontosan egy fához van kötve,
3. egy sátor akkor köthető egy fához, ha a parcellák, amelyeken állnak, oldalszomszédok,
4. olyan parcellák, amelyeken sátrak állnak, sem oldal-, sem sarokszomszédok nem lehetnek, azaz egy sátor nem érinthet egyetlen másik sátrat sem.

A fák helyzetét a mátrixbeli sor- és oszlopszámukkal adjuk meg. Egy fához tartozó sátor helyét a fához viszonyított helyzetével (észak, kelet, dél, nyugat) jellemezzük.

A feladvány megoldásához érdemes lehet feltérképezni, hogy egy fához mely irányokban lehet sátrat kötni. Például a kert bal felső sarkában álló fához északi és nyugati irányban nem köthető sátor, mert ezekben az irányokban már nincsenek parcellák.

Az irányokat az égtájak angol nevének kezdőbetűjével jelöljük, a w, n, e, s Prolog atomok rendre a west – nyugati, north – északi, east – keleti, ill. south – déli irányt jelölik.

Ebben a feladatban ún. iránylisták építésével és átalakításával foglalkozunk. Egy iránylista az égtájakat jelölő atomok egy nem-üres részhalmazát tartalmazza (megengedve a teljes 4-elemű halmazt is), lexikografikus (ábécé) sorrendben (a rendezést célszerű a sort/2 beépített eljárással végezni). Minden fához egy iránylistát rendelünk, amely a fához tartozó sátor lehetséges elhelyezéseit adja meg.

Az iranylistak/3 predikátum

Az eljárásnak két bemenő és egy kimenő paramétere van.

1. Az NM bemenő paraméter egy N-M pár, ahol N ill. M a kert, mint mátrix sorainak ill. oszlopainak a száma.
2. Az Fs bemenő paraméter a kertbeli fák helyét írja le I-J alakú számpárokból álló f hosszúságú lista formájában, ahol I ill. J az adott fa sorának ill. oszlopának sorszáma.
3. Az ILs kimenő paraméter egy f hosszúságú lista, amelynek elemei iránylisták. Az ILs lista l-edik eleme azt írja elő, hogy az Fs lista l-edik eleme által meghatározott fához képest melyik oldalszomszéd parcellákra lehet a fához tartozó sátrat helyezni.

Az iranylistak(NM, Fs, ILs) eljáráshívás végrehajtása:

• Az Fs lista által megadott fa-pozíciók mindegyikéhez előállít egy iránylistát.
• Az iránylista alapértelmezésben mind a négy égtájat tartalmazza (lexikografikus sorrendben)
• Ha az adott fa valamelyik oldalszomszédján egy másik fa található, vagy az adott oldalszomszéd a kerten kívül van, akkor az adott oldalszomszédra mutató irányt el kell hagyni az iránylistából.
• Más indokkal nem szabad atomokat elhagyni az iránylistából.
• Ha legalább egy fa-pozícióhoz egy üres lista van rendelve (ami azt jelenti, hogy a feladványnak nincs megoldása), akkor az ILs kimenő paraméter értéke az üres lista, egyébként pedig a fákhoz rendelt (nem-üres) iránylisták listája kell legyen.

Példák

| ?- iranylistak(2-3, [1-1,2-2], ILs).
ILs = [[e,s],[e,n,w]] ? ; 
no

| ?- iranylistak(3-3, [1-1,2-1], ILs).
ILs = [[e],[e,s]] ? ; 
no

| ?- iranylistak(6-6, [1-3,1-5,3-1,4-6,5-1,5-4,6-5], ILs).
ILs = [[e,s,w],[e,s,w],[e,n,s],[n,s,w],[e,n,s],[e,n,s,w],[e,n,w]] ? ; 
no

| ?- iranylistak(2-3, [1-1,1-2,2-1], ILs).
ILs = [] ? ; 
no

A sator_szukites/4 predikátum

Az eljárásnak három bemenő és egy kimenő paramétere van.

1. Az Fs bemenő paraméter a kertbeli fák helyét a fenti módon leíró f hosszúságú lista.
2. Az I bemenő paraméter (1 ≤ I ≤ f) az Fs lista által leírt I-edik fát jelöli ki.
3. Az ILs0 bemenő paraméter a kertbeli fák iránylistáit tartalmazó lista.
4. Az ILs kimenő paraméter a kertbeli fák esetlegesen szűkített iránylistáit tartalmazó lista.

Az eljárást alapvetően akkor érdemes használni, amikor az ILs0 lista I-edik eleme egy egyelemű (irány)lista, azaz az I-edik fához egyértelműen rendelhető sátor. Ebben az esetben lehetőség nyílik az iránylisták szűkítésére.

Az eljárás megírásakor feltételezhetjük, hogy az ILs0 bemenő paramétert az iranylistak/3 eljárás állította elő, vagy ILs0 ebből szűkítéssel (iránylista-elemek elhagyásával) keletkezett. Tehát az iranylistak/3-ban végzett szűkítéseket itt felesleges megismételni. (A kerten kívüli parcellák felismerésére itt nincs is módunk, hiszen a kert méreteit megadó NM paraméter nem áll rendelkezésünkre.)

A sator_szukites(Fs, I, ILs0, ILs) eljáráshívás végrehajtása:

• Ha az ILs0 lista I-edik eleme nem egy egyelemű (irány)lista, akkor az eljáráshívás meghiúsul, ezzel jelezve, hogy a szűkítés nem alkalmazható.
• Egyébként (azaz ha az I-edik iránylista egyelemű, és ebből következően az I-edik sátor helye egyértelműen meghatározott) összegyűjti azokat a parcellákat, amelyekre az I-től különböző sorszámú fák (röviden többi fa) sátrai nem kerülhetnek:
  • az I-edik fához tartozó sátor parcellája;
  • valamint ennek a parcellának az oldal és sarokszomszédai (maximum 8 ilyen mező lehet).
• A többi fa iránylistáiból elhagyja azokat az irányokat, amelyek a fent összegyűjött parcellák valamelyikére mutatnak.
• Más indokkal nem szabad atomokat elhagyni az iránylistákból.
• Ha legalább egy fa-pozícióhoz egy üres lista van rendelve (ami azt jelenti, hogy a feladványnak nincs megoldása), akkor az ILs kimenő paraméter értéke az üres lista, egyébként pedig a fákhoz rendelt (nem-üres) iránylisták listája kell legyen.

Példák

| ?- sator_szukites([1-1,2-2], 2, [[e],[n,s]], ILs).
no

| ?- sator_szukites([1-1,2-2], 2, [[e,s],[s]], ILs).
ILs = [[e],[s]] ? ;
no

| ?- sator_szukites([5-2,2-2], 1, [[n],[e,n,s,w]],ILs).
ILs = [[n],[e,n,w]] ? ; 
no

| ?- sator_szukites([4-2,2-2], 1, [[n],[e,n,s,w]],ILs).
ILs = [[n],[n]] ? ; 
no

| ?- sator_szukites([1-1,1-5,3-3,3-5], 3, [[e,s],[e,s,w],[n],[e,n,s,w]],ILs).
ILs = [[s],[e,s],[n],[e,n,s]] ? ; 
no

| ?- sator_szukites([1-1,2-2], 2, [[e,s],[n]], ILs).
ILs = [] ? ;
no

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

A fenti eljárások paramétereinek típusát a következő – megjegyzésként megadott – Prolog-típusdefiníciók írják le.

% :- type parcMutató ==    int-int.          % egy parcella helyét meghatározó egészszám-pár
% :- type fák ==           list(parcMutató). % a fák helyeit tartalmazó lista
% :- type irány    --->    n                 % észak 
%                        ; e                 % kelet 
%                        ; s                 % dél   
%                        ; w.                % nyugat
% :- type iránylista ==    list(irany).      % egy adott fához rendelt sátor
                                             % lehetséges irányait megadó lista
% :- type iránylisták ==   list(iránylista). % az összes fa iránylistája

% :- pred iranylistak(parcMutató::in         % NM
%                     fák::in,               % Fs
%                     iránylisták::out)      % ILs
					     
% :- pred sator_szukites(fák::in,            % Fs
%                        int::in,            % I
%                        iránylisták::in,    % ILs0
%                        iránylisták::out)   % ILs

Egy teljes példasor

Az alábbiakban egy olyan példasort adunk meg, amely egy egyszerű feladvány teljes megoldási folyamatát mutatja be.

Tekintsük az alábbi, három sorból és négy oszlopból álló, három fát (F1, F2 és F3) tartalmazó feladványt, amelyben nincsenek összegfeltételek (a sátrak soronkénti ill. oszloponkénti számára nincs semmilyen megszorítás):

               +-------------+     
               | F1 F2 .  .  |        Fs = [1-1,1-2,3-4]
               | .  .  .  .  |     
               | .  .  .  F3 |
               +-------------+

1. A kezdeti iránylista előállítása:

| ?- Fs=[1-1,1-2,3-4], iranylistak(3-4, Fs, ILs0).                                --->  ILs0 = [[s],[e,s],[n,w]]

          +-------------+     
          | F1 F2 .  .  |        Fs = [1-1,1-2,  3-4]
          | .  .  .  .  |     
          | .  .  .  F3 |      ILs0 = [[s],[e,s],[n,w]]
          +-------------+

2. Mivel az F1 fa iránylistája egyelemű, érdemes meghívni a sator_szukites eljárást:

| ?- Fs=[1-1,1-2,3-4], ILs0=[[s],[e,s],[n,w]], sator_szukites(Fs, 1, ILs0, ILs1). --->  ILs1 = [[s],[e],[n,w]]

          +-------------+     
          | F1 F2 .  .  |        Fs = [1-1,1-2,3-4]
          | S  x  .  .  |     
          | x  x  .  F3 |      ILs1 = [[s],[e],[n,w]]
          +-------------+

A sátrakat S, E, N, W betűkkel ábrázoljuk, ezzel jelezve, hogy a fájukhoz képest milyen irányban állnak. Azokat a mezőket, amelyekre szomszédsági korlátozások miatt nem kerülhet sátor (ezek egy már ismert helyű sátor oldal- ill. sarokszomszédai) x betűkkel jelezzük.

A fenti sator_szukites(Fs, 1, ILs0, ILs1) hívás feladata, hogy az 1-es sorszámú fához tartozó, egyértelműen déli irányban levő sátort elhelyezze, ennek a mezőnek még jelöletlen szomszédait x betűkkel jelölje, és a többi fák iránylistáiból elhagyja azokat az irányokat, amelyek x-szel jelölt mezőkbe mutatnak. Példánkban egyetlen ilyen van: az F2 fa déli iránya; ezért az ILs0 második eleméből ([e,s]) elhagyjuk az s elemet, és így áll elő az új iránylista-lista, az ILs1.



3. Mivel most már az F2 fa iránylistája is egyelemű, érdemes újra meghívni a sator_szukites eljárást, de most a 2-es sorszámú fára:

| ?- Fs=[1-1,1-2,3-4], ILs1=[[s],[e],[n,w]],   sator_szukites(Fs, 2, ILs1, ILs2). --->  ILs2 = [[s],[e],[w]]

          +-------------+     
          | F1 F2 E  x  |        Fs = [1-1,1-2,3-4]
          | S  x  x  x  |     
          | x  x  .  F3 |      ILs2 = [[s],[e],[w]]
          +-------------+
  

Itt is történt szűkítés: F3 iránylistájából elhagytuk az északi irányt, mert az F3 fölötti mező F2 sátrának sarokszomszédja.

4. Ezzel meg is oldottuk a feladatot. Bár itt most felesleges, általános esetben érdemes lehet még egy szűkítést lefuttatni:

   | ?- Fs=[1-1,1-2,3-4], ILs2=[[s],[e],[w]],     sator_szukites(Fs, 3, ILs2, ILs3). --->  ILs3 = [[s],[e],[w]]
   
             +-------------+     
             | F1 F2 E  x  |        Fs = [1-1,1-2,3-4]
             | S  x  x  x  |     
             | x  x  W  F3 |      ILs3 = [[s],[e],[w]]
             +-------------+
   

További szűkítést nem kaptunk, de az ellentmondásre utaló ILs3 = [] választ sem, így a kapott egyelemű iránylisták az eredeti feladat egyetlen megoldását mutatják: [s,e,w]

Tudnivalók a beadásról