BME Villamosmérnöki és Informatikai Kar
Mérnök-informatikus szak
Nappali tagozat
2013/2014-es tanév, őszi félév

Deklaratív programozás

2. kis házi feladat: Megengedett mezőértékek meghatározása

1.0 változat
Utolsó módosítás: 2013-09-16
Kiadás: 2013-09-16
Beadási határidő: Prolog 2013-10-23, 23:59; Erlang 2013-10-27, 23:59

A feladat

A feladat azoknak a megengedett mezőértékeknek a meghatározása, amelyek a félévi nagy házi feladatban specifikált Sudoku-tábla egy adott mezőjében előfordulhatnak.

Legyen a Sudoku-táblában k a cellák oldalhossza. Egy adott mező értékeként megengedett egy szám, ha 1..k*k közötti egész, teljesíti az adott mezőben szereplő szám- és paritási infók által előírt megszorításokat, továbbá 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.

A feladat bemenete tehát egy Sudoku-tábla és azon belül egy mező. A Sudoku-táblát a nagy házi feladatban specifikált Prolog-struktúrával, illetve Erlang-párral adjuk meg. Az adott mezőt egy sor-oszlop koordinátapárral határozzuk meg, ahol a Sudoku-tábla bal felső mezőjének koordinátája: (1,1). 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.

Egy Sudoku feladvány megoldásában egy adott mezőben nyilván nem szerepelhet egy – a fenti definíció szerint – nem megengedett számérték, hiszen egy ilyen érték nem tesz eleget a Sudoku megoldásokra előírt valamelyik megszorításnak. Bonyolultabb következtetésekkel más értékekről is kimutatható, hogy nem szerepelhetnek a megoldás egy adott mezőjében. 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.

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 fent leírt definíció szerint kell a megengedett értékek listáját előállítani. Ilyen eseteket mutatunk be alább, a Prolog és Erlang példafutások között: az első két példában a megengedett értékek listájában szerepelnie kell a 4 számnak, annak ellenére, hogy belátható, hogy ez az érték az adott helyen nem szerepelhet az adott feladvány megoldásában.

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

Prolog-specifikációk

Írjon Prolog-eljárást ertekek/3 néven, amely egy adott Sudoku-tábla adott mezőjére előállítja a megengedett mezőértékek listáját. A szóbanforgó mezőt egy R-C struktúrával adjuk meg, ahol R a mező sorának, míg C a mező oszlopának a sorszáma, 1-től számozva.

% :- type col  == int.
% :- type row  == int.
% :- type coords -->row-col.
% :- pred ertekek(sspec::in, coords::in, list(int)::out).
% ertekek(SSpec, R_C, Vals), ahol
%   SSpec az sspec típusspecifikációnak megfelelő Sudoku-tábla.
%   R_C az adott tábla egy mezőjének (sor-oszlop formában megadott) koordinátája.
%   Vals list(int) típusú mezőértéklista, az SSpec tábla R_C koordinátájú
%   mezőjében megengedett értékek listája. Egy érték pontosan akkor szerepel
%   a Vals listában, ha:
%    (a) 1..k*k közötti egész, ahol k az SSpec tábla cellamérete,
%    (b) teljesíti az adott mezőre vonatkozó szám- és paritási infók
%        által előírt megszorításokat, továbbá
%    (c) különbözik az adott mezőt tartalmazó sor, oszlop és cella többi
%        mezőjében szereplő száminfóktól.

Erlang-specifikációk

Írjon Erlang-függvényt ertekek/2 néven, amely egy Sudoku-tábla adott mezőjére előállítja a megengedett mezőértékek listáját. A szóbanforgó mezőt egy {R,C} párral adjuk meg, ahol R a mező sorának, míg C a mező oszlopának a sorszáma, 1-től számozva.

%% @type col() = integer().
%% @type row() = integer().
%% @type coords() = {row(),col()}.
%% @spec khf2:ertekek(SSpec::sspec(), R_C::coords()) -> Vals::[integer()]
%%   Vals az SSpec specifikációval megadott Sudoku-tábla R_C
%%   koordinátájú mezőjében megengedett értékek listája.
%%   Egy érték pontosan akkor szerepel a Vals listában, ha teljesíti a
%%   fenti Prolog specifikációban felsorolt (a), (b) és (c) feltételeket.

