A feladat

Ez a leírás a Deklaratív programozás c. tárgyból kiadott 6., 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 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,
5. a mátrix egyes soraira és oszlopaira előírt összegfeltételeknek teljesülnie kell, ezeket két lista formájában adjuk meg:
   • az Ss n-elemű lista i-edik eleme az i-edik sorban levő sátrak számát adja meg, ha ez a szám nem-negatív, egyébként nincs megszorítás az adott sorban levő sátrak számára;
   • az Os m-elemű lista i-edik eleme az i-edik oszlopban levő sátrak számát adja meg (negatív szám jelentése azonos a fentivel).

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.

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.

Iránylistának nevezünk egy a fenti égtáj-atomokból álló ismétlődésmentes, lexikografikusan rendezett listát. Minden fához egy iránylistát rendelünk, amely a fához tartozó sátor lehetséges elhelyezéseit adja meg.

Ebben a feladatban iránylisták szűkítésével foglalkozunk, összegfeltételek alapján.

Az osszeg_szukites/4 predikátum

Írjon egy osszeg_szukites(Fs, Osszegfeltetel, ILs0, ILs) Prolog-eljárást, amely egy egyetlen sorra vagy oszlopra vonatkozó Osszegfeltetel alapján végez el egy esetleges iránylista szűkítést: az ILs0 iránylista-lista egyes elemeiből elhagy olyan irányokat, amelyek választása esetén a szóbanforgó összegfeltétel biztosan nem teljesül (és a szűkített iránylista-listát ILs-ben adja vissza).

Például, ha az összegfeltétel azt írja elő, hogy az 5. oszlop összege 0, akkor a 4. oszlopban levő fák iránylistáiból a keleti irányt, a 6. oszlopban levő fák iránylistáiból a nyugati irányt, az 5. oszlopban levő fák iránylistáiból a déli és északi irányt el lehet hagyni. Hasonló szűkítést lehet elvégezni, ha pl. az 5. oszlop előírt összege 3, de már van három olyan fa, amelyeknek egyelemű az iránylistája, és ezen iránylisták szerint mindhárom fa sátra az 5. oszlopba kerül.

Egy másik fajta szűkítési példa: a 3. sor előírt összege 2, viszont csak két olyan fa van, amelyek sátra a 3. sorba kerülhet. Ebben az esetben az adott két fának az iránylistájából el kell hagyni az összes olyan irányt, amely nem a 3. sorba mutat. (Vegyük észre, hogy ez nem feltétlenül jelenti azt, hogy a két fa iránylistája egyeleművé válik: ha pl. az egyik fa a 3. sorban van, akkor itt ki tudjuk zárni az északi és déli irányt, de a keleti és a nyugati meg kell maradjon, hiszen mindkettő a 3. sorba mutat.)

Az osszeg_szukites(Fs, Osszegfeltetel, ILs0, ILs) 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 Osszegfeltetel bemenő paraméter alakja sor(I,Db) vagy oszl(J,Db) (1 ≤ I ≤ n, 1 ≤ J ≤ m, Db ≥ 0), az első esetben az I-edik sorra, a második esetben a J-edik oszlopra vonatkozó Db darabszámú feltétel alapján kell a szűkítést elvégezni.
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ás végrehajtásának pontos leírásához bevezetjük a következő elnevezéseket:

• Egy fa biztosan egy adott sorba/oszlopba mutat, ha a hozzá tartozó iránylista bármely elemének választása esetén a fához tartozó sátor az adott sorba/oszlopba kerül. (Megjegyzés: ez csak akkor lehetséges, ha az iránylista legfeljebb kételemű.)
• Egy fa esetleg egy adott sorba/oszlopba mutat, ha nem teljesül rá az előző feltétel, de a hozzá tartozó iránylista legalább egy elemének választása esetén a fához tartozó sátor az adott sorba/oszlopba kerül.

Az osszeg_szukites/4 eljárás bemenő paraméterei által leírt minden egyes állapotban meg lehet állapítani azoknak a fáknak a számát, amelyek biztosan ill. esetleg az adott sorba/oszlopba kerülnek; jelöljük ezeket a számokat rendre b-vel ill. e-vel.

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

• Az adott paraméterek alapján előállítjuk az Osszegfeltetel-ben jelzett sorba/oszlopba biztosan mutató fák b ill. az ide esetleg mutató fák e számát, illetve az Osszegfeltetel-ben szereplő Db sátor-darabszámot.
  1. Ha b + e < Db , akkor a feladványnak az adott paraméterekkel nincs megoldása, amit az eljáráshívás az ILs = [] behelyettesítéssel jelez.
  2. Egyébként, ha b + e = Db , akkor az összes esetleges fának a megadott sorba/oszlopba kell mutatnia, hogy a feltétel teljesülhessen. Ennek megfelelően ILs0-ban az esetleges fáknak megfelelő iránylistákat szűkíteni kell úgy, hogy azokban csak az adott sorba/oszlopba mutató irány(ok) maradjanak, és az így módosított iránylista-listát kell az ILs paraméterben kiadni.
  3. Egyébként, ha b = Db , akkor semelyik esetleges fának sem szabad a megadott sorba/oszlopba mutatnia, hogy a feltétel teljesülhessen. Ennek megfelelően ILs0-ban az esetleges fáknak megfelelő iránylistákból el kell hagyni az adott sorba/oszlopba mutató irányokat, és az így módosított iránylista-listát kell az ILs paraméterben kiadni. (Ennek az esetnek a megvalósítása opcionális.)
  4. Egyébként, ha b > Db , akkor a feladványnak az adott paraméterekkel nincs megoldása, amit az eljáráshívás az ILs = [] behelyettesítéssel jelez.
