| BME Villamosmérnöki és Informatikai Kar
Mérnök-informatikus szak |
Nappali tagozat
2008/2009-es tanév, őszi félév
|
A feladat azoknak a megengedett mezőértékeknek a meghatározása,
amelyek a félévi nagy
házi feladatban specifikált Sudoku-tábla egy adott mezőjében
előfordulhatnak. Ha a Sudoku-táblában k a cellák oldalhossza,
akkor a mezők értéke 1..k*k közötti egész szám lehet. E
tartományon belül egy adott mező megengedett értékeit a rá, valamint az őt
magában foglaló sor, oszlop, illetve cella mezőire vonatkozó infók szabják
meg.
A Sudoku-táblát a nagy házi feladatban specifikált Prolog-struktúrával, illetve Erlang-párral adjuk meg. A Sudoku-tábla bal felső mezőjének koordinátája: (1,1). Az adott mezőt a koordinátáival határozzuk meg. Eredményként a megengedett mezőértékeket tartalmazó listát kell visszaadni. A lista elemeinek sorrendje tetszőleges, de ismétlődő elem nem lehet benne.
A kis házi feladatban a nagy házi feladatban ismertetett infóelemek közül a
számértékeket, továbbá az adott mezőre vonatkozó e
és o jeleket kell figyelembe venni, a szomszédsági
megszorításokat megadó s és w jeleket figyelmen
kívül kell hagyni.
Egy adott mező értékeként megengedett egy szám, ha 1..k*k
közötti egész, teljesíti az adott mezőre vonatkozó e és
o jelek, valamint a számérték által előírt megszorításokat, továbbá
különbözik az adott mezőt tartalmazó sor, oszlop és cella összes többi mezőjére
előírt számértéktől.
ertekek/3 néven, amely egy Sudoku-tábla
adott mezőjére előállítja a megengedett mezőértékek listáját. Ha a
megadott paraméterekkel a lista nem állítható elő, az eredmény
a false atom legyen.
%% @type col() = integer().
%% @type row() = integer().
%% @spec khf2:ertekek(SSpec::sspec(), Col::col(), Row::row()) -> Vals::[integer()]
%% Vals az SSpec specifikációval megadott Sudoku-tábla (Col,Row) koordinátájú
%% mezőjében megengedett értékek listája. Tehát egy érték pontosan akkor
%% szerepel a Vals listában, ha:
%% (a) 1..k*k közötti egész, ahol k az SSpec tábla cellamérete,
%% (b) teljesíti az adott mezőre vonatkozó e és o jelek, valamint a számérték
%% által előírt megszorításokat, továbbá
%% (c) különbözik az adott mezőt tartalmazó sor, oszlop és cella összes többi
%% mezőjére előírt számértéktől.
A programot tartalmazó modul két attribútuma ez legyen:
-module(khf2). -export([ertekek/3]).
ertekek/4 néven, amely egy Sudoku-tábla
adott mezőjére előállítja a megengedett mezőértékek listáját. Ha a
megadott paraméterekkel a lista nem állítható elő, az eljárás hiúsuljon
meg.
% :- type col == int.
% :- type row == int.
% :- pred ertekek(sspec::in, col::in, row::in, list(int)::out).
% ertekek(SSpec, Col, Row, Vals), ahol
% SSpec az sspec specifikációnak megfelelő Sudoku-tábla,
% Col a col, Row a row típusnak megfelelő koordináta,
% Vals list(int) típusú mezőértéklista.
% Vals az SSpec tábla (Col,Row) koordinátájú mezőjében megengedett értékek
% listája, azaz azoknak az értékeknek a listája, amelyek teljesítik
% a fenti Erlang specifikációban felsorolt (a), (b) és (c) feltételeket.
| ?- ertekek(s(2, [[[e,w,v(2),s], [w], [e], []],
[ [], [e,s,w], [], [o]],
[ [], [], [v(1)], []],
[ [w], [s], [], []]]), 2, 2, Vals).
Vals = [4] ? ;
no
| ?- ertekek(s(2, [[[e,w,v(2),s], [w], [e], []],
[ [], [e,s,w], [], [o]],
[ [], [], [v(1)], []],
[ [w], [s], [], []]]), 2, 9, Vals).
no
| ?- ertekek(s(2, [[[e,w,v(2),s], [w], [e], []],
[ [], [e,s,w], [], [o]],
[ [], [], [v(1)], []],
[ [w], [s], [], []]]), 1, 1, Vals).
Vals = [2] ? ;
no
| ?- ertekek(s(2, [[[e,w,v(3),s], [w], [e], []],
[ [], [e,s,w], [], [o]],
[ [], [], [v(1)], []],
[ [w], [s], [], []]]), 1, 1, Vals).
Vals = [] ? ;
no
| ?- ertekek(s(2, [[[e,w,v(2),s], [w], [e], []],
[ [], [v(2)], [], [o]],
[ [], [], [v(1)], []],
[ [w], [s], [], []]]), 2, 2, Vals).
Vals = [] ? ;
no
| ?- ertekek(s(3, [[[v(2)], [],[v(9)], [s], [], [s], [s], [e], []],
[ [], [s],[v(4)], [w],[v(9)],[v(8)], [], [o], [e]],
[ [],[e,w],[v(1)], [w], [], [o], [], [w], [s,w]],
[ [], [], [], [w], [], [w], [], [o], []],
[ [], [], [], [], [w], [], [w], [w],[v(8)]],
[ [], [], [], [], [], [], [o], [o], []],
[ [], [], [],[v(3)], [], [],[v(1)], [e], [s]],
[ [], [], [],[v(1)], [], [],[v(2)], [], [e]],
[ [], [], [], [w], [w],[v(2)], [], [w], []]]), 6, 3, Vals).
Vals = [3, 5, 7] ? ;
no
1> khf2:ertekek({2, [[[e,w,2,s], [w], [e], []],
[ [], [e,s,w], [], [o]],
[ [], [], [1], []],
[ [w], [s], [], []]]}, 1, 3).
[3, 4]
2> khf2:ertekek({2, [[[e,w,2,s], [w], [e], []],
[ [], [e,s,w], [], [o]],
[ [], [], [1], []],
[ [w], [s], [], []]]}, 1, 9).
false
3> khf2:ertekek({2, [[[e,w,2,s], [w], [e], []],
[ [], [e,s,w], [], [o]],
[ [], [], [1], []],
[ [w], [s], [], []]]}, 1, 1).
[2]
4> khf2:ertekek({2, [[[e,w,3,s], [w], [e], []],
[ [], [e,s,w], [], [o]],
[ [], [], [1], []],
[ [w], [s], [], []]]}, 1, 1).
[]
5> khf2:ertekek({2, [[[e,w,2,s], [w], [e], []],
[ [], [2], [], [o]],
[ [], [], [1], []],
[ [w], [s], [], []]]}, 2, 2).
[]
6> khf2:ertekek({2, [[[e,w,2,s], [w], [e], []],
[ [], [e,o], [], [o]],
[ [], [], [1], []],
[ [w], [s], [], []]]}, 2, 2).
[]
7> khf2:ertekek({3, [[ [2], [], [9], [s], [], [s], [s], [e], []],
[ [], [s], [4], [w], [9], [8], [], [o], [e]],
[ [],[e,w], [1], [w], [], [o], [], [w],[s,w]],
[ [], [], [], [w], [], [w], [], [o], []],
[ [], [], [], [], [w], [], [w], [w], [8]],
[ [], [], [], [], [], [], [o], [o], []],
[ [], [], [], [3], [], [], [1], [e], [s]],
[ [], [], [], [1], [], [], [2], [], [e]],
[ [], [], [], [w], [w], [2], [], [w], []]]}, 2, 3).
[6, 8]
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.