| BME Villamosmérnöki és Informatikai Kar
Mérnök-informatikus alapszak |
Nappali tagozat
2016/2017-es tanév, őszi félév
|
A feladat egy teljesen kitöltött Sudoku helyességének ellenőrzése. Azaz, felhasználva a félévi nagy házi feladat kiírásában szereplő definíciókat, a feladat annak eldöntése, hogy egy adott érték-mátrix megoldása-e egy adott Sudoku-feladványnak, vagyis, hogy az érték-mátrix a Sudoku-feladvány által előírt összes megszorítást kielégíti-e.
A mátrixok méretét, illetve az infók formáját nem kell ellenőrizni,
feltehető, hogy a feladványnak és az érték-mátrixnak 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.
megoldase/2 néven annak megállapítására,
hogy egy adott érték-mátrix megoldása-e egy adott Sudoku-feladványnak.
% :- pred megoldase(sspec::in, ssol::in).
% megoldase(+SSpec,+SSol) : sikeres, ha az SSol érték-mátrix megoldása az SSpec Sudoku-feladványnak.
khf3:megoldase/2 néven annak megállapítására,
hogy egy adott érték-mátrix megoldása-e egy adott Sudoku-feladványnak.
%% @spec khf3:megoldase(SSpec::sspec(), SSol::ssol()) -> B::bool().
%% B igaz, ha SSol megoldása az SSpec feladványnak.
A programot tartalmazó modul attribútumai ezek legyenek:
-module(khf3).
-author('email@unit.org.hu').
-vsn('year-mm-dd').
-export([megoldase/2]).
|?- megoldase(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]]
).
yes
|?- megoldase(s(2,
[[[v(2)], [w], [s], []],
[ [], [s], [], [o]],
[ [], [], [v(1)], []],
[ [], [], [], []]]),
[[2,3, 4,1],
[4,1, 2,3],
[3,2, 1,4],
[1,4, 3,2]]
).
no
|?- megoldase(s(2,
[[ [e,v(2),s], [w], [e], []],
[ [], [e,s,w], [], [o]],
[ [], [], [v(1)], []],
[ [], [], [], []]]),
[[2,1, 4,3],
[3,4, 2,1],
[4,3, 1,2],
[1,2, 3,4]]
).
yes
|?- megoldase(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
|?- megoldase(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
khf3:megoldase({2,
[[ [], [], [], []],
[ [], [], [], []],
[ [], [], [], []],
[ [], [], [], []]]},
[[2,3, 4,1],
[4,1, 2,3],
[3,2, 1,4],
[1,4, 3,2]]
).
true
khf3:megoldase({2,
[[ [2], [w], [], [w]],
[ [], [s], [], [o]],
[ [], [], [1], []],
[ [], [], [], []]]},
[[2,3, 4,1],
[4,1, 2,3],
[3,2, 1,4],
[1,4, 3,2]]
).
true
khf3:megoldase({2,
[[ [], [], [], []],
[ [], [], [], []],
[ [], [], [], []],
[ [], [], [], []]]},
[[2,4, 3,1],
[4,1, 2,3],
[3,2, 1,4],
[1,3, 4,2]]
).
false
khf3:megoldase({2,
[[ [], [], [], []],
[ [], [], [], []],
[ [], [], [], []],
[ [], [], [], []]]},
[[2,3, 4,1],
[4,1, 2,3],
[1,4, 1,4],
[3,2, 3,2]]
).
false
khf3:megoldase({2,
[[ [], [], [], []],
[ [], [], [], []],
[ [], [], [], []],
[ [], [], [], []]]},
[[2,3, 4,1],
[4,1, 2,3],
[3,2, 1,4],
[1,4, 2,3]]
).
false
khf3:megoldase({2,
[[ [], [], [], []],
[ [], [], [], []],
[ [], [], [], []],
[ [], [], [2], []]]},
[[2,3, 4,1],
[4,1, 2,3],
[3,2, 1,4],
[1,4, 3,2]]
).
false
khf3:megoldase({2,
[[ [], [], [], []],
[ [], [], [], []],
[ [], [], [], []],
[ [], [], [e], []]]},
[[2,3, 4,1],
[4,1, 2,3],
[3,2, 1,4],
[1,4, 3,2]]
).
false
khf3:megoldase({2,
[[ [], [], [], []],
[ [], [], [], []],
[ [], [], [], []],
[ [], [], [], [o]]]},
[[2,3, 4,1],
[4,1, 2,3],
[3,2, 1,4],
[1,4, 3,2]]
).
false
khf3:megoldase({2,
[[ [], [], [], []],
[ [], [], [], []],
[ [], [], [], [s]],
[ [], [], [], []]]},
[[2,3, 4,1],
[4,1, 2,3],
[3,2, 1,4],
[1,4, 3,2]]
).
false
khf3:megoldase({2,
[[ [], [], [w], []],
[ [], [], [], []],
[ [], [], [], []],
[ [], [], [], []]]},
[[3,2, 4,1],
[4,1, 2,3],
[2,3, 1,4],
[1,4, 3,2]]
).
false
khf3:megoldase({2,
[[ [2], [w], [s], []],
[ [], [s], [], [o]],
[ [], [], [1], []],
[ [], [], [], []]]},
[[2,3, 4,1],
[4,1, 2,3],
[3,2, 1,4],
[1,4, 3,2]]
).
false
khf3:megoldase({2,
[[ [e,2,s], [w], [e], []],
[ [], [e,s,w], [], [o]],
[ [], [], [1], []],
[ [], [], [], []]]},
[[2,1, 4,3],
[3,4, 2,1],
[4,3, 1,2],
[1,2, 3,4]]
).
true
khf3:megoldase({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
khf3:megoldase({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
A programok készülhetnek MS Windows alatt is, de Linux alatt is működniük kell. A beadott programokat Linux környezetben a SICStus Prolog 4.3.x, ill. az Erlang/OTP R16B rendszerekkel teszteljük.
Ennek a kis házi feladatnak a beadása ugyan nem kötelező, azonban a félévközi követelmények teljesítéséhez a félév során legalább három kisházifeladat-megoldást – közülük legalább egyet Prolog és legalább egyet Erlang nyelven – sikeresen be kell adni. Sikeres az a megoldás, amelyik az összes tesztesetre helyes választ ad. Ha ezt a kis házi feladatot mindkét nyelven sikeresen beadja, az természetesen két megoldásnak számit.
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.)
Az osztá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.