Deklaratív programozás

A feladat

Adott egy, a féléves nagy házi feladatban specifikált, m*m méretű Sudoku-feladvány, ahol m a sorok (és oszlopok) számát jelöli (m=k²), és a távolságkonstans az n érték. Tegyük fel, hogy egy Sudoku-feladvány minden mezőjére valamilyen módon előállítottuk az adott mezőn még lehetséges értékek listáját, amit egy ún. értéklista-mátrixszal adunk meg. Egy adott mező értéklistájának nevezzük az 1..m intervallumba eső számokból képzett, az adott mezőn megengedett értékeket tartalmazó nem-üres listát. Az értéklista-mátrix egy olyan Sudoku-mátrix, amelynek elemei a megfelelő mezőkhöz tartozó értéklisták. Ebben a kis házi feladatban a feladvány egy adott mezőjéhez tartozó értéklistát kell szűkítenie a Sudoku-feladványban az adott mezőre vonatkozó távolságkorlátok alapján.

A Sudoku-feladvány specifikációja szerint két oldalszomszédos mező között mindig fennáll valamilyen távolságkorlát. Az oldalszomszédos mezők észak-déli, illetve kelet-nyugati elhelyezkedésűek lehetnek.

Ha a feladványban az északi, illetve a keleti mezőben szerepel az s, illetve a w távolságinfó, akkor pozitív távolságkorlátról, ellenkező esetben negatív távolságkorlátról beszélünk. A pozitív távolságkorlát azt írja elő, hogy a két mező távolságának (különbségük abszolút értékének) n-nek kell lennie, negatív távolságkorlát esetén viszont a két mező távolsága csak n-től különböző érték lehet.

Ha ismert egy mező értéklistája, akkor a távolságkorlát alapján bizonyos értékek kizárhatók az oldalszomszédos mező értéklistájából. Ha például n = 2, m = 9 és egy mező értéklistája [3,7], akkor pozitív távolságkorlát fennállása esetén az oldalszomszéd csak az [1,5,9] értékek egyike lehet, tehát a [2,3,4,6,7,8] értékek kizárhatók. Ha ugyanerre a mezőre a másik oldalszomszédja miatt negatív távolságkorlát is vonatkozik, akkor a másik oldalszomszéd értéke nem lehet 5, hiszen ez a 3 és a 7 értékektől egyaránt 2 távolságra van (ui. ha az oldalszomszéd értéke 5 lenne, akkor bárhogyan is választanánk értéket a [3,7] listából, a negatív távolságkorlát nem teljesülne).

Általánosan: egy adott érték kizárható, ha az oldalszomszédnak nincs olyan megengedett értéke (az értéklistájában), amely az adott értékkel együtt a távolságkorlátot kielégíti. A feladat tehát az, hogy egy adott mező értéklistájából elhagyjuk mindazon értékeket, amelyek az oldalszomszédjainak értéklistái és távolságkorlátjai alapján kizárhatók. Előfordulhat, hogy az összes megengedett érték kizárható; ilyenkor üres listát kell visszaadni.

A Sudoku-feladványt a nagy házi feladatban specifikált Prolog-struktúrával, illetve Erlang-párral, az adott mezőt a sor-oszlop koordinátáival adjuk meg (a Sudoku-tábla bal felső mezőjének a koordinátája (1,1)). Eredményül az adott mező értéklistájának azon elemeiből álló listát kell visszaadni, amelyeket az adott mező egyik oldalszomszédja sem zár ki. Az eredménylista elemeinek sorrendje tetszőleges, de ismétlődő elem nem lehet benne.

Az eredménylista meghatározásánál a fentieken kívül más szempontot nem szabad figyelembe venni. Tekintsük pl. a következő esetet: legyen a távolságkonstans n = 1, és legyen a vizsgált mezőnek egy déli oldalszomszédja, amelyhez az egyelemű [3] értéklista tartozik, és amelyre negatív távolságkorlát vonatkozik. Ebben az esetben a vizsgált mező értéklistájából az adott déli szomszéd miatt a 2 és 4 értékeket kell elhagyni. Nem szabad viszont a 3 értéket elhagyni, mert ezt az értéket nem egy távolságkorlát zárja ki, hanem az az előírás, hogy egy oszlopban nem fordulhat elő kétszer ugyanaz az érték (amit ebben a feladatban nem szabad vizsgálni).

Erlang-specifikációk

%% @type sspec() = {dist(), board()}.
%% @type dist()   = integer().
%% @type field()  = [info()].
%% @type info()   = s | w | integer().
%% @type board()  = [[field()]].
%% @type sasol()  = [[[integer()]]].
%% @type col()    = int.
%% @type row()    = int.
%% @type pvlist() = [int].

