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.

Kirakós játék elemei Összerakott kukorica kirakós játék
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 modulo m é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:

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   OO 
j−2 j−1 j j+1 j+2
i−2  OO  
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 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

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.

Prolog-hívás és eredmény Elhelyezés
?- csutkajo(3,3,[elem(['OO','X.','OO'],1-1,true),
                 elem(['O.','OX','O.'],1-0,false)]).
true
A 3 × 3 méretű csutka
012
0 001
1 101
2 001
?- csutkajo(3,3,[elem(['OO','X.','OO'],1-1,false),
                 elem(['O.','OX','O.'],1-0,false)]).
false
A 3 × 3 méretű csutka
012
0  00,1
1 101
2  00,1
?- csutkajo(3,4,[elem(['OO','X.','OO'],1-1,true),
                 elem(['O.','OX','O.'],1-0,false)]).
false
A 3 × 4 méretű csutka
0123
0 00 1
1 10 1
2 00 1
?- csutkajo(3,4,[elem(['OO','X.','OO'],1-1,true),
                 elem(['O.','OX','O.'],1-0,false),
                 elem(['..O','OXO','..O'],1-3,true)]).
false
A 3 × 4 méretű csutka
0123
0 0021
1 1,2021,2
2 0021

Tudnivalók a beadásról

DP Admin: dvacakrobotjaitoknakpadm@dp.iit.bme.hu Vissza az elejére / Back to the top