BME Villamosmérnöki és Informatikai Kar
Műszaki Informatikus Szak |
Nappali tagozat
2008/2009-es tanév, tavaszi félév
|
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, amely n
darab k*k
méretű
négyzetes cellára bomlik, ahol 1
≤ k
≤
10
. 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 eset a száminfó, ahol a szám egy 1
és n
közötti egész érték. Ebben az esetben a Sudoku-megoldásban az adott mezőbe a megadott
számértéknek kell kerülnie. A távolságinfó
azt írja elő, hogy az adott mező értékének a megadott számértékkel kell különböznie az
alatta, illetve tőle balra levő mező értékétől. Egy mezőben egyfajta infóból legfeljebb
egy lehet, tehát egy mezőre nulla, egy vagy két infó vonatkozhat.
A közismert, klasszikus Sudoku az ismertetett feladványnak egy olyan speciális esete, amelyben csak száminfók vannak.
Három Sudoku-feladványt
mutatunk az 1. ábrán, ahol rendre k = 3, 2, 3
.
Az első feladványban csak száminfók vannak, mint a hagyományos Sudokuban. A második és harmadik feladványban vannak távolságinfók is, amelyeket egy betűvel és a betű után álló számmal jelölünk. Kétféle távolságinfó van, amelyek jelentése a következő:
si
: az adott és az alatta levő mező értéke
közötti különbség abszolút értéke i
(s = south),wi
: az adott és a tőle balra levő mező értéke
közötti különbség abszolút értéke i
(w = west). Ha egy mező tartalmaz i értékű távolságinfót, akkor azt mondjuk, hogy az adott mező és az infó által kijelölt szomszéd mező között i értékű távolságkorlátozás (vagy rövidebben távolságkorlát) áll fenn. A távolságkorlát fogalma szimmetrikus, tehát ugyanilyen értékű korlátozás áll fenn a szomszéd és az infót tartalmazó mező között is.
A Sudoku-feladvány bal szélső oszlopának mezőiben is állhat wi
, alsó
sorának mezőiben pedig si
, annak ellenére, hogy nincs
hasznosítható jelentésük. Az ilyen infókat a feladvány megoldásánál figyelmen
kívül kell hagyni.
Az 1. ábrán látható három feladvány egy-egy megoldását a 2. ábra mutatja. Az első és a harmadik feladványnak van más megoldása is, a középsőnek az ábrán szereplő tábla az egyetlen megoldása.
Írjon sudoku
néven olyan a SICStus clpfd
könyvtárára épülő Prolog-eljárást, 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 sorok listájaként megadott feladvány, ahol egy sor a benne
levő mezők listája.
Egy így megadott feladvány esetén jelölje n
a
K*K
értéket.
A feladvány egyes mezőiben infók esetleg üres listája áll. Egy infó
s(I)
, w(I)
vagy v(J)
alakú struktúra lehet. Az első két esetben I
egy 1
és
n-1
közé eső egész szám,
amely az adott mező és déli (s
, south) illetve nyugati
(w
, west) oldalszomszédja közötti különbséget
írja elő. A harmadik esetben J
egy 1
és
n
közé eső egész szám, az adott mező előírt érteke
(v
, value). Az
infók listájában az elemek sorrendje tetszőleges.
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),s(1)], [s(3)], [], []], [ [], [s(1),w(1)], [], [v(1)]], [ [], [], [v(1)], [s(2)]], [ [w(2)], [s(1)], [], []]])
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]]
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 ---> s(int); w(int); 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).
Programját keretprogram segítségével próbálhatja ki. A keretprogramot a beadáskor használt és még további 300 tesztesettel együtt innen töltheti le.
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
írjuk le: először a száminfót adjuk meg decimális számként, majd
a távolságinfókat. Az utóbbiak ábrázolása a következő: először az
s
vagy w
betűjelet írjuk
le, ezt követően pedig a távolságot decimális számként. A távolságérték
elhagyható, alapértelmezése 1. Az egy mezőhöz tartozó infók leírásában
szóköz nem szerepelhet.
Például az 1. ábra közepső Sudoku-feladványát a 3. ábrán látható módon ábrázolhatjuk a bemeneti szövegfájlban:
2 2s s3 - - - s1w - 1 - - 1 s2 w2 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 ksudoku.pl
Prolog-keretprogram a következő négy eljárást
exportálja:
sudoku_be(file::in, sspec::out)
sudoku_ki(file::in, ssol::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('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.
Programját úgy írja meg (választása szerint vagy magyarul, vagy angolul), hogy a szövege 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-diákon használt szövegelrendezési konvenciókat! Ne írjon 72 karakternél hosszabb sorokat! Minden eljáráshoz készítsen fejkommentet!
A programhoz készítsen 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 program készülhet MS Windows alatt is, de Linux alatt is működnie kell. A beadott programokat Linux környezetben a SICStus Prolog 3.12.x, rendszerrel teszteljük.
A programot és az elektronikus dokumentációt webes felületen lehet külön-külön feltölteni az NLP 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.
A program és az elektronikus dokumentáció beadási határideje 2009. május 22., péntek, 24h.