2. nagy házi feladat (Prolog): Kirakós játék megoldása

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 megold/4 eljárás készítése, amely ütközésmentesen, az összes elemet felhasználva lefedi az n×m méretű rácsot. Az elemek egy része már le van helyezve a csutkára, azokat tilos áthelyezni. Ha nincs megoldás, az eljárás meghiúsul. Ha több megoldás is van, az eljárás ezeket mind, tetszőleges sorrendben felsorolja. Az elemek megadása megegyezik a kisháziban megszokottakkal.

      % megold(+N, +M, +Elemek0, -Elemek):
      % Egy N sorból és M oszlopból álló csutkára lehelyezi az Elemek0
      % listában adott elemeket. Elemek0 egy lista, melynek minden eleme
      % vagy egy elem(Sorok) vagy egy elem(Sorok,I-J,F) struktúra. Ebben Sorok
      % az adott elem karakteres megadása, I-J a referenciaszem helye F pedig false vagy true,
      % annak függvényében, hogy forgatás nélkül, vagy 180 fokkal elforgatva van
      % az elem a csutkára helyezve. Ha csak a Sorok van megadva, az elem
      % helyének megtalálása az eljárás feladata. A kimenő Elemek lista felépítése
      % hasonló, csak ott már minden elem(Sorok,I-J,F) struktúra, ami egy ütközésmentes
      % elhelyezést ad meg. Ha ez nem lehetséges, az eljárás meghiúsul.
    
Az eljárás paraméterei a következők:

A megold/4 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 elem      --->   elem(sorok)                      % egy lehelyezendő elem
  %                        ; elem(sorok,                      % egy lehelyezett elem
  %                               sorIndex-oszlopIndex,
  %                               forgatas).
  % :- type elemek      ==   list(elem).                      % a lehelyezendő/lehelyezett elemek egy listája
  % :- pred megold(sorSzam::in,                               % N
  %                oszlopSzam::in,                            % M
  %                elemek::in,                                % Elemek0
  %                elemek::out).                              % Elemek
  

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

?- megold(4, 4,
          [elem(['.O.', 'OXO']),
           elem(['O..', 'XOO']),
           elem(['O.', 'XO'],1-0,false),
           elem(['..O', 'OXO', '..O'],2-2,false)],Elemek).

Elemek = [elem(['.O.', 'OXO'],0-2,true),
          elem(['O..', 'XOO'],3-0,false),
          elem(['O.', 'XO'],1-0,false),
          elem(['..O', 'OXO', '..O'],2-2,false)] ;
false
?- megold(4, 4,
          [elem(['.O.', 'OXO']),
           elem(['O..', 'XOO']),
           elem(['O.', 'XO']), 
           elem(['O.', 'XO'],1-0,false),
           elem(['..O', 'OXO', '..O'],2-2,false)],Elemek).

false
?- megold(3, 3,
          [elem(['X'],0-2,false),
           elem(['X'],2-2,true),
           elem(['X'],2-0,false),
           elem(['XO','O.']),
           elem(['.O','OX'])],Elemek).

Elemek = [elem(['X'],0-2,false),
          elem(['X'],2-2,true),
          elem(['X'],2-0,false),
          elem(['XO', 'O.'],1-1,false),
          elem(['.O', 'OX'],0-0,true)] ;
Elemek = [elem(['X'],0-2,false),
          elem(['X'],2-2,true),
          elem(['X'],2-0,false),
          elem(['XO', 'O.'],0-0,false),
          elem(['.O', 'OX'],1-1,true)] ;
false

?- findall(1,megold(2, 4, 
                    [elem(['OX']),
                     elem(['OX']),
                     elem(['OX']),
                     elem(['OX'])], Elemek),_L), length(_L,N).

N = 1536 ;
false

?- megold(2, 4,
          [elem(['OX']),
           elem(['OX']),
           elem(['OX']),
           elem(['OX']),
           elem(['OX']),
           elem(['OX']),
           elem(['OX']),
           elem(['OX'])], Elemek).

false

Tudnivalók a beadásról

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