Deklaratív programozás

2. kis házi feladat: Érték-mátrix távolságinfók szerinti részleges helyessége

1.0 változat
Utolsó módosítás: 2017-10-01
Kiadás: 2017-10-03
A beadási határidők a főoldalon olvashatók.

A feladat

A feladat a félévi nagy házi feladatban specifikált Sudoku-feladvány és egy részlegesen kitöltött érték-mátrix összevetése a távolságinfók szempontjából. Pontosítva: egy adott Sudoku-feladvány és egy részlegesen kitöltött érték-mátrix esetén el kell dönteni, hogy az érték-mátrix teljesíti-e a feladványban szereplő távolságinfók által támasztott feltételeket.

Egy m*m méretű részlegesen kitöltött érték-mátrix egy olyan érték-mátrix (lásd a nagy házi feladat kiírását) amelynek mezői 0 és m = k² közé eső egész számok. Egy részlegesen kitöltött érték-mátrix tehát két dologban tér el a nagy házi feladatban specifikált Sudoku-megoldástól:

0 értékek is szerepelhetnek benne, amelyek a még ki nem töltött mezőknek felelnek meg. Ennek megfelelően ha egy távolságinfó által kijelölt két mező közül legalább az egyik 0, akkor az adott távolságinfót teljesültnek tekintjük.
Az érték-mátrix nem feltétlenül teljesíti a nagy házi feladatban a sudoku megoldással szemben támasztott elvárásokat, tehát előfordulhat benne számismétlés (a nem 0 értékek esetén is), és a feladványban előírt távolságinfók sem feltétlenül teljesülnek.

Összefoglalva: egy részlegesen kitöltött érték-mátrix nem teljesíti egy adott Sudoku-feladvány távolságinfói által támasztott feltételeket, ha az érték-mátrixban van két nem-nulla értékű oldalszomszédos mező, amely mezőpárra

a Sudoku-feladvány előír egy távolságinfót, de a két mező értékenek távolsága nem n; vagy

a Sudoku-feladvány nem ír elő távolságinfót, de a két mező értékének távolsága n;

ahol n a Sudoku-feladványban megadott távolságkonstans.

A kisházi megoldásában a Sudoku-feladványban szereplő száminfókat figyelmen kívül kell hagynia. Emellett annak sincs jelentősége, hogy az érték-mátrix (a számismétlés szempontjából) ellentmondásmentes-e vagy sem.

Erlang-specifikációk

Írjon Erlang-függvényt khf2:n_away/2 néven egy Sudoku-tábla távolságinfók szerinti részleges helyességének a megállapítására.

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

%% @type ssol() = [[integer()]].

%% @spec khf2:n_away(SSpec::sspec(), SSol::ssol()) -> B::bool().
%% B igaz, ha az SSol részlegesen kitöltött érték-mátrix teljesíti az SSpec
%% Sudoku-feladványban szereplő távolságinfók által támasztott feltételeket.

A programot tartalmazó modul attribútumai ezek legyenek:

-module(khf2).
-author('email@unit.org.hu').
-vsn('year-mm-dd').
-export([n_away/2]).
%-compile(export_all).

Prolog-specifikációk

Írjon Prolog-eljárást n_away/2 néven egy Sudoku-tábla távolságinfók szerinti részleges helyességének a megállapítására.

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

% :- type ssol == list(list(int)).

% :- pred n_away(sspec::in, ssol::in).
% n_away(SSpec, SSol): Az SSol részlegesen kitöltött érték-mátrix teljesíti az SSpec
% Sudoku-feladványban szereplő távolságinfók által támasztott feltételeket.

Példák

Prolog

| ?- n_away(s(1, [[[s], [],    [],[s]],
                  [ [], [],    [], []],

                  [ [],[s], [s,w], []],
                  [[4], [],   [w], []]
                 ]
             ), 
            [[ 2, 4,  1, 3],
             [ 3, 1,  4, 2],
             [ 1, 3,  2, 4],
             [ 4, 2,  3, 1]]
           ).
yes

| ?- n_away(s(1, [[[s], [],    [],[s]],
                  [ [], [],    [], []],

                  [ [],[s], [s,w], []],
                  [[4], [],   [w], []]
                 ]
             ), 
            [[ 0, 2,  0, 2],
             [ 2, 0,  0, 0],
             [ 0, 0,  2, 0],
             [ 2, 0,  3, 0]]
           ).
yes

Ebben az érték-mátrixban csak egy olyan oldalszomszédos mezőpár van, amely nem-nulla értékeket tartalmaz, mégpedig a 3. sor 3. mezője és az alatta levő mező. Mivel ezen két mező értékének távolsága 1, és a Sudoku-feladvány megfelelő mezője tartalmaz egy s távolságinfót, ezért az érték-mátrix teljesíti a feladvány távolságinfói által támasztott feltételeket.

| ?- n_away(s(1, [[[s], [],    [],[s]],
                  [ [], [],    [], []],

                  [ [],[s], [s,w], []],
                  [[4], [],   [w], []]
                 ]
             ), 
            [[ 2, 4,  1, 3],
             [ 3, 1,  2, 4],
             [ 1, 3,  4, 2],
             [ 4, 2,  3, 1]]
           ).
no

Az utóbbi esetben azért kapunk nemleges választ, mert például a feladvány 1. sorának 3. oszlopában nem szerepel az s távolságinfó, ugyanakkor az érték-mátrix ezen mezőjében az 1 érték, míg a tőle délre levőben a 2 érték szerepel, azaz a két szomszédos mező távolsága a feladványban szereplő 1 távolságkonstans.

Erlang

khf2:n_away({1, [[[s], [],    [],[s]],
                 [ [], [],    [], []],

                 [ [],[s], [s,w], []],
                 [[4], [],   [w], []]
                ]
            }, 
            [[ 2, 4,  1, 3],
             [ 3, 1,  4, 2],
             [ 1, 3,  2, 4],
             [ 4, 2,  3, 1]]
           ).
true

khf2:n_away({1, [[[s], [],    [],[s]],
                 [ [], [],    [], []],

                 [ [],[s], [s,w], []],
                 [[4], [],   [w], []]
                ]
            }, 
            [[ 0, 2,  0, 2],
             [ 2, 0,  0, 0],
             [ 0, 0,  2, 0],
             [ 2, 0,  3, 0]]
           ).
true

khf2:n_away({1, [[[s], [],    [],[s]],
                 [ [], [],    [], []],

                 [ [],[s], [s,w], []],
                 [[4], [],   [w], []]
                ]
            }, 
            [[ 2, 4,  1, 3],
             [ 3, 1,  2, 4],
             [ 1, 3,  4, 2],
             [ 4, 2,  3, 1]]
           ).
false

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.3.x, ill. az Erlang/OTP R16B rendszerekkel teszteljük.

Ennek a kis házi feladatnak a beadása ugyan nem kötelező, azonban a félévközi követelmények teljesítéséhez a félév során legalább három kisházifeladat-megoldást – közülük legalább egyet Prolog és legalább egyet Erlang nyelven – sikeresen be kell adni. Sikeres az a megoldás, amelyik az összes tesztesetre helyes választ ad. Ha ezt a kis házi feladatot mindkét nyelven sikeresen beadja, az természetesen két megoldásnak számít.

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 kettes számú kis házi feladat, ennek megfelelően az ETS a beküldött megoldást khf2.pl, ill. khf2.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.