Deklaratív programozás

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 távolságinfók szerint megengedettnek nevezünk egy, az 1..k*k intervallumba eső v egész értéket, ha v eleget tesz az adott mezőre előírt összes távolságkorlátnak. Vagyis ha az adott mezőre és egy oldalszomszédjára fennáll egy i értékű távolságkorlát, és az oldalszomszédra adott egy j értékű száminfó, akkor a távolságkorlát szerint v=j+i vagy v=j-i. Végül azt mondjuk, hogy a v értéket távolságinfó tiltja, ha v nem megengedett a távolságinfók szerint.

Megjegyzések

1. Ha v egy olyan számérték, amely a fenti definíció szerint nem megengedett egy Sudoku-feladvány adott koordinátájú mezőjére nézve, akkor v nyilván nem szerepelhet az adott Sudoku-feladvány megoldásának adott koordinátájú mezőjében. Tehát a megoldás egy mezőjének az értéke mindenképpen (a fenti definíció szerint) megengedett értékek közül kerül ki.
2. A "megengedett" értékek halmazát tovább lehetne szűkíteni bonyolultabb következtetésekkel, például a fenti definícióban nem említett, de a nagy házi feladatban definiált ellentmondásosság felhasználásával. Fontos, hogy e kis házi feladat megoldásában az ellentmondásosságot figyelmen kívül kell hagyni, és összetett következtetéseket nem szabad végezni: pontosan a fenti definíció szerint kell értelmezni a megengedett mezőérték fogalmát. Az alábbi futási példák között az első Prolog és az első Erlang példa illusztrálja ezt: bár ki lehetne következtetni, hogy a kérdezett mezőben nem szerepelhet a 3-as szám, a válasz szerint mégsem tiltott ez a szám, a fenti definíciót követve.

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 az adott mezőre és valamely oldalszomszédjára vonatkozó távolságinfó.

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.

Prolog-specifikációk

% :- type xcoord == int.
% :- type ycoord == int.
% :- type value == int.
% :- pred t_tiltott(sspec::in, xcoord::in, ycoord::in, value::in).
% t_tiltott(+SSpec, +X, +Y, +V), ahol
%   SSpec az sspec specifikációnak megfelelő Sudoku-feladvány, X a xcoord,
%   Y a ycoord típusnak megfelelő koordináta, V pedig int típusú mezőérték.
% t_tiltott sikeresen lefut, ha az SSpec feladvány (X,Y) koordinátájú mezőjében
% a V érték előfordulását egy SSpec-beli távolságinfó tiltja, azaz az adott
% mezőre és egy szomszédjára fennáll egy I értékű távolságkorlát, miközben
% az adott szomszéd mező J értékű száminfót tartalmaz és |J-V| \= I.

Erlang-specifikációk

%% @type xcoord() = integer().
%% @type ycoord() = integer().
%% @type value()  = integer().
%% @spec khf2:t_tiltott(SSpec::sspec(), X::xcoord(), Y::ycoord(), V::value()) -> Answer::bool() 
% Answer = true, ha az SSpec feladvány (X,Y) koordinátájú mezőjében
% a V érték előfordulását egy SSpec-beli távolságinfó tiltja, azaz az adott
% mezőre és egy szomszédjára fennáll egy I értékű távolságkorlát, miközben
% az adott szomszéd mező J értékű száminfót tartalmaz és |J-V| \= I.

-module(khf2).
-author(szerzo@hol.hu)
-vsn('year-mm-dd').
-export([t_tiltott/4]).

Példák

Prolog

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

Erlang

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

Tudnivalók a beadásról

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

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.