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
is it just me or...
als je al die kansen berekend met de pc en stappen.
is het toch vrij weinig aan meer ?
Er zijn geen kansen in dit probleem. En inderdaad, sommige mensen zien het oplossen van een kubus als een leuk probleem, maar als je weet dat een computer het een paar honderdduizend keer sneller op kan lossen en beter, dan gaat de lol er snel van af.

Dus, ik zou zeggen: ga eens Go spelen of Civilization. In Civilization kun je de computer wel redelijk makkelijk verslaan als deze niet valsspeelt.
Mensen schaken toch ook nog steeds? Het is gewoon een kwestie van "leuk" en je kunt altijd proberen steeds sneller te zijn. Ik geloof dat mijn kubusrecord iets van 75 seconden is.
Het is eigenlijk bizar hoe zo iets ogenschijnlijk simpels zo extreem lastig kan zijn om (al dan niet efficiënt) op te lossen. Binnen een paar stappen is van orde chaos te maken en je hebt een heel stuk intelligentie nodig om er weer orde van te maken.
Dat noemt men entropie of 'maat van wanorde' (en dus chaos). Vergelijk het evengoed met je kamer op orde houden. Als je dat systematisch doet (je laat slechts kleine afwijking van 'perfecte' orde toe), kost het je weinig moeite, maar laat je het allemaal even slingeren, dan heb je er een heleboel werk aan. Hetgeen je beschrijft is eigenlijk niks anders.

[Reactie gewijzigd door mooseman007 op 10 augustus 2010 12:44]

Maar de mate van wanorde van deze kubus is beperkt, er is een maximaal wanordelijke toestand - het punt waarop iedere slag tot een minder wanordelijke staat en dus in de richting van de oplossing leidt. Deze toestand (lees: chaos) gaat dus niet ergens aan vooraf, maar is inherent aan het object. Wellicht is er helemaal geen verschil tussen de 'opgeloste' en meest wanordelijke toestand... (?)
Het oplossen is niet het probleem. Het gaat hier om het aantal stappen dat nodig is om elke kubus op te lossen. Er is nu bewezen dat dit hoogstens 20 is. Dus in 20 stappen kan je elke gedraaide kubus oplossen.
Stickertjes er af halen en opnieuw er op plakken: opgelost zonder 1x te draaien.

Life can be simple...
Je kan de stukjes er ook uithalen en hem dan weer goed in elkaar zetten ;) Gelukkig kan ik hem gewoon oplossen alleen wel in heel wat meer stapjes.
Wat is uberhaupt het nut om eerst alle kleuren door elkaar te draaien en het daarna weer ongedaan te maken...

Als je er zo naar kijkt dan is de kubus van Rubik niets anders dan tijdsverspilling ;)
Alles is relatief. Als iemand een pistool tegen je hoofd houdt en zegt dat je die rubik cube moet oplossen omdat je anders geëxecuteerd wordt zal je niet snel denken dat het een tijdsverspilling is.
Wel als er wordt gezegd dat het moet gebeuren in minder dan 16 stappen :Y) .
@Gopal, hoeft niet. Ze hebben toch ook bewezen dat er 91.365.146.187.124.313 zijn die in exact 15 stappen opgelost kunnen worden? :)
Dan moet je net geluk hebben dat de kubus die je hebt in minder gedaan kan worden. Als je een opgeloste kubus 1 draai geeft kun je hem oplossen in 1 stap.
Maar dat lijkt me enigszins vergelijkbaar met Russisch roulette :)
Zo weet ik ook nog wel een ander spelletje: Waarom schop je een bal weg die je net aan een van de 11 tegenstanders hebt ontfutseld :? En dan nog 90 miljard andere voorbeelden ;)
10, de laatste staat te lummelen tussen een paar palen met een net
Als we toch wiskundig bezig zijn.. Het zijn er (volgens jouw logica de keeper niet meegerekend, hoewel dat natuurlijk ook een volwaardige speler is) 9. 11 - keeper - jezelf = 9!
Het blijven 11 tegenstanders, tussen de palen of niet, met of zonder bal, jezelf meegerekend of niet...
Het gaat om de tegenpartij, daar hoor je zelf niet bij toch? :)
Afhankelijk van wat ze betalen..
Zo ken ik er nog wel een paar.
(Overkoepelend met 'Wat is het nut van geboren worden als je toch weer doodgaat.')

