Ha egy külföldit megkérdeznek Magyarország nevezetességeiről, nagy valószínűséggel megemlíti a Rubik-kockát is, amely sokak szemében immár jobban azonosítja hazánkat, mint a „gulasch” vagy a „tsardas”. A Bűvös kockaként (sőt Magyar kockaként) is emlegetett játék története a hetvenes évek elejére nyúlik vissza: feltalálója, az Iparművészeti Főiskola Belsőépítészeti Tanszékének oktatója, Rubik Ernő 1975 januárjában adta be szabadalmát a Találmányi Hivatalba. A kocka karrierje ettől kezdve töretlen: számos díjat nyert szerte a világon, bekerült a nagy „szótárba”, az Oxford English Dictionarybe, s még világbajnokságot is szerveztek köré. Ez utóbbi már csak annak ismeretében is érthető, hogy – bizonyos számítások szerint – 1400 milliárd évre lenne szükség ahhoz, hogy minden lehetőséget kirakjunk (egy fordításra egy másodpercet számolva).

Egy kocka, amely megmozgatta a világot

Nem véletlen tehát, hogy a Rubik-kocka, pontosabban annak kirakása, az informatikusok fantáziáját is megmozgatta, s még a szuperszámítógépek számolási kapacitását is bevetették, hogy megtalálják „Isten algoritmusát”, azt az algoritmust, amely a lehető legkevesebb lépéssel juttat el a célhoz: a Rubik-kocka kirakásához (az elnevezés hátterében egyébként az áll, hogy sokak szerint Isten tudja a legkevesebb számú mozdulatból megfejteni a kockát.).
Az egyik ezzel kapcsolatos, figyelemre méltó kutatási projekt a bostoni Northeastern Egyetem két tudósának nevéhez fűződik: Daniel Kunkle és Gene Cooperman most azon dolgoznak, hogy a szuperkomputer számolási erejének segítségével bebizonyítsák, akár 26-nál is kevesebb lépésből vissza lehet forgatni a kockát, akárhogyan is álljon az. A kutatók hamar rájöttek arra, hogy a lehetséges 43 252 003 274 489 856 000-féle kockapozícióból való visszaállítás kiszámolása még a legszuperebb számítógépen is kifog, ezért más módszert kerestek. 15 ezer olyan helyzetet találtak, amely megoldható 13 vagy annál kevesebb lépésből. Ezzel a feladattal egy egyszerű PC is elboldogul, mégpedig úgy, hogy végigvizsgál minden lehetséges mozdulatot.

Csak 1,4 trillió
Ezután azt kellett kikalkulálni, hogy hány lépés kell ahhoz, hogy bármilyen véletlenszerű kockaállást ezen 15000 speciális konfiguráció valamelyikébe forgassanak. Egy speciális osztályozási rendszerrel elérték, hogy „csak” 1,4 trillió lehetséges eset jöhessen szóba, ami természetesen már nagyságrendekkel kevesebb, mint amiről kezdetben szó volt, de persze még így is félelmetesen nagy szám. Ekkor hívták segítségül a szuperkomputert.
Mondják, az ördög a részletekben bújik, nos, Kunkle-ék ezt kissé átfogalmazták, miszerint az ördög a merevlemezen rejtőzött el, egészen pontosan az információk sorrendjében. A tudósok rájöttek, ha azt akarják, hogy a szuperszámítógép elboldoguljon a feladattal, olyan sorrendben kell elhelyezni az információkat, hogy a komputernek a lehető legkevesebbet kelljen kutakodnia a merevlemezen.
63 órányi számolás után végre eredményt kaptak: a szuperkomputer kikalkulálta, hogy nem kell több, mint 16 lépés ahhoz, hogy bármilyen véletlenszerű konfigurációt olyan speciális állásba kerüljön, amely megfelel a már említett 15 ezer forgatás valamelyikének. És mivel ez utóbbiak 13 lépésnél nem többől kirakhatók, a megközelítés azt mutatta, hogy 29 lépés elég bármilyen helyzetű Rubik kocka kirakásához.
Sajnos ez az eredmény még nem volt elég jó ahhoz, hogy új rekordot állítson fel. Tavaly ugyanis Silviu Radu (Lund Institute of Technology, Svédország) bebizonyította, hogy bármely Rubik kocka nem több, mint 27 lépésben kirakható. Kunkle és Cooperman rájöttek, hogy az új rekord felállításához 3 lépést még el kell tüntetniük. Kis idő elteltével kimutatták, hogy 80 millió konfigurációt leszámítva, valamennyi állás megoldható 26 vagy kevesebb lépésből. Ezután már csak erre a bizonyos 80 millió helyzetre koncentráltak, s meg is lett fáradozásuk gyümölcse: valamennyi helyzetből 26 vagy annál kevesebb lépéssel eljutottak a kiindulásig.
A tudósok ez év nyarán nyilvánosságra is hozták az eredményeiket egy nemzetközi szimpóziumon (International Symposium on Symbolic and Algebraic Computation - Waterloo, Ontario).

Ha már úgyis annyira ráérnek a számítógépek…

Nem öncélúan
A kutatásnak azonban ezzel még messze nincsen vége. A két bostoni tudós most a maximum 25 lépés elérésén fáradozik, de persze nem is titkolják, hogy a távolabbi cél az „isteni szám” (pontosabban lépésszám) elérése, amellyel (illetve amelynél kevesebbel) bármilyen állás a kiinduló helyzetbe hozható. Az átfogó kutatások jelenleg azt sugallják, hogy ez a bizonyos szám 20 körül mozog.
Kutatómunkájuk persze nem öncélú, hiszen – ahogy Kunkle a szimpózium sajtótájékoztatóján megjegyezte – ezeket a technikákat bármilyen kombinatorikai problémára lehet alkalmazni. Példaként a dáma- és sakkjátékot, a repülőjáratok ütemezését, valamint a fehérjekapcsolódást említette.