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 haat dat kubus, ik had hem ooit gekregen 1x geprobeerd en dus nooit meer.
Ik zij alleen dat ik hem had opgelost (ik had stickers verplaatst O-)

[Reactie gewijzigd door kevinkrs op 10 augustus 2010 12:41]

In de appstore is hier een heel handig programmaatje voor: cubecheater.

Vul je kubus in als uitgangspositie, volg de stappen et voila!
versta er ook geen bal van van zo'n dingen :p
De makkelijke oplossing? een haarföhn en een mesje dan is het zo gepiept.
Vroeger (20 jaar geleden) veel met die kubus gespeeld en mijn zusje goed in de maling genomen door 4 kleur stickers om te wisselen, sindsdien was die kubus nooit meer oplosbaar ! ;)
:p ik heb ooit zown ding gekregen, een oom van mij draajde hem zo terug in mekaar,!
maar ook wweer uitmekaar :P dat vond ik niet leuk heb 1 maal 4 vlakken ze zelfde kleur gehad en 2 andere geel en wit, in het midden gehad:o dat is mijn verste oplossing!! maar ook stiekum een klein jaar over gedaan,

al met al vind ik het gewoon een DUIVELS ding, want het vreet Energie, Tijd, en gewoon je HUmeur!
En toen gebruikte je google ;)
Of natuurlijk Yahoo!
Echt respect voor deze wetenschappers en mooi om te horen dat google hier ook aan wilde mee werken. Ik zelf kan zon ding net oplossen in een minuut en ben onder andere ook bezig met een eigen rubic cube solver die ik in C++ script.

[Reactie gewijzigd door Lupo1989 op 11 augustus 2010 13:25]

stel elke verdraaide kubus is in maximaal 20 stappen op te lossen. waarom zien mensen die oplossing danniet?

in dat filmpje in twee delen waar de oplossing wordt gevonden door een aantal algoritmes een aantal keer achter elkaar te doen, kom je op veel stappen. de hele kunst is het combineren van al die stappen, en het wegstrepen van de stappen die elkaar opheffen.
zoals je ziet zijn de gebruikte algorites er steeds op gebaseerd dat het deel dat je al hebt opgelost niet weer in de war te schoppen. misschien zijn e simpeler algoritmes. en misschien zijn er algoritmes die de oplossing in andere deelstappen onderverdeelt.
nu wordt er begonnen met een zijde. eerst een kruis, dan de hoekjes.

er gaat daarna steeds tijd een zeten zitten in het ongeschonden houden van de reeds opgeloste zijden.
stel dat je die buiten beschouwing kunt laten, of " onthouden" ( net als bij een staartdeling) vervolgens kijk je welke zetten elkaar zouden opheffen, en dan scheelt dat zo de helft aan zetten.

misschien is het ook een snellere oplossing als je bijvoorbeeld niet 1 vlak eerst oplost, maar dat je de blokjes " klaar zet" en dat ze vervolgens bij een volgend algoritme automatisch in een oordelige positie blijven om daarna op de goeie plek te worden gedraaid, als dat nog niet automatisch is gebeurd. dat moet mogelijk zijn, en dat zal ook zijn wat er gebeurt wanneer een computer de " magische 20 of minder zetten" heeft bedacht.

het probleem is dat een mens niet voor alle " losse" blokjes ( slechts20) steentjes het patroon herkent.
uiteindelijk heb je maar twee soorten blokjes, 8 hoekblokjes en 12 zijde-blokjes. je hebt dus 20 problemen die je op moet lossen, en voor elk hoek blokje hebt je "slechts" 7 foute posities, waarbij het blokje zelf ook nog eens 3 standen kan hebben. echter in elk geval kun je met 3 draaien het blokje in het goeie vlak op de goeie plek krijgen, en kun ej dat met verschillende algoritmes doen, die vervolgens een " reeks" andere verandering met zich mee brengen, die de puzzel ook in een meer of mindere staat van oplossing brengen.

mensen die door het bestuderen van de kubus, en dus wel patronen herkennen, kunnen zo in veel minder stappen de kubus oplossen..

ik heb zelf wel eens met rubicks clocks gespeeld, maar dat si een relatief simpel en straight forward probleempje vergeleken met de kubus, maar de aanpak om in zo weinig mogelijk zetten en eenvoudig de oplossing te vinden is daar al mogelijk zonder van et voren patronen te moeten herkennen. als je die in twee kanten oplost, en je kiest de gunstigste dan hoef je alleen daarvan maar het patroon te herkennen. en dat zijn dan maar 8 klokjes die dezelfde kant op moeten zijzen als die ene andere. 8 versus 20 qua patroonherkennins is al een stuk makkelijker, maar ook de mogelijkheden zijn dus giganisch veel kleiner

de kubus hadden we heel vroeger ook, maar die is inderdaad door schroeven en wrikken toch wel aan zijn einde gekomen, voordat ik in staat was die kubus op te lossen.

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