Rubiks terning kan altid løses med maksimalt 20 drejninger
Med hjælp fra Googles computere er samtlige 43 milliarder milliarder kombinationer af Rubiks terning løst med 20 eller færre drejninger.
Læs mere om
Dokumentation
Så er det endeligt bevist, at alle Rubiks terninger kan løses med maksimalt 20 drejninger.
En gruppe Rubik-entusiaster har med hjælp fra Google brugt 35 CPU-år på at bevise dette ved simpelt hen at gennemgå alle godt 43 milliarder milliarder positioner.
Helt præcist findes der (8! × 3^7) × (12! × 2^11)/2 = 43.252.003.274.489.856.000 kombinationer.
Hovedpersonen bag resultatet er Tomas Rokicki – en computeringeniør i Californien, der har etableret sit eget firma Instantis.
Han oplyser, at han har tænkt over problemet gennem 15 år og har arbejdet seriøst med det de seneste fem år.
For to år siden viste han, at man altid med 22 eller færre drejninger kan løse en Rubiks terning. Men siden 1995 har man kendt en kombination, der kræver 20 drejninger – og formodningen har siden da været, at 20 også ville være det maksimale antal drejninger, man har behov for at løse en vilkårlig kombination.
Sådan blev problemet løst
Men hvordan gennemgår man i praksis mere en 43 milliarder milliarder kombinationer? Thomas Rokicki forklarer på sit website, at man først deler det op i 2.217.093.120 sæt hver med 19.508.28.800 positioner.
Så udnytter man symmetrier til at reducere antallet af sæt, der skal løses, til kun 55.882.296.
Næste skridt er at erkende, at man ikke skal finde den optimale løsningsmetode for hver kombination, man skal blot vise, at 20 drejninger er nok til at løse terningen. Det er et meget lettere problem.
Rokicki skrev et program, der kunne løse hvert sæt på 20 sekunder på en god pc (Intel Nahalem, fire kerner, 2,8 GHz). Med en enkelt computer til rådighed ville det således have taget 1,1 milliarder sekunder eller 35 år at løse opgaven.
Men de 55.882.296 sæt blev i stedet fordelt på et stort antal computere hos Google, som løste dem alle i løbet af et par uger. Tomas Rokicki forklarer, at Google ikke ønsker at give detaljer om computersystemet.
Absolut mange, relativt få
Ud over Tomas Rokicki har matematikeren Morley Davidson fra Kent State University, John Dethridge fra Google og matematiklærer Herbert Kociemba fra Darmstadt i Tyskland deltaget i projektet.
Siden 1995 har man som nævnt vidst, at der findes positioner, der kræver 20 drejninger for at blive løst. Det vides stadig ikke præcist, hvor mange sådanne positioner, der findes, men Tomas Rokicki vurderer, at antallet nok er omkring 300 millioner.
Det er mange i absolut antal, men få relativt – de mange kombinationsmuligheder, der findes.
Se videoen af en 17-årig Rubiks-ekspert, der klarer terningen med bind for øjnene - dog ikke på 20 drejninger. For ægte Rubiks-entusiaster er der altid en verdensrekord at gå efter.
