Deklaratív programozás

3. kis házi feladat: Száminfók tiltotta mezőérték

1.0 változat
Utolsó módosítás: 2013-02-27
Kiadás: 2013-03-03
Beadási határidő: Prolog 2013-04-28, Erlang 2013-05-05

Definíciók

A feladat a félévi nagy házi feladathoz kapcsolódik, az ott megadott definíciók ismeretét feltételezzük.

Egy k cellaméretű Sudoku-feladványban egy adott mezőre nézve száminfók szerint megengedettnek nevezünk egy, az 1..k*k intervallumba eső egész értéket, ha különbözik az adott mezőt tartalmazó sor, oszlop és cella összes többi mezőjére vonatkozó száminfóban előírt értéktől. Azt mondjuk, hogy egy értéket száminfó tilt, ha az nem megengedett a száminfók szerint.

A feladat

A feladat annak megállapítása, hogy egy Sudoku-feladvány adott mezőjében valamely mezőérték előfordulását tiltja-e száminfó.

A Sudoku-feladványt a nagy házi feladatban specifikált Prolog-struktúrával, illetve Erlang-párral írjuk le. A vizsgálandó mezőt a koordinátáival, a vizsgálandó értéket egy egész számmal adjuk meg. A koordináták és a vizsgálandó érték helyességét ellenőrizni nem kell, feltehetjük, hogy mind a koordináták, mind a mezőérték az 1..k*k tartományba esnek.

Megjegyzések

Fontos, hogy egy mezőérték akkor is lehet megengedett a fenti definíció szerint, ha a Sudoku-feladvány ellentmondásos más száminfók vagy távolságinfók miatt. Tehát az összetett következtetésektől e feladat megoldásánál is tartózkodni kell.

Prolog-specifikációk

Írjon Prolog-predikátumot sz_tiltott/4 néven (ahol sz_tiltott a száminfó_tiltott rövidítése), amely megvizsgálja, hogy tiltja-e száminfó valamely érték előfordulását egy Sudoku-tábla adott mezőjében.

% :- type xcoord  == int.
% :- type ycoord  == int.
% :- type value == int.
% :- pred sz_tiltott(sspec::in, xcoord::in, ycoord::in, value::in).
% sz_tiltott(+SSpec, +X, +Y, +V), ahol
%   SSpec az sspec specifikációnak megfelelő Sudoku-tábla, X a xcoord,
%   Y a ycoord típusnak megfelelő koordináta, V pedig value típusú mezőérték.
% sz_tiltott sikeresen lefut, ha az SSpec tábla (X,Y) koordinátájú mezőjében a V érték
% előfordulását egy SSpec-beli száminfó tiltja, azaz v(V) alakú száminfó van az adott
% mezőt tartalmazó sor, oszlop vagy cella legalább egy, az adottól különböző mezőjében.

Erlang-specifikációk

Írjon Erlang-predikátumot sz_tiltott/4 néven (ahol sz_tiltott a száminfó_tiltott rövidítése), amely megvizsgálja, hogy tiltja-e száminfó valamely érték előfordulását egy Sudoku-tábla adott mezőjében.

%% @type xcoord() = integer().
%% @type ycoord() = integer().
%% @type value()  = integer().
%% @spec khf3:sz_tiltott(SSpec::sspec(), X::xcoord(), Y::ycoord(), V::value()) -> Answer::bool() 
%% Answer = true, ha az SSpec tábla (X,Y) koordinátájú mezőjében a V érték előfordulását egy
%% SSpec-beli száminfó tiltja, azaz {v,V} alakú száminfó van az adott mezőt tartalmazó sor,
%% oszlop vagy cella legalább egy, az adottól különböző mezőjében.

A programot tartalmazó modul attribútumai ezek legyenek:

-module(khf3).
-author(szerzo@hol.hu)
-vsn('yyyy-mm-dd')
-export([sz_tiltott/4]).

Példák

Prolog

| ?- [user].
% consulting user...
| feladvany1(s(2, [[ [v(2),s(1)],      [w(2)],          [],          []],
                   [          [],          [],          [],      [s(3)]],
                   [      [s(1)],          [],      [v(3)],          []],
                   [      [w(2)],      [s(1)],          [],          []]])).
% consulted user in module user, 10 msec 512 bytes
yes
| ?- feladvany1(_F), sz_tiltott(_F, 1, 1, 2).
no
| ?- feladvany1(_F), sz_tiltott(_F, 2, 2, 3).
no
| ?- feladvany1(_F), sz_tiltott(_F, 1, 2, 2).
yes
| ?- feladvany1(_F), sz_tiltott(_F, 1, 2, 3).
no
| ?- feladvany1(_F), sz_tiltott(_F, 2, 1, 2).
yes
| ?- feladvany1(_F), sz_tiltott(_F, 4, 3, 3).
yes
| ?- sz_tiltott(s(2, [[ [v(2),s(1)],      [w(2)],          [],          []],
                   [          [],          [],          [],      [s(3)]],
                   [      [s(1)],          [],      [v(3)],      [v(2)]],
                   [      [w(2)],      [s(1)],          [],          []]]), 4, 2, 1).
no

Erlang

1> F0 =
    {2, [[ [{v,2},{s,1}],      [{w,2}],          [],           []],
           [          [],           [],          [],      [{s,3}]],
           [     [{s,1}],           [],     [{v,3}],           []],
           [     [{w,2}],      [{s,1}],          [],           []]]}.
...
2> khf3:sz_tiltott(F0, 1, 1, 2).
false
3> khf3:sz_tiltott(F0, 2, 2, 3).
false
4> khf3:sz_tiltott(F0, 1, 2, 2).
true
5> khf3:sz_tiltott(F0, 1, 2, 3).
false
6> khf3:sz_tiltott(F0, 2, 1, 2).
true
7> khf3:sz_tiltott(F0, 4, 3, 3).
true
8> khf3:sz_tiltott(
    {2, [[ [{v,2},{s,1}],      [{w,2}],           [],           []],
           [          [],           [],           [],      [{s,3}]],
           [     [{s,1}],           [],      [{v,3}],      [{v,2}]],
           [     [{w,2}],      [{s,1}],           [],           []]]}, 4, 2, 1).
false

Tudnivalók a beadásról

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

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

A vizsgaosztá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.