BME Villamosmérnöki és Informatikai Kar
Műszaki Informatikus Szak
Nappali tagozat
2008/2009-es tanév, tavaszi félév

Nagyhatékonyságú programozás

Nagy házi feladat, 1.0 változat

Utolsó módosítás: 2009-04-08
Kiadás: 2009-04-08
Beadási határidő: 2009-05-22

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, amely n darab k*k méretű négyzetes cellára bomlik, ahol 1k10. 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.

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

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ő:

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.

Három Sudoku-megoldás
2. ábra

A megoldandó feladat

Í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

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 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 ---> 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).

Keretprogram

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 keretprogram specifikációja

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.

Dokumentációs követelmények

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.

Egyéb követelmények és tudnivalók

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.


szeredi@cs.bme.hu