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

Deklaratív programozás

Nagy házi feladat

1.0 változat
Utolsó módosítás: 2011-10-18
Kiadás: 2011-10-18

Sudoku-variáció: páratlan összegek

A megoldandó feladat a közismert Sudoku egy variánsa.

A Sudoku-feladvány egy n=k*k sorból és n oszlopból álló négyzetes tábla (mátrix), ahol 1 ≤ k ≤ 6. A táblát k*k méretű kis mátrixokra daraboljuk fel, a kis mátrixokat celláknak nevezzük. A feldarabolás analóg az 1. kis házi feladatban megismerttel: a Sudoku-tábla ott definiált (k,k) paraméterű feldarabolása nem más, mint a cellák listája.

A Sudoku-feladvány egyes mezői segítő információkat (röviden infókat) tartalmazhatnak. A feladvány megfejtése, azaz a Sudoku-megoldás a bemenettel azonos méretű olyan négyzetes tábla, amelynek minden mezője 1 és n közötti egészekkel van kitöltve úgy, hogy egy-egy cella összes mezőjében, továbbá a tábla egy-egy sorában, illetve oszlopában különböző számok vannak. Emellett a Sudoku-megoldásnak az infók által leírt feltételeknek is meg kell felelnie.

A legegyszerűbb esetben az infó egy szám: az adott mező előírt értéke. További infó lehet az, hogy az adott mező páros vagy páratlan értékű, illetve az, hogy az adott mező értéke és az alatta, illetve tőle balra levő mező értékének az összege páratlan. A száminfótól különböző előírásokból többféle is lehet egy mezőben.

Három Sudoku-feladványt mutatunk az 1. ábrán, ahol rendre k = 3, 2, 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

 

2

w

e

 

 

es4

 

o

 

 

1

 

w

 

 

2

 

9

s

 

s

s

e

 

3

s

4

w

9

8

 

o

e

 

ew

1

w

 

o

 

w

sw9

7

 

 

w

 

w

 

o

 

1

 

 

 

w

 

w

w

8

4

 

 

 

 

 

o

o

 

 

s

s

3

7

 

1

e

s

 

5

 

1

 

 

2

 

e

 

1

 

w

w

2

 

w

 

1. ábra

Az első feladványban csak száminfók vannak, mint a hagyományos Sudokuban. A második és harmadik feladványban betűk is szerepelnek, ezek jelentése:

Az e és o betűkkel jelzett megszorításokat együttesen paritási infónak, míg az s és w betűkkel jelzetteket szomszédsági infónak nevezzük.

A Sudoku-feladvány bal szélső oszlopának mezőiben nem állhat w, alsó sorának mezőiben pedig s, mivel ezek az infók nem létező mezőkre vonatkoznának.

Egy mezőben az ötféle infó (a száminfó ill. a négyféle, betűkkel jelzett infók) mindegyike legfeljebb egyszer szerepelhet. Megengedett, hogy ezek az infók ellentmondjanak egymásnak (pl. egy páratlan értéket jelző o infó mellett állhat egy páros szám száminfóként) – ilyen esetben természetesen a feladványnak nincs megoldása.

Az infók halmazának nem kell teljesnek lennie: ha egy infó nincs megadva a feladványban, az nem jelenti azt, hogy az infó által jelzett korlátozás nem teljesül. Például, ha egy mezőben nem szerepel e betű, attól még lehet az adott mező értéke páros. Hasonlóképpen, ha egy mezőben nem szerepel az s betű, attól még a benne és az alatta levő mezőben levő számok összege lehet páratlan.

Az 1. ábrán látható három feladvány egy-egy megoldását a 2. ábra mutatja. Az első feladványnak van más megoldása is, a másik kettőnek az ábrán szereplő tábla az egyetlen megoldása.

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

2

1

4

3

3

4

2

1

4

3

1

2

1

2

3

4

2

8

9

6

1

7

5

4

3

3

7

4

5

9

8

6

1

2

5

6

1

2

4

3

7

8

9

7

3

8

9

2

1

4

5

6

1

9

5

7

6

4

3

2

8

4

2

6

8

3

5

9

7

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

9

7

2. ábra

A megoldandó feladat

Írjon sudoku néven olyan Prolog-eljárást, ill. Erlang-függvényt, amely egy feladvány összes megoldását előállítja!

A Prolog-eljárásnak két paramétere van. Első (bemenő) paramétere a feladványt, második (kimenő) paramétere a megoldást írja le. Az eljárásnak a visszalépések során minden megoldást pontosan egyszer kell kiadnia. Ha a feladványnak nincs megoldása, az eljárás hiúsuljon meg.

