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.

Tegyük fel, hogy adott egy Sudoku-feladvány, amelynek cellamérete k.

A Sudoku-feladványban egy adott mezőre nézve megengedettnek nevezünk egy I értéket, ha az teljesíti a következő feltételeket:

1. I egy egész szám, és 1 ≤ I≤ k*k;
2. I eleget tesz az adott mezőben szereplő szám- és paritási infók által előírt megszorításoknak;
3. I különbözik az adott mezőt tartalmazó sor, oszlop és cella többi mezőjében szereplő száminfók által előírt értékektől.

Megjegyzések

1. Ha I 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 I nyilván nem szerepelhet az adott Sudoku-feladvány megoldásának adott koordinátájú mezőjében, hiszen ha a fenti 1.-3. feltételek közül valamelyik nem teljesül, akkor ezzel a Sudoku megoldásokra előírt valamelyik feltétel sérül. 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, és/vagy a fenti definícióban nem említett információk (pl. szomszédsági infók) felhasználásával. Ha például egy k=2 cellaméretű Sudoku-feladvány egy sorának 1. és 2. mezőjében rendre a 2 és e infók szerepelnek, akkor ennek a sornak a 3. és 4. eleméről könnyen belátható, hogy ezek csak páratlanok lehetnek, ugyanis a sorban már van két páros elem (az 1. és a 2.). Hasonló következtetésre juthatunk abban az esetben, ha a sor 2. és 3. mezőjében rendre a w és e infók szerepelnek: ekkor a sor 4. eleméről látható be, hogy az biztosan páratlan.
3. Fontos, hogy a kis házi feladat megoldásában a szomszédsági megszorításokat megadó s és w jeleket 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ő Erlang és az első Prolog példa illusztrálja ezt: bár ki lehetne következtetni, hogy a kérdezett mezőben nem szerepelhet a 4-es szám, a válasznak mégis tartalmaznia kell ezt a számot, a fenti definíciót követve.

A feladat

A feladat egy Sudoku-feladvány adott koordinátájú mezőjére nézve megengedett mezőértékek meghatározása.

A feladat bemenete tehát egy Sudoku-feladvány és azon belül egy mező helye. A Sudoku-feladványt a nagy házi feladatban specifikált Prolog-struktúrával, illetve Erlang-párral adjuk meg. A mező helyét az őt tartalmazó oszlop és sor sorszámával adjuk meg, ahol a számozást 1-gyel kezdjük. A feladat kimenete a megengedett mezőértékeket tartalmazó, esetleg üres lista. A lista elemeinek sorrendje tetszőleges, de ismétlődő elem nem lehet benne.

A házi feladat megoldása során a paraméterekre vonatkozó formai előírások meglétét nem kell ellenőriznie, azaz feltételezheti, hogy

• a feladványt leíró adatstruktúra megfelel a nagy házi feladat kiírásában megadott formai követelményeknek;
• az adott mezőt meghatározó sor- és oszlopkoordináták az 1..k*k tartományba esnek, ahol k a feladvány cellamérete.

Erlang-specifikációk

%% @type col() = integer().
%% @type row() = integer().
%% @spec khf2:ertekek(SSpec::sspec(), Col::col(), Row::row()) -> Vals::[integer()] 
%%   Vals az SSpec specifikációval megadott Sudoku-feladvány (Col,Row) koordinátájú
%%   mezőjében megengedett értékek listája. Tehát egy érték pontosan akkor 
%%   szerepel a Vals listában, ha:
%%    (1) 1..k*k közötti egész, ahol k az SSpec feladvány cellamérete,
%%    (2) teljesíti az adott mezőre vonatkozó e és o jelek, valamint a száminfó
%%        által előírt megszorításokat, továbbá
%%    (3) különbözik az adott mezőt tartalmazó sor, oszlop és cella összes többi
%%        mezőjére előírt száminfóktól.

-module(khf2).
-author(email@unit.org.hu).
-vsn('year-mm-dd').
-export([ertekek/3]).

Prolog-specifikációk

% :- type col  == int.
% :- type row  == int.
% :- pred ertekek(sspec::in, col::in, row::in, list(int)::out).
% ertekek(SSpec, Col, Row, Vals), ahol
%   SSpec az sspec specifikációnak megfelelő Sudoku-feladvány,
%   Col a col, Row a row típusnak megfelelő koordináta,
%   Vals list(int) típusú mezőértéklista.
% Vals az SSpec feladvány (Col,Row) koordinátájú mezőjében megengedett értékek
% listája, azaz azoknak az értékeknek a listája, amelyek teljesítik
% a fenti Erlang specifikációban felsorolt (1), (2) és (3) feltételeket.

Példák

Erlang

1> khf2:ertekek({2, [[      [2],      [e],       [],       []],
                     [       [],       [],       [],       []],
                     [       [],       [],       [],       []],
                     [       [],       [],       [],       []]]}, 3, 1).
[1, 3, 4]

2> khf2:ertekek({2, [[[e,w,2,s],      [w],      [e],       []],
                     [       [],  [e,s,w],       [],      [o]],
                     [       [],       [],      [1],       []],
                     [      [w],      [s],       [],       []]]}, 1, 3).
