1. ábra
| BME Villamosmérnöki és Informatikai Kar
Mérnök-informatikus mesterszak |
Nappali tagozat
2010/2011-es tanév, őszi félév
|
A megoldandó feladat a közismert Sudoku egy variánsa (n-away sudoku).
A Sudoku-feladvány egy m=k*k sorból és m
oszlopból álló négyzetes tábla, amely m darab k*k
méretű négyzetes cellára bomlik, ahol 1 ≤ k ≤ 5.
Emellett a feladvány részét képezi egy n távolságkonstans,
amely az ún. távolságinfók értelmezéséhez szükséges, ahol 1 ≤ n
≤ m-1.
A Sudoku-tábla 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
m 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.
Az infó legegyszerűbb esete a száminfó, amely egy 1
és m 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.
Az infók másik fajtája a távolságinfó, amely kétféle lehet: s
és w. Az előbbi azt írja le, hogy az adott mező
értéke n távolságra van az alatta - azaz tőle délre (south) -
levő mező értékétől, míg az utóbbi ugyanezt állítja az adott mező bal
oldali - azaz tőle nyugatra (west) levő - szomszédjáról. Két érték
távolságán különbségük abszolút értékét értjük.
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 n. Másszóval egy
Sudoku-megoldás nem megfelelő, 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.
Egy mezőben egyfajta infóból legfeljebb egy lehet, tehát egy mezőre 0, 1, 2 vagy 3 infó vonatkozhat.
Három Sudoku-feladványt mutatunk az 1. ábrán, amelyek paraméterei
rendre k = 3, n = 2; k = 2, n = 1; és k = 3, n = 3.
Az 1. ábrán látható három feladvány megoldását a 2. ábra mutatja. Mindhárom feladványnak ez az egyetlen megoldása. Általános esetben természetesen egy feladvány megoldásainak száma lehet 0, 1, vagy több.
Írjon sudoku néven egy olyan, a clpfd könyvtárat
felhaszná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(N,T)
felépítésű struktúra, ahol
N a távolságkonstans,T a sorok listájaként megadott négyzetes tábla, ahol
egy sor a benne levő mezők listája.T lista hossza M, és minden elemének a hossza
is M. Itt M egy négyzetszám, azaz M =
K*K, ahol K a Sudoku-cella mérete.
A feladvány egyes mezőiben infók esetleg üres listája áll. Egy infó az
s vagy a w atom, illetve az 1 ≤ I ≤
M szám lehet. 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(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]]
| ?- 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 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).
Programját keretprogram segítségével próbálhatja ki. A keretprogramot 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 keretprogrammal azonos specifikációjú programot fogunk használni.
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, az infókat tetszőleges sorrendben
adhatjuk meg; a mezőhöz tartozó infók között nem lehet szóköz.
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:
1 s - - s - - - - - s sw - 4 - w -3. ábra
A keretprogram kimenete a 4. ábrán bemutatotthoz hasonló tartalmú szövegfájl.
----- 2 4 1 3 3 1 4 2 1 3 2 4 4 2 3 1 -----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 4.1.1 (x86-linux-glibc2.7): Tue Dec 15 16:13:21 CET 2009
Licensed to BUTE-DP-course
| ?- [ksudoku].
% consulting d:/dokumentumok/bme/deklapo/09a/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/10a/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.
A programot ú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 hosszú sorokat! Minden eljáráshoz és függvényhez 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 4.1.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 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.