BME Villamosmérnöki és Informatikai Kar
Mérnök-informatikus szak
Nappali tagozat
2014/2015-es tanév, őszi félév

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: 2014-10-04
Kiadás: 2014-10-04
Beadási határidő: Erlang 2014-10-19, 23:59; Prolog 2014-10-26, 23:59

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

  1. 0 értékek is szerepelhetnek benne, amelyek a még ki nem töltött mezőknek felelnek meg. 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.
  2. A 0 értékektől függetlenül nem feltétlenül helyes megoldás sem a számismétlés, sem a távolságinfók szempontjából.

Egy részlegesen kitöltött érték-mátrix tehát 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
    

    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.

    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
    

    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.

    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 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.