[3, 4]

3> khf2:ertekek({2, [[[e,w,2,s],      [w],      [e],       []],
                     [       [],  [e,s,w],       [],      [o]],
                     [       [],       [],      [1],       []],
                     [      [w],      [s],       [],       []]]}, 1, 1).
[2]

4> khf2:ertekek({2, [[[e,w,3,s],      [w],      [e],       []],
                     [       [],  [e,s,w],       [],      [o]],
                     [       [],       [],      [1],       []],
                     [      [w],      [s],       [],       []]]}, 1, 1).
[]

5> khf2:ertekek({2, [[[e,w,2,s],      [w],      [e],       []],
                     [       [],      [2],       [],      [o]],
                     [       [],       [],      [1],       []],
                     [      [w],      [s],       [],       []]]}, 2, 2).
[]

6> khf2:ertekek({2, [[[e,w,2,s],      [w],      [e],       []],
                     [       [],    [e,o],       [],      [o]],
                     [       [],       [],      [1],       []],
                     [      [w],      [s],       [],       []]]}, 2, 2).
[]

7> khf2:ertekek({3, [[  [2],   [],  [9],  [s],   [],  [s],  [s],  [e],   []],
                     [   [],  [s],  [4],  [w],  [9],  [8],   [],  [o],  [e]],
                     [   [],[e,w],  [1],  [w],   [],  [o],   [],  [w],[s,w]],
                     [   [],   [],   [],  [w],   [],  [w],   [],  [o],   []],
                     [   [],   [],   [],   [],  [w],   [],  [w],  [w],  [8]],
                     [   [],   [],   [],   [],   [],   [],  [o],  [o],   []],
                     [   [],   [],   [],  [3],   [],   [],  [1],  [e],  [s]],
                     [   [],   [],   [],  [1],   [],   [],  [2],   [],  [e]],
                     [   [],   [],   [],  [w],  [w],  [2],   [],  [w],   []]]}, 2, 3).
[6, 8]

Prolog

| ?- ertekek(s(2, [[      [v(2)],         [e],          [],          []],
                    [         [],          [],          [],          []],
                    [         [],          [],          [],          []],
                    [         [],          [],          [],          []]]), 4, 1, Vals).
Vals = [1,3,4] ? ;
no

| ?- ertekek(s(2, [[[e,w,v(2),s],         [w],         [e],          []],
                   [          [],     [e,s,w],          [],         [o]],
                   [          [],          [],      [v(1)],          []],
                   [         [w],         [s],          [],          []]]), 2, 2, Vals).
Vals = [4] ? ;
no

| ?- ertekek(s(2, [[[e,w,v(2),s],         [w],         [e],          []],
                   [          [],     [e,s,w],          [],         [o]],
                   [          [],          [],      [v(1)],          []],
                   [         [w],         [s],          [],          []]]), 1, 1, Vals).
Vals = [2] ? ;
no

| ?- ertekek(s(2, [[[e,w,v(3),s],         [w],         [e],          []],
                   [          [],     [e,s,w],          [],         [o]],
                   [          [],          [],      [v(1)],          []],
                   [         [w],         [s],          [],          []]]), 1, 1, Vals).
Vals = [] ? ;
no

| ?- ertekek(s(2, [[[e,w,v(2),s],         [w],         [e],          []],
                   [          [],      [v(2)],          [],         [o]],
                   [          [],          [],      [v(1)],          []],
                   [         [w],         [s],          [],          []]]), 2, 2, Vals).
Vals = [] ? ;
no

| ?- ertekek(s(3, [[[v(2)],   [],[v(9)],   [s],    [],   [s],   [s],  [e],    []],
                   [    [],  [s],[v(4)],   [w],[v(9)],[v(8)],    [],  [o],   [e]],
                   [    [],[e,w],[v(1)],   [w],    [],   [o],    [],  [w], [s,w]],
                   [    [],   [],    [],   [w],    [],   [w],    [],  [o],    []],
                   [    [],   [],    [],    [],   [w],    [],   [w],  [w],[v(8)]],
                   [    [],   [],    [],    [],    [],    [],   [o],  [o],    []],
                   [    [],   [],    [],[v(3)],    [],    [],[v(1)],  [e],   [s]],
                   [    [],   [],    [],[v(1)],    [],    [],[v(2)],   [],   [e]],
                   [    [],   [],    [],   [w],   [w],[v(2)],    [],  [w],    []]]), 6, 3, Vals).
Vals = [3, 5, 7] ? ;
no

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.

Gyakorló feladatok

1. Az L1 és az L2 lista L3 = L1 - L2 különbségének előállítása. (Itt L3 az L1-nek azokat az elemeit tartalmazza, amelyek L2-ben nem fordulnak elő.) Az ismétlődő elemek kezelésére többféle módszert is kipróbálhat.
2. Halmazok metszetének, uniójának, ill. különbségének előállítása (egy halmaz ábrázolására használhat rendezett vagy nem rendezett listát).
3. Lista rendezése különféle módszerekkel.