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

Deklaratív programozás

Nagy házi feladat, 1.3 változat

Utolsó módosítás: 2008-11-12
Kiadás: 2008-10-25
Beadási határidő: 2008-12-08

Sudoku-variáció

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, amelynek n cellája egyenként n mezőt tartalmazó négyzet, ahol 1k5. 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; száminfó legfeljebb egyszer fordulhat elő az adott mezőben. További infó lehet az, hogy az adott mező páros vagy páratlan értékű, illetve az, hogy az adott mező értéke pontosan 1-gyel tér el az alatta, illetve tőle balra levő mező értékétől; az ilyen előírásokból több, akár egymásnak vagy a száminfónak ellentmondóak is vonatkozhatnak ugyanarra a mezőre, bármilyen kombinációban.

Három Sudoku-feladványt mutatunk az 1. ábrán, ahol rendre k = 3, 2, 3.

Három Sudoku-feladvány
1. ábra

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

A Sudoku-feladvány bal szélső oszlopának mezőiben is állhat w, alsó sorának mezőiben pedig s, annak ellenére, hogy nincs hasznosítható jelentésük. A mezőre vonatkozó infónak nem kell teljesnek lennie. Ha például egy infó csak az o betűből áll, akkor az alatta és a tőle balra levő mezőben tőle akár 1-gyel eltérő érték is lehet.

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.

Három Sudoku-megoldás
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, [[[e,w,v(2),s],         [w],         [e],          []],
              [          [],     [e,s,w],          [],         [o]],
              [          [],          [],      [v(1)],          []],
              [         [w],         [s],          [],          []]])

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, [[[e,w,2,s],      [w],      [e],       []],
             [       [],  [e,s,w],       [],      [o]],
             [       [],       [],      [1],       []],
             [      [w],      [s],       [],       []]]}

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 két attribútuma ez legyen:
-module(sudoku).
-export([sudoku/1]).

Keretprogramok

Programjait keretprogramok segítségével próbálhatja ki. A keretprogramokat a beadáskor használthoz hasonló tesztesetekkel együtt innen töltheti le. 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
   ew2s  w     e     -
   -     esw   -     o
   -     -     1     -
   w     s     -     -
      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 3.12.5 (x86-linux-glibc2.3): Sun Mar 12 09:39:40 CET 2006
Licensed to BUTE-DP-course
| ?- [ksudoku].
% consulting d:/dokumentumok/bme/deklapo/07s/ksudoku.pl...
%  module sudoku_frame imported into user
%  loading e:/programozas/sicstus/library/lists.po...
%  module lists imported into sudoku_frame
%  loaded e:/programozas/sicstus/library/lists.po in module lists, 15 msec 11688 bytes
% consulted d:/dokumentumok/bme/deklapo/07s/ksudoku.pl in module sudoku_keret, 15 msec 29792 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 interpretert ú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, é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.6.3  (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! 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 3.12.x, ill. az Erlang/OTP R12B rendszerekkel teszteljük.

A programokat és az elektronikus dokumentációt webes felületen lehet 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 beadása, elfogadása és a tesztesetek 40%-ának sikeres megoldása az aláírás feltétele. A nagy házi feladat elfogadása azt jelenti, hogy a hallgatónak a gyakorlatokon, illetve a feladat beadását követő konzultáción a feladatra vonatkozó kérdések megválaszolásával, illetve módosított részfeladatok megoldásával meg kell győznie a konzulensét arról, hogy a feladatot ő készítette el, és a feladat elkészítéséhez szükséges tudás birtokában van.

A nagy házi feladat megoldását azoknak is javasoljuk, akik korábban szereztek aláírást: ez a deklaratív nyelvek magasszintű elsajátítását nagymértékben segíti.

A programok és az elektronikus dokumentáció beadási határideje 2008. december 8., hétfő, 24h.

Az értékeléshez a beadási tesztsorozathoz hasonló nehézségű teszteseteket fogunk használni. Az időkorláton belül helyes eredményt adó tesztesetek mindegyikére 0,5-0,5 pontot adunk. a 10 tesztesetre összesen tehát nyelvenként maximum 5 pontot kaphat. 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 pontot kaphat (ez 15%-a a pluszpontok nélkül elérhető legfeljebb 100 alappontnak).

Azok a programok, amelyek az alapteszt minden 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.

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@inf.bme.hu