Deklaratív programozás

Definíciók

Sudoku-mátrixnak hívunk egy olyan négyzetes mátrixot, amelyben a sorok (és az oszlopok) száma egy k² ≥ 1 négyzetszám. (Tehát a mátrix elemeinek száma k⁴.)

Egy Sudoku-mátrixban cellának hívunk egy olyan (folytonos) részmátrixot, amely k sorból és k oszlopból áll, és bal felső sarkának sor- ill. oszlopsorszáma i*k+1 ill. j*k+1, ahol 0 ≤ i,j ≤ k-1 (a sorokat és oszlopokat 1-től számozzuk).

Tehát egy Sudoku-mátrix k² darab diszjunkt cellára bontható szét. A cellákat a bal felső sarkuk (R, C) sor-oszlop koordinátapárjai lexikografikus rendezésének megfelelően rakjuk sorba, és látjuk el egy 1 és k² közötti sorszámmal (R ill. C a bal felső sarok sorának ill. oszlopának száma). Másképpen mondva a cellákat sorfolytonosan számozzuk, 1-től kezdve.

A Sudoku-mátrix elemeit az alábbiakban mezőknek is nevezzük.

Megjegyezzük, hogy a fenti definíciók megegyeznek a félévi nagy házi feladatban leírt definíciókkal.

A feladat

Az S Sudoku-mátrixot egy olyan (Prolog ill. Erlang) listaként adjuk meg, amelynek i. eleme a mátrix i. sorának mezőit tartalmazó lista.

A C eredményt egy olyan lista formájában várjuk, amely a keresett cella mezőinek értékét oszlopfolytonosan tartalmazza.

A Sudoku-mátrix mezőinek típusa és értéke a jelen feladat szempontjából érdektelen, de az alábbi specifikációkban úgy tekintjük, hogy a mezők egész számok.

Feltételezheti, hogy

1. az S lista hossza egy k²≥ 1 négyzetszám;
2. S minden elemének (azaz a mátrix minden sorának) a hossza szintén k²;
3. az I sorszám-paraméter értékére fennáll, hogy 1 ≤ I ≤ k².

Prolog-specifikációk

Írjon Prolog-eljárást cella/3 néven, amely egy Sudoku-mátrixból egy adott sorszámú cellát vág ki, és a fent specifikált módon adja vissza.

% :- type field == int.
% :- type board  == list(list(field)).
% :- pred cella(board::in, int::in, list(field)::out).
% cella(S, I, C): C egy olyan lista, amely az S Sudoku-mátrix I.
%    cellájának elemeit oszlopfolytonosan tartalmazza.

	K is integer(sqrt(M)).

Erlang-specifikációk

%% @type field() = integer().
%% @type board() = [[field()]].
%% @spec khf1:cella(S::board(), I::integer()) -> C::[field()].
%%   C egy olyan lista, amely az S Sudoku-mátrix I.
%%   cellájának elemeit oszlopfolytonosan tartalmazza.

-module(khf1).
-author(email@unit.org.hu).
-vsn('year-mm-dd').
-export([cella/2]).
%-compile(export_all).

Példák

Prolog

| ?- cella([[6]], 1, C).
C = [6] ? ;
no

| ?- cella([[6,2,3,4],
            [9,7,8,3],
            [1,4,5,7],
            [4,6,1,2]], 4, C).
C = [5,1,7,2] ? ;
no

| ?- cella([[0,8,0,2,3,4,1,0,5],
            [0,0,9,0,5,0,4,0,1],
            [8,0,0,2,9,6,1,0,4],
            [0,2,1,7,8,0,0,0,0],
            [0,3,9,0,5,7,2,0,7],
            [0,4,0,8,2,9,6,1,3],
            [0,1,0,9,0,5,0,4,0],
            [0,5,0,6,0,2,7,3,9],
            [0,0,0,0,0,0,0,0,0]], 6, C).
C = [0,2,6,0,0,1,0,7,3] ? ;
no

Erlang

1> khf1:cella([[0]], 1).
[0]

2> khf1:cella([[6,2,3,4],
               [9,7,8,3],
               [1,4,5,7],
               [4,6,1,2]], 2).
[3,8,4,3]

3> khf1:cella([[0,8,0,2,3,4,1,0,5],
               [0,0,9,0,5,0,4,0,1],
               [8,0,0,2,9,6,1,0,4],
               [0,2,1,7,8,0,0,0,0],
               [0,3,9,0,5,7,2,0,7],
               [0,4,0,8,2,9,6,1,3],
               [0,1,0,9,0,5,0,4,0],
               [0,5,0,6,0,2,7,3,9],
               [0,0,0,0,0,0,0,0,0]], 4).
[0,0,0,2,3,4,1,9,0]

Tudnivalók a beadásról

A programok készülhetnek MS Windows alatt is, de Linux alatt is mûködniük kell. A beadott programokat Linux környezetben a SICStus Prolog 4.2.x, ill. az Erlang/OTP R14A rendszerekkel teszteljük.

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 az egyes számú kis házi feladat, ennek megfelelően az ETS a beküldött megoldást khf1.pl, ill. khf1.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

1. Lista szeletének (i. és j. sorszámú elemek közötti részének) előállítása.
2. Sorfolytonosan, illetve oszlopfolytonosan tárolt mátrix i. sorának előallítása.
3. Sorfolytonosan, illetve oszlopfolytonosan tárolt mátrix j. oszlopának előállítása.
4. Sorok listájaként tárolt mátrix sorfolytonosan, illetve oszlopfolytonosan tárolt változatának előállítása.
5. Sorfolytonosan, illetve oszlopfolytonosan tárolt mátrix sorok listájaként tárolt változatának előállítása.