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 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:
N száma, ahol 0 < N.M száma, ahol 0 < M.Elemek listája. Minden elemet egy elem(Sorok) összetett kifejezés ír le,
amelyben a Sorok lista egyforma hosszú atomokból áll, és az elem elforgatás nélküli (0 fokos) alakját írja le.
Feltételezheti, hogy mindegyik elem úgy van elhelyezve, hogy minden kukoricaszeme a csutkán helyezkedik el, azaz nem lóg le róla.
Csutka0 listák listája. A lista minden eleme egy lista, ami egy sort reprezentál.
A sorokat reprezentáló listák minden eleme vagy egy egész szám, ami a fedett elemeket jelöli, vagy egy üres lista, ami az üres helyeket jelöli.
Csutka listák listája. A lista minden eleme egy lista, ami egy sort reprezentál.
A sorokat reprezentáló listák minden eleme vagy egy egész szám, ami a fedett elemeket jelöli, vagy egy lista.
A lista vagy üres, vagy Elem-Forgatás párokat tárol, ahol Elem az egy, a mezőre Forgatás forgatással, ütközés nélkül lehelyezhető elem (nullával kezdődő) sorszáma.
Az Elem-Forgatás párok sorrendje a listán belül tetszőleges.
A referencia_lehet/5 eljárás minden helyes bemenetre sikeresen lefut.
% :- 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.
?- 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
| DP Admin: dvacakrobotjaitoknakpadm@dp.iit.bme.hu | Vissza az elejére / Back to the top |