4. kis házi feladat: Kirakós játék megoldásának ellenőrzése
Kiadás: 2026-11-04, beadási határidő a honlapon.
Verzió: $LastChangedDate$
A feladat egy térbeli kirakós játékot vizsgál.
A játék célja, hogy egy henger alakú kukoricacsutkára összetapadt kukoricaszemekből álló elemeket helyezzük el úgy, hogy a csutka minden részét pontosan egyszer fedjük be.
A kirakós elemei és az összerakott játék. Képek forrása:
thill.me.
A játékot egy olyan n×m méretű, azaz n sorból és m oszlopból álló négyzetráccsal modellezhetjük, ahol az oszlopindexet modulom értelmezzük. Így például egy 4×5 méretű csutkán a 2-0 és 2-5 párok ugyanazt a mezőt jelölik.
Az összetapadt kukoricaszemekből álló elemekre a következő jelölést vezetjük be: ha az elem belefér egy k×l méretű négyzetrácsba, akkor egy k elemű, egyenként l karakteres atomból álló listával ábrázoljuk. Az atomok kizárólag a 0'. (pont), 0'O, 0'X karakterekből állnak.
Ezeknek a jelentése az alábbi:
A 0'. karakterek az üres helyeket jelölik, ahol nincs kukoricaszem.
A 0'O karakterek a kukoricaszemeket jelölik. Feltételezheti, hogy a kukoricaszemek összefüggő elemet alkotnak.
Az elemben egyetlen kukoricaszem 0'O karakter helyett 0'X karakterrel van megjelölve. Ez a referencia-kukoricaszem. Amikor azt mondjuk, hogy az elemet a csutkán az i-j mezőre helyeztük, akkor a referencia-kukoricaszem a csutka i. sorában és j. oszlopában foglal helyet.
Mivel a csutka hengeres, az elemek is egy hengerpalástra illeszkednek. Ezért az elemeket csak 0 vagy 180 fokkal forgathatjuk el. Ha az elem a csutkán az atomok listájával leírt elrendezésben található meg, azt mondjuk, hogy 0 fokkal van elforgatva. A másik lehetséges elforgatás a referencia-kukoricaszem körül történő 180 fokos elforgatás (azaz középpontos tükrözés).
Egy L alakú elem kódolása és elhelyezése; az X referencia-kukoricaszem a i-j koordinátájú mezőn van
Prolog-kód
Elhelyezés, 0°
Elhelyezés, 180°
elem = [
'X.',
'O.',
'OO'
]
j−2
j−1
j
j+1
j+2
i−2
i−1
i
X
i+1
O
i+2
O
O
j−2
j−1
j
j+1
j+2
i−2
O
O
i−1
O
i
X
i+1
i+2
A feladat célja egy olyan csutkajo/3 eljárás elkészítése, amely egy csutka adott mezőire, adott elforgatással elhelyezendő elemekről megállapítja, hogy ütközés nélkül lefedik-e az egész csutkát:
% csutkajo(+N, +M, +Lehelyez): igaz, ha egy NxM-es (N soros és M oszlopos)
% táblára lehelyezve a Lehelyez listában levő elemeket, a csutka minden
% mezőjén pontosan egy kukoricaszem esik. A Lehelyez lista a lehelyezendő
% elemeket az elem(Sorok, I-J, F) struktúrában tárolja, ahol Sorok az elem
% atomok listájával megadott alakja, az I-J pár a referencia-kukoricaszem
% sora és oszlopa. Ha F=true, az elemet 180 fokkal elforgatva kell
% lehelyezni.
Az eljárás paraméterei a következők:
A csutka sorainak N száma, ahol 0 < N.
A csutka oszlopainak M száma, ahol 0 < M.
A csutkára helyezendő elemek Lehelyez listája. Minden elhelyezést egy elem(Sorok, I-J, F) összetett kifejezés ír le, amelynek jelentése a következő:
A Sorok lista egyforma hosszú atomokból áll, és az elem elforgatás nélküli (0 fokos) alakját írja le.
Az I-J számpár az elem referencia-kukoricaszemének I sorindexe és J oszlopindexe a csutkán (0 ≤ I,J < N).
Az F logikai érték az elem elforgatását jelzi: false esetén az elemet nem forgatjuk el (0 fok), true esetén pedig 180 fokkal forgatjuk el.
Feltételezheti, hogy mindegyik elem úgy van elhelyezve, hogy minden kukoricaszeme a csutkán helyezkedik el, azaz nem lóg le róla.
A csutkajo/3 eljárás sikeresen lefut, ha az elhelyezendő elemek ütközés nélkül lefedik az egész csutkát. Azaz minden mezőt pontosan egy elem fed le kukoricaszemmel. Amennyiben nincs minden mező lefedve, vagy az elemek ütköznek, az eljárás meghiúsul.
A csutkajo/3 eljárás paramétereinek típusát a következő – megjegyzésként megadott – Prolog-típusdefiníciók írják le.
% :- type sorSzam == integer. % a csutka sorainak a száma
% :- type oszlopSzam == integer. % a csutka oszlopainak a száma
% :- type sorIndex == integer. % a csutka egy sorának indexe
% :- type oszlopIndex == integer. % a csutka egy oszlopának indexe
% :- type forgatas ---> false % nincs forgatás
; true. % van forgatás
% :- type sorok == list(atom). % egy elem szöveges leírása
% :- type elemek == list(elem(sorok, % a lehelyezendő elemek egy listája
sorIndex-oszlopIndex,
forgatas)).
% :- pred csutkajo(sorSzam::in, % N
% oszlopSzam::in, % M
% elemek::in). % Lehelyez
A beadott programokat Linux környezetben SWI Prolog (10.1.13) rendszerrel teszteljük.
Tippek
A Sorok lista feldolgozásához az atom_codes/2 könyvtári eljárást ajánljuk.
Példák
Az ábrák mezőiben az őket lefedő elemek indexe látható. Ha egy mezőn több elem is található, az összes indexet feltüntetjük. A félkövér index azt jelzi, hogy az adott elemnek ezen a mezőn van a referencia-kukoricaszeme. Az elemeket a 0., 1. és 2. indexhez rendre sárga, kék és zöld háttér jelöli.