Je leest:

Zó moeilijk is de Rubikkubus niet!

Zó moeilijk is de Rubikkubus niet!

Complexiteit van draaipuzzel is laag

Auteur: | 10 augustus 2011

Informatici van het Massachusetts Institute of Technology hebben een methode gevonden om willekeurig grote Rubikkubussen op te lossen. Ze vonden dat het maximale aantal stappen om een n x n x n kubus op te lossen, van de orde n kwadraat gedeeld door log n is.

De standaard Rubikkubus heeft het formaat 3 × 3 × 3

De Rubikkubus – grote hit uit de jaren tachtig van de vorige eeuw – heeft ook de wiskundige gemeenschap aardig beziggehouden. De standaard Rubikkubus heeft het formaat 3 × 3 × 3: deze kubus heeft negen kleurrijke vakjes op elke zijde. De kubus is opgelost als alle kanten eenzelfde kleur hebben. Vorig jaar werd bewezen dat het maximale aantal stappen nodig om een Rubikkubus op te lossen (‘Gods getal’) gelijk is aan 20.

Gods getal voor grotere kubussen

Deze zomer hebben Erik Demaine – informaticus aan het Massachusetts Institute of Technology – en een aantal collega’s een algoritme gepresenteerd dat gebruikt kan worden voor het oplossen van willekeurig grote Rubikkubussen. Daarmee kunnen ze berekenen van welke orde van grootte Gods getal is voor een n x n x n kubus. Zij vonden dat het aantal stappen dat nodig is voor het oplossen van een n x n x n kubus voor voldoende grote waarden van n, proportioneel is met n2 / log n. Dat betekent dat je twee constantes a en b, en een derde getal N kunt vinden, zodanig dat voor elke n > N geldt dat Gods getal voor een n x n x n kubus tussen a · n2 / log n en b · n2 / log n ligt.

Een grotere Rubikkubus: 5 × 5 × 5.

Lage complexiteit

Deze onder- en bovengrens van Gods getal lijken behoorlijk grof. Toch geeft het resultaat een heel goed beeld van hoeveel een Rubikkubus moeilijker wordt om op te lossen naarmate het aantal vierkantjes van de kubus toeneemt. En dat blijkt heel erg mee te vallen.

In de complexiteitstheorie spreekt men van een moeilijk probleem (in vakjargon NP-probleem) indien het aantal stappen dat nodig is om tot de oplossing te komen, een exponentiële functie is, bijvoorbeeld 2n. En dat is hier niet het geval. Bekijk onderstaande figuur maar eens. Je ziet dat de grafiek van de functie 2n (exponentieel) heel hard stijgt, de grafiek van n2 (polyominaal, dus niet exponentieel) minder en de grafiek van n2 / log n nog minder. Het plaatje maakt duidelijk dat de Rubikkubus niet heel veel moeilijker wordt naarmate het aantal vakjes toeneemt. Of, zoals wiskundigen het graag zeggen: de Rubikkubus heeft een lage complexiteit.

Effectieve methode

Om de waarde n2 / log n te vinden, heeft Demaine een truc bestudeerd die veel kubusoplossers toepassen: het verplaatsen van een enkel vakje naar de juiste positie terwijl alle andere vakjes zo veel mogelijk op hun plaats blijven. Het was al bekend dat het aantal stappen dat nodig is om een kubus met deze techniek op de lossen proportioneel is met n2; dat volgt uit het feit dat een n x n x n kubus 6n2 vakjes heeft.

Demaine en zijn collega’s hebben de methode effectiever gemaakt door zich niet op een enkel vakje te concentreren, maar door groepen vakjes die dezelfde richting op moeten tegelijk te verplaatsen. Daarmee konden ze n2 reduceren met een factor 1 / log n.

Open vragen

Er zijn nog altijd veel vragen omtrent de Rubikkubus onbeantwoord. De eerste vraag waar Demaine zich mee bezig wil houden, is om de benadering n2 / log n precies te maken voor iedere n. Ook zijn ‘Gods getallen’ voor alle Rubikkubussen groter dan 3 × 3 × 3 nog onbekend.

Zie ook:

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

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.