Deklaratív programozás

1. kis házi feladat: Sudoku-mátrix előállítása

1.1 változat
Utolsó módosítás: 2008-03-19
Kiadás: 2008-03-06
Beadási határidő: 2008-03-25

A feladat

A feladat a féléves nagy házi feladatban specifikált Sudoku-táblából egy cellaméretű négyzetes mátrix előállítása.

A Sudoku-táblát a nagy házi feladatban specifikált Prolog-struktúrával, illetve SML-párral adjuk meg.

A kért mátrix bal felső mezőjét a Sudoku-tábla egy mezőjének a koordinátáival (a tábla egy oszlopának és egy sorának a megadásával) adjuk meg. A Sudoku-tábla bal felső mezőjének koordinátája: (1,1). Az eredmény egy olyan lista, amely a keresett mátrix mezőinek értékét sorfolytonosan tartalmazza.

SML-specifikációk

Írjon SML-függvényt matrix néven, amely egy Sudoku-táblából egy cellaméretű mátrixot állít elő. Ha a megadott paraméterekkel a mátrix nem állítható elő, az eredmény az üres lista.

(* type col = int
   type row = int
   matrix : (sspec, col, row) -> field list 
   matrix (t, x, y) = a t Sudoku-tábla (x,y) koordinátájú mezőjével meghatározott,
                      cellaméretű mátrix, sorfolytonos ábrázolással
*)

Prolog-specifikációk

Írjon Prolog-eljárást matrix/4 néven, amely egy Sudoku-táblából egy cellaméretű mátrixot állít elő. Ha a megadott paraméterekkel a mátrix nem állítható elő, az eljárás hiúsuljon meg.

% :- type col  == int.
% :- type row  == int.
% :- pred matrix(sspec::in, col::in, row::in, list(field)::out).
% matrix(T,X,Y,C), ahol
%   T az sspec specifikációnak megfelelő Sudoku-tábla,
%   X a col, Y a row típusnak megfelelő koordináta,
%   C a list(field) típusnak megfelelő mezőlista.

Példák

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

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

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

- matrix((3, [[0,2,3,4,1,0,5,8,0],
              [0,7,8,0,0,0,0,2,1],
              [0,0,5,7,2,0,0,3,9],
              [0,8,2,9,6,1,0,4,0],
              [0,9,0,5,0,4,0,1,0],
              [0,6,0,2,7,3,9,5,0]]), 5, 2);
> val it = [0,0,0,2,0,0,6,1,0] : int list

- matrix((3, [[6,2,3,4,1,9,5,8,7],
              [9,7,8,3,5,6,4,2,1],
              [1,4,5,7,2,8,6,3,9],
              [5,8,2,9,6,1,7,4,3],
              [3,9,7,5,8,4,2,1,6],
              [4,6,1,2,7,3,9,5,8]]), 5, 2);
> val it = [5,6,4,2,8,6,6,1,7] : int list

- matrix((3, [[6,2,3,4,1,9,5,8,7],
              [9,7,8,3,5,6,4,2,1],
              [1,4,5,7,2,8,6,3,9],
              [5,8,2,9,6,1,7,4,3],
              [3,9,7,5,8,4,2,1,6],
              [4,6,1,2,7,3,9,5,8]]), 8, 2);
> val it = [] : int list

Tudnivalók a beadásról

A programot az Elektronikus Tanársegéddel kell majd beadni, a HF beadás menüpont alatt. A beadási határidő 2008. március 25., kedd 24:00.

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.

Gyakorló feladatok

A tantermi gyakorlatokon és otthon a következő kisebb feladatok megoldását javasoljuk.

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

dp@inf.bme.hu