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 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:
0'. karakterek az üres helyeket jelölik, ahol nincs kukoricaszem.0'O karakterek a kukoricaszemeket jelölik. Feltételezheti, hogy a kukoricaszemek összefüggő elemet alkotnak.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).
| Prolog-kód | Elhelyezés, 0° | Elhelyezés, 180° | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
elem = [ 'X.', 'O.', 'OO' ] |
|
|
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:
N száma, ahol 0 < N.M száma, ahol 0 < M.Elemek0 listája. Minden elemet egy elem(Sorok) vagy elem(Sorok,I-J,F)
összetett kifejezés ír le, annak függvényében, hogy az elem helye előre adott-e.
A változók jelentése a következő:
Sorok lista egyforma hosszú atomokból áll, és az elem elforgatás nélküli (0 fokos) alakját írja le.I-J számpár az elem referencia-kukoricaszemének I sorindexe és J oszlopindexe a csutkán (0 ≤ I,J < N).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.Elemek lista. Ebben már minden elem lehelyezett, a csutka összes mezője fedett és nincs két elem, ami egymást ütné.
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
| DP Admin: dvacakrobotjaitoknakpadm@dp.iit.bme.hu | Vissza az elejére / Back to the top |