| BME Villamosmérnöki és Informatikai Kar
Műszaki informatika szak |
Nappali tagozat
2007/2008-as tanév, tavaszi félév
|
A feladvány a közismert Sudoku egy variánsa.
Egy s=n*k sorból és o=m*k oszlopból álló tábla
c=n*m cellája egyenként k*k mezőt tartalmazó
négyzet, ahol 1 ≤ k ≤ 5 és
1 ≤ n, m ≤ k. A
kezdetben részben kitöltött táblát úgy kell kitölteni 1
és k*k közötti egészekkel, 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 legyenek.
Egy hagyományos, részben kitöltött Sudoku-táblát és néhány variánsát mutatja az 1. ábra.
+++++++++++++++++++ + 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 3|5 8 + + 7 8| 2 1+ + 5| 3 9+ +-----------+ + 8 2| 4 + + 9 | 1 + + 6 |9 5 + +-----------+ +7 4 |3 + +2 3 |8 9 + + 5 9|1 7 + +++++++++++++ |
+++++++++++++++++++ + 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 + +++++++++++++++++++ |
+++++++++++++ + 2 3|4 1 + + 7 8| + + 5|7 2 + +-----------+ + 8 2|9 6 1+ + 9 |5 4+ + 6 |2 7 3+ +++++++++++++ |
+++++++++ +2 3|4 + + 4| 2+ +-------+ + 2| + + |2 3+ +++++++++ |
|
| 1. ábra |
n=3, m=3, k=3,s=9, o=9, c=9
|
n=3, m=2, k=3,s=9, o=6, c=6
|
n=2, m=3, k=3,s=6, o=9, c=6
|
n=2, m=2, k=3,s=6, o=6, c=4
|
n=2, m=2, k=2,s=4, o=4, c=4
|
Írjon sudoku néven olyan Prolog-eljárást, ill.
SML-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
K a cellák oldalhossza,T a táblát sorok listájaként írja le, ahol egy sor a benne
levő számok listája.
A Prolog-eljárás kimenő paramétere ugyancsak egy s(K,T)
struktúra.
A bemenő paraméterben a keresett (ismeretlen értékű) mezőket 0 jelöli.
Például az 1. ábra középső, n=2, m=3,
k=3, s=6, o=9, c=6
paraméterű feladványát a következő Prolog-struktúrával írjuk le:
s(3, [[0,2,3,4,1,0,5,8,0], [0,7,8,0,0,0,0,2,1], [0,0,5,7,2,0,0,3,9],
[0,8,2,9,6,1,0,4,0], [0,9,0,5,0,4,0,1,0], [0,6,0,2,7,3,9,5,0]])
A feladvány egy megoldását a következő struktúra írja le:
s(3, [[6,2,3,4,1,9,5,8,7], [9,7,8,3,5,6,4,2,1], [1,4,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], [4,6,1,2,7,3,9,5,8]])
Az SML-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 SML-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.
Az SML-függvény eredménye egy ugyancsak (k, t) párokból álló
lista.
Például az 1. ábra középső, n=2, m=3,
k=3, s=6, o=9, c=6
paraméterű feladványát a következő SML-párral írjuk le:
(3, [[0,2,3,4,1,0,5,8,0], [0,7,8,0,0,0,0,2,1], [0,0,5,7,2,0,0,3,9],
[0,8,2,9,6,1,0,4,0], [0,9,0,5,0,4,0,1,0], [0,6,0,2,7,3,9,5,0]])
A feladvány megoldásait a következő lista írja le:
[(3, [[6,2,3,4,1,9,5,8,7], [9,7,8,3,5,6,4,2,1], [1,4,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], [4,6,1,2,7,3,9,5,8]])
(...), ...
(...)
]
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 == int.
% :- type board == list list field.
% sudoku(SSpec, SSol):
% SSol az SSpec specifikációnak megfelelő megoldás.
% :- pred sudoku(sspec::in, sspec::out).
A sudoku SML-függvény típusát a következő
SML-típusszinonimák és - itt megjegyzésként megadott -
típusspecifikáció írják le.
type size = int; type field = int; type board = field list list; type sspec = size * board; (* sudoku : sspec -> sspec list *)
Programjait keretprogramok segítségével próbálhatja ki. A keretprogramokat a beadáskor használthoz hasonló tesztesetekkel együtt letöltheti később 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 cella méretét, minden egyes további nemüres sora a Sudoku-tábla egy-egy sorát tartalmazza, ahol az egyes mezők értékét egy vagy több szóköz választja el. Például az 1. ábra bal szélén látható Sudoku-táblát a 2. ábrán látható módon ábrázoljuk a szövegfájlban:
3
0 2 3 4 1 0 5 8 0
0 7 8 0 0 0 0 2 1
0 0 5 7 2 0 0 3 9
0 8 2 9 6 1 0 4 0
0 9 0 5 0 4 0 1 0
0 6 0 2 7 3 9 5 0
7 4 0 0 9 5 3 0 0
2 3 0 0 0 0 8 9 0
0 5 9 0 3 2 1 7 0
2. ábra
A keretprogram kimenete a 3. ábrán bemutatotthoz hasonló tartalmú szövegfájl.
-----
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
-----
9 2 3 4 1 6 5 8 7
4 7 8 3 5 9 6 2 1
6 1 5 7 2 8 4 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
-----
9 2 3 4 1 6 5 8 7
6 7 8 3 5 9 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
-----
3. ábra
A Prolog-keretprogram a következő négy eljárást exportálja:
sudoku_be(file::in, sspec::out)sudoku_ki(file::in, sspec::in)megold(file::in, file::in)sudoku/2 eljárást.stopper(file::in, file::in)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(..., ...).
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 SML-keretprogram a következő négy függvényt exportálja:
sudoku_be ff szövegfájlból beolvasott adatokból képzett
feladványleíró.sudoku_ki(m, ms)m szövegfájlba kiírja a feladványnak az
ms listával átadott megoldását.megold(f, m)f szövegfájlból és kiírja az
összes megoldását az m szövegfájlba. Ehhez felhasználja
a sudoku függvényt. Eredménye az f
nevet és a megoldások számát tartalmazó füzér.stopper(f, m)megold, 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 bemenetet, ill. a kimenetet a terminálra irányíthatjuk Unix alatt a
/dev/stdin, ill. a /dev/stdout, MS DOS/Windows
alatt mindkét esetben a con fájlnév megadásával.
Használat: olvassa be az interpreterbe a
ksudoku.sml programot, és a megfelelő paraméterekre
alkalmazza a kívánt függvényt:
Moscow ML version 2.01 (January 2004) Enter `quit();' to quit. - use "ksudoku.sml"; > val it = () : unit - stopper (..., ...);
A keretprogram a use "sudoku.sml" kifejezéssel betölti a
keretprogrammal azonos könyvtárban lévő sudoku.sml
programot.
Miután a saját sudoku.sml programját módosította,
betöltheti a módosított programot, de betöltheti újra a
ksudoku.sml programot is, hiszen az betölti a módosított
programot is. Sokszor célszerű az SML értelmezőt is újraindítani.
mosml értelmezőprogrammal futtatja, hanem előbb lefordítja és
összeszerkeszti az mosmlc fordítóprogrammal, majd az
összeszerkesztett programot futtatja. Ezért a beküldött programban
olyan függvényeket nem szabad használnia, amelyeket csak az interpreter
ismer; ilyen pl. a load vagy a printVal.
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 SML-jegyzetben látható szövegelrendezési szokásokat! 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.
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 MOSML 2.01 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ó módosított beadási határideje 2008. május 13., kedd, 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ó SML-, 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.