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

Deklaratív programozás

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

1.0 változat
Utolsó módosítás: 2012-10-10
Kiadás: 2012-10-12
Beadási határidő: Prolog 2012-11-19 hétfő, 23:59; Erlang 2012-11-26 hétfő, 23:59

A feladat

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. minden sorában, oszlopában, illetve cellájában 1 és n közötti, egymástól különböző értékű mezők vannak,
  2. kielégíti az adott Sudoku-feladványt, azaz a benne szereplő ún. segítő információk (infók) által előírt összes feltételt.

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.

Erlang-specifikációk

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

Prolog-specifikációk

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

Példák

Erlang

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

Prolog

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

Tudnivalók a beadásról

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.)

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.

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.