Vermaak kan af en toe best wel wat waard zijn :)
Wat is uberhaupt het nut van het leven als je alles tijdsverspilling vind? Wat voor zin heeft het om te werken als je je geld alleen maar uit kunt geven aan zaken waarmee je nog meer tijd kan verspillen? Als je met alles zo redeneert als jij kun je er beter nu al een eind aan maken.
Voor de rest van de wereld, die graag nog wat lol wil hebben in z'n bestaan en van puzzels houdt, is het geen tijdsverspilling, maar een manier om jezelf te vermaken. Net als iedere andere hobby. Daarom lach ik mensen die videogames "zonde van de tijd" vinden ook altijd hartelijk uit. Tis niet alsof de ene hobby een "betere" hobby is dan de andere. Persoonlijk vind ik de hele avond voor de TV zitten zappen (een van de favoriete bezigheden van de oudere generatie) verspilling van tijd, maar dat is mijn mening, geen feit.
Stickertjes er af halen en opnieuw er op plakken
Dat zijn meestal meer dan 20 stappen.
Hmm.... Oh ja? Eigenlijk is dat ook wel een leuke puzzel.... Hoeveel stickertjes moet je er minimaal vanaf halen. Het zijn er totaal 6*9=54, maar 6 zitten er in ieder geval al goed. Misschien wel meer.

Wiskunde blijft een leuk vak :)
laat maar.

[Reactie gewijzigd door Aham brahmasmi op 10 augustus 2010 15:24]

Ik haalde em altijd uit elkaar :P
inderdaad, dat deed ik ook altijd: dat ging een stuk sneller.

Een beetje geïnspireerd door Alexander de Grote... :P
Kan ik al ergens invoeren hoe mijn kubus eruit ziet zodat ik die 20 stappen kan zien. I like to cheat.
http://www.youtube.com/watch?v=uBqaOs6omrI
8.8 seconde, zijn sommige hersennen en handen dus nog steeds sneller dan googles computers?
Nee. Die computers hebben alle mogelijke uitgansposities doorgerekend. Die persoon die het in 8.8. seconden doet (er zijn nog snellere, google Erik Akkersdijk) die kijkt eerst hoe de uitgangs positie is (op toernooien krijg je 15 seconden als ik het goed heb), maakt een aanvalsplan en gebruikt dan een aantal algoritmes om de kubus op te lossen. Dus dat is 1 oplossing voor 1 uitgangspositie.

[Reactie gewijzigd door Acid_Burn op 10 augustus 2010 12:08]

Hij doet meer dan die 20 stappen in die 8.8 secondes.

Overigens: het wereldrecord staat op naam van een Nederlander.
Ik dacht altijd dat het antwoord 42 stappen was. Maar goed: God's number = 20.
42 stappen voor een kubus van 6x9
20 stappen, da's nog steeds veel!
In 6 stappen lukte mij al 25 jaar geleden:
-stap 1: pak schroevendraaier
-stap 2: wrik de blokjes los
-stap 3: sorteer de blokjes
-stap 4: zet 'm weer in elkaar
-stap 5: berg schroevendraaier op
-stap 6: realiseer dat je valsgespeeld hebt omdat je de skills niet hebt om het eerlijk te doen ;(
stap2: wrik 20 blokjes los... dat zijn al 20 stapjes
stap4: zet 20 blokjes op de juiste plek terug, dat zijn weer 20 stapjes.

Ik heb nog een 5x5x5 kubus staan. Ik ben benieuwd in hoeveel stappen die maximaal op te lossen is :D
Ik ken iemand met een 2x2x2 kubus. Die zijn redelijk simpel. Ik deed m een keer uit m'n kop. Na een paar uur draaien zat ie weer goed. 3x3x3 lukt me nog wel met een tutorial. 4x4x4 ga ik niet eens aan beginnen -.-
En inderdaad, je kunt zo'n kubus sneller oplossen door te draaien dan met een schroevedraaier, mits je weet hoe het werkt ;)
tsja, de een is meer een wiskundige, de ander meer een werktuigbouwkundige...
achter het groene stickertje zit een schroefje!
Nou moet je als speler die oplossing alleen nog even zien
LoL. Volgens mij is de rubiks kubus een van de grootste frustraties ooit!

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 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