BME Villamosmérnöki és Informatikai Kar
Mérnök-informatikus szak

Nappali tagozat

2020/2021-es tanév, őszi félév

Deklaratív programozás

Nagy házi feladat

1.2. változat
Utolsó módosítás: 2020-10-31
Kiadás: 2020-10-01
A beadási határidők a weboldalon olvashatók.

Sudoku távolságkorlátokkal

A megoldandó feladat a közismert Sudoku egy variánsa (n-away sudoku).

Definíciók

Sudoku-mátrixnak hívunk egy olyan négyzetes mátrixot, amelyben a sorok (és az oszlopok) száma egy m = k² ≥ 1 négyzetszám. (Tehát a mátrix elemeinek száma m² = k⁴.)

Egy Sudoku-mátrixban cellának hívunk egy olyan (folytonos) részmátrixot, amely k sorból és k oszlopból áll, és bal felső sarkának sor- ill. oszlopszáma i*k+1 ill. j*k+1, ahol 0 ≤ i,j ≤ k-1 (a sorokat és oszlopokat 1-től számozzuk).

A Sudoku-mátrix elemeit mezőknek is nevezzük.

Egy Sudoku-feladvány két részből áll. Az egyik rész egy olyan Sudoku-mátrix, amelynek egyes mezői segítő információkat (röviden infókat) tartalmaznak, ezt infómátrixnak nevezzük. A Sudoku játék közismert alapváltozatában csak ún. száminfók fordulnak elő, amelyek azt írják elő, hogy a megoldás adott mezője egy adott számot tartalmazzon.

A feladvány másik része egy n távolságkonstans, amely az ún. távolságinfók értelmezéséhez szükséges, ahol 1 ≤ n ≤ m-1.

Nevezzünk értékmátrixnak egy olyan Sudoku-mátrixot, amelynek mezői egész számok. Egy m*m méretű Sudoku-feladvány megoldása egy m*m méretű értékmátrix, ha

mezői 1 és m közé eső egész számok,
minden sorában, oszlopában és cellájában különböző számok állnak
(tehát (i) és (ii) összevonása: a mátrix minden ilyen részterülete az 1..m egész számok mindegyikét pontosan egyszer tartalmazza),
teljesíti az infók által előírt korlátozásokat.

A feladvány egy (i,j) koordinátájú mezőjében levő M száminfó azt írja elő, hogy a megoldás azonos helyzetű, (i,j) koordinátájú mezője az M számot kell tartalmazza.

A jelen házi feladatban a száminfók mellett egy további fajta segítő információ fordulhat elő: a távolságinfó. A távolságinfó azt az információt hordozza, hogy az adott mezőben valamint egy megadott szomszédos mezőben levő értékek távolsága n. Két érték távolságán különbségük abszolút értékét értjük. A távolságinfó kétféle lehet: déli és nyugati. A déli azt írja le, hogy az adott mező értéke n távolságra van az alatta levő mező értékétől, míg a nyugati ugyanezt állítja az adott mező bal oldali szomszédjáról.

A feladvány az összes lehetséges távolságinfót tartalmazza. Tehát ha a Sudoku-feladvány egy mezője nem tartalmazza az s (w) infót, akkor biztos, hogy az adott mező és a déli (nyugati) szomszédja közötti távolság nem n. Másszóval egy értékmátrix nem megoldás, ha egy olyan oldalszomszédos mezőpárt tartalmaz, amelyek távolsága n, és ugyanakkor a pár északi (keleti) mezője a feladványban nem tartalmazza az s (w) távolságinfót.

Megjegyzés

Az újságokban vagy a világhálón publikált, "emberi fogyasztásra" szánt Sudoku-feladványok többnyire egyetlen megoldással bírnak. A jelen házi feladatban a megoldások számára nem teszünk semmilyen megszorítást, így a feladványoknak lehet 0, 1 vagy több megoldása is.

Példák

Három Sudoku-feladványt mutatunk az 1. ábrán, ahol a k cellaméret és az n távolságkonstans rendre k=3, n=2; k=2, n=1 és k=3, n=3.

1. ábra

A legegyszerűbb esetben az infó egy szám: az adott mező előírt értéke. A további infókat egybetűs azonosítókkal jelezzük. A száminfótól különböző előírásokból többféle is lehet egy mezőben. A feladványokban betűk jelzik a távolságinfókat, ezek jelentése:

s (south): az adott és az alatta levő mező értékének távolsága n,
w (west): az adott és a tőle balra levő mező értékének távolsága n.

