20 mozdulattal kirakható bármely Rubik kocka

15 évig tartott mire eljutottak erre a pontra, most már azonban bizonyos, hogy akárhogyan is keverjenek össze egy Rubik-kockát, azt legfeljebb 20 mozdulattal ki lehet rakni - és még a matricákat sem kell leszedni.

Az 1980-as évek legnagyobb sikerű fejtörőjének számító logikai játék titka már az 1979-es világpremier óta foglalkoztatja a kutatókat, akik az összesen 43 252 003 274 489 856 000-féle kezdő pozícióból próbálták megtalálni az "isteni számot", azaz, hogy legfeljebb hány lépés kell a kocka kirakásához. Az eredményt közzétevő csapat a Google számítási teljesítményét és jópár matematikai csavart ötvözve végigellenőrizte az összes, 43 kvintrillió lehetséges összekevert pozíciót, amit a kocka fel tud venni, megfejtve ezzel a híres kocka legnagyobb matematikai rejtvényét.

A kutatók 1995-ig még úgy vélték, hogy legfeljebb 18 lépés szükséges a kocka optimális kirakásához, azonban Michael Reid matematikus felfedezett egy olyan kombinációt, amelyet 20 lépésnél kevesebb forgatással nem lehet megoldani. A végleges válaszra csak a számítástechnika fejlődése adhatta meg a választ, bár a jelenlegi szuperszámítógépek teljesítménye sem elegendő ahhoz, hogy minden lehetséges kombinációt végigpróbáljanak.

Az elsődleges áttörést egy, a csoportelmélet elnevezésű matematikai ágból vett technikának köszönhették, magyarázta Tomas Rokicki, kaliforniai programozó, aki az elmúlt 15 évet annak a legkisebb számnak a keresésével töltötte, amivel a kocka bármelyik elrendezése kirakható. Az "Isten számaként" is emlegetett értékről 2008-ban számoltunk be legutóbb, amikor Rokicki 22-re csökkentette, azonban már akkor is egyértelmű volt, hogy ez még nem a legkisebb szám.

A csoportelméletből származtatott technikával először felosztották az összes lehetséges kezdő konfigurációt 2,2 milliárd csoportra, melyek mindegyike 19,5 milliárd elrendezést foglalt magába, annak megfelelően hogyan reagálnak ezek a konfigurációk a kocka tekergetésének 10 lehetséges mozdulatára. A kocka különböző szimmetriáit kihasználva a projekten dolgozó matematikusoknak sikerült a csoportok számát 56 millióra csökkenteniük, mondván például, ha egy összekevert kockát egyszerűen az oldalára, vagy fejjel lefelé fordítunk, azzal nem lesz nehezebb a kirakása, tehát ezeket az egyenértékű pozíciókat máris el lehetett vetni. Ettől azonban még rengeteg ellenőrizendő induló konfiguráció maradt, ezért a csapat kidolgozott egy algoritmust a folyamat felgyorsítására.

A korábbi módszerekkel másodpercenként körülbelül 4000 kockát tudtak végigpróbálni, az algoritmus megvizsgált egy sorozat induló mozdulatot, majd meghatározta, hogy az eredményként kapott pozíció közelebb van-e a megoldáshoz. Ha nem, akkor az algoritmus elvetette ezeket a lépéseket és újra indult. Rocicki felismerte, hogy ezek a zsákutcába torkolló lépések valójában más kiindulási pozíciók megoldásai, ami elvezette egy algoritmushoz, mellyel egy másodperc alatt egymilliárd kockát tudott kipróbálni.

Ez a metódus olyan, mintha egy barátunkat meglátogatnánk egy számunkra ismeretlen városban, megkapjuk tőle az útirányt, hogy mikor forduljunk jobbra vagy balra, viszont azt nem árulta el, hogy mi is valójában a kiindulási pontunk. Ha egy véletlenszerű pontról kiindulva követjük az iránymutatást, igen csekély esélyünk lesz eljutni a célállomáshoz, ha azonban sikerül összeilleszteni a megfelelő kiinduló ponttal, akkor biztosan odaérünk.

A csapat algoritmusa a kissé leegyszerűsített példánkhoz hasonlóan, rendkívüli sebességgel párosítja a mozdulatokat a megfelelő kiinduló ponttal, így egy 19,5 milliárdos sorozatot 20 másodperc alatt meg tudnak oldani, ami döbbenetes sebességnek tűnik, de még így is 35 évig tartana egy hagyományos számítógép számára a teljes feladat megoldása, ezért a csapat egy újabb huszárvágást eszközölt a megoldás érdekében. John Dethridge, a Google egyik mérnöke a számítógépes birodalom szabad számítási kapacitásának felhasználásával néhány hét alatt megoldotta a problémát.

Azt már évek óta tudták, hogy a Rubik-kocka egyes konfigurációi csupán 20 forgatást igényelnek - sok matematikus sejtette is, hogy egyik elrendezésnek sincs szüksége ennél többre, a 15 éves kitartó kutatás azonban megerősítette feltevésüket. "Az ilyen kutatások példázzák, hogyan használható a tiszta matematika a nagy számítási kapacitást igénylő problémák leegyszerűsítésére" - tette hozzá Mark Kambites, a Manchester Egyetem egyik matematikusa, aki nem vett részt Rocki csapatának munkájában.