| BME Villamosmérnöki és Informatikai Kar
Mérnök-informatikus szak |
Nappali tagozat
2012/2013-es tanév, őszi félév
|
A feladat a félévi nagy házi feladathoz kapcsolódik, az ott megadott definíciók ismeretét feltételezzük.
A feladat egy Sudoku-megoldás helyességének ellenőrzése, azaz annak eldöntése, hogy az adott Sudoku-megoldás helyes megoldása-e egy adott Sudoku-feladványnak, a nagy házi feladat definíciós részében leírtak értelmében.
A Sudoku-feladványt a nagy házi feladatban leírt Prolog-struktúrával, illetve Erlang-párral adjuk meg.
A Sudoku-megoldás a Sudoku-feladvánnyal azonos méretű, egész számokból álló mátrix, amelyet listák listájaként ábrázolunk.
Egy n=k*k sorból és n oszlopból álló
Sudoku-megoldás akkor helyes egy adott Sudoku-feladványra nézve, ha
1 és
n közötti, egymástól különböző értékű mezők vannak,
A feladvány és a megoldás méretét, illetve az infók formáját nem kell ellenőrizni,
feltehető, hogy a feladványnak és a megoldásnak a megadott
k cellaméretnek megfelelő számú sora és oszlopa van, és az is,
hogy az infókat a specifikációban leírtak szerint adtuk meg.
khf3:helyese/2 néven egy Sudoku-megoldás
helyességének a megállapítására.
%% @spec khf3:helyese(SSpec::sspec(), SSol::ssol()) -> B::bool().
%% B igaz, ha a teljesen kitöltött SSol Sudoku-megoldás
%% (a) minden sorában, oszlopában, illetve cellájában egymástól különböző
%% értékű, az SSpec által előírt tartományba eső egészek vannak,
%% (b) kielégíti az SSpec specifikációt.
A programot tartalmazó modul attribútumai ezek legyenek:
-module(khf3).
-author(email@unit.org.hu).
-vsn('year-mm-dd').
-export([helyese/2]).
helyese/2 néven egy Sudoku-megoldás
helyességének a megállapítására.
% :- type ssol == list(list(int)).
% :- pred helyese(sspec::in, ssol::in).
% helyese(+SSpec,+SSol) : sikeres, ha a teljesen kitöltött SSol Sudoku-megoldás
% (a) minden sorában, oszlopában, illetve cellájában egymástól különböző
% értékű, az SSpec által előírt tartományba eső egészek vannak,
% (b) kielégíti az SSpec specifikációt.
1> khf3:helyese({2,
[[ [2], [w], [], [w]],
[ [], [s], [], [o]],
[ [], [], [1], []],
[ [], [], [], []]]},
[[2,3, 4,1],
[4,1, 2,3],
[3,2, 1,4],
[1,4, 3,2]]
).
false
2> khf3:helyese({2,
[[ [2], [w], [], []],
[ [], [s], [], [o]],
[ [], [], [1], []],
[ [], [], [], []]]},
[[2,3, 4,1],
[4,1, 2,3],
[3,2, 1,4],
[1,4, 3,2]]
).
true
3> khf3:helyese({2,
[[ [e,w,2,s], [w], [e], []],
[ [], [e,s,w], [], [o]],
[ [], [], [1], []],
[ [w], [s], [], []]]},
[[2,1, 4,3],
[3,4, 2,1],
[4,3, 1,2],
[1,2, 3,4]]
).
true
4> khf3:helyese({3,
[[ [], [2], [3], [4], [1], [], [5], [8], []],
[ [], [7], [8], [], [], [], [], [2], [1]],
[ [], [], [5], [7], [2], [], [], [3], [9]],
[ [], [8], [2], [9], [6], [1], [], [4], []],
[ [], [9], [], [5], [], [4], [], [1], []],
[ [], [6], [], [2], [7], [3], [9], [5], []],
[ [7], [4], [], [], [9], [5], [3], [], []],
[ [2], [3], [], [], [], [], [8], [9], []],
[ [], [5], [9], [], [3], [2], [1], [7], []]]},
[[6,2,3, 4,1,9, 5,8,7],
[9,7,8, 3,5,6, 4,2,1],
[4,1,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],
[1,6,4, 2,7,3, 9,5,8],
[7,4,1, 8,9,5, 3,6,2],
[2,3,6, 1,4,7, 8,9,5],
[8,5,9, 6,3,2, 1,7,4]]
).
true
5> khf3:helyese({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,8,9, 6,1,7, 5,4,3],
[3,7,4, 5,9,8, 6,1,2],
[5,6,1, 2,4,3, 9,8,7],
[7,3,8, 9,2,1, 4,5,6],
[1,9,5, 7,6,4, 3,2,8],
[4,2,6, 8,3,5, 7,9,1],
[8,4,2, 3,7,9, 1,6,5],
[9,5,7, 1,8,6, 2,3,4],
[6,1,3, 4,5,2, 8,7,9]]
).
true
|?- helyese(s(2,
[[[v(2)], [w], [], [w]],
[ [], [s], [], [o]],
[ [], [], [v(1)], []],
[ [], [], [], []]]),
[[2,3, 4,1],
[4,1, 2,3],
[3,2, 1,4],
[1,4, 3,2]]
).
no
|?- helyese(s(2,
[[[v(2)], [w], [], []],
[ [], [s], [], [o]],
[ [], [], [v(1)], []],
[ [], [], [], []]]),
[[2,3, 4,1],
[4,1, 2,3],
[3,2, 1,4],
[1,4, 3,2]]
).
yes
|?- helyese(s(2,
[[[e,w,v(2),s], [w], [e], []],
[ [], [e,s,w], [], [o]],
[ [], [], [v(1)], []],
[ [w], [s], [], []]]),
[[2,1, 4,3],
[3,4, 2,1],
[4,3, 1,2],
[1,2, 3,4]]
).
yes
|?- helyese(s(3,
[[ [],[v(2)],[v(3)], [v(4)],[v(1)], [], [v(5)],[v(8)], []],
[ [],[v(7)],[v(8)], [], [], [], [],[v(2)],[v(1)]],
[ [], [],[v(5)], [v(7)],[v(2)], [], [],[v(3)],[v(9)]],
[ [],[v(8)],[v(2)], [v(9)],[v(6)],[v(1)], [],[v(4)], []],
[ [],[v(9)], [], [v(5)], [],[v(4)], [],[v(1)], []],
[ [],[v(6)], [], [v(2)],[v(7)],[v(3)], [v(9)],[v(5)], []],
[[v(7)],[v(4)], [], [],[v(9)],[v(5)], [v(3)], [], []],
[[v(2)],[v(3)], [], [], [], [], [v(8)],[v(9)], []],
[ [],[v(5)],[v(9)], [],[v(3)],[v(2)], [v(1)],[v(7)], []]]),
[[6,2,3, 4,1,9, 5,8,7],
[9,7,8, 3,5,6, 4,2,1],
[4,1,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],
[1,6,4, 2,7,3, 9,5,8],
[7,4,1, 8,9,5, 3,6,2],
[2,3,6, 1,4,7, 8,9,5],
[8,5,9, 6,3,2, 1,7,4]]
).
yes
|?- helyese(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], []]]),
[[2,8,9, 6,1,7, 5,4,3],
[3,7,4, 5,9,8, 6,1,2],
[5,6,1, 2,4,3, 9,8,7],
[7,3,8, 9,2,1, 4,5,6],
[1,9,5, 7,6,4, 3,2,8],
[4,2,6, 8,3,5, 7,9,1],
[8,4,2, 3,7,9, 1,6,5],
[9,5,7, 1,8,6, 2,3,4],
[6,1,3, 4,5,2, 8,7,9]]
).
yes
A programot az Elektronikus
Tanársegéd (ETS) segítségével weben keresztül lehet beadni, a HF
beadás menüpont alatt. Ez a hármas számú kis
házi feladat, ennek megfelelően az ETS a beküldött megoldást
khf3.pl, ill. khf3.erl néven tárolja el és hivatkozik rá.
(A feltöltendő állomány neve tetszőleges lehet, az ETS átnevezi.)
A vizsgaosztályzat megállapításakor a határidőre beadott, minden tesztesetre helyesen működő feladatmegoldásért plusz 1-1 pont jár.