Deklaratív programozás

A feladat

A feladat a közismert Sudoku rejtvényhez kapcsolódik.

Egy Sudoku-tábla egy m=k*k sorból és m oszlopból álló négyzetes táblázat, amely m darab k*k méretű négyzetes cellára bomlik. A kis házi feladat megoldásakor feltételezheti, hogy 1 ≤ k ≤ 5.

A feladat egy részlegesen kitöltött Sudoku-tábla ellentmondásmentességének ellenőrzése. A Sudoku-táblát sorok listájaként adjuk meg, ahol a sorok egész számok listái. Feltételezheti (tehát nem kell ellenőriznie), hogy a sorok listája pontosan m sort és soronként pontosan m számot tartalmaz, ahol a számok 0 és m közé esnek. A 0 szám a még ki nem töltött mezőket jelöli.

Egy Sudoku-táblát ellentmondásosnak nevezünk, ha van olyan sora, oszlopa vagy cellája, amelyben egy nullától különböző egész szám legalább kétszer előfordul.

Erlang-specifikációk

%% @type ssol() = [[integer()]].
%% @spec khf1:consistent(SSol::ssol()) -> B::bool().
%% B igaz, ha az SSol Sudoku-tábla minden egyes sorára, oszlopára és
%% cellájára fennáll, hogy a benne előforduló pozitív számok mind különbözőek. 

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

Prolog-specifikációk

% :- type ssol == list(list(int)).
% :- pred consistent(ssol::in).
% consistent(SSol): A SSol Sudoku-tábla minden egyes sorára, oszlopára és
% cellájára fennáll, hogy a benne előforduló pozitív számok mind különbözőek.

Megjegyzés: Az is/2 beépített eljárás alábbi hívásával lehet egy M négyzetszám gyökét egész számként a K változóban előállítani:

	K is integer(sqrt(M)).

Példák

Prolog

|?- consistent(
               [[1]]
              ).
yes

 |?- consistent(
		[[2,3, 4,1],
		 [4,0, 2,0],

		 [0,2, 1,4],
		 [0,4, 0,2]]
	       ).
yes

 |?- consistent(
		[[2,3, 0,1],
		 [1,0, 2,3],

		 [3,2, 1,4],
		 [4,0, 0,1]]
               ).
no

 |?- consistent(
		[[0,0, 0,0],
		 [0,0, 0,0],

		 [0,0, 0,0],
		 [0,0, 0,0]]
	       ).
yes

 |?- consistent(
		[[0,0, 0,0],
		 [0,0, 0,0],

		 [1,0, 0,0],
		 [0,1, 0,0]]
	       ).
no

Erlang

khf1:consistent(
		[[1]]
	       ).
true

khf1:consistent(
		[[2,3, 4,1],
		 [4,0, 2,0],

		 [0,2, 1,4],
		 [0,4, 0,2]]
	       ).
true

khf1:consistent(
		[[2,3, 0,1],
		 [1,0, 2,3],

		 [3,2, 1,4],
		 [4,0, 0,1]]
	       ).
false

khf1:consistent(
		[[0,0, 0,0],
		 [0,0, 0,0],

		 [0,0, 0,0],
		 [0,0, 0,0]]
	       ).
true

khf1:consistent(
		[[0,0, 0,0],
		 [0,0, 0,0],

		 [1,0, 0,0],
		 [0,1, 0,0]]
	       ).
false

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.