A Prolog-eljárás bemenő paramétere egy 

    s(K,T)

felépítésű struktúra, ahol

A feladványban minden mező infók listáját tartalmazza. Infó az e, o, s és w atom, továbbá a v(N) struktúra, ahol N az adott mező előírt értéke (a v rövidítés az angol value szóból származik). Az infók listájában az elemek sorrendje tetszőleges; a lista üres is lehet.

A Prolog-eljárás kimenő paramétere a feladvány egy megoldása, amely számokat tartalmazó listák listájaként van ábrázolva.

Például az 1. ábra középső feladványát a következő Prolog-struktúrával írjuk le: 

       s(2, [[[v(2)],         [w],         [e],          []],
             [    [],  [e,s,v(4)],          [],         [o]],
             [    [],          [],      [v(1)],          []],
             [    [],         [w],          [],          []]])

A feladvány egyetlen megoldását a következő lista írja le: 

        [[ 2, 1, 4, 3],
         [ 3, 4, 2, 1],
         [ 4, 3, 1, 2],
         [ 1, 2, 3, 4]]

Az Erlang-függvény egyetlen paramétere a feladványt, az eredménye a megoldásokat írja le. Az eredménylistának a feladvány összes megoldását tartalmaznia kell, mégpedig minden megoldást pontosan egyszer. Ha a feladványnak nincs megoldása, az eredmény az üres lista.

Az Erlang-függvény paramétere egy {K,T} pár, ahol K és T jelentése azonos a Prolog-eljárás K és T struktúraelemeinek a jelentésével.

A feladványban minden mező infók listáját tartalmazza. Infó az e, o, s és w atom, továbbá az N szám (az adott mező előírt értéke). Az infók listájában az elemek sorrendje tetszőleges; a lista üres is lehet.

Az Erlang-függvény eredménye a feladvány összes megoldásának listája, ahol mindegyik megoldás számokat tartalmazó listák listájaként van ábrázolva.

Például az 1. ábra középső feladványát a következő Erlang-párral írjuk le: 

        {2, [[      [2],      [w],      [e],       []],
             [       [],  [e,s,4],       [],      [o]],
             [       [],       [],      [1],       []],
             [       [],      [w],       [],       []]]}

A feladvány egyetlen megoldását tartalmazó lista a következő: 

        [[[ 2, 1, 4, 3],
          [ 3, 4, 2, 1],
          [ 4, 3, 1, 2],
          [ 1, 2, 3, 4]]]

A megírandó függvény, ill. eljárás specifikációja

A sudoku/2 Prolog-eljárás típusát a következő - megjegyzésként megadott - Prolog-típusdefiníciók írják le. 

% :- type sspec ---> s(size, board).
% :- type size  == int.
% :- type field == list(info).
% :- type info ---> e; o; s; w; v(int).
% :- type board == list(list(field)).

% :- type ssol == list(list(int)).

% sudoku(SSpec, SSol):
% SSol az SSpec feladványt kielégítő megoldás.
% :- pred sudoku(sspec::in, ssol::out).

A sudoku:sudoku/1 Erlang-függvény típusát a következő - megjegyzésként megadott - Erlang-típusdefiníciók írják le. 

%% @type sspec() = {size(), board()}.
%% @type size()  = integer().
%% @type field() = [info()].
%% @type info()  = e | o | s | w | integer().
%% @type board() = [[field()]].

%% @type ssol() = [[integer()]].

%% @spec sudoku:sudoku(SSpec::sspec()) -> SSols::[ssol()].
%% @doc  SSols az SSpec feladványt kielégítő megoldások listája.
A programot tartalmazó modul attribútumai ezek legyenek: 
-module(sudoku).
-author(email@unit.org.hu).
-vsn('year-mm-dd').
-export([sudoku/1]).

A házi feladat megoldása során a feladványra vonatkozó, fent ismertetett formai előírások meglétét nem kell ellenőriznie. Mind a Prolog, mind az Erlang nyelv esetén feltételezheti, hogy

Keretprogramok

Programjait keretprogramok segítségével próbálhatja ki. A keretprogramokat a beadáskor használthoz hasonló tesztesetekkel együtt letöltheti innen. A nagy házi feladatok teszteléséhez és értékeléséhez a keretprogramokkal azonos specifikációjú programokat fogunk használni.