A programot tartalmazó modul attribútumai ezek legyenek:
-module(khf2).
-author(email@unit.org.hu).
-vsn('year-mm-dd').
-export([ertekek/2]).

Példák

Prolog

| ?- ertekek(
             s(2, [[[v(2)],          [],         [e],          []],
                   [    [],         [s],          [],         [o]],
                   [    [],          [],      [v(1)],          []],
                   [    [],         [w],          [],          []]]), 1-4, Vals).
Vals = [1,3,4] ? ;
no
| ?- ertekek(
             s(2, [[[v(2)],         [w],          [],          []],
                   [    [],         [s],          [],         [o]],
                   [    [],          [],      [v(1)],          []],
                   [    [],         [w],          [],          []]]), 1-2, Vals).
Vals = [1,3,4] ? ;
no
| ?- ertekek(
             s(2, [[[v(2)],          [],         [e],          []],
                   [    [],         [s],          [],         [o]],
                   [    [],          [],      [v(1)],          []],
                   [    [],         [w],          [],          []]]), 1-3, Vals).
Vals = [4] ? ;
no
| ?- ertekek(
             s(2, [[[v(2)],          [],         [e],          []],
                   [    [],         [e],          [],         [o]],
                   [    [],          [],      [v(1)],          []],
                   [    [],         [w],          [],          []]]), 2-2, Vals).
Vals = [4] ? ;
no
| ?- ertekek(
             s(2, [[[v(2)],         [w],         [e],          []],
                   [    [],          [],          [],         [o]],
                   [    [],          [],      [v(4)],          []],
                   [    [],         [w],          [],          []]]), 1-3, Vals).
Vals = [] ? ;
no
| ?- ertekek(
             s(2, [[[v(2)],         [w],         [e],          []],
                   [    [],  [e,s,v(2)],          [],         [o]],
                   [    [],          [],      [v(4)],          []],
                   [    [],         [w],          [],          []]]), 1-1, 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],    []]]), 3-6, Vals).
Vals = [3,5,7] ? ;
no

Erlang

1> khf2:ertekek(
              {2, [[   [2],          [],         [e],          []],
                   [    [],         [s],          [],         [o]],
                   [    [],          [],         [1],          []],
                   [    [],         [w],          [],          []]]}, {1,4}).
[1, 3, 4]
2> khf2:ertekek(
              {2, [[   [2],         [w],          [],          []],
                   [    [],         [s],          [],         [o]],
                   [    [],          [],         [1],          []],
                   [    [],         [w],          [],          []]]}, {1,2}).
[1, 3, 4]
3> khf2:ertekek(
              {2, [[   [2],          [],         [e],          []],
                   [    [],         [s],          [],         [o]],
                   [    [],          [],         [1],          []],
                   [    [],         [w],          [],          []]]}, {1,1}).
[2]
4> khf2:ertekek(
              {2, [[   [2],          [],         [e],          []],
                   [    [],         [e],          [],         [o]],
                   [    [],          [],         [1],          []],
                   [    [],         [w],          [],          []]]}, {4,2}).
[1, 2, 3, 4]
5> khf2:ertekek(
              {2, [[    [],         [w],       [o,e],          []],
                   [    [],          [],          [],         [o]],
                   [    [],          [],          [],          []],
                   [    [],         [w],          [],          []]]}, {1,3}).
[]
6> khf2:ertekek(
              {2, [[   [o],         [w],         [e],          []],
                   [    [],     [e,s,1],          [],         [o]],
                   [    [],          [],         [4],          []],
                   [   [3],         [w],          [],          []]]}, {1,1}).
[]
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],    []]]}, {3,2}).
[6,8]
8> khf2:ertekek(
             {2, [[     [2],         [w],     [e],      []],
                  [      [],     [e,s,2],      [],     [o]],
                  [      [],          [],     [4],      []],
                  [      [],         [w],      [],     []]]}, {1,1}).
[]

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

Az osztá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

A házi feladat megoldásának előkészítésére a következő kisebb gyakorló feladatok megoldását javasoljuk.
  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. Egy sorok listájaként tárolt mátrix adott mezőjét befoglaló k-méretű cella elemeit tartalmazó lista előállítása.
  3. 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).
  4. Lista rendezése különféle módszerekkel.