Az s és w betűk távolságinfókat adnak meg.

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 a háromféle infó (a száminfó ill. a kétféle, betűkkel jelzett infók) mindegyike legfeljebb egyszer szerepelhet.

Az 1. ábrán látható három feladvány egy-egy megoldását a 2. ábra mutatja. Mindhárom feladványnak ez az egyetlen megoldása.

2. ábra

A megoldandó programozási 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! Feltételezheti, hogy a feladvány cellamérete legfeljebb 10.

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 (tetszőleges sorrendben). Ez azt is jelenti, hogy ha a feladványnak nincs megoldása, az eljárásnak meg kell hiúsulnia.

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

    s(N,T)

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

N a távolságkonstans,
T a sorok listájaként megadott feladvány, ahol egy sor a benne levő mezők listája.

A feladvány egy mezőjét infók listájaként adjuk meg. Infó lehet az s és w atom, továbbá az 1 ≤ I ≤ m szám lehet. Az infók listájában mindegyik atom illetve szám legfeljebb egyszer, de tetszőleges sorrendben fordulhat elő, és a lista üres is lehet.

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

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

        s(1, [[  [s],    [],     [],    [s]],
              [   [],    [],     [],     []],
              [   [],   [s],  [s,w],     []],
              [  [4],    [],    [w],     []]])

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

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

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 (tetszőleges sorrendben). Ez azt is jelenti, hogy ha a feladványnak nincs megoldása, az eredmény az üres lista kell legyen.

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

A feladványban minden mező infók listáját tartalmazza. Infó az s és w atom, továbbá az 1 ≤ I ≤ m szám (az adott mező előírt értéke). Az infók listájában ezek legfeljebb egyszer, de tetszőleges sorrendben fordulhatnak elő, és a lista üres is lehet.

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

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


        {1, [[  [s],    [],     [],    [s]],
              [   [],    [],     [],     []],
              [   [],   [s],  [s,w],     []],
              [  [4],    [],    [w],     []]]}

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

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

A házi feladat megoldása során a feladványt megadó bemenő paraméterre vonatkozó formai előírások meglétét nem kell ellenőriznie, azaz feltételezheti, hogy a paraméter megfelel a fent ismertetett formai követelményeknek.

További példafutások:

   | ?- sudoku(s(1, [[[s], [],    [],[s]],
                     [ [], [],    [], []],
   
                     [ [],[s], [s,w], []],
                     [ [], [],   [w], []]
                    ]
                    ), Table).
   Table = [[3,1,4,2],
            [2,4,1,3],
            [4,2,3,1],
            [1,3,2,4]] ? ;
   Table = [[2,4,1,3],
            [3,1,4,2],
            [1,3,2,4],
            [4,2,3,1]] ? ;
   no
   | ?- sudoku(s(1, [[[s], [],    [],[s]],
                     [ [], [],    [], []],

                     [ [],[s], [s,w], []],
                     [[4], [],    [], []]
                    ]
                 ), Table).

   no

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(dist, board).
% :- type dist  == int.
% :- type field == list(info).
% :- type info ---> s; w; 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() :: {dist(), board()}.
-type dist()  :: integer().
-type field() :: [info()].
-type info()  :: s | w | integer().
-type board() :: [[field()]].

-type ssol()  :: [[integer()]].

-spec sudoku:sudoku(SSpec::sspec()) -> SSols::[ssol()].
%% 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]).
%-compile(export_all).

A -vsn(...), ill. a -export(...) attribútum paraméterének (Erlang atomként) a saját nevét vagy email-címét, ill. a programverzió keltét adja meg.

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

a sudoku eljárás, ill. függvény első paraméterében a fenti típusdefinícióknak megfelelő feladvány-adatstruktúrát kap;
a feladványban megadott infómátrixnak m sora és m oszlopa van;
a száminfókban szereplő egész értékek az 1..m tartományba esnek.

Keretprogramok

Programjait keretprogramok segítségével próbálhatja ki. A keretprogramokat a beadáskor használthoz hasonló tesztesetekkel együtt töltheti le:

Keretprogramok + tesztesetek + futási idők + README.txt (ZIP).

A nagy házi feladatok teszteléséhez és értékeléséhez a keretprogramokkal azonos specifikációjú programokat fogunk használni. Olvassa el a README.txt-t!

A keretprogram bemenete egy olyan szövegfájl, amelynek első nem üres sora a Sudoku-feladvány távolságkonstansá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:

   1
   s    -    -    s
   -    -    -    -
   -    s   sw    -
   4    -    w    -

3. ábra

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

4. ábra

A Prolog-keretprogram

A ksudoku.pl Prolog-keretprogram a következő eljárásokat exportálja:

