6. kis házi feladat: Kirakós játék megoldása felé: lefedhető mezők

Kiadás: 2026-11-18, 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 lefedheto/5 eljárás készítése, amely egy részben lefedett, és lehetséges referenciákat tartalmazó csutka esetény megállapítja, mely mezők fedhetők le melyik referenciaszem által. A részben lefedett, és lehetséges referenciákat tartalmazó csutka az 5. kisházi feladatban eredményül kapott struktúrájú, azaz egy olyan n×m méretű rács, ahol a lefedett mezőkön az ott levő elem sorszáma található. A nem fedett mezőkön, pedig a fedettekhez képest ütközésmentesen lehelyezhető referenciaszem sorszáma és forgatása.

      % lefedheto(+N, +M, +Elemek, +Csutka, -Fedheto):
      % Az N sorból és M oszlopból álló Fedheto rácsra megállapítja a már
      % fedett mezőket, és a Csutka rácson megjelölt referenciaszemek által
      % lefedhető mezőket. Csutka formátuma megegyezik az 5. kisházi kimeneti
      % változójának formátumával.
      % Fedheto egy N elemű lista, aminek minden eleme egy M elemű lista. 
      % Az M elemű lista minden eleme a csutka egy mezőjét reprezentálja.
      % Egy mező pontosan akkor fedett, ha a megfelelő listaelem pontosan egy
      % egész számot tartalmaz. Ezek megegyeznek a Csutka paraméterben fedett elemekkel.
      % A nem fedett mezők vagy üres listák vagy forras(Sorszam,I-J,Forgat)
      % struktúrák listája, ahol Sorszam annak az elemnek a sorszáma, ami a mezőt fedheti,
      % I és J a referenciaszem sora illetve oszlopa és Forgat true vagy false, az elem 
      % forgatását jelzi.
    
Az eljárás paraméterei a következők:

A lefedheto/5 eljárás minden helyes bemenetre sikeresen lefut.

A lefedheto/5 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 sorszam     ==   integer.                         % az elem bemeneti listában elfoglalt (nullával kezdődő) sorszáma
  % :- 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)).
  % :- type mezo      --->   integer
  %                        ; list(sorszam-forgatas)
  % :- type csutka      ==   list(list(mezo)).                % a csutka leírása
  % :- type fedheto_m --->   integer                          % a fedhető rács egy mezője
  %                        ; list(forras(sorszam,
  %                                      sorSzam-oszlopSzam
  %                                      forgatas)).
  % :- type fedheto     ==   list(list(fedheto_m))            % a fedhető rács leírása
  % :- pred referencia_lehet(sorSzam::in,                     % N
  %                          oszlopSzam::in,                  % M
  %                          elemek::in,                      % Elemek
  %                          csutka::in,                      % Csutka
  %                          fedheto::out).                   % Fedheto
  

A beadott programokat Linux környezetben SWI Prolog (10.1.13) rendszerrel teszteljük.

Példák

?- lefedheto(3, 3,
             [elem(['OX']),
              elem(['OXO'])],
             [[2 , 3 , 4 ],
              [[], [], []],
              [[], [], []]], Fedheto).

Fedheto = [[2 , 3 , 4 ],
           [[], [], []],
           [[], [], []]] ;
false
?- lefedheto(3, 3,
             [elem(['OX']),
              elem(['OXO'])],
             [[2               , 3               , 4 ],
              [[]              , [0-false,0-true], []],
              [[0-false,1-true], []              , []]], Fedheto).

Fedheto = [[2                                        , 3                                        , 4                                        ],
           [[forras(0,1-1,false)]                    , [forras(0,1-1,true), forras(0,1-1,false)], [forras(0,1-1,true)]                     ],
           [[forras(1,2-0,true), forras(0,2-0,false)], [forras(1,2-0,true)]                     , [forras(1,2-0,true), forras(0,2-0,false)]]] ;
false
?- lefedheto(4, 4,
             [elem(['.O.','OXO']),
              elem(['O..','XOO'])],
             [[2        , [], [0-true], []],
              [2        , 2 , []      , 3 ],
              [[]       , 3 , 3       , 3 ],
              [[1-false], [], []      , 3 ]], Fedheto).

Fedheto = [[2                    , [forras(0,0-2,true)] , [forras(0,0-2,true)] , [forras(0,0-2,true)]],
           [2                    , 2                    , [forras(0,0-2,true)] , 3                   ],
           [[forras(1,3-0,false)], 3                    , 3                    , 3                   ],
           [[forras(1,3-0,false)], [forras(1,3-0,false)], [forras(1,3-0,false)], 3                   ]] ;
false



Tudnivalók a beadásról

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