Rubik-kocka: valódi megoldó-algoritmus PHP-ben

A szerver PHP-ben kever meg egy Rubik-kockát (vagy a te kockádat), és két módszerrel is megoldja. A megoldást lépésről lépésre visszajátszhatod a 3D-kockán: látod, melyik lap merre fordul, és hogy a módszer éppen melyik szakaszánál tart.

A PHP megoldja a kockát…
Húzással szabadon forgatható a nézet: ez nem a kocka állapotát változtatja, csak azt, honnan nézed.

A PHP megoldja a kockát…

Tempó
Billentyűk: ← → léptetés, szóköz lejátszás és szünet, Home/End eleje és vége.

Hogyan olvasd a lépéseket?

A kockát végig ugyanúgy tartjuk: fehér közép felül, zöld közép feléd. A betű azt a lapot jelöli, amelyik fordul.

R
a lap negyed fordulata az óramutató járása szerint, ha szemből a lapra nézel
R'
ugyanez az óramutatóval szemben (a vessző az ellentétes irány)
R2
fél fordulat (két negyed, az irány mindegy)
Vidd az egeret (vagy a billentyűzet-fókuszt) egy lapbetűre vagy egy lépésre: a kockán kiemelődik a lap, és nyíl mutatja a forgás irányát.

Réteges módszer vs. Kociemba: hogyan oldja meg a gép a kockát?

A réteges (kezdő) módszer emberi logikát követ: először az alsó réteget rakja ki (kereszt, majd sarkok), utána a középső réteg éleit, végül négy lépésben a felső réteget. Ez itt jellemzően 120-150 lépés, mert minden szakasz csak a már kész részeket kímélő, rövid algoritmusokat ismételget, de ugyanezt a menetet egy ember is meg tudja tanulni.

A Kociemba-algoritmus a kockát matematikai struktúraként kezeli, és két fázisban keres: először egy olyan köztes állapotba jut, ahonnan már korlátozott mozdulatkészlet is elég, majd ezzel fejezi be. Előre kiszámolt táblák mondják meg a keresésnek, mennyi van még legalább hátra, így jellemzően 20-22 lépéses megoldást talál, néhány tized másodperc alatt.

2010-ben számítógépes bizonyítással igazolták, hogy minden lehetséges Rubik-kocka-állapot legfeljebb 20 mozdulattal megoldható: ez az "Isten száma" (God's Number), és a Kociemba-algoritmus ehhez az elméleti optimumhoz kerül közel.

A kocka lehetséges állapotainak száma kb. 43 trillió (4,3×10¹⁹): ezért nem lehet puszta próbálgatással megoldani, és kell hozzá vagy emberi stratégia, vagy okos, csoportelméleti keresés.