5. kis házi feladat: Kirakós játék megoldása felé: ütközésmentes referenciák

Kiadás: 2026-11-11, 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 referencia_lehet/5 eljárás készítése, amely egy részben lefedett csutka esetén megállapítja néhány elhelyezendő elemről, hogy hol lehet a referenciaszemük. Egy részben lefedett csutkát egy olyan n×m méretű rács ábrázol, ahol a lefedett mezőkön az ott levő elem sorszáma található. Cél az üres mezőkre felírni, hogy melyik elemet milyen forgatással lehet (a többi elemtől függetlenül) ütközés nélkül lehelyezni.

      % referencia_lehet(+N, +M, +Elemek, +Csutka0, -Csutka):
      % Az N sorból és M oszlopból álló, részben lefedett Csutka0 csutkára
      % megállapítja, hogy az Elemek listában levő elemeket melyik mezőkre, milyen
      % forgatással lehet lehelyezni, egymástól függetlenül.
      % Csutka0 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. A többi elem üres lista.
      % Csutka felépítése hasonló, csak az üres listák helyett Elem-Forgatas
      % alakú párok listái vannak, ahol Elem egy elem (nullával kezdődő) sorszáma,
      % Forgatas pedig true vagy false. Egy Elem-Forgatas pár akkor része a listának, ha 
      % a részben feledett listára az Elem sorszámú elem Forgatás forgatással
      % ütközés nélkül lehelyezhető.
    
Az eljárás paraméterei a következők:

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

A referencia_lehet/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
  % :- pred referencia_lehet(sorSzam::in,                     % N
  %                          oszlopSzam::in,                  % M
  %                          elemek::in,                      % Elemek
  %                          csutka::in,                      % Csutka0
  %                          csutka::out).                    % Csutka
  

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

Példák

?- referencia_lehet(4, 4,
                    [elem(['XO','O.','OO']),
                     elem(['O.','OX','O.'])],
                    [[2 , 2 , 2 , 2 ],
                     [2 , [], [], 2 ],
                     [[], 3 , 3 , []],
                     [[], [], [], []]], Csutka).

Csutka = [[2 , 2  ,2  ,2 ],
          [2 , [] ,[] ,2 ],
          [[], 3  ,3  ,[]],
          [[], [] ,[] ,[]]] ;
false
?- referencia_lehet(4, 4,
                    [elem(['XO','O.','OO']),
                     elem(['O.','OX','O.'])],
                    [[2 , 2 , 2 , 2 ],
                     [[], [], [], []],
                     [[], [], [], []],
                     [[], [], [], []]], Csutka).

Csutka = [[2               , 2                , 2                , 2                ],
         [[0-false]        , [0-false]        , [0-false]        , [0-false]        ],
         [[1-true, 1-false], [1-true, 1-false], [1-true, 1-false], [1-true, 1-false]],
         [[0-true]         , [0-true]         , [0-true]         , [0-true]         ]] ;
false
?- referencia_lehet(4, 4,
                    [elem(['OO','X.','OO']),
                     elem(['O.','OX','O.'])],
                    [[2 , 2 , 2 , 2 ],
                     [[], [], [], []],
                     [[], [], [], []],
                     [[], [], [], []]], Csutka).

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

Csutka = [[2        , [], [0-true], []],
          [2        , 2 , []      , 3 ],
          [[]       , 3 , 3       , 3 ],
          [[1-false], [], []      , 3 ]]
false

Tudnivalók a beadásról

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