Sudoku n-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 = k² ≥ 1 négyzetszám. (Tehát a mátrix elemeinek száma m² = k⁴.)

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. oszlopsorszá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ék-má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ék-má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 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. A déli azt írja le, 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ő bal oldali 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ék-má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ések

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

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:

• s (south): az adott és az alatta levő mező értékének távolsága n,
• w (west): az adott és a tőle balra levő mező értékének távolsága n.

Az s és w betűk távolságinfókat adnak meg.

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.

2. ábra

A megoldandó programozási feladat

Írjon sudoku néven olyan Prolog-eljárást, ill. Erlang-függvényt, amely egy feladvány összes megoldását előállítja! Feltételezheti, hogy a feladvány cellamérete legfeljebb 10.

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

• N a távolságkonstans,
• T a sorok listájaként megadott feladvány, ahol egy sor a benne levő mezők listája.

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

Az Erlang-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 (tetszőleges sorrendben). Ez azt is jelenti, hogy ha a feladványnak nincs megoldása, az eredmény az üres lista kell legyen.

Az Erlang-függvény paramétere egy {N,T} pár, ahol N és T jelentése azonos a Prolog-eljárás N és T struktúraelemeinek a jelentésével.

A feladványban minden mező infók listáját tartalmazza. Infó az s és w atom, továbbá az 1 ≤ I ≤ m szám (az adott mező előírt értéke). Az infók listájában ezek legfeljebb egyszer, de tetszőleges sorrendben fordulhatnak elő, és a lista üres is lehet.

Az Erlang-függvény eredménye a feladvány összes megoldásának listája, ahol mindegyik megoldást 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ő Erlang-párral írjuk le:

        {1, [[  [s],    [],     [],    [s]],
              [   [],    [],     [],     []],
              [   [],   [s],  [s,w],     []],
              [  [4],    [],    [w],     []]]}

A feladvány egyetlen megoldását tartalmazó lista a következő:

        [[[ 2, 4, 1, 3],
          [ 3, 1, 4, 2],
          [ 1, 3, 2, 4],
          [ 4, 2, 3, 1]]]

A házi feladat megoldása során a feladványt megadó bemenő paraméterre vonatkozó formai előírások meglétét nem kell ellenőriznie, azaz feltételezheti, hogy a paraméter megfelel a fent ismertetett formai követelményeknek.

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

A sudoku:sudoku/1 Erlang-függvény típusát a következő - megjegyzésként megadott - Erlang-típusdefiníciók írják le.

%% @type sspec() = {dist(), board()}.
%% @type dist()  = integer().
%% @type field() = [info()].
%% @type info()  = s | w | integer().
%% @type board() = [[field()]].

%% @type ssol() = [[integer()]].

%% @spec sudoku:sudoku(SSpec::sspec()) -> SSols::[ssol()].
%% @doc  SSols az SSpec feladványt kielégítő megoldások listája.

-module(sudoku).
-author('email@unit.org.hu').
-vsn('year-mm-dd').
-export([sudoku/1]).

A házi feladat megoldása során a feladványra vonatkozó, fent ismertetett formai előírások meglétét nem kell ellenőriznie. Mind a Prolog, mind az Erlang nyelv esetén feltételezheti, hogy

• a sudoku eljárás, ill. függvény első paraméterében a fenti típusdefinícióknak megfelelő feladvány-adatstruktúrát kap;
• a feladványban megadott infó-mátrixnak m sora és m oszlopa van;
• a száminfókban szereplő egész értékek az 1..m tartományba esnek.

Keretprogramok

Programjait keretprogramok segítségével próbálhatja ki. A keretprogramokat a beadáskor használthoz hasonló tesztesetekkel együtt töltheti le:

• Keretprogramok + tesztesetek (ZIP)

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    -

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

A Prolog-keretprogram

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:

• lefuttatja a tesztet az első paraméterben megadott, másodpercben értelmezett időkorláttal,
• ellenőrzi, hogy a testXXXs.txt állományban megadott megoldáshalmazt kapta,
• olvasható formában (lásd megold/2) kiírja az eredményt a tests_out könyvtár testXXXt.txt nevű állományába.

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.2.3 (x86-linux-glibc2.5): Fri Oct  5 15:56:32 CEST 2012
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.

Az Erlang-keretprogram

A ksudoku.erl Erlang-keretprogram a következő függvényeket exportálja:

@spec ksudoku:sudoku_be(FileIn::string()) -> SSpec::sspec()

SSpec a FileIn szövegfájlból beolvasott Sudoku-feladvány.

@spec ksudoku:sudoku_ki(FileOut::string(), SSols::[ssol()]) -> void()

