RAČ UNALNIŠ TVO Algoritem za reševanje Rubikove kocke sU sU vU Natalija Špur -> Poznate Rubikovo kocko? Ali jo znate rešiti? Ce ne, potem je ta Članek ravno za vas! Vse, kar potrebujete, je Rubikova kocka ter volja za reševanje. Rubikova kocka je trodimenzionalna sestavljanka, ki jo je leta 1974 izumil Erno Rubik. Poznamo različne dimenzije kock, kot so 2 x 2 x 2, 3 x 3 x 3,4 x 4 x 4. SLIKA 1. Kocka dimenzije 2 x 2 x 2 Cilj reševanja je sestaviti enobarvne ploskve. Kocka je zasnovana tako, da posamezne plasti lahko zavrtimo v različne smeri. V tem članku je predstavljena Fridrichina metoda, s katero rešimo kocko dimenzije 3 x 3 x 3. Kocka dimenzije 3 x 3 x 3 je sestavljena iz 26-ih manjših kockic. Razlocimo tri vrste kockic: Sredinska kockica ali center je kockica na sredini vsake plasti, ki se ne premika. Iz nje lahko razberemo barvo celotne ploskve. Kocka dimenzije 3 3 3 ima šest sredinskih kockic. SLIKA 2. Kocka dimenzije 3 x 3 x 3 SLIKA 3. Kocka dimenzije 4 x 4 x 4 Kotna kockica ali kot je kockica na sticišcu treh plasti in ima tri barve. Kocka dimenzije 3 x 3 x 3 ima osem kotnih kockic. Robna kockica ali rob je kockica na sticišcu dveh plasti in ima dve barvi. Kocka dimenzije 3 x 3 x 3 ima 12 robnih kockic. PRESEK 42 (2014/2015) 4 18 RAČU N A L NIŠTVO SLIKA 4. Sredinske kockice SLIKA 5. Kotne kockice SLIKA 6. Robne kockice Vsaka izmed šestih ploskev je obarvana z eno od barv: oranžno, modro, belo, zeleno, rdeco ali rumeno. Barva ploskve je določena s sredinsko koc-kico. Ploskev je sestavljena iz devetih ploskev koc-kic. Razlocimo spodnjo, zgornjo, prednjo, zadnjo, levo in desno ploskev. SLIKA 7. Ploskve Plast je tretjina kocke, ki je sestavljena iz devetih kockic (razen srednje plasti, ki jo sestavlja osem kockic). Kocka dimenzije 3 x 3 x 3 ima tri plasti. SLIKA 8. Ploskev Fridrichina metoda Fridrichina metoda je najbolj znana metoda reševanje Rubikove kocke. Ime je dobila po Jessici Fridrich, ki je profesorica na Univerzi Binghamton. S hitrostnim reševanjem Rubikove kocke se je zacela ukvarjati leta 1981 [3]. Postopek reševanja je razdeljen v vec delov, ki se morajo izvesti v pravilnem zaporedju. 24 PRESEK 42 (2014/2015) 4 RAČUNALNIŠ TVO SLIKA 9. Plast Lgor: levo plast obrnemo gor za 90° Ldo1: levo plast obrnemo dol za 90° (en obrat). (en obrat). Ddes: spodnj o plast obrnemo v smeri urinega ka- ^desno. zalca za 90° (en obrat). Dlevo. spodnj o plast obrnemo v levo za 90 obrat). Udesno. zgornjo plast obrnemo v smeri urinega kazalca za 90° (en obrat). U levo. SLIKA 10. Orientirana kockica Uporabljali bomo naslednje ukaze. ■ Fdesno. prednjo plast obrnemo v smeri urinega kazalca za 90° (en obrat). ■ Flevo. prednjo plast obrnemo v nasprotni smeri urinega kazalca za 90° (en obrat). ■ Rgor. desno plast obrnemo gor za 90° (en obrat). ■ desno plast obrnemo dol za 90° (en obrat). U desno (en -desno Rgor zgornjo plast obrnemo v nasprotni smeri D levo urinega kazalca za 90° (en obrat). Pravilno orientirana kockica pomeni, da se barva posamezne ploskve kotne kockice ujema s centri sti-kajocih se plasti (slika 10). Pravilno poravnana kotna kockica vsebuje barve stikajocih se plasti, ni pa nujno, daje pravilno orientirana (slika 12). Nerešena kockica pomeni, da kockica ni pravilno poravnana ali orientirana. Fridrichina metoda je sestavljena iz sledečih korakov: ■ križ (cross), ■ prvi dve plasti (First two Layers: F2L), ■ orientacija zadnje plasti (Orientation of Last Layer: OLL), ■ permutacija zadnje plasti (Permutation of the Last Layer: PLL). Vsi koraki metode bodo predstavljeni bolj podrobno. SLIKA11. Ukazi Križ Cilj. pravilno poravnane in orientirane robne kockice v zgornji plasti (v našem primeru bele barve - slika 13). 1. Ponavljaj, dokler robne kockice zgornje plasti niso pravilno poravnane in orientirane. 1.1. Postavitev kocke. ploskev, na kateri želiš narediti križ, naj bo zgoraj. 1.2. Poišči nerešeno zgornjo robno kockico prednje plasti in obrni kocko, da bo izbrana kockica na prednji plasti. L PRESEK 42 (2014/2015) 4 25 RAČU N A L NIŠTVO SLIKA 12. Poravnana kockica SLIKA 13. Križ SLIKA 15. Premik robne kockice SLIKA 16. Nepravilno orientirana robna kockica 1.3. Premakni pravilno poravnano ali orientirano robno kockico (takšne barve, kot je center prednje in zgornje ploskve - slika 14), da bo v spodnji plasti pod centrom prednje plasti (slika 15). 1.4. 2 X Flevo. 1.5. Ce robna kockica ni pravilno orientirana (slika 1g). Flevo ydesno ^gor ylevo SLIKA 14. Iskana robna Prvi dve plasti Ta korak bo razdeljen na podkoraka Reši kote prve plasti in Reši srednjo plast. Reši kote prve plasti Cilj. pravilno orientirane kockice v zgornji plasti (slika 17). kockica SLIKA 17. Rešena prva plast 26 PRESEK 42 (2014/2015) 4 RAČ UNALNIŠ TVO 1. Ponavljaj, dokler kotne kockice zgornje plasti niso pravilno orientirane. 1.1. Postavitev kocke: rešene robne kockice (križ) naj bodo na zgornji ploskvi. 1.2. Če obstaja nerešena kotna kockica barve zgornje ploskve v spodnji plasti (slika 18), zavrti spodnjo plast (Dlevo ali Ddesno), da bo izbrana kockica poravnana v spodnji plasti. 1.2.1. Če ima pravilno poravnana kotna kockica na spodnji ploskvi barvo centra zgornje ploskve: Rdol 2 X Dlevo Rgor plevo R dol Ddesno , Rgor. 1.2.2. Če ima pravilno poravnana kotna kockica na desni ploskvi barvo centra zgornje ploskve: Rdol Ddesno Rgor 1.2.3. Če ima pravilno poravnana kotna kockica na prednji ploskvi barvo centra zgornje ploskve: Ddesno Rdol Dlevo Rgor 1.3. Če v spodnji plasti ni vec nerešenih kockic , zgornja plast pa še ni rešena , poišči v zgornji plasti napacno orientirano kotno kockico, obrni kocko, da je v desnem sprednjem kotu in jo prestavi v spodnjo plast: Rdol Ddesno Rgor Dlevo Reši srednjo plast Cilj: pravilno orientirane in poravnane kockice v srednji plasti (slika 19). 1. Obrni kocko, da je trenutna zgornja plast sedaj spodnja plast. 2. Ponavljaj, dokler v zgornji plasti niso robne kockice pravilno poravnane in orientirane 2.1. Poišci robno kockico zgornje plasti, ki na nobeni ploskvi ne vsebuje barve centra. 2.2. Če ni takšne kockice (slika 20): SLIKA 18. Spodnja kotna kockica SLIKA 19. Rešeni spodnji dve plasti SLIKA 20. Robne kockice z barvo centra SLIKA 21. Rezultat po izvedbi koraka 2.4. SLIKA 22. Poravnava zgornje plasti PRESEK 42 (2014/2015) 4 27 RAČ UNALNIŠ TVO 2.2.1. Izvedi korake tocke 2.4. (slika 21) ali 2.5., da spraviš desno ali levo robno kockico prednje plasti v zgornjo plast. 2.2.2. Poravnaj zgornjo plast, da se bo robna kockica ujemala s centrom ene izmed ploskev (slika 22). 2.3. Obrni spodnji dve plasti, da se bo prednja ploskev robne kockice ujemala s centrom prednje ploskve (slika 23). 2.4. Če se zgornja ploskev robne kockice ujema s centrom desne ploskve: ydesno Rgor ylevo Rdol ylevo plevo ydesno pdesno (dobimo situacijo prikazano na sliki 24). 2.5. Če se zgornja ploskev robne kockice ujema s centrom leve ploskve (slika 23): ylevo pgor ydesno pdol ydesno pdesno ylevo plevo Orientacija in permutacija zadnje plasti Cilj: pravilno orientirane in poravnane kockice v zgornji plasti (slika 25). 1. Če imaš na zgornji ploskvi že križ , pojdi na korak 3. 2. Ponavljaj, dokler nimaš na zgornji ploskvi križa. 2.1. Obrni kocko tako , da bo zgornja plast v enem izmed prikazanih položajev na spodnjih slikah. S puščicami zgoraj je nakazan prehod med koraki , ki ga izvedemo s ponovitvami algoritma 2.2 (slika 26): pdesno Rgor ydesno Rdol ylevo levo 3. Ponavljaj, dokler niso robne kockice zgornje plasti pravilno poravnane in orientirane: SLIKA 25. Rešena Rubikova kocka 3.1. Če imaš en križ na eni izmed ploskev (križ na zgornji ploskvi ne šteje!) obrni kocko , da bo križ na sprednji ploskvi. 3.2. Poravnaj zgornjo plast tako , da dobiš dva križa na dveh ploskvah. 3.3. Če sta križa na sosednjih ploskvah: obrni kocko, da imaš na desni in zadnji ploskvi križ. 3.4. Če sta križa na nasprotnih ploskvah: obrni kocko, da bo križ na prednji in zadnji ploskvi. 3.5. Izvedi: Rgor ydesno Rdol ydesno Rgor 2 X Ušesno Rdol ydesno 4. Če v zgornji plasti nimaš nic pravilno poravnanih kotnih kockic: 4.1. Ponavljaj, dokler nimaš vsaj ene pravilno poravnane kotne kockice: y desno , Rgor , ylevo , Lgor , U desno dol levo dol Rdol ylevo pU 5. Obrni kocko tako da bo pravilno poravnana kotna kockica v desnem zgornjem kotu. 28 PRESEK 42 (2014/2015) 4 28 RAČ UNALNIŠ TVO > > > SLIKA 26. Prehod med koraki po izvedbi koraka 2.2. 6. Ponavljaj, dokler niso vse kotne kockice pravilno poravnane: ydesno Rgor ylevo ^§or ydesno Rdol ylevo L^ol 7. Ponavljaj, dokler se vse kotne kockice ne ujemajo z barvami sprednje in zgornje ploskve. 7.1. Obrni zgornjo plast, da bo nerešena kotna kockica v desnem zgornjem kotu. 7.2. Ponavljaj, dokler se barve kotne kockice ne ujemajo s sprednjo in zgornjo ploskvijo: Rdol pdesno Rgor plevo 8. Poravnaj plasti kocke, da se bodo ujemale s ploskvami kocke. Zaključek Uspelo? Če ne, nic zato. Poskusi znova. Če ti je uspelo, odlično! Pridno vadi, da ti bo reševanje šlo hitreje od rok. Še zanimivost: v Sloveniji imamo Rubik klub (RubiKS), za ljudi vseh starosti, ki se ukvarjajo z dejavnostjo, povezano z mehanskimi ugankami, med njimi tudi Rubikovo kocko [4]. V eni od prihodnjih številk bomo predstavili algoritem za reševanje Rubikovih kock 4 x 4 x 4. Literatura [1] How to Solve the Rubik's Cube! (Beginner Method) (citirano dne 23. 12. 2014, dostopno na https://www.youtube.com/watch?v= tYmtdFM1Zwk). [2] S. Gerhold, Razvoj interaktivne Rubikove kocke, Ljubljana, 2014. [3] Jessica Fridrich (citirano dne 23. 12. 2014, dostopno na http://www.ws.binghamton.edu/ fridri ch/). [4] Rubiks (citirano dne 23. 12. 2014, dostopno na http://www. rubik.si/klub/). [5] http://commons.wi kimedia.org/wi ki/ File:Rubi x_cube.j pg [6] http://zavaboy.devi antart.com/art/ Ani mated-Blank-Rubi k-s-Cube-53031084 [7] http://www.wikihow.com/ Make-Awesome-Rubi k's-Cube-Patterns _XXX Križne vsote -i' -i' -i' Naloga reševalca je, da izpolni bele kvadratke s števkami od 1 do 9 tako, da bo vsota števk v zaporednih belih kvadratkih po vrsticah in po stolpcih enaka številu, ki je zapisano v sivem kvadratku na začetku vrstice (stolpca) nad (pod) diagonalo. Pri tem morajo biti vse števke v posamezni vrstici (stolpcu) razlicne. „ 5 2 14 2 14 8 7 XXX PRESEK 42 (2014/2015) 4 29