Een Rubik-kubus oplossen in 26 stappen


De Rubik-kubus is een puzzel die al heel wat mensen plezier of wanhoop heeft gebracht. Maar ook voor wiskundigen is de puzzel interessant. Computerwetenschapper Gene Cooperman en zijn doctoraatsstudent Dan Kunkle van de Northeastern University in Boston hebben bewezen dat je de Rubik-kubus kan oplossen in 26 stappen. Tevoren stond de teller op 27 stappen. Dit maximale aantal stappen dat nodig is om de Rubik-kubus vanuit elke toestand te kunnen oplossen, staat bekend als “God’s Number”. De onderzoekers gebruikten niet alleen slimme algebra, maar ook uitgebreide berekeningen op een parallelle computer.

De Rubik-kubus is sinds zijn uitvinding in de jaren 1970 door de Hongaar Ernő Rubik een excellent proefkonijn om nieuwe technieken op te testen voor het oplossen van combinatorische problemen op grote schaal. Zo zegt Cooperman in het persbericht:

The Rubik’s cube is a testing ground for problems of search and enumeration. Search and enumeration is a large research area encompassing many researchers working in different disciplines — from artificial intelligence to operations. The Rubik’s cube allows researchers from different disciplines to compare their methods on a single, well-known problem.

Elke zijde van de kubus bestaat uit 9 kleinere vierkanten, waarvan je de configuratie kan aanpassen door een zijde van de kubus te roteren over 90, 180 of 270°. 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 Rubik-kubus zijn dus enkel de ‘legale’ permutaties nodig.

Deze legale permutaties vormen een gesloten systeem: een legale permutatie gevolgd door een legale permutatie is ook een legale permutatie. 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. Deze eigenschappen zeggen ons samen dat de permutaties van de Rubik-kubus een groep vormen. Wiskunde-auteur Brian Hayes noemt de Rubik-kubus dan ook een groepentheoriemachine:

It’s well-known that Rubik’s cube isn’t really a toy or a puzzle but rather a group-theory machine in disguise.


Hoe kunnen we nu wiskundig het oplossen van de Rubik-kubus analyseren? Daarvoor visualiseren we de permutatiegroep als een Cayleygraaf: dit is een netwerk waarvan de punten de legale toestanden/permutaties van de kubus zijn. Twee punten in de graaf zijn verbonden door een lijn wanneer je van de ene naar de andere toestand kan gaan door een legale stap, die ook een permutatie is. De opgeloste toestand (de identiteitspermutatie) is één van de punten in de graaf en het probleem om de Rubik-kubus op te lossen komt dan overeen met het vinden van een pad in de graaf van een willekeurig punt naar het punt van de opgeloste toestand.

Hoe weten we nu dat de Rubik-kubus altijd op te lossen is in maximum 26 stappen? In theorie volstaat het om van alle mogelijke paden in de graaf na te gaan of ze niet meer dan 26 stappen bevatten. In de praktijk is dit echter niet te berekenen, want de Cayleygraaf van de groep van legale Rubik-permutaties bestaat uit 43 252 003 274 489 856 000 punten.

Cooperman en Kunkle maakten dus gebruik van de structuur van de groep om het aantal punten in de Cayleygraaf te reduceren. Ze lieten eerst enkel 180° rotaties toe als legale stappen, wat hen een subgroep van de volledige groep van legale stappen opleverde. Ze maakten bovendien gebruik van de symmetrie van de kubus. Hierdoor konden ze de Cayleygraaf reduceren tot 15 752 punten. Na een dag berekeningen op een computer konden ze zo verifiëren dat de kubus vanuit elke begintoestand met deze rotaties in maximum 13 stappen kan opgelost worden.

Cooperman en Kunkle konden verder bewijzen dat de afstand tussen een 90°- of 270°-rotatie en een 180°-rotatie maximum 16 stappen bedraagt, waardoor het totale maximum voor alle legale stappen 13 + 16 = 29 bedraagt. Dit deel van hun berekeningen vereiste 7 Tbyte aan schijfruimte en 8000 processoruren verwerkingstijd op een DataStar-cluster van het San Diego Supercomputer Center (SDSC). Een verdere analyse kon hier nog drie stappen van elimineren. Het bleek namelijk dat hun methode slechts een relatief klein aantal toestanden met meer dan 26 stappen bekwam. Voor deze toestanden vonden ze met brute-force search oplossingen van in totaal 26 stappen.

Meer informatie over hoe de auteurs tot het resultaat kwamen is te vinden in hun artikel Twenty-Six Moves Suffice for Rubik’s Cube. De auteurs vermelden dat ze met dezelfde technieken binnenkort waarschijnlijk het maximum aantal stappen kunnen reduceren tot 25. Specialisten vermoeden dat het maximum ergens rond de 22 moet liggen. UCLA-computerwetenschapper Richard Korf bewees in 1997 dat het gemiddelde aantal benodigde stappen niet meer dan 18 is en hij vermoedt dat het maximaal aantal stappen rond de 20 ligt. Cooperman en Kunkle citeren zo ook David Singmaster en Alexander Frey uit hun boek Handbook of Cubik Math:

No one knows how many moves would be needed for “God’s Algorithm” assuming he always used the fewest moves required to restore the cube. It has been proven that some patterns must exist that require at least seventeen moves to restore but no one knows what those patterns may be. Experienced group theorists have conjectured that the smallest number of moves which would be sufficient to restore any scrambled pattern —that is, the number of moves required for “God’s Algorithm” — is probably in the low twenties.

Meer informatie over de wiskunde van de Rubik-kubus is te vinden in het gratis te downloaden boek Mathematics of the Rubik’s Cube van W.D. Joyner. Wie zelf tips wil leren om de Rubik-kubus op te lossen kan terecht op How to solve the Rubik’s Cube van Wikibooks.

Trackbacks & Pings

  1. Getallen door mijn hoofd at QED on 03 Jul 2007 at 3:58 pm

    [...] rubik’s kubus oplossen: Dat kan in maximaal 26 stappen, weten we sinds vorige maand. [...]

  2. Harige dozen plaatjes at QED on 13 Oct 2007 at 6:05 pm

    [...] De rubik’s kubus oplossen was ook deze maand weer populair. Het kan in 26 stappen. [...]

  3. Maximum 25 stappen voor een Rubik-kubus at QED on 27 Mar 2008 at 10:45 pm

    [...] “God’s Number” voor de Rubik-kubus is weer een stapje omlaag gegaan. Vorig jaar bewezen computerwetenschappers Gene Cooperman en Dan Kunkle nog dat de Rubik-kubus vanuit elke toestand kan opgelost worden in maximum 26 stappen. Ik schreef toen: De auteurs vermelden dat ze met dezelfde technieken binnenkort waarschijnlijk het maximum aantal stappen kunnen reduceren tot 25. [...]

Comments

  1. Koen VervloesemNo Gravatar" onclick="javascript:urchinTracker( wrote:

    Vreemd dat de BBC twee maanden hierna pas met het nieuws naar buiten komt: http://news.bbc.co.uk/2/hi/technology/6949149.stm

    Komkommertijd?

  2. SarahNo Gravatar" onclick="javascript:urchinTracker( wrote:

    Het Happy New Ears festival voor nieuwe muziek organiseert 29/9 een concert ‘Cubing’ van de Canadese muzikanten van Artificiel. Ze gebruiken de Rubik Cube als interface om beeld en geluid aan te sturen.

  3. Koen VervloesemNo Gravatar" onclick="javascript:urchinTracker( wrote:

    Leuk!

Post a Comment

Your email is never published nor shared. Required fields are marked *

*

*