% :- pred sudoku_be(file::in, sspec::out).

A megnevezett szövegfájlból beolvassa a feladványt, és visszaadja a kimenő paraméterben.

% :- pred 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.

% :- pred 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.

% :- pred 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.

% :- pred teljes_teszt(int::in).

A tests könyvtárban levő összes testXXXd.txt tesztállomány esetén:

lefuttatja a tesztet az első paraméterben megadott, másodpercben értelmezett időkorláttal,
ellenőrzi, hogy a testXXXs.txt állományban megadott megoldáshalmazt kapta,
olvasható formában (lásd megold/2) kiírja az eredményt a tests_out könyvtár testXXXt.txt nevű állományába.

A fenti állománynevekben XXX egy tetszőleges hosszúságú számjegysorozatot jelöl. Ezt az eljárást Eisenberger András ültette át Prologra.

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 indítsa el a SICStus rendszert, és töltse be a keretprogramot. Példa:

SICStus 4.2.3 (x86-linux-glibc2.5): Fri Oct  5 15:56:32 CEST 2012
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 interpretert újraindítania, sem a keretprogramot újra betöltenie.

Az Erlang-keretprogram

A ksudoku.erl Erlang-keretprogram a következő függvényeket 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()]) -> no_return()

Az SSols listában átadott Sudoku-megoldásokat kiírja a FileOut szövegfájlba.

-spec ksudoku:megold(FileIn::string(), FileOut::string()) -> no_return()

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()) -> no_return()

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.

-spec teljes_teszt(Timeout::integer()) -> [done|timeout].

A tests könyvtárban levő összes testXXXd.txt tesztállomány esetén:

lefuttatja a tesztet Timeout másodperces időkorláttal,
ellenőrzi, hogy a testXXXs.txt állományban megadott megoldáshalmazt kapta,
olvasható formában (lásd megold/2) kiírja az eredményt a tests_out könyvtár testXXXt.txt nevű állományába.

A fenti állománynevekben XXX egy tetszőleges hosszúságú számjegysorozatot jelöl. Ezt a függvényt Eisenberger András egészítette ki a megoldás ellenőrzésével.

Használat: saját sudoku.erl nevű programját a ksudoku.erl nevű keretprogrammal azonos mappába tegye, különben a keretprogram nem fogja megtalálni. Lépjen be ebbe a mappába, és fordítsa le mindkét programot:

erlc ksudoku.erl
erlc sudoku.erl

Saját programját minden változtatás után újra le kell fordítania.

Ezután indítsa el az Erlang interpretert, és töltse be a lefordított keretprogramot; vele együtt a saját programját is betölti az interpreter:

Erlang/OTP 23 [erts-11.1] [source] [64-bit] [smp:4:4] [ds:4:4:10] [async-threads:1] [hipe]
Eshell V11.1  (abort with ^G)
1> l(ksudoku).
{module,ksudoku}
2>

A tests mappában lévő teszteseteket az alábbihoz hasonló függvényhívásokkal futtathatja:

2> ksudoku:stopper("tests/test001d.txt","test001s.txt").

Figyelem: a kimenő fájlt ne a tests mappába tegye, különben felülírja az ott található mintamegoldást.

Saját tesztfájlokat is készíthet, ezeknek tetszőleges nevet adhat, és tetszőleges mappába teheti őket.

Javítás után az újrafordított sudoku.erl programját betöltheti az l(sudoku). paranccsal, vagy a keretprogrammal együtt az l(ksudoku). paranccsal. Időnként célszerű lehet tiszta lappal indulni, azaz újraindítani az Erlang interpretert.

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:

Követelmények elemzése
Tervezés, az egyes eljárások, ill. függvények specifikálása
Kódolás Erlang-, ill. Prolog-nyelven, az algoritmusok ismertetése
Tesztelési megfontolások
Kipróbálási tapasztalatok

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

Megoldásában Prolog nyelven tetszőleges könyvtárakat használhat, kivéve a clpfd, clpq, clpr, clpb, chr és atts 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. Hasonlóképpen tiltott a mellékhatásos beépített eljárások, így az assert, retract, bb_put, bb_get stb. használata.

Erlang nyelven az adatbázist vagy egyéb mellékhatást használó függvények használata tilos (erlang:get, erlang:put, digraph modul, io modul stb.). Néhány megengedett, állapotmentes modul: array, dict, gb_*, lists, math, ord*, queue, sets, string.

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 weboldalon olvasható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 fegyelmi eljárást kezdeményezünk. Az algoritmusra vonatkozó ötletek cseréjét viszont nem tiltjuk.