RACU N A L NI STVO Rubikovo maščevanje; algoritem za reševanje Rubikove kocke 4 x 4 x 4 - 1. del Marko Jakovac -> V članku [7] smo spoznali algoritem za reševanje Rubikove kocke dimenzije 3 x 3 x 3. Med drugim je bila v tem članku omenjena tudi Rubikova kocka dimenzije 4 x 4 x 4, ki jo lahko vidimo na sliki 1 [1]. Poljudno jo imenujemo tudi Rubikovo maščevanje (ang. Rubik's revenge) [5]. V nadaljevanju si bomo pogledali, zakaj je dobila takšno ime in kako jo rešimo. Pri tem bomo uporabljali podobne izraze kot v članku za reševanje Rubikove kocke dimenzije 3x3x3. Osnovni pojmi Cilj reševanja Rubikove kocke dimenzije 4 x 4 x 4 ostaja enak kot pri Rubikovi kocki dimenzije 3x3x3, tj. sestaviti enobarvne ploske. Rubikova kocka dimenzije 4 x 4 x 4 ima šest ploskev. Vsaka ploskev je sestavljena iz 16-ih ploskev manjših kockic in je obarvana z eno izmed naslednjih barv: bela, rumena, modra, zelena, rdeca in oranžna. Vseh manjših koc-kic v celotni Rubikovi kocki dimenzije 4 x 4 x 4 je natancno 56 in jih ločimo glede na njihovo lego v večji kocki: SLIKA 1. Rubikova kocka dimenzije 4 x 4 x 4 ■ Sredinska kockica je ena izmed štirih kockic na sredini vsake ploskve. Štiri sredinske kockice na isti ploskvi imenujemo sredina. Dve vodoravni ali navpicni sosednji sredinski kockici imenujemo sredinska vrstica. Za razliko od Rubikove kocke dimenzije 3 x 3 x 3 se sredinske kockice med reševanjem kocke premikajo. Rubikova kocka dimenzije 4x4x4 ima 24 sredinskih kockic. 22 PRESEK 45 (2017/2018) 1 RACUNALNIŠ TVO ■ Kotna kockica je kockica na stičišču treh ploskev in ima natančno tri barve. Rubikova kocka dimenzije 4 x 4 x 4 ima osem kotnih kockic. ■ Robna kockica je kockica na sticišcu dveh ploskev in ima natancno dve barvi. Sosednji robni kockici imenujemo robna vrstica. Rubikova kocka dimenzije 4 x 4 x 4 ima 24 robnih kockic. Plast Rubikove kocke dimenzije 4 x 4 x 4 je cetrtina celotne kocke. Zunanji plasti sta sestavljeni vsaka iz 16-ih kockic, srednji plasti pa vsaka iz 12-ih kockic. Rubikovo maščevanje Da bi razumeli ozadje reševanja Rubikove kocke dimenzije 4x4x4, moramo najprej razumeti strukturo klasicne Rubikove kocke dimenzije 3 x 3 x 3. Marsikoga je že zamikalo, da bi Rubikovo kocko razstavil na manjše kockice. Ce to naredimo in nato kockice sestavimo nazaj v vecjo kocko, se lahko zgodi, da leta ne bo vec rešljiva. Dovolj je že, da izderemo eno kockico, jo obrnemo in vstavimo nazaj v vecjo kocko. In prav s tem dejstvom je povezana Rubikova kocka dimenzije 4 x 4 x 4. Takoj lahko opazimo, da pri klasicni kocki med njenim reševanje sredinska koc-kica miruje in nam s tem nudi oporo pri reševanju same kocke. Pri Rubikovi kocki dimenzije 4 x 4 x 4 pa imamo na vsaki ploskvi štiri sredinske kockice in posledicno se te med reševanjem premikajo. To pa ima na samo reševanje enak ucinek, kakor da bi razdrto Rubikovo kocko dimenzije 3 x 3 x 3 morali najprej pravilno sestaviti, preden se lotimo njenega reševanja. Preneseno v jezik reševanja Rubikove kocke dimenzije 4 x 4 x 4 to pomeni, da si lahko med njenim reševanjem otežimo delo do te mere, da bomo od nekega trenutka naprej reševali nerešljivo kocko. Ce se zgodi prav to, je treba v vecini primerov z reševanjem priceti od zacetka. Prav zaradi tega dejstva je Rubikova kocka dimenzije 4 x 4 x 4 dobila ime Ru-bikovo mašcevanje. Ukazi za reševanje Rubikove kocke dimenzije 4x 4 x 4 Uporabili bomo ukaze, ki so bili vpeljani v clanku [7], ter jih nekoliko dopolnili, saj Rubikova kocka dimenzije 4 x 4 x 4 vsebuje vec plasti. Prav tako bomo v nekem trenutku reševanje Rubikove kocke dimenzije 4 x 4 x 4 prevedli ne reševanje Rubikove kocke dimenzije 3 x 3 x 3, zato je zelo pomembno, da znamo najprej rešiti klasicno Rubikovo kocko [2, 7] in da dobro poznamo vse ukaze, ki nas privedejo do rešitve. Locili bomo naslednje ukaze: ■ Pdesno: P-plast obrnemo v smeri urinega kazalca za 90°(en obrat). Plevo: P-plast obrnemo v nasprotni smeri urinega kazalca za 90°(en obrat). ■ P2: P-plast obrnemo v poljubni smeri za 180°(dva obrata). Pri tem bo oznaka P predstavljala eno izmed naslednjih plasti: F-sprednja plast, f-srednja sprednja plast, B-zadnja plast, b-srednja zadnja plast, U-zgor-nja plast, u-srednja zgornja plast, D-spodnja plast, d-srednja spodnja plast, L-leva plast, l-srednja leva plast, R-desna plast, r-srednja desna plast (slika 2). L l r R ^ ^ ^ ^ U-> u d D -> F SLIKA 2. Vse plasti Rubikove kocke dimenzije 4 x 4 x 4 Pozor! Vse omenjene ukaze izvajamo tako, da v izvedbi danega ukaza gledamo izbrano plast. Ce npr. obrnemo zadnjo plast v smeri urinega kazalca, bi v primeru, da bi obrat gledali s sprednje strani, videli obrat v nasprotni smeri urinega kazalca. Prav tako je zelo pomembno, da pri premikih srednjih plasti (f,b,u,d,l,r) ne premikamo hkrati tudi zunanjih plasti (F,B,U,D,L,R), kar je pogosta napaka, ki se dogaja pri reševanju vecjih kock. Na slikah bodo kockice, ki v danem trenutku ne bodo pomembne, oznacene s sivo barvo. Uporabljena metoda za reševanje Rubikove kocke dimenzije 4 x 4 x 4 je z nekaj spremembami in al- PRESEK 45 (2017/2018) 1 23 RACUNALNIŠ TVO —^ ternativnimi premiki povzeta po [6] in vsebuje naslednje korake: ■ enobarvne sredine (sestavljanje sredinskih kockic tako, da bo vsaka sredina vsebovala enake sredinske kockice), ■ dvobarvne robove (sestavljanje robnih vrstic tako, da bosta obe kockici poljubne robne vrstice enaki), ■ algoritem za Rubikovo kocko dimenzije 3 x 3 x 3 (sestavljanje Rubikove kocke dimenzije 4 x 4 x 4 s pomočjo algoritma za sestavljanje Rubikove kocke dimenzije 3 x 3 x 3), ■ parnost orientacije zadnje plasti (ang. OLL parity - orientation last layer parity) in parnost permu-tacije zadnje plasti (ang. PLL parity - permutation last layer parity). Enobarvne sredine Na kocki želimo sestaviti vseh šest sredin tako, da bo vsaka sredina vsebovala kockice enake barve. Enobarvne sredine nam bodo služile kot oporne tocke za nadaljnje reševanje kocke, pri tem pa moramo paziti, da vse enobarvne sredine postavimo na ustrezna mesta, saj lahko v nasprotnem primeru dobimo nerešljivo kocko in vsi nadaljnji koraki bi bili zaman. Najprej je treba prouciti kocko in ugotoviti katere barve so si nasprotne. To storimo tako, da po-išcemo dve kotni kockici z dvema enakima barvama (kockici ni potrebno premikati). Tretja barva, ki je razlicna na obeh kotnih kockicah, nam pove, kateri barvi morata v pravilno sestavljeni kocki biti na nasprotnih ploskvah. V našem primeru so nasprotne naslednje barve: bela-rumena, modra-zelena, rdeca-oranžna (na nekaterih kockah je lahko tudi drugace). Ko dolocimo nasprotne barve, je treba dolociti tudi njihovo pravilno orientacijo. To naredimo tako, da pogledamo eno izmed kotnih kockic, ki nam pove, katere tri barve se morajo srecati v dolocenem kotu. V našem primeru v enem kotu najdemo skupaj belo, zeleno in rdeco barvo. Na sliki 3 smo dve izbrani kotni kockici postavili tako, da hkrati vidimo dve nasprotni barvi (bela-rumena) in tri barve, ki se srecajo v dolocenem kotu (bela-zelena-rdeca). Sedaj imamo vse podatke, da ustrezno sestavimo enobarvne sredine. Cilj: sestaviti prvo in drugo enobarvno sredino z nasprotnima barvama na sprednji in zadnji ploskvi (v našem primeru bela in rumena barva). Pogled spredaj/levo/zgoraj m Pogled spredaj/levo/spodaj xm m SLIKA 3. Dve nasprotni barvi (bela-rumena) in pravilna orientacija treh barv (bela-zelena-rdeca) Postavitev kocke: kocko postavite poljubno, vendar je pri izvajanju nadaljnjih korakov vec ne obra-cajte. Ce obstaja bela sredinska vrstica, jo premaknite v u-plast na sprednji ploskvi. Ce bela sredinska vrstica ne obstaja, postavite dve beli sredinski kockici, kot prikazuje slika 4, in izvedite: ldesno, F2. Pogled spredaj/levo/zgoraj \1 SLIKA 4. Postavitev prvih dveh belih sredinskih kockic Ce obstaja rumena sredinska vrstica, jo s pomocjo f-plasti, b-plasti, d-plasti in zunanjih plasti (brez uporabe F-plasti) premaknite v u-plast na zadnji ploskvi. Ce rumena sredina vrstica ne obstaja, s pomocjo f-plasti, b-plasti, d-plasti in zunanjih plasti (brez uporabe F-plasti) postavite dve rumeni sredinski kockici, kot prikazuje slika 5, in izvedite: flevo, dlevo, B2. Ce obstaja tudi druga rumena sredinska vrstica in ne sestavlja rumene sredine na zadnji ploskvi, jo s pomocjo f-plasti, b-plasti, d-plasti in zunanjih pla- 24 PRESEK 45 (2017/2018) 1 24 RACUNALNIŠ TVO Pogled spredaj/levo/zgoraj Pogled spredaj/levo/zgoraj Pogled zadaj/desno/zgoraj SLIKA 5. Postavitev prvih dveh rumenih sredinskih kockic sti (brez uporabe F-plasti in B-plasti) premaknite v d-plast na zadnji ploskvi. ■ Če druga rumena sredinska vrstica ne obstaja, s pomočjo f-plasti, b-plasti, d-plasti in zunanjih plasti (brez uporabe F-plasti in B-plasti) postavite preostali rumeni sredinski kockici, kot prikazuje slika 6, in izvedite: flevo, dlevo. Pogled spredaj/levo/zgoraj Pogled zadaj/desno/zgoraj SLIKA 6. Postavitev drugih dveh rumenih sredinskih kockic ■ Če obstaja tudi druga bela sredinska vrstica in ne sestavlja bele sredine na sprednji ploskvi, s pomočjo f-plasti, b-plasti in zunanjih plasti (brez uporabe F-plasti) pripravite kocko, kot prikazuje slika 7, in izvedite: L2, dlevo, L2, ddesno. ■ Ce druga bela sredinska vrstica ne obstaja, a obstajata dve beli sredinski kockici v f-plasti in/ali b-plasti, ju s pomocjo f-plasti, b-plasti in zunanjih plasti (brez uporabe F-plasti) postavite, kot prikazuje slika 8, in izvedite: flevo, L2, dlevo, L2, ddesno. Ce druga bela sredinska vrstica ne obstaja in obstaja ena bela sredinska kockica v f-plasti ali b-plasti, s pomocjo f-plasti, b-plasti in zunanjih plasti pripravite kocko, kot prikazuje slika 9, in izvedite: F^esno dlesno Flevo dlevo SLIKA 7. Postavitev druge bele sredinske vrstice Pogled spredaj/levo/zgoraj Pogled zadaj/desno/zgoraj SLIKA 8. Postavitev drugih dveh belih sredinskih kockic Pogled spredaj/levo/zgoraj Pogled zadaj/desno/zgoraj SLIKA 9. Postavitev drugih dveh belih sredinskih kockic, kjer je ena sredinska kockica na sprednji ploskvi Nadaljujemo s sestavljanjem dveh novih enobarvnih sredin z nasprotnima barvama. Postopek bo podoben, vendar bodo v njem pomembne razlike, saj v tem primeru veČc ne smemo posegati v obe ploskvi, kjer sta že sestavljeni prvi dve enobarvni sredini. PRESEK 45 (2017/2018) 1 25 RAČU N A L NIŠTVO —^ Cilj: sestaviti tretjo in cetrto enobarvno sredino z nasprotnima barvama na sprednji in zadnji ploskvi (v našem primeru modra in zelena barva). ■ Postavitev kocke: kocko postavite tako, da bosta že sestavljeni enobarvni sredini na zgornji in spodnji ploskvi (npr. bela sredina zgoraj in rumena sredina spodaj) in je pri izvajanju nadaljnjih korakov vec ne obračajte. ■ Ce ima kocka že sestavljeni obe sredini, a nista na nasprotnih ploskvah, pripravite kocko, kot prikazuje slika 10, in izvedite: dlevo, B2, d2, L2, dlevo. Pogled spredaj/levo/zgoraj Pogled spredaj/levo/spodaj Pogled spredaj/levo/zgoraj SLIKA 11. Postavitev prvih dveh modrih sredinskih kockic Ce obstaja zelena sredinska vrstica, jo s pomočjo d-plasti in zunanjih plasti premaknite v u-plast na zadnji ploskvi. Ce zelena sredinska vrstica ne obstaja, s pomocjo d-plasti in zunanjih plasti postavite dve zeleni sredinski kockici, kot prikazuje slika 12, in izvedite: dlevo L^esno dlevo b2 Pogled spredaj/levo/zgoraj SLIKA 10. Modra in zelena sredina nista na nasprotnih ploskvah Ce obstaja modra sredinska vrstica, jo s pomocjo d-plasti in zunanjih plasti premaknite v u-plast na sprednji ploskvi. Ce modra sredinska vrstica ne obstaja, postavite dve modri sredinski kockici, kot prikazuje slika 11, in izvedite: ddesno, Flevo. SLIKA 12. Postavitev prvih dveh zelenih sredinskih kockic ■ Ce obstaja tudi druga modra sredinska vrstica, jo s pomocjo d-plasti in zunanjih plasti premaknite v u-plast na levi ploskvi. ■ Ce druga modra sredinska vrstica ne obstaja, s pomoCcjo d-plasti in zunanjih plasti postavite dve modri sredinski kockici, kot prikazuje slika 13, in izvedite: dlevo, Llevo. Pogled spredaj/levo/zgoraj Pogled zadaj/desno/zgoraj I SLIKA 13. Postavitev drugih dveh modrih sredinskih kockic Ce obstaja tudi druga zelena sredinska vrstica, jo s pomoCcjo d-plasti in zunanjih plasti premaknite v u-plast na desni ploskvi. Ce druga zelena sredinska vrstica ne obstaja, s pomocjo d-plasti in zunanjih plasti postavite dve zeleni sredinski kockici, kot prikazuje slika 14, in izvedite: ddesno, Rlevo. Pripravite kocko, kot prikazuje slika 15, in izvedite: ddesno. 26 PRESEK 45 (2017/2018) 1 RACUNALNIŠ TVO Pogled spredaj/desno/zgoraj Pogled zadaj/levo/zgoraj SLIKA 14. Postavitev drugih dveh zelenih sredinskih kockic Pogled spredaj/levo/zgoraj Pogled zadaj/levo/zgoraj SLIKA 16. Pravilna orientacija rdece sredine Cilj: sestaviti peto in šesto enobarvno sredino s pravilno orientiranima nasprotnima barvama na sprednji in zadnji ploskvi (v našem primeru rdeca barva na sprednji ploskvi in oranžna barva na zadnji ploskvi). ■ Postavitev kocke: kocko postavite tako, kot prikazuje slika 16, in je pri izvajanju nadaljnjih korakov vec ne obračajte. ■ Če ima kocka že sestavljeno rdečo in oranžno sredino, a sta na napacnih ploskvah (oranžna sredina na sprednji ploskvi in rdeca sredina na zadnji ploskvi), izvedite: d2, F2, B2, d2. ■ Če ima kocka na sprednji in zadnji ploskvi šahovski vzorec, jo s pomoČcjo F-plasti in B-plasti pripravite, kot prikazuje slika 17, in izvedite: d2, Fdesno B^esno d2 Pogled spredaj/levo/zgoraj Pogled zadaj/levo/zgoraj SLIKA 15. Postavitev modrih in zelenih sredinskih vrstic Sedaj imamo sestavljene že štiri enobarvne sredine, tako da nam preostaneta le še dve. V našem primeru sta to rdeca in oranžna sredina. V zadnjem koraku bo orientacija zelo pomembna, saj vemo, da mora rdeca barva mejiti na belo in zeleno, zato bomo glede na sliko 16 na sprednji ploskvi sestavili rdeco sredino, na zadnji ploskvi pa oranžno sredino. Pogled spredaj/levo/zgoraj SLIKA 17. Šahovski vzorec na sprednji in zadnji ploskvi ■ Če ima kocka na sprednji ploskvi šahovski vzorec, na zadnji ploskvi pa eno rdeco in eno oranžno sredinsko vrstico, jo s pomoČcjo F-plasti in B-plasti pripravite, kot prikazuje slika 18, in izvedite: d2, Bdesno d2 Opomba. Po tem koraku obe sredini še ne bosta sestavljeni in je treba izvesti še enega izmed naslednjih korakov. ■ Če ima kocka na sprednji ploskvi eno rdeco in eno oranžno sredinsko vrstico, na zadnji ploskvi pa šahovski vzorec, jo s pomoČcjo F-plasti in B-plasti pripravite, kot prikazuje slika 19, in izvedite: d2, Blevo, d2. Opomba. Po tem koraku obe sredini še ne bosta sestavljeni in je treba izvesti še enega izmed naslednjih korakov. ■ Če ima kocka na sprednji ploskvi tri rdece sredinske kockice, jo s pomocjo F-plasti in B-plasti pripravite, kot prikazuje slika 20, in izvedite: d2, Flevo d2 PRESEK 45 (2017/2018) 1 27 RAČU N A L NIŠTVO —^ Pogled spredaj/levo/zgoraj Pogled zadaj/levo/zgoraj Pogled spredaj/levo/zgoraj Pogled zadaj/levo/zgoraj S= SLIKA 18. Šahovski vzorec le na sprednji ploskvi SLIKA 21. Ena rdeča sredinska kockica na sprednji ploskvi Pogled spredaj/levo/zgoraj Pogled zadaj/levo/zgoraj SLIKA 19. Šahovski vzorec le na zadnji ploskvi Pogled spredaj/levo/zgoraj Pogled zadaj/levo/zgoraj Pogled spredaj/levo/zgoraj Pogled zadaj/levo/zgoraj SLIKA 22. Ena rdeča in ena oranžna sredinska vrstica na sprednji in zadnji ploskvi Ce ste uspešno izvedli vse tri opisane postopke, potem bi morala kocka imeti pravilno sestavljenih vseh šest enobarvnih sredin (slika 23). Pred nadaljevanjem postopka je priporočljivo še enkrat preveriti s poljubno kotno kockico, če so vse barvne sredine na ustreznih mestih. SLIKA 20. Tri rdece sredinske kockice na sprednji ploskvi Ce ima kocka na sprednji ploskvi eno rdece sredinsko kockico, jo s pomočjo F-plasti in B-plasti pripravite, kot prikazuje slika 21, in izvedite: d2, Flevo,B2,d2. Ce ima kocka na sprednji in zadnji ploskvi eno rdeco in eno oranžno sredinsko vrstico, jo s po-mocjo F-plasti in B-plasti pripravite, kot prikazuje slika 22, in izvedite: d2, B2, d2. Pogled spredaj/levo/zgoraj Pogled zadaj/levo/spodaj SLIKA 23. Pravilno sestavljenih vseh šest enobarvnih sredin 28 PRESEK 45 (2017/2018) 1 RACUNALNIŠ TVO Se nadaljuje ... V naslednji številki revije Presek si bomo pogledali še preostale tri korake našega algoritma in s tem dokončno rešili Rubikovo kocko dimenzije 4 x 4 x 4. Literatura [1] Best Speed Cubes, dostopno na http://www. bestspeedcubes.com/4x4-rubi ks-cubes/, ogled dne 22. 4. 2017. [2] How to Solve the Rubik's Cube! (Beginner Method), dostopno na https : //www. youtube. com/watch?v=tYmtdFM1Zwk, ogled dne 22. 4. 2017. [3] Jessica Fridrich, dostopno na http://www.ws. binghamton.edu/fridrich/, citirano dne 22. 4. 2017. [4] Professor's Cube, dostopno na https: //en.wiki pedi a.org/wi ki/Professor\ %27s\_Cube, ogled dne 22. 4. 2017. [5] Rubik's Revenge, Wikipedia, dostopno na https://en.wiki pedia.org/wi ki/Rubi k\ %27s\_Revenge, ogled dne 22. 4. 2017. [6] Solving the Rubik's Revenge (x4 x 4), dostopno na http://www.speedcubi ng.com/chris/ 4-sol uti on . html, ogled dne 22. 4. 2017. [7] N. Špur, Algoritem za reševanje Rubikove kocke, Presek, 42 (2014/2015), 4, 23-29. _XXX www.obzornik.si www.presek.si www.dmfa-zaloznistvo.si Barvni sudoku •4/ -i' •i' V 8 x 8 kvadratkov moraš vpisati začetna naravna števila od 1 do 8 tako, da bo v vsaki vrstici, v vsakem stolpcu in v kvadratkih iste barve (pravokotnikih 2 x 4) nastopalo vseh 8 števil. 2 3 1 3 8 4 5 4 1 7 8 6 4 2 4 6 5 2 O v O □ O m > a < a > m H >W m a 2 L 5 E 8 L 6 4 L 8 17 9 2 S L E 4 6 Z 8 E L 7 S E S L 1 9 4 8 Z 8 E L L 17 Z 5 9 S 4 9 Z L 8 3 L 9 L Z 8 S L E 17 1 L 3 17 S 9 2 8 XXX PRESEK 45 (2017/2018) 1 29