Deklaratív programozás

2. kis házi feladat: Sudoku-megoldás távolságinfók szerinti részleges helyessége

1.1 változat
Utolsó módosítás: 2010-02-21
Kiadás: 2010-02-21
Beadási határidő: Prolog 2010-03-29, 24:00; Erlang 2010-04-05, 24:00

A feladat

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

Egy részlegesen kitöltött Sudoku-megoldás annyiban tér el a nagy házi feladatban specifikált Sudoku-megoldástól, hogy benne 0 értékek is szerepelhetnek, amelyek a még ki nem töltött mezőknek felelnek meg (hasonlóan az első kis házi feladathoz). 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.

Egy részleges Sudoku-megoldás tehát nem teljesíti egy adott Sudoku-feladvány távolságinfói által támasztott feltételeket, ha a Sudoku-megoldásban 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ékének 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 a Sudoku-megoldás (az 1. kisházi értelmében) 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észleges Sudoku-megoldás 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észleges Sudoku-megoldás 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 a Sudoku-megoldásban 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 a megoldás 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 a megoldás 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 programot az Elektronikus Tanársegéddel kell beadni (l. HF beadás menüpont).

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.

dp@inf.bme.hu