BME Villamosmérnöki és Informatikai Kar
Mérnök-informatikus alapszak
Nappali tagozat
2016/2017-es tanév, őszi félév

Deklaratív programozás

3. kis házi feladat: Sudoku-megoldás ellenőrzése

1.1 változat
Utolsó módosítás: 2016-09-25
Kiadás: 2016-09-25
Beadási határidők a főoldalon.

A feladat

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.

Prolog-specifikációk

Írjon Prolog-eljárást 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.

Erlang-specifikációk

Írjon Erlang-függvényt 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]).

Példák

Az Erlang-tesztek minden alapesetre mutatunk példát, amikor az érték-mátrix nem megoldása a feladványnak. Természetesen programjának Prolog-változatát is érdemes lefuttatnia ezekre az alapesetekre.

Prolog

|?- 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

Erlang

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

Tudnivalók a beadásról

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.

Gyakorló feladatok

A házi feladat megoldásának előkészítésére a következő kisebb gyakorló 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, ill. mátrix minden elemére teljesül-e egy adott predikátum.
  3. Annak eldöntése, hogy egy lista, ill. mátrix legalább egy elemére teljesül-e egy adott predikátum.