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őt tartalmazó sor, oszlop vagy cella bármely másik mezőjében található száminfó.

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

Erlang-specifikációk

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

-module(khf3).
-author(szerzo@hol.hu)
-vsn('2009-04-22')
-export([sz-tiltott/4]).

Prolog-specifikációk

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

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

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.