Az SSols listában átadott Sudoku-megoldásokat kiírja a FileOut szövegfájlba.

@spec ksudoku:megold(FileIn::string(), FileOut::string()) -> void()

Beolvas egy feladványt a FileIn szövegfájlból és összes megoldását kiírja a FileOut szövegfájlba. Ehhez felhasználja a sudoku:sudoku/1 függvényt.

@spec ksudoku:stopper(FileIn::string(), FileOut::string()) -> void()

Mint ksudoku:megold/2, de a végén kiírja a FileIn nevét, a megoldások számát és a futási időt is.

@spec teljes_teszt(Timeout::integer()) -> [done|timeout].

A tests könyvtárban levő összes testXXXd.txt tesztállomány esetén:

• lefuttatja a tesztet Timeout másodperces időkorláttal,
• ellenőrzi, hogy a testXXXs.txt állományban megadott megoldáshalmazt kapta,
• olvasható formában (lásd megold/2) kiírja az eredményt a tests_out könyvtár testXXXt.txt nevű állományába.

A fenti állománynevekben XXX egy tetszőleges hosszúságú számjegysorozatot jelöl.
Ezt a függvényt Eisenberger András egészítette ki a megoldás ellenőrzésével.

Használat: saját sudoku.erl nevű programját minden változtatás után fordítsa le, és sudoku.beam néven rakja a keretprogrammal azonos mappába, különben a ksudoku.erl keretprogram nem találja meg. Ezután indítsa el az Erlang rendszert, és töltse be a lefordított keretprogramot. Példa:

Eshell V5.8  (abort with ^G)
1> l(ksudoku).
{module,ksudoku}
2> ksudoku:stopper("teszt0.txt","teszt0.sol").

A keretprogram automatikusan betölti a sudoku.beam programot, feltéve, hogy a keretprogrammal azonos mappában van.

Ha a saját sudoku.erl programját módosítja, a lefordítása után betöltheti az l(sudoku). paranccsal, de újra betöltheti a ksudoku.erl keretprogramot is, ami magával húzza a módosított programot. Egyes esetekben célszerű újraindítani az Erlang értelmezőt.

Dokumentációs követelmények

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 Erlang-diákon használt szövegelrendezési konvenciókat! Javasoljuk, hogy 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:

• Követelmények elemzése
• Tervezés, az egyes eljárások, ill. függvények specifikálása
• Kódolás Erlang-, ill. Prolog-nyelven, az algoritmusok ismertetése
• Tesztelési megfontolások
• Kipróbálási tapasztalatok

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 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 4.3.x, ill. az Erlang/OTP R16B rendszerekkel teszteljük.

Megoldásában Prolog nyelven tetszőleges könyvtárakat használhat, kivéve a clpfd, clpq, clpr, clpb, chr és atts Prolog-könyvtárakat: az ezeket a könyvtárakat felhasználó megoldások a létraversenyben nem vehetnek részt, és így megajánlott jegyet sem kaphatnak. Hasonlóképpen tiltott a mellékhatásos beépített eljárások, így az assert, retract, bb_put, bb_get stb. használata.

Erlang nyelven az adatbázist vagy egyéb mellékhatást használó függvények használata tilos (erlang:get, erlang:put, digraph modul, io modul stb.). Néhány megengedett, állapotmentes modul: array, dict, gb_*, lists, math, ord*, queue, sets, string.

A programokat és az elektronikus dokumentációt webes felületen lehet majd 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 elkészítése nem kötelező, de megoldását mindenkinek javasoljuk: ez a deklaratív nyelvek magas szintű elsajátítását nagy mértékben segíti.

A beadási határidő után értékeljük a programokat (ez az ún. "éles" teszt). Ehhez a beadási tesztsorozathoz hasonló nehézségű teszteseteket használunk. Az időkorláton belül helyes eredményt adó tesztesetek mindegyikére 0,5–0,5 pontot adunk, a 10 tesztesetre tehát nyelvenként összesen maximum 5 pontot. 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 pont kapható (ez 15%-a a pluszpontok nélkül elérhető legfeljebb 100 alappontnak).

Azok a programok, amelyek az éles teszt legalább 8 feladatát helyesen és az előírt időkorláton belül megoldják, létraversenyben vesznek részt. A leggyorsabban futó Erlang-, 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.

Azok a hallgatók, akik mindkét nyelvből bejutnak a létraversenybe - a tantárgyi adatlapon leírt feltételek fennállása esetén - megajánlott jegyet kapnak.

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 fegyelmi eljárást kezdeményezünk. Az algoritmusra vonatkozó ötletek cseréjét viszont nem tiltjuk.