Sudoku szomszédsági korlátokkal

Definíciók

Sudoku-mátrixnak hívunk egy olyan négyzetes mátrixot, amelyben a sorok (és az oszlopok) száma egy n = k² ≥ 1 négyzetszám. (Tehát a mátrix elemeinek száma n² = 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 egy olyan Sudoku-mátrix, amelynek egyes mezői segítő információkat (röviden infókat) tartalmaznak. 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.

Egy n*n méretű Sudoku-feladvány helyes megoldása egy olyan n*n-es Sudoku-mátrix, amelynek mezői 1 és n közé eső egész számok. A megoldás helyességének alapfeltétele, hogy annak minden sorában, oszlopában és cellájában különböző számok álljanak, tehát a mátrix minden ilyen részterülete az 1..n számok mindegyikét pontosan egyszer tartalmazza. Emellett a megoldás helyességéhez az is szükséges, hogy teljesítse 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 két további fajta segítő információ fordulhat elő. A paritási infó a megoldás adott mezőjének paritását adja meg, tehát előírja, hogy az páros vagy páratlan értékű legyen. A szomszédsági infó azt az információt hordozza, hogy az adott mező értéke pontosan 1-gyel tér el az alatta, illetve a tőle balra levő mező értékétől (azaz ezek a mezőértékek szomszédos egész számok). A paritási és szomszédsági korlátozásokból egy mezőre több is vonatkozhat, ezek akár egymásnak vagy a száminfónak is ellentmondhatnak.

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.
2. A világhálón is találkozhatunk olyan Sudoku variánsokkal, amelyek szomszédsági megszorításokat tartalmaznak (lásd pl. a "Consecutive Sudoku" keresés eredményét). Ezen feladványok megoldási szabályai sokszor azt az információt is közlik, hogy a szomszédsági infók halmaza teljes, azaz a feladványban az összes teljesülő szomszédsági infó meg van adva. A jelen házi feladatban nem garantáljuk, hogy az összes lehetséges szomszédsági infó szerepel a feladványban. Ez azt jelenti, hogy akkor is megengedett, hogy a megoldás egy adott mezője az alatta vagy a tőle balra levő mező értékétől 1-gyel térjen el, ha az adott mezőre nem vonatkozik szomszédsági infó.

Példák

Példaként három Sudoku-feladványt mutatunk az 1. ábrán, ahol a k cellaméret rendre 3, 2, 3.

1. ábra

Az első feladványban csak száminfók vannak, mint a hagyományos Sudokuban. A második és harmadik feladványban betűk jelzik a paritási és szomszédsági infókat, ezek jelentése:

• e (even): az adott mező értéke páros,
• o (odd): az adott mező értéke páratlan,
• s (south): az adott és az alatta levő mező értéke között 1 a különbség,
• w (west): az adott és a tőle balra levő mező értéke között 1 a különbség.

A Sudoku-feladvány bal szélső oszlopának mezőiben is állhat w, alsó sorának mezőiben pedig s, annak ellenére, hogy nincs hasznosítható jelentésük. Ezeket az infókat 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ő feladványnak van más megoldása is, a másik kettőnek az ábrán szereplő tábla az egyetlen megoldása. A szomszédsági infók nem-teljes voltára (lásd a fenti második megjegyzést) több példát is találhatunk ezekben a feladványokban. Például a középső feladvány második sorának első mezője nem tartalmaz szomszédsági infót, pedig a megoldás adott mezőjének értéke 3, az alatta levő mező értéke pedig 4, azaz pontosan 1-gyel térnek el egymástól.

2. ábra

A megoldandó programozási feladat

Írjon sudoku néven olyan Prolog-eljárást, amely egy feladvány összes megoldását előállítja! Feltételezheti, hogy a feladvány cellamérete legfeljebb 10, azaz a sudoku-mátrix oldalhossza legfeljebb 100.

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(K,F)

felépítésű struktúra, ahol

• K a cellák oldalhossza,
• F 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 e, o, s és w atom, továbbá a v(N) struktúra, ahol N az adott mező előírt értéke (a v rövidítés az angol value szóból származik). Az infók listájában mindegyik atom illetve a struktúra 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, 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, [[[e,w,v(2),s],         [w],         [e],          []],
              [          [],     [e,s,w],          [],         [o]],
              [          [],          [],      [v(1)],          []],
              [         [w],         [s],          [],          []]])

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 ---> e; o; s; w; 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á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 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 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:

   2
   ew2s  w     e     -
   -     esw   -     o
   -     -     1     -
   w     s     -     -

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

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). (ezt az eljárást Eisenberger András ültette át Prologra)

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.

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.2.1 (x86-linux-glibc2.5): Wed Feb  1 01:12:14 CET 2012
Licensed to BUTE DP Course
| ?- [ksudoku].
% consulting d:/dokumentumok/bme/dp/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/dp/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

A 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 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
• Modellezés, a változók, tartományok, korlátok megválasztása
• Tervezés, az egyes eljárások specifikálása
• Kódolás 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.2.x rendszerekkel teszteljük.

Megoldását a SICStus Prolog clpfd, könyvtárának felhasználásával kell megirnia.

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.