Deklaratív programozás

A feladat

Jelölje k a félévi nagy házi feladatban specifikált Sudoku-táblában a cellák oldalhosszát: ekkor bármely mező értéke legfeljebb 1 és k*k közötti egész szám lehet. Most a feladat annak megállapítása, hogy egy ilyen Sudoku-tábla 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-táblát a nagy házi feladatban specifikált Prolog-struktúrával, illetve Erlang-párral írjuk le. A Sudoku-tábla bal felső mezőjének koordinátája: (1,1). 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.

Egy adott mező értékeként most tehát megengedett egy szám, ha teljesíti az alábbi két feltételt:

1. 1..k*k közötti egész szám;
2. ha az adott mezőre és egy oldalszomszédjára meg van adva egy i értékű távolságkorlát, az adott oldalszomszédra pedig egy n értékű száminfó, akkor az n+i és n-i számok egyike.

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 tábla (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('2009-04-02')
-export([t-tiltott/4]).

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-tábla, 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 tábla (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.

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 vizsgaosztályzat megállapításakor a határidőre beadott, helyesen megoldott kis házi feladatokért plusz 1-1 pont jár.