Cookies op Tweakers

Tweakers maakt gebruik van cookies, onder andere om de website te analyseren, het gebruiksgemak te vergroten en advertenties te tonen. Door gebruik te maken van deze website, of door op 'Ga verder' te klikken, geef je toestemming voor het gebruik van cookies. Wil je meer informatie over cookies en hoe ze worden gebruikt, bekijk dan ons cookiebeleid.

Meer informatie

Kubus van Rubik oplosbaar in 20 stappen

Een groep onderzoekers heeft vastgesteld dat de door de Hongaar Rubik ontworpen puzzelkubus altijd in maximaal twintig stappen naar zijn originele staat kan worden gebracht. Voor het bewijs was het equivalent van 35 jaar computerrekentijd nodig.

De onderzoekers van de universiteiten Kent State, Darmstadt en Palo Alto schreven een programma dat een subset van posities in twintig seconden kon oplossen. Die subsets bestonden ieder weer uit ruim negentien miljard posities. De ruim 43 triljard mogelijke posities van Rubiks kubus zijn onder te verdelen in ruim 2,2 miljard subsets, maar door overlap kan dit aantal worden gereduceerd tot een kleine 56 miljoen subsets.

Op de systemen van Google, dat de benodigde rekencapaciteit aan de onderzoekers doneerde, bleek het algoritme nooit meer dan twintig stappen nodig te hebben om de puzzel op te lossen, ongeacht de uitgangspositie. Het minimale benodigde aantal stappen om de puzzel op te lossen is gestaag omlaag gebracht. In 1981 werd bewezen dat elke positie in 52 stappen kon worden opgelost; in 2008 werd een algoritme van maximaal 22 stappen gepresenteerd. Door alle mogelijke posities door te rekenen, kunnen de wiskundigen nu met zekerheid zeggen dat elke kubus in maximaal twintig stappen kan worden opgelost.

Het is niet bekend hoeveel uitgangsposities die volle twintig stappen vergen, maar vooralsnog vonden de onderzoekers er ongeveer twaalf miljoen. Ze denken dat er in totaal zo'n 300 miljoen zijn. Wel berekenden ze dat er precies 91.365.146.187.124.313 uitgangsposities zijn die in vijftien stappen zijn op te lossen. Tot dusver waren alleen de oplossingen tot en met veertien stappen bekend. Alle uitgangsposities die zestien tot twintig stappen vergen, moeten nog berekend worden.

Door Willem de Moor

Redacteur componenten

10-08-2010 • 11:47

147 Linkedin Google+

Submitter: Henk007

Lees meer

Reacties (147)

Wijzig sortering
ik heb eigenlijk nog nooit geteld hoeveel stappen ik er over doe maar ik weet da het rond de 3a 4 minuten duurt bij mij naargelang de kwaliteit van de kubus
ik mis de robot arm die het ook ff laat zien
Hmmm... lijkt me veel interessanter een reeks te ontwikkelen waarmee je alle uitgangsposities kunt oplossen - waarbij bij de ene de reeks verder doorloopt dan de ander uiteraard...
En dus de ene reeks ook overloopt in de ander? Je zou dan een reeks krijgen die waarschijnlijk minimaal zoveel stappen heeft als alle mogelijke combinaties.
Ik heb deze ooit uit mijn hoofd kunnen oplossen, maar dat is al weer even geleden ;)
Hmm, 35 jaar rekentijd, gelukkig kunnen mensen het sneller ;)
http://www.youtube.com/watch?v=VzGjbjUPVUo
Hmm, 35 jaar rekentijd, gelukkig kunnen mensen het sneller ;)
Alle oplossingen ? Begin maar.
uit elkaar halen en dan weer goed in elkaar zetten is ook slim.
noem het maar lateraal denken.
Voor het bewijs was het equivalent van 35 jaar computerrekentijd nodig.
Lekker vaag... equivalent van 35 jaar computerrekentijd... gebaseerd op wat voor een computer dan? Een 286 of een leuke i7?
Als je meer wilt weten moet je de bron lezen.
Google does not release information on their computer systems, but it would take a good desktop PC (Intel Nehalem, four-core, 2.8GHz) 1.1 billion seconds, or about 35 CPU years, to perform this calculation.

stond op hun website :)
Leuk om je vrienden te imponeren ermee, zeker als je het ook nog met 1 hand kan.
Nog leuker als je het zonder handen kunt, met een zelfgebouwde robot (zie video die himlims_ hierboven heeft gepost).
Ik heb ook een keer een speciale rubiks cube gekocht met meerdere delen :p Nog nooit opgelost.. Wat zijn die dingen moeilijk.


@ marktm

Die is goed :p. Weet niet of ik het knap of eng moet vinden.

[Reactie gewijzigd door Thomas op 10 augustus 2010 12:31]

Binnen een paar stappen is van orde chaos te maken...
Dat is juist het idee achter een puzzel. :)
Voor de ene persoon is na 2 keer draaien de orde weg en voor de ander pas na 8 keer draaien. Alles hangt af van het ruimtelijk inzicht van de persoon.

Op het moment dat je alle mogelijke uitgangsposities hebt kun je de oplossingen opstellen.
Net zoals met schaak- en damcomputers.

Ze kunnen deze systemen beter voor "real-life" (maatschappelijke) puzzels gebruiken , of draaf ik nu weer door .... 8)7

Op dit item kan niet meer gereageerd worden.


OnePlus 7 Pro (8GB intern) Microsoft Xbox One S All-Digital Edition LG OLED C9 Google Pixel 3a XL FIFA 19 Samsung Galaxy S10 Sony PlayStation 5 Smartphones

Tweakers vormt samen met Tweakers Elect, Hardware.Info, Autotrack, Nationale Vacaturebank, Intermediair en Independer de Persgroep Online Services B.V.
Alle rechten voorbehouden © 1998 - 2019 Hosting door True