Je leest:

Rubikkubus in slechts 26 stappen

Rubikkubus in slechts 26 stappen

(oorspronkelijke titel van 6 juni 2007; update 17 augustus 2010: 20 stappen)

Auteurs: en | 17 augustus 2010

Het aantal draaibewegingen dat nodig is om een Rubikkubus op te lossen, bedraagt nooit meer dan 26. Dat bewezen twee informatici uit Boston. Men vermoedt dat het nog zuiniger kan, maar dat heeft nog niemand ooit kunnen bewijzen.

Update 17 augustus 2010: God’s number is 20

Een in de war gedraaide Rubikkubus kan altijd in twintig draaibewegingen of minder worden opgelost. Lager wordt het niet: sommige standen van de kubus hebben echt twintig keer draaien nodig. Dat hebben wetenschappers van de universiteiten van het Californische Palo Alto, het Britse Kent State en het Duitse Darmstadt bewezen. Ze maakten gebruik van door Google beschikbare computerruimte, schrijven ze op Cube20.org. Ze noemen twintig God’s number, omdat het het maximale aantal keer draaien is dat een alwetende nodig zou hebben voor de puzzel.

In de jaren tachtig van de vorige eeuw was de Rubikkubus een grote hit. Jong en oud draaiden zich suf aan deze kubuspuzzel, die negen kleurrijke vakjes op elke zijde bevat. De kubus is opgelost als alle kanten eenzelfde kleur hebben.

Wiskundigen hadden met deze puzzel stof tot nadenken: hoe vaak moet je minimaal draaien om de kubus opgelost te krijgen, en hoe vaak maximaal? In de beginjaren tachtig bedroeg de best bekende ondergrens 17 (dat wil zeggen: men wist zeker dat er toestanden bestaan waar vanuit niet minder dan 17 zetten nodig zijn om de puzzel op te lossen). De best bekende bovengrens was toen 52 (dat wil zeggen: vanuit elke toestand kan de kubus met maximaal 52 draaibewegingen worden opgelost). Deze grenzen zijn later verbeterd. In 1995 was de best bekende ondergrens 20. Vorig jaar werd de bovengrens verbeterd tot 27.

De informatici Gene Cooperman en zijn doctoraatsstudent Dan Kunkle van de Northeastern University in Boston hebben de bovengrens nu teruggebracht tot 26.

De Rubikkubus kan in 43.252.003.274.489.856.000 toestanden worden gedraaid. Vanuit elke toestand kan de kubus met 26 draaibewegingen of minder worden opgelost.

Groepentheorie

De Rubikkubus kan in meer dan 43 triljoen (43 × 1018) toestanden worden gedraaid. Door de ogen van een wiskundige bekeken, is elke toestand van de kubus een permutatie van de vierkanten: de locatie van elk vierkant in de ‘opgeloste toestand’ wordt door de permutatie afgebeeld op een nieuwe locatie van de kubus in dooreengegooide toestand. Sommige permutaties zijn niet mogelijk: zo kan een centraal vierkant van een zijde niet verschoven worden. Voor een wiskundige analyse van het oplossen van de Rubikkubus zijn dus enkel de ‘legale’ permutaties nodig.

Deze legale permutaties vormen een gesloten systeem. Dat betekent dat een legale permutatie gevolgd door een legale permutatie óók een legale permutatie is. De inverse van een legale permutatie is ook een legale permutatie: draai de kubus gewoon terug naar de vorige toestand. Bovendien is niets doen met de kubus ook een legale permutatie: de identiteitspermutatie. Een laatste eigenschap van deze permutaties is dat ze associatief zijn. Al deze eigenschappen samen zeggen dat de permutaties van de Rubikkubus een groep vormen.

Hulp van de computer

Hoe weten we nu dat de Rubikkubus altijd op te lossen is in maximaal 26 stappen? In theorie volstaat het om van alle mogelijke toestanden na te gaan of ze niet meer dan 26 draaibewegingen nodig hebben. In de praktijk lukt dit echter niet, want 43 triljoen toestanden zijn er, óók voor een computer, veel te veel.

Cooperman en Kunkle ontwikkelden een oplosmethode voor de Rubikkubus, waarbij ze gebruik maakten van slimme algebra en computerberekeningen die zeven terabytes (1 terabyte = 1000 gigabytes) aan schijfruimte en 8000 processoruren verwerkingstijd op een DataStar-cluster van het San Diego Supercomputer Center vereisten. Het bleek dat met hun methode relatief weinig toestanden meer dan 26 stappen behoefden om tot de ‘opgeloste toestand’ te komen. Voor deze toestanden vonden ze met brute-force search oplossingen van maximaal 26 stappen.