• Ha a fenti négy feltétel egyike sem teljesül, akkor az eljáráshívás hiúsuljon meg, jelezve, hogy szűkítés nem alkalmazható.
• A fentiekben leírtakon túl további szűkítést nem szabad alkalmazni.

Példák

| ?- osszeg_szukites([6-6,9-7], oszl(7,2), [[n,s,w],[e,n,s,w]], ILs).      % b = 0, e = 1, Db = 2  (i)
ILs = [] ? ;
no
| ?- osszeg_szukites([6-6,9-7], oszl(7,2), [[e,n,s,w],[e,n,s,w]], ILs).    % b = 0, e = 2, Db = 2  (ii)
ILs = [[e],[n,s]] ? ;
no
| ?- osszeg_szukites([6-6,9-7], oszl(7,2), [[e,n,s,w],[n,s]], ILs).        % b = 1, e = 1, Db = 2  (ii)
ILs = [[e],[n,s]] ? ;
no
| ?- osszeg_szukites([6-6,9-7], oszl(7,1), [[e,n,s,w],[n,s]], ILs).        % b = 1, e = 1, Db = 1  (iii)
ILs = [[n,s,w],[n,s]] ? ;
no
| ?- osszeg_szukites([6-6,9-7], oszl(7,0), [[e,n,s,w],[n,s]], ILs).        % b = 1, e = 1, Db = 0  (iv)
ILs = [] ? ;
no
| ?- osszeg_szukites([6-6,9-7], oszl(7,1), [[e,n,s,w],[e,n,s,w]], ILs).    % b = 0, e = 2, Db = 1  (meghiúsulás)
no

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

% :- 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

% :- type összegfeltétel
                      ==   sor(int, int)     % sor(I,Db): az I-edik sorbeli sátrak száma Db
                         ; oszl(int, int).   % oszl(J,Db): a J-edik oszlopbeli sátrak száma Db

% :- pred osszeg_szukites(fák::in,           % Fs
%                         összegfeltétel::in,% Osszegfeltetel
%                         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. Ebben felhasználjuk az 5. kis házi feladatban definiált iranylistak/3 és sator_szukites/4 eljárásokat is.

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 a következő összegfeltételeknek kell teljesülniük: az első sorban 2 sátor van, az első oszlopban pedig 1

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

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

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

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

2. Alkalmazzunk szűkítést az 1. sorbeli összegfeltételre (b = 0, e = 2, Db = 2, ii. eset):

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

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

Az első sorban két sátrat kell elhelyeznünk, de csak két fának lehet sátra ebben a sorban (F3 sátra nem kerülhet az 1. sorba). Emiatt az F1 fa iránylistájából elhagyjuk a déli, az F2 iránylistájából pedig a keleti és déli irányt,

Mivel az első sorra vonatkozó összegfeltétel szűkítést váltott ki, erre a feltételre a továbbiakban nem lesz szükség. Ennek jelzésére a további ábrákon az első sor elötti 2-es darabszámot már nem is jelenítjük meg

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

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

            1
          +-------------+     
          | N  x  F1 .  |        Fs = [1-3,2-1,3-2]
          | F2 x  .  .  |      ILs2 = [[e],[n],[e,w]]
          | .  F3 .  .  |
          +-------------+

Itt most az F1 és F3 fák iránylistái szűkültek, az előbbiből a nyugati, az utóbbiból az északi irányt hagytuk el.



4. Az F1 fa iránylistája egyelemű lett, így érdemes újra meghívni a sator_szukites eljárást, az 1-es sorszámú fára:

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

            1
          +-------------+     
          | N  x  F1 E  |        Fs = [1-3,2-1,3-2]
          | F2 x  x  x  |      ILs3 = [[e],[n],[e,w]]
          | .  F3 .  .  |
          +-------------+

Itt most nem történt szűkítés mert az F1 fa keleti irányú sátrának szomszédos mezőin amúgy sem lehetett volna sátor.

5. Most szűkítsünk az 1. oszlopra vonatkozó összegfeltétel szerint (b = 1, e = 1, Db = 1, iii. eset):

| ?- Fs=[1-3,2-1,3-2], ILs3 = [[e],[n],[e,w]],
     osszeg_szukites(Fs, oszl(1,1), ILs3, ILs4).           --->  ILs4 = [[e],[n],[e]]

            1
          +-------------+     
          | N  x  F1 E  |        Fs = [1-3,2-1,3-2]
          | F2 x  x  x  |      ILs4 = [[e],[n],[e]]
          | x  F3 .  .  |
          +-------------+

6. Mivel az F3 fa iránylistája egyelemű, alkalmazzuk rá a sator_szukites eljárást

   | ?- Fs=[1-3,2-1,3-2], ILs4 = [[e],[n],[e]],
        sator_szukites(Fs, 3, ILs4, ILs5).                   --->  ILs5 = [[e],[n],[e]]
               
             +-------------+     
             | N  x  F1 E  |        Fs = [1-3,2-1,3-2]
             | F2 x  x  x  |      ILs5 = [[e],[n],[e]]
             | x  F3 E  x  |
             +-------------+
   

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

Tudnivalók a beadásról