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, amelyben a távolságkonstans az n érték. Tegyük fel, hogy egy Sudoku-megoldás minden mezőjére valamilyen módon előállítottuk az adott mezőn még lehetséges értékek listáját. Egy ilyen részleges megoldást egy olyan m*m méretű mátrix ír le, amelynek mezői az 1..m intervallumba eső számokból képzett, az adott mezőn megengedett értékeket tartalmazó nem-üres listák. Ebben a kis házi feladatban a részleges Sudoku-megoldás 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 a megengedett értékek listája egy adott mezőn, akkor a távolságkorlát alapján bizonyos értékek kizárhatók az oldalszomszédos mező megengedett értékei közül. Ha például n = 2, m = 9 és egy mező megengedett értékeinek a listá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, amely az adott értékkel együtt a távolságkorlátot kielégíti. A feladat tehát az, hogy egy adott mező megengedett értékeinek a listájából elhagyjuk mindazokat az é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 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 megengedett értékek listáit tartalmazó
%% SASol Sudoku-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 megengedett értékek listáit tartalmazó
% SASol Sudoku-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]],
1>                     [[],   [],  [],   []],
1>                     [[],   [s], [s,w],[]],
1>                     [[4],  [],  [w],  []]]
1>                  },
1>                  [[[1,2,3],[4],      [1,2,3],  [1,2,3]],
1>                   [[2,3],  [1],      [2,3,4],  [2,3,4]],
1>                   [[1,2],  [3],      [1,2,4],  [1,2,4]],
1>                   [[4],    [1,2],    [1,2,3],  [1,2,3]]]
1>                 },
1> Ns=lists:seq(1,4),
1> [{{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 vizsgaosztályzat megállapításakor a határidőre beadott, helyesen megoldott kis házi feladatokért plusz 1-1 pont jár.