Verder onderzoek

Richard Korf van de University of California, Los Angeles, bewees in 1997 dat het gemiddelde aantal benodigde stappen om de Rubikkubus op te lossen, niet meer dan 18 is en hij vermoedt dat het maximale aantal benodigde stappen 20 is. Dat zou betekenen dat de best bekende ondergrens niet te verbeteren valt. Deze claim kon hij echter niet bewijzen. Rubikkubus-onderzoekers kunnen dus, ook na het nieuwe resultaat van Cooperman en Kunkle, nog niet op hun lauweren gaan rusten. Dat kan pas als de beste ondergrens gelijk is aan de beste bovengrens.

Wereldkampioenschap

De populariteit van de Rubikkubus is de laatste jaren weer toegenomen. Sinds 2003 worden er zelfs wereldkampioenschappen gehouden. Het officiële record staat sinds 7 januari 2007 op naam van de Koreaan Yu Jeong-Min. Hij behaalde een gemiddelde tijd van 11,76 seconden bij vijf pogingen.

VoetRubik

Het had een sketch van Van Kooten en De Bie kunnen zijn: ‘het wereldkampioenschap Foot Rubik Cube’. Los de kubus zo snel mogelijk op met de voeten. Het huidige record (maart 2006) staat op naam van de Fin Anssi Vanhala. Hij had 1 minuut en 18 seconden nodig. Andere varianten, zoals ‘kubus geblinddoekt oplossen’, vind je bijvoorbeeld op Wikipedia, zie de links hieronder.

Van de Rubikkubus bestaan diverse variaties. De nieuwste variant: de Irregular IQ Cube. Hoe kun je van een onregelmatig veelvlak een kubus maken?

Update 31 maart 2008: het kan in 25 stappen!

God’s Number voor de Rubikkubus is weer een stapje omlaag gegaan. Vorig jaar bewezen de informatici Gene Cooperman en Dan Kunkle nog dat de Rubikkubus vanuit elke toestand kan worden opgelost in maximaal 26 stappen, zie het onderstaande Kennislinkartikel van 6 juni 2007. Zij vermeldden toen dat ze binnen afzienbare tijd met dezelfde technieken die bovengrens waarschijnlijk konden aanscherpen tot 25. Tomas Rokicki heeft die reductie nu uitgevoerd. Zijn artikel Twenty-Five Moves Suffice for Rubik’s Cube staat op de website arXiv.org.

Update 4 mei 2008: het kan zelfs in 23 stappen!

Nog geen twee maanden geleden bewees Tomas Rokicki dat de Rubikkubus vanuit elke toestand kan worden opgelost in maximaal 25 stappen. Hij verwachtte toen dat deze bovengrens met zijn methode snel kan worden verscherpt naar 24. Nu is het zover, en zelfs beter dan verwacht: Rokicki heeft het aantal stappen gereduceerd tot 23. Dezelfde technieken werden gebruikt als in het bewijs van vorige maand, enkel met meer computerkracht.

Update 14 maart 2010: het kan zelfs in 22 stappen!

Bijna twee jaar hoorden we niets van Tomas Rokicki over zijn zoektocht naar het grootste aantal draaiingen dat zeker nodig is om een Rubikkubus vanuit een willekeurige toestand op te lossen. Maar in het maartnummer van The Mathematical Intelligencer staat een artikel waarin hij de bovengrens verscherpt van 23 tot 22. De eerste pagina van zijn artikel Twenty-two Moves Suffice for Rubik’s Cube is gratis te zien. Wiskundigen vermoeden dat het maximale aantal stappen rond de 20 ligt. Het zou wel eens kunnen dat Rokicki binnenkort de kleinste bovengrens vindt van het aantal stappen dat nodig is om een willekeurige toestand van de Rubikkubus op te kunnen lossen.

Meer informatie:

Dit artikel is een publicatie van NEMO Kennislink.
© NEMO Kennislink, sommige rechten voorbehouden
Dit artikel publiceerde NEMO Kennislink op 17 augustus 2010

Discussieer mee

0

Vragen, opmerkingen of bijdragen over dit artikel of het onderwerp? Neem deel aan de discussie.

NEMO Kennislink nieuwsbrief
Ontvang elke week onze nieuwsbrief met het laatste nieuws uit de wetenschap.