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
Met het boekje " Sleutel tot het geheim van de wonderkubus"

van Don Taylor uitgegeven door H.J.W. Becht te Amsterdam

En een half jaar ploeteren! :(

lukt het mij met enige regelmaat het ding op te lossen! :)
Vandaag een hele fijne Radio3 fail. Dit was vandaag pas "nieuws" voor op de radio.. Ze moesten zich schamen..
Slimme Hongaar, die heeft die kubus zonder computers ontworpen en wist al voor de computer dat het in max 20 stappen atijd moet. Nu zijn die rare rubik-forums en how to solve Rubik's cube video's op youtube zinloos! Het zou toch ook stom zijn als je de tijd van je leven op zo een forum zal verprutsen?
Knap. 20 jaar geleden kreeg ik zo'n ding, in de war gedraaid en nooit meer goed gekomen.
Hoeveel is 43 triljard mogelijke posities eigenlijk?
43.000.000.000.000.000.000.000 dus
91.365.146.187.124.313 is dus relatief weinig :)

(bron=wikipedia)

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

43,000,000,000,000
*edit*
Hangt blijkbaar ook een beetje af van wie het zegt, heh.

[Reactie gewijzigd door cgpirre op 10 augustus 2010 11:56]

43,000,000,000,000
Dat is 43 biljoen
Nee, dat is fout. Op zijn minst is het 43.

Dit is 43 biljoen: 43.000.000.000.000

Dit is de europese methode. De amerikaanse is precies omgekeerd.

[Reactie gewijzigd door Thy King op 10 augustus 2010 12:15]

Als je hier kijkt zie je het werkelijke getal staan (43,252,003,274,489,856,000) en dat is in nederlandse notatie 43 triljoen (en een beetje)
die americanen kennen (meen ik) toch geen -jard? (biljard bv betekent volgens mij toch wat anders ;) ) die tellen toch van million, billion, trillion
Dat zou dan de, voornamelijk engelse, versie van triljoen zijn. Triljard bestaat in die variant niet.

@hAi
Dan moet je er punten tussen zetten in plaats van komma's.

[Reactie gewijzigd door cnieuweboer op 10 augustus 2010 12:11]

Marcelloz zit goed hoor.

43 triljard = 43 * 10^21
43.000.000.000.000.000.000.000

43,000,000,000,000 is 43 biljoen.

Als ik wil mierenneuken is het eigenlijk 43 trillion. Je schrijft het met komma's als separators dus dan gebruik je de Engelse notatie en dus ook de short scale en niet de long scale :P
mja. gewoon geknipt van de nederlandse wikipedia pagina:
http://nl.wikipedia.org/wiki/Triljard
gewoon 1021
de oplossing _/-\o_

Nu snel die Engelse notitie (met 'komma' en zonder '-jard') weer vergeten 8)7
Komt er nog een patch voor uit? Mijn kubus loopt de hele tijd vast.
1 2 3 4 5

Op dit item kan niet meer gereageerd worden.


OnePlus 7 Pro (8GB intern) Nintendo Switch Lite LG OLED C9 Google Pixel 3a XL FIFA 19 Samsung Galaxy S10 Sony PlayStation 5 Games

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