Deklaratív programozás

A feladat

Egy Sudoku-tábla akkor felel meg a nagy házi feladat szerinti specifikációnak, ha bármely sorában, oszlopában, illetve cellájában nincs két azonos - 0-tól különböző - értékű mező.

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

SML-specifikációk

(* helyese : sspec -> bool
   helyese t = igaz, ha a t részlegesen vagy teljesen kitöltött Sudoku-tábla helyes
*)

Prolog-specifikációk

% :- pred helyese(sspec::in).
% helyese(T), ahol az sspec specifikációnak megfelelő T egy részlegesen
%             vagy teljesen kitöltött Sudoku-tábla

Példák

|?- helyese(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]])).
yes

|?- helyese(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]])).
yes

|?- helyese(s(3, [[6,9,0, 1,8,0],
                  [0,3,0, 0,9,0],
                  [1,0,8, 6,0,5],

                  [5,2,6, 7,3,8],
                  [7,8,4, 1,5,9],
                  [9,1,3, 0,0,6]])).
no

- helyese(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]]);
> val it = true : bool

- helyese(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]]);
> val it = true : bool

- helyese(3, [[6,9,0, 1,8,0],
              [0,3,0, 0,9,0],
              [1,0,8, 6,0,5],

              [5,2,6, 7,3,8],
              [7,8,4, 1,5,9],
              [9,1,3, 0,0,6]]);
> val it = false : bool

Tudnivalók a beadásról

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

1. Annak eldöntése, hogy egy listában vannak-e ismétlődő elemek.
2. Annak eldöntése, hogy egy lista minden elemére teljesül-e egy adott predikátum.
3. Annak eldöntése, hogy egy lista legalább egy elemére teljesül-e egy adott predikátum.
4. Annak eldöntése, hogy egy többfelé ágazó rekurzív adatstruktúrában vannak-e ismétlődő elemek.
5. Annak eldöntése, hogy egy többfelé ágazó rekurzív adatstruktúra minden elemére teljesül-e egy adott predikátum.
6. Annak eldöntése, hogy egy többfelé ágazó rekurzív adatstruktúra legalább egy elemére teljesül-e egy adott predikátum.