BME Villamosmérnöki és Informatikai Kar
Gazdasági informatikus mesterszak
Nappali tagozat
2012/2013-es tanév, őszi félév

Alkalmazott funkcionális és logikai programozás

1. házi feladat: Sudoku cella előállítása

1.0 változat
Utolsó módosítás: 2012-10-10
Kiadás: 2012-10-08
Beadási határidő: Prolog 2012-10-22, 23:59; F# 2012-10-29, 23:59

Definíciók

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

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

A feladat

A feladat egy adott S Sudoku-mátrix egy adott I sorszámú C cellájának előállítása.

Az S Sudoku-mátrixot egy olyan (Prolog, ill. F#) 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 k2≥ 1 négyzetszám,
  2. S minden elemének (azaz a mátrix minden sorának) a hossza szintén k2;
  3. az I sorszám-paraméter értékére fennáll, hogy 1 ≤ I ≤ k2.

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.

F#-specifikációk

Írjon F#-függvényt cella/2 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 = field list list
// val cella : board -> int -> field list
// cella S I = egy olyan lista, amely az S Sudoku-mátrix I.
//   cellájának elemeit oszlopfolytonosan tartalmazza.
A programot tartalmazó modul első három sora ez legyen (értelemszerűen a program írójának levélcímét és az aktuális programverzió keltét írja be a megfelelő helyekre):
module cella
// author(email@unit.org.hu)
// vsn('year-mm-dd')

Példák

| ?- 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
1> cella.cella [[0]] 1;;
[0]
2> cella.cella [[6;2;3;4];
                [9;7;8;3];
                [1;4;5;7];
                [4;6;1;2]]  2;;
[3;8;4;3]
3> cella.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 házi feladat Prolog-, illetve F#-megoldását elektronikus levélben kell elküldeni az adott tárgyrész előadójának.

Gyakorló feladatok

A házi feladat megoldásának előkészítésére a következő kisebb feladatok megoldását javasoljuk.
  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.