Magiske mønstre
30. mai 2016

Hvor mange trekk trengs for å løse Rubiks kube?

(Publisert i Aftenposten mandag 30. mai 2016.)

  • Hvor mange trekk trengs for å løse Rubiks kube?
  • Hvor raskt kan Rubiks kube løses?
  • Her er mer om kubeforskning og kuberekorder!

Hvor mange trekk trengs for å løse Rubiks kube?

Et presist matematisk problem om Rubiks kube, som stod åpent og ubesvart helt frem til 2010, er spørsmålet om hvor mange trekk som trengs for å løse den. Mer spesifikt: Hvor mange trekk er nødvendig for å løse alle mulige konfigurasjoner av kuben?

Hvis du roter til kuben bare littegrann, er det veldig få trekk som trengs. Jo mer du roter den til, jo flere trekk trengs for å løse den. Men nøyaktig hvor går grensen? Hvis du roter den til så mye som mulig, hvor mange trekk trengs da?

For ordens skyld: Dette er ikke et enkelt spørsmål å svare på, for kuben kan være i førtitre milliarder milliarder (43 252 003 274 489 856 000) forskjellige tilstander.

Jakten på øvre og nedre grenser

Matematikere er glad i å snakke om øvre og nedre grenser, og slik er det også med dette spørsmålet. La oss begynne med den øvre grensen for hvor mange trekk som trengs. En øvre grense vil si et antall trekk som er slik at ingen konfigurasjon krever flere trekk enn dette tallet.

På slutten av 70-tallet beviste den britiske matematikeren David Singmaster (1939–) at det er tilstrekkelig med 277 trekk. Det vil si at 277 trekk er en øvre grense: Ved hjelp av 277 trekk, kan enhver kube løses.

Men siden 70-tallet har matematikere stadig klart å finne lavere tall. På begynnelsen av 80-tallet fant Morwen Thistlethwaite ut at 52 trekk var tilstrekkelig. Det var lenge usikkert om den øvre grensen kunne være lavere.

På motsatt side jaktet man på nedre grenser for hvor mange trekk som var nødvendig. Man hadde lenge kjent til spesielle kubekonfigurasjoner som krevde atten trekk, men det var uklart om tallet kunne være høyere. Fantes det konfigurasjoner som var enda vanskeligere å løse?

På midten av 90-tallet fant man en spesiell konfigurasjon, superflip, som faktisk krevde tjue trekk. Dette var den nye nedre grensen, og det skulle ta ytterligere femten år før man fant ut hva den øvre grensen var.

I 2010 fant man svaret: Tjue var også den øvre grensen! Det betyr at det både er nødvendig og tilstrekkelig med tjue trekk for å løse enhver konfigurasjon av Rubiks kube. Det er nødvendig på grunn av konfigurasjoner som superflip, og det tilstrekkelig fordi det aldri trengs mer enn tjue trekk for å løse enhver kube.

Det var den amerikanske programmereren Tomas Rokicki fra Palo Alto i California som stod for gjennombruddet, med god hjelp fra Google, som donerte ledig regnekraft fra sine mange datamaskiner. Dette tallet har senere blitt referert til som Guds tall, og hele historien kan leses på nettsiden cube20.org.

En mer finkornet analyse

Historien om øvre og nedre grenser stopper egentlig ikke med tallet tjue. Hele historien over forutsetter nemlig at ett trekk består av å vri én av sidene helt fritt, det vil si 90 grader i en retning eller 180 grader.

Hvis vi begrenser oss til trekk med nøyaktig 90 grader, får vi en annen analyse. Matematikere liker å sette navn på ting, og dette kalles ofte for kvartmetrikk i stedet for halvmetrikk.

Dette gir et mye vanskeligere problem, fordi en vridning på 180 grader, nå teller som to trekk i stedet for ett. Historien med øvre og nedre grenser utviklet seg på samme måte, og i august 2014 ble problemet endelig løst.

Det var igjen Tomas Rokicki og hans samarbeidspartnere som fant svaret: Med kvartmetrikk er svaret 26.

Hvor raskt kan Rubiks kube løses?

Det blir stadig satt nye rekorder i å løse kuben raskest mulig. Hvis vi ser på nettsidene til World Cube Association, en flott ressurs for konkurranser og registrerte kuberekorder, ser vi hvordan rekordene for den vanlige 3x3x3-kuben har utviklet seg fra 2004 til 2016:

I grafen over er alle de offisielle rekordene, men også alle tiende- og hundredeplassene, tegnet inn. Det er tydelig at vi nærmer oss en grense for hvor raskt kuben kan løses. Den nåværende verdensrekorden for å løse den vanlige 3x3x3-kuben ble satt at den amerikanske 14-åringen Lucas Etter i november 2015 og er nå på 4,90 sekunder.

Norske rekorder

Her i Norge er det Jonathan Hamstad og Morten Arborg som kniver om Norgesrekorden. Siden oktober 2015 er det førstnevnte som har rekorden på 6,33 sekunder. For å se alle rekordene, anbefaler jeg nettsidene til World Cube Association, og på nettsidene til Norges kubeforbund finner du informasjon om kubing i Norge.

Roboter er raskere enn mennesker

Det er kanskje ingen overraskelse av roboter løser Rubiks kube raskere enn oss mennesker. Men akkurat hvor raskt klarer en robot å løse kuben?

I januar 2016 ble det satt en ny verdensrekord i robotkubing. Da klarte en robot å både se, analysere og fullstendig løse kuben på ikke mer enn 0,887 sekunder.

Et univers av kubevarianter

Til slutt må det nevnes at det er svært mange varianter både når det gjelder hvordan man løser kuben og hvordan kubeliknende vripuslespill er konstruert. I videoen over kan du se litt av dette fascinerende universet av varianter.

av Roger Antonsen