%% @spec khf3:avalues(SSpec::sspec(), SASol::sasol(), Col::col(), Row::row()) -> Pvals::pvlist().
%% Az SSpec Sudoku-feladvány és a SASol értéklista-mátrix alapján a
%% (Col,Row) koordinátájú mezőre előállított szűkített értéklista Pvals.
%% A szűkített értéklista az adott mező eredeti értéklistájának azokat
%% az elemeit tartalmazza, amelyeket egyik oldalszomszéd sem zár ki.

-module(khf3).
-author(email@unit.org.hu).
-vsn('year-mm-dd').
-export([avalues/4]).
%-compile(export_all).

Prolog-specifikációk

% :- type sspec ---> s(dist, board).
% :- type dist  == int.
% :- type field == list(info).
% :- type info ---> s; w; int.
% :- type board == list(list(field)).
% :- type sasol == list(list(list(int))).
% :- type col == int.
% :- type row == int.
% :- type pvlist == list(int).

% :- pred avalues(sspec::in, sasol::in, col::in, row::in, pvlist::out).

% avalues(+SSpec, +SASol, +Col, +Row, -L):
% Az SSpec Sudoku-feladvány és a SASol értéklista-mátrix alapján a
% (Col,Row) koordinátájú mezőre előállított szűkített értéklista L.
% A szűkített értéklista az adott mező eredeti értéklistájának azokat
% az elemeit tartalmazza, amelyeket egyik oldalszomszéd sem zár ki.

Példák

Prolog

| ?- between(1, 4, R),
     between(1, 4, C),
     avalues(s(1, [[[s],  [],  [],  [s]],
                   [[],   [],  [],   []],
		  
                   [[],   [s], [s,w],[]],
                   [[4],  [],  [w],  []]]
              ), 
   	     [[[1,2,3],[4],      [1,2,3],  [1,2,3]],
              [[2,3],  [1],      [2,3,4],  [2,3,4]],
	      [[1,2],  [3],      [1,2,4],  [1,2,4]],
	      [[4],    [1,2],    [1,2,3],  [1,2,3]]],
             C, R, L),
     write(R-C), write('   '), write(L), nl, fail.
1-1   [1,2]
1-2   [4]
1-3   [1,2]
1-4   [1,2,3]
2-1   [3]
2-2   [1]
2-3   [3,4]
2-4   [2,3,4]
3-1   [1]
3-2   [3]
3-3   [2,4]
3-4   [1,2,4]
4-1   [4]
4-2   [2]
4-3   [1,2,3]
4-4   [1,2,3]
no
| ?- 

Erlang

1> {SSpec,SASol} = {{1,[[[s],  [],  [],  [s]],
                       [[],   [],  [],   []],
                       [[],   [s], [s,w],[]],
                       [[4],  [],  [w],  []]]
                    }, 
                    [[[1,2,3],[4],      [1,2,3],  [1,2,3]],
                     [[2,3],  [1],      [2,3,4],  [2,3,4]],
                     [[1,2],  [3],      [1,2,4],  [1,2,4]],
                     [[4],    [1,2],    [1,2,3],  [1,2,3]]]
                   },
   Ns=lists:seq(1,4),
   [{{R,C},khf3:avalues(SSpec,SASol,C,R)} || R <- Ns, C <- Ns].
[{{1,1},[1,2]},
 {{1,2},[4]},
 {{1,3},[1,2]},
 {{1,4},[1,2,3]},
 {{2,1},[3]},
 {{2,2},[1]},
 {{2,3},[3,4]},
 {{2,4},[2,3,4]},
 {{3,1},[1]},
 {{3,2},[3]},
 {{3,3},[2,4]},
 {{3,4},[1,2,4]},
 {{4,1},[4]},
 {{4,2},[2]},
 {{4,3},[1,2,3]},
 {{4,4},[1,2,3]}]
2> 

Tudnivalók a beadásról

A programok készülhetnek MS Windows alatt is, de Linux alatt is működniük kell. A beadott programokat Linux környezetben a SICStus Prolog 4.2.x, ill. az Erlang/OTP R14A rendszerekkel teszteljük.

A programot az Elektronikus Tanársegéd (ETS) segítségével weben keresztül lehet beadni, a HF beadás menüpont alatt. Ez a hármas számú kis házi feladat, ennek megfelelően az ETS a beküldött megoldást khf3.pl, ill. khf3.erl néven tárolja el és hivatkozik rá. (A feltöltendő állomány neve tetszőleges lehet, az ETS átnevezi.)

Az osztályzat megállapításakor a határidőre beadott, minden tesztesetre helyesen működő feladatmegoldásért plusz 1-1 pont jár.

Gyakorló feladatok

1. Annak eldöntése, hogy egy listában vannak-e ismétlődő elemek.
2. Annak eldöntése, hogy egy lista, ill. mátrix minden elemére teljesül-e egy adott predikátum.
3. Annak eldöntése, hogy egy lista, ill. mátrix legalább egy elemére teljesül-e egy adott predikátum.