Google helpt raadsel Rubiks cube op te lossen

Vanaf het begin is er gespeculeerd over de vraag, of er een maximum was aan het aantal stappen dat nodig was om vanuit een willekeurige beginstand alle vlakjes van een kleur aan hun eigen kant te krijgen. Dat werd het getal van God genoemd: alleen het opperwezen zou weten hoeveel handelingen daarvoor nodig waren. Het aantal uitgangsposities is namelijk enorm. De 26 basiskubusjes kunnen in 43 miljard miljard verschillende posities gedraaid worden.

Door de jaren heen hebben wetenschappers gerekend aan getal van God. In 1981 lag dat nog op 52. In de jaren daarna werd dat stapsgewijs teruggebracht tot 22 – in 2008. Maar daarmee was nog geen zekerheid over het maximum.

Wetenschappers van de Kent State University in Engeland hebben het raadsel nu opgelost door alle uitgangsposities door te rekenen. In eerste instantie verdeelden ze het aantal mogelijk posities in 2,2 miljard groepen van 20 miljard uitgangsposities. Om dat tot een handzamer dataset om te vormen, werden daaruit eerst de symmetrische configuraties van de kubus geëlimineerd. Dat reduceerde het aantal door te rekenen posities tot 56 miljoen groepen van 20 miljard posities.

Doorrekenen of die altijd in 20 handelingen of meer goed te draaien zijn, zou nog steeds een klus voor een supercomputer zijn. Op een desktop-pc met vierkernige Nehalem-processor zou het 35 jaar geduurd hebben om dat allemaal door te rekenen, aldus de onderzoekers. Een aanbod van Google om het probleem in zijn rekencentra door te rekenen maakte het onnodig om dure supercomputertijd te huren. Google had voor het doorrekenen enkele weken nodig; welke configuratie daarvoor werd gebruikt, is niet bekend gemaakt.

Daarbij is geen enkele positie gevonden die meer dan 20 draaiingen vergt, waarmee het bewijs is geleverd – zij het met brute kracht. Een beschrijving van de oplossing is online gezet.