BME Villamosmérnöki és Informatikai Kar
Mérnök-informatikus alapszak
Nappali tagozat
2009/2010-es tanév, tavaszi félév

Deklaratív programozás

1. kis házi feladat: Sudoku-tábla ellentmondásmentességének ellenőrzése

1.1 változat
Utolsó módosítás: 2010-03-15
Kiadás: 2010-02-21
Beadási határidő: Prolog 2010-03-17, 24:00; Erlang 2010-03-22, 24:00

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 1k5.

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

Írjon Erlang-függvényt khf1:consistent/1 néven egy Sudoku-tábla ellentmondásmentességének a megállapítására.
%% @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.
A programot tartalmazó modul attribútumai ezek legyenek:
-module(khf1).
-author(email@unit.org.hu).
-vsn('year-mm-dd').
-export([consistent/1]).
%-compile(export_all).

Prolog-specifikációk

Írjon Prolog-eljárást consistent/1 néven egy Sudoku-tábla ellentmondásmentességének a megállapítására.
% :- 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 programot az Elektronikus Tanársegéddel kell beadni (l. HF beadás menüpont).

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

Otthoni gyakorlásra a következő kisebb feladatok megoldását javasoljuk.
  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.

dp@inf.bme.hu