BME Villamosmérnöki és Informatikai Kar
Mérnök-informatikus mesterszak
Nappali tagozat
2020/2021-es tanév, tavaszi félév

Nagyhatékonyságú Deklaratív Programozás

Nagy házi feladat

1.0 változat
Utolsó módosítás: 2021-04-16

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 = k2 ≥ 1 négyzetszám. (Tehát a mátrix elemeinek száma m2 = k4.)

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

  1. mezői 1 és m közé eső egész számok,
  2. 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),
  3. 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 ezek jelölése rendre s és w. A déli távolságinfó azt írja elő, 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ő baloldali 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.

Három Sudoku-feladvány
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:

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.

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

A megoldandó programozási feladat

Í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 (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

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]]

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

Keretprogram

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

   -----
   
   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ő 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: 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.6.0 (...)
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.

Dokumentációs követelmények

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 PDF 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 4 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.


szeredi@cs.bme.hu