A keretprogram bemenete egy olyan szövegfájl, amelynek első nem üres sora a Sudoku-feladvány cellaméretét, minden egyes további nem üres sora a Sudoku-feladvány egy-egy sorát tartalmazza, ahol az egyes mezők értékét egy vagy több szóköz választja el. A - karakter jelzi, ha egy mező nem tartalmaz infót. Ha tartalmaz, a mezőt az infók felsorolásával adjuk meg: a számot decimális alakban, a többi infót a betűjelével írjuk le; a jelek közé nem szabad szóközt tenni.

Például az 1. ábra közepső Sudoku-feladványát a 3. ábrán látható módon ábrázoljuk a bemeneti szövegfájlban: 

   2
   2   w   e   -
   -   es4 -   o
   -   -   1   -
   -   w   -   -
      3. ábra

A keretprogram kimenete a 4. ábrán bemutatotthoz hasonló tartalmú szövegfájl. 

   -----

   2  1  4  3
   3  4  2  1
   4  3  1  2
   1  2  3  4

   -----
      4. ábra

A Prolog-keretprogram

A ksudoku.pl Prolog-keretprogram a következő négy eljárást exportálja:

sudoku_be(file::in, sspec::out)
A megnevezett szövegfájlból beolvassa a feladványt, és visszaadja a kimenő paraméterben.
sudoku_ki(file::in, ssol::in)
A megnevezett szövegfájlba kiírja a feladvány második paraméterként átadott összes megoldását.
megold(file::in, file::in)
Beolvas egy feladványt az első paraméterrel megnevezett szövegfájlból, és kiírja az összes megoldását a második paraméterrel megnevezett szövegfájlba. Ehhez felhasználja a sudoku/2 eljárást.
stopper(file::in, file::in)
Mint megold/2, de a végén kiírja a feladvány nevét, a megoldások számát és a futási időt is.

A keretprogram felhasználja a file típust: 

% :- type file == atom.

A file típusú paraméterben a user atomot megadva a terminálról vihetünk be, ill. a terminálra írathatunk ki adatokat. Egyébként a megadott nevű fájlba írunk, ill. fájlból olvasunk.

Használat: saját programját a sudoku.pl nevű fájlba tegye, különben a ksudoku.pl keretprogram nem találja meg. Ezután futtassa a SICStus interpretert, és töltse be a keretprogramot. Példa: 

SICStus 4.2.0 (x86-linux-glibc2.7): Mon Mar  7 20:03:49 CET 2011
Licensed to BUTE DP Course
| ?- [ksudoku].
% compiling /home/szeredi/tmp/ksudoku.pl...
%  module sudoku_keret imported into user
(...)
% compiled /home/szeredi/tmp/ksudoku.pl in module sudoku_keret, 30 msec 78104 bytes
yes
| ?- stopper('teszt0.txt', 'teszt0.sol').

A stopper/2, ill. megold/2 eljárások meghívása a sudoku.pl programot automatikusan betölti (ha szükséges), ezért ennek módosításakor nem kell sem a SICStus rendszert újraindítania, sem a keretprogramot újra betöltenie.

Az Erlang-keretprogram

A ksudoku.erl Erlang-keretprogram a következő négy függvényt exportálja:

@spec ksudoku:sudoku_be(FileIn::string()) -> SSpec::sspec()
SSpec a FileIn szövegfájlból beolvasott Sudoku-feladvány.
@spec ksudoku:sudoku_ki(FileOut::string(), SSols::[ssol()]) -> void()
Az SSols listában átadott Sudoku-megoldásokat kiírja a FileOut szövegfájlba.
@spec ksudoku:megold(FileIn::string(), FileOut::string()) -> void()
Beolvas egy feladványt a FileIn szövegfájlból és összes megoldását kiírja a FileOut szövegfájlba. Ehhez felhasználja a sudoku:sudoku/1 függvényt.
@spec ksudoku:stopper(FileIn::string(), FileOut::string()) -> void()
Mint ksudoku:megold/2, de a végén kiírja a FileIn nevét, a megoldások számát és a futási időt is.

Használat: saját sudoku.erl nevű programját minden változtatás után fordítsa le (pl. az erlc paranccsal vagy a c/1 shell függvénnyel) és sudoku.beam néven rakja a keretprogrammal azonos mappába, különben a ksudoku.erl keretprogram nem találja meg. Ezután indítsa el az Erlang interpretert, és töltse be a lefordított keretprogramot. Példa: 

Eshell V5.8  (abort with ^G)
1> l(ksudoku).
{module,ksudoku}
2> ksudoku:stopper("teszt0.txt","teszt0.sol").

A keretprogram automatikusan betölti a sudoku.beam programot, feltéve, hogy a keretprogrammal azonos mappában van.

Ha a saját sudoku.erl programját módosítja, a lefordítása után betöltheti az l(sudoku). paranccsal, de újra betöltheti a ksudoku.erl keretprogramot is, ami magával húzza a módosított programot. Egyes esetekben célszerű újraindítani az Erlang értelmezőt.

Dokumentációs követelmények

Mindkét programot úgy írja meg (választása szerint vagy magyarul, vagy angolul), hogy a szövegük jól olvasható legyen: válasszon értelmes neveket, specifikálja a paraméterek és más azonosítók szerepét és értelmezési tartományát, magyarázza meg az egyes eljárások, ill. függvények feladatát és működését! Kövesse a Prolog-, ill. az Erlang-diákon használt szövegelrendezési konvenciókat! Javasoljuk, hogy ne írjon 72 karakternél hosszabb sorokat. Minden eljáráshoz és függvényhez készítsen fejkommentet!

A két programhoz készítsen közös dokumentációt; vagy magyarul, vagy angolul. A dokumentáció tartalma legalább a következő legyen:

Fogalmazzon világosan és tömören, ügyeljen a helyes nyelvhasználatra és a helyesírási szabályok betartására! Az indokoltan elvárható formai követelmények be nem tartását, a gondatlan kivitelt szankcionáljuk.

A dokumentációt elektronikus alakban adja be HTML, PDF, esetleg ASCII formátumban.

Egyéb követelmények és tudnivalók

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.2.x, ill. az Erlang/OTP R14A rendszerekkel teszteljük.

Megoldásában tetszőleges könyvtárakat használhat, kivéve a clpfd, clpq, clpr, clpb és chr Prolog-könyvtárakat: az ezeket a könyvtárakat felhasználó megoldások a létraversenyben nem vehetnek részt, és így megajánlott jegyet sem kaphatnak.

A programokat és az elektronikus dokumentációt webes felületen lehet majd külön-külön feltölteni az Elektronikus Tanársegéd HF beadás menüpontjában. A beadást többször is megismételheti, az utoljára beadott megoldást tekintjük érvényesnek.

Programját egy tízelemű tesztsorozattal automatikusan futtatjuk. A teszteseteket úgy választjuk meg, hogy legalább négy feladványt a kevésbé ötletes programok is meg tudjanak oldani. Az eredményt levélben közöljük és az ETS-ben is megnézhető.

A nagy házi feladat elkészítése nem kötelező, de megoldását mindenkinek javasoljuk: ez a deklaratív nyelvek magas szintű elsajátítását nagy mértékben segíti.

A beadási határidők:

A beadási határidő után értékeljük a programokat (ez az ún. "éles" teszt). Ehhez a beadási tesztsorozathoz hasonló nehézségű teszteseteket használunk. Az időkorláton belül helyes eredményt adó tesztesetek mindegyikére 0,5–0,5 pontot adunk, a 10 tesztesetre tehát nyelvenként összesen maximum 5 pontot. Ezen felül a dokumentációt, a programkód olvashatóságát, kommentezettségét is értékeljük, nyelvenként maximum 2,5 ponttal. A mindkét nyelven beadott nagy házi feladatra tehát maximum 15 pont kapható (ez 15%-a a pluszpontok nélkül elérhető legfeljebb 100 alappontnak).

Azok a programok, amelyek az éles teszt legalább 8 feladatát helyesen és az előírt időkorláton belül megoldják, létraversenyben vesznek részt. A leggyorsabban futó Erlang-, ill. Prolog-programokra - helyezési számuktól függően - külön-külön 7,5 és 0,5 közötti pluszpont kapható. Ha valaki tehát mindkét nyelvből a leggyorsabb programot írja meg, akkor a 100 alapponton felül 15 pluszpontot kap.

Azok a hallgatók, akik mindkét nyelvből bejutnak a létraversenybe - a tantárgyi adatlapon leírt feltételek fennállása esetén - megajánlott jegyet kapnak.

A programot és dokumentációt mindenkinek saját magának kell elkészítenie. A beadott nagy házi feladatokat gépi úton hasonlítjuk össze, másolás esetén a kódot adó és kapó hallgató sem kaphat pontot. Az algoritmusra vonatkozó ötletek cseréjét viszont nem tiltjuk.

dp-adm@inf.bme.hu