'Rubik-kubus altijd in 26 stappen op te lossen'

Onderzoekers van een universiteit in Boston hebben met de hulp van een supercomputer aangetoond dat een Rubik-kubus altijd in slechts zesentwintig stappen opgelost kan worden.

Omdat een Rubik-kubus miljarden verschillende toestanden kent, zou het zelfs voor een supercomputer ondoenbaar zijn om alle mogelijke combinaties helemaal uit te rekenen. Daniel Kunkle en Gene Cooperman, twee studenten van de universiteit, zijn daarom uitgegaan van 15.000 toestanden waarvan bekend is dat ze in een paar stappen opgelost kunnen worden. Door vervolgens van elke mogelijke toestand te berekenen hoe een van deze 15.000 varianten verkregen kan worden, kon heel wat tijd bespaard worden. Op deze manier becijferden de 'kubisten' dat heel veel Kubik-configuraties in zesentwintig stappen tot een oplossing gebracht konden worden.

Door zich vervolgens te concentreren op de resterende situaties, waarvoor niet meer dan negenentwintig acties nodig waren, slaagde men erin om ook deze lastige gevallen met slechts zesentwintig handelingen op te lossen. Wetenschappers zijn al sinds jaar en dag op zoek naar het zogenaamde 'God's Number', het minimale aantal stappen dat nodig is om een willekeurige Rubik-kubus op te lossen. Theoretici hebben reeds becijferd dat dit getal zich ergens tussen de twintig en vijfentwintig moet bevinden, hoewel dit nog niet wetenschappelijk aangetoond is.

Reacties (121)

[Anoniem: 33810]

Het enige dat mij verbaasd...we kunnen met supercomputers wel de natuur nabootsen en voorspellingen geven over o.a. het weer...maar iets "simpels" als het oplossen van een 6x3x3 kubusjes kubus lukt niet?

Maar wel slim gevonden om dan uit te gaan van bekende situaties, en hier naar toe te rekenen. Dat is nu effectief omgaan met "beperkte" rekenkracht.

[Reactie gewijzigd door Anoniem: 33810 op 23 juli 2024 12:51]

[xaveriussmet]

Je kan uit elke toestand 2*(3+3+3)=18 verschillende verschuivingen toepassen. (3 zijden, met elk 3 rijen, en je kan ze telkens naar links of naar rechts draaien)

18 mogelijkheden om van een toestand naar een andere te gaan... Als je er dan 26 stappen over doet, heb je in totaal 18^26 = 4.33595866 * 10^32 keuzes gehad... en jij vraagt je af waarom dat zo lang duurt?

Een klimaatmodel is volgens mij dan wel nog eenvoudiger hoor.. daar heb je 'n aantal factoren, en die geven je gewoon 1 uitkomst.

[long]

Klimaatmodellen heten niet voor niets zo, het zijn modellen. Die zijn zo vereenvoudigd dat er iets overblijft wat wel binnen een redelijke tijd op te lossen is (zoals hier ook een slimmigheidje is gebruikt voor de kubus, omdat het anders te lang duurt).
Het klimaat is natuurlijk niet te vergelijken met een wiskundig probleem. Bij het klimaat zijn zoveel factoren die verschillende invloeden op elkaar uitoefenen dat het al heel snel veel ingewikkelder wordt dan deze kubus.

Overigens komt er ook niet zomaar 1 uitkomst uit, anders zouden er bij de neerslagverwachting niet van die dikke marges getoond worden op langere termijn. Het weer/klimaat is chaotisch, waardoor kleine veranderingen hele grote verschillen in uitkomst kunnen creëren.

[HugoBoss1985]

Als je over het over natuurverschijnselen hebt, dan is het inderdaad nabootsen of voorspellen.
Hier gaat het over iets wat tastbaar is...

[Jejking]

Ja, maar wat denk jij dan? Er zijn slechts een aantal bepaalde instructies en formules beschikbaar, en daar moet hij het mee doen. Dan wordt het al snel lastig hoor

[blorf]

Zo'n ding heeft 54 vakken die 7 kleuren kunnen hebben dus het aantal mogelijke combinaties is 54^7 = 1.338.925.209.984.
Valt mee toch? Of zie ik nog iets over het hoofd?

edit: 6 dus

[Reactie gewijzigd door blorf op 23 juli 2024 12:51]

[Darude1234]

Volgens wikipedia zijn er: 43.252.003.274.489.856.000 (43,25 triljoen) combinaties mogelijk.

Met 8 hoekblokjes en 12 randblokjes zijn 8!·12!·38·212 verschillende posities mogelijk. Het is echter niet mogelijk elke situatie door draaiingen te bereiken:

* een hoekblokje kan niet onafhankelijk gedraaid worden;
* een randblokje kan niet onafhankelijk gedraaid worden;
* twee blokjes kunnen niet onafhankelijk van plaats wisselen.

Deze drie soorten manipulaties kunnen alleen in paren gebeuren, tenzij de kubus gedemonteerd wordt. Daarom moet bovenstaande waarde nog door 12 gedeeld worden. Dit levert 43.252.003.274.489.856.000 verschillende posities. Slechts één daarvan is de goede oplossing.

[Anoniem: 93798]

54^6 24.794.911.296 ... dit klopt niet ...

Het aantal combinaties is

Deze drie soorten manipulaties kunnen alleen in paren gebeuren, tenzij de kubus gedemonteerd wordt. Daarom moet bovenstaande waarde nog door 12 gedeeld worden. Dit levert 43.252.003.274.489.856.000 verschillende posities. Slechts één daarvan is de goede oplossing.

(bron: http://nl.wikipedia.org/wiki/Rubiks_kubus)

de kleuren zijn wit - geel - oranje - rood - groen - blauw

wat betreft 1 zijde oplossen is niet zo moeilijk ... echter wil je van nature uit 1 zijde oplossen en dan de rest maar zo werkt het helemaal niet

[Reactie gewijzigd door Anoniem: 93798 op 23 juli 2024 12:51]

[Twixie]

Ik dacht al dat 'miljarden' (cfr artikel) nogal een serieus understatement was. Indien het slechts enkele miljarden zou geweest zijn, zou een supercomputer er zeker wel mee overweg kunnen.
Lijkt alsof de auteur geen goed besef heeft van hoe weinig een miljard wel is als het om computing gaat.

[iAR]

Is het niet zes kleuren? Elke kant van een vierkant 1?

Ik heb dat ding nooit echt aangeraakt, ik werd er sjaggo van. Ik had volgens mij 26.000 stappen nodig om één zijde de zelfde kleur te laten hebben.

[Anoniem: 98216]

Er zijn maar 9 vakjes in elke kleur. Dat beperkt het aantal combinaties nogal. (en zijn het niet 6 kleuren, gewoon 1 per kant?)

[Reactie gewijzigd door Anoniem: 98216 op 23 juli 2024 12:51]

[MrCyber]

En maar 8 ervan kun je verplaatsen. Het centrale vlak kan je niet verplaatsen. Dat helpt ook alweer.

[LessRam]

Daarnaast zitten er per hoek 3 kleuren aan elkaar vast, en op de riben ook nogeens 2 kleuren.....

[[J.d.I.] DirtyHarry]

Er zijn zelfs minder combinaties mogelijk, omdat je vergeet dat er van elke kleur 9 vakjes zijn. Een compleet groene kubus bijvoorbeeld behoort niet tot de mogelijkheden
En daarbij zijn er 6 kleuren, niet 7

[Reactie gewijzigd door [J.d.I.] DirtyHarry op 23 juli 2024 12:51]

[PiepPiep]

Bijna, volgens mij moet je op deze manier 6^54 rekenen, een stuk meer dus.

/edit
Er zijn 8 hoeken te verdelen over de kubus, dus 8! mogelijkheden om ze te verdelen.
De hoeken kunnen op 3 manieren bevestigd worden, dus 3^8 mogelijkheden.
Er zijn 12 zijkanten dus 12! mogelijkheden.
Zijkanten kunnen op 2 manieren erin dus 2^12 mogelijkheden.
8! * 3^8 * 12! * 2^12 = 40320 * 6561 * 479001600 * 4096 = 519.024.039.293.878.272.000

[Reactie gewijzigd door PiepPiep op 23 juli 2024 12:51]

[hyriand]

*edit* ik sprak bullshit

[Reactie gewijzigd door hyriand op 23 juli 2024 12:51]

[suprcow]

ik heb t vermoeden dat de computer het wel kan berekenen alleen
dat de mens niet weet hoe hij het de computer duidelijk moet maken
hoe hij het moet berekeken...

[engelbertus]

ik denk dat je het wel weet, ( in plaats van vermoedt) maar niet weet hoe je het ons moet vertellen

[Anoniem: 217034]

Ben ik hier de enige die het verspilling van tijd en geld vind om een (waarschijnlijk miljoenen kostende) supercomputer voor zoiets nutteloos te gebruiken als het oplossen van een rubik's kubus gerelateerd probleem?
Gebruik zo'n ding liever voor onderzoek naar medicijnen o.i.d. Dit soort projectjes zijn misschien leuk als hobby, maar wie dit wetenschap durft te noemen is echt de weg kwijt.

[marcieking]

Dat heet fundamenteel onderzoek, en het gaat om het verkrijgen van kennis om de kennis, niet om de toepassing. Het heeft vaak als resultaat dat de antwoorden die hierdoor verkregen worden op hele andere, onverwachte terreinen gebruikt kan worden.

[Anoniem: 217034]

Als jij als hoofd wetenschappelijk onderzoek van een universiteit met een vastgesteld budget moest kiezen tussen twee projecten, dit rubiks-kubus project en bijvoorbeeld een project waarin men wil proberen een deel van het menselijk brein te simuleren op een supercomputer, teneinde het begrip van de hersenen te vergroten, waarbij de supercomputer tijd benodigd het zelfde is voor beide projecten - welke zou jij als rationeel mens dan kiezen? Welke zou de belasting betalende burger kiezen denk jij?

Natuurlijk is fundamenteel onderzoek belangrijk, maar een universiteit hoort geen speeltuin te zijn waar maar eindeloos aangelummeld mag worden met dit soort pseudo-wetenschappelijke hobbyprojecten.

Ik kan ook best gesubsidieerd gaan zitten uitrekenen wat de wiskundig optimale oplossing is voor een potje Kolonisten van Katan, maar denk je dat iemand daar op zit te wachten?

[Anoniem: 119135]

Bas T, je hebt hier nu een uur zitten posten. Had je in die tijd niet beter brieven kunnen schrijven voor Amnesty International of iets dergelijks?

Er is altijd wel iets nuttigers te bedenken dan het doen van willekeurig welke activiteit.

[Martijn-Tuup]

ik denk dat jij even voorbij schiet aan het feit, dat we zonder wiskunde in de wetenschap nergens zouden zijn en waren geweest! Zonder wiskunde ook geen onderzoek naar medicijnen. Of schrijf jij even de programma's die nodig zijn om complexe eiwitten te modelleren?

[Reactie gewijzigd door Martijn-Tuup op 23 juli 2024 12:51]

[Anoniem: 217034]

Natuurlijk, mij hoor je ook niet het nut van de wiskunde bagettaliseren. Alles wat ik zeg is; dit specifieke onderzoek heeft geen enkele intrinsieke waarde.
MIsschien dat deze vondst ooit kan helpen bij het oplossen van een ander probleem, maar die kans zal onnoemelijk klein zijn, en zelfs dan niets anders dan puur toeval. M.i. is het beter je te richten op iets waarvan je vermoed dat het ook voor nuttige toepassingen bruikbaar is. Onderzoekstijd is kostbaar, haar verkwanselen aan dit soort projecten gaat ten koste van de 'goodwill' van de belastingbetaler.

[Reactie gewijzigd door Anoniem: 217034 op 23 juli 2024 12:51]

[TD-er]

Vergeet niet dat ook dit soort onderzoeken kan leiden tot nieuwe inzichten, die mogelijk in de toekomst kunnen leiden tot het nog sneller kunnen vinden van geneesmiddelen.
Bijvoorbeeld het vouwen van eiwitten is iets waar zo ongelooflijk veel rekenkracht voor nodig is, dat dat gewoonweg niet eens met een supercomputer in korte tijd allemaal berekend kan worden.
Heel mischien is de methode die ze nu bedacht hebben in een omgewerkte vorm ook toepasbaar op dit probleem -dus alle uitgangsposities herleiden tot standaard oplossingen- en is het ineens wel op te lossen.

Wat ik dus wil zeggen is dat ook ogenschijnlijk nutteloze dingen best wel nuttig kunnen zijn.

[Kalief]

Dan kunnen we er nu golf ratings op toe gaan passen. "Vier slagen under par."

[AndriesLouw]

Hmm, zeker weer zo'n filmpje dat achteruit afgespeeld wordt

[Reactie gewijzigd door AndriesLouw op 23 juli 2024 12:51]

[Anoniem: 63672]

En nu wil ik wel weten HOE ik het zelf kan oplossen, dan ben ik bereid om mijn kubus uit het stof te halen

[Anoniem: 175502]

http://nl.youtube.com/res...ik%27s+cube&search=Zoeken

[Henk007]

Omdat een Rubik-kubus miljarden verschillende toestanden kent, zou het zelfs voor een supercomputer ondoenbaar zijn om alle mogelijke combinaties helemaal uit te rekenen.

Als dit waar zou zijn, zou het voor een huis-tuin en keuken PC-tje een peulenschilletje zijn om te bruteforcen. Het totale aantal configuraties is echter een beetje meer, namelijk 4.3*10¹⁹, volgens diverse online bronnen. Zelf kan ik het niet narekenen helaas
virtuële kubus om zelf mee te spelen.

[Reactie gewijzigd door Henk007 op 23 juli 2024 12:51]

[LessRam]

Die is echt veel moeilijker dan The real thing, de echt had ik in 1983 binnen 2 minuten makkelijk weer goed. (inderdaad met de etages-formule)

Toevallig heb ik 2 weken geleden een nieuwe kubus gekocht, en weet de laatste stap niet meer...... de laatste 4 hoekpunten op het laatste vlak.

[Anoniem: 211458]

Wat die kerel in dat filmpje doet is ook niet echt fair! Sommige kleuren zijn al 3-4 vlakjes bij elkaar!

[SKiLLa]

Maakt niets uit, op YouTube staan zat filmpjes waarin ze 't binnen 20s. oplossen, met 1 hand en zelfs geblindoekt binnen 1.5 minuut !!!

PS: het wiskundig bewijzen dat een Rubik-kus altijd in 26 stappen op te lossen is, is vele malen complexer dan een (sub-optimaal) oplossing voor een willekeurige beginstand te berekenen, volgens mij halen een aantal mensen dat hier door elkaar

[Reactie gewijzigd door SKiLLa op 23 juli 2024 12:51]

[Anoniem: 229978]

Die wetenschappers lopen flink achter! Er bestaat al jaren een programma "Cube Explorer" waarmee je de kubus in gemiddeld 19 slagen kunt oplossen, vaak zelfs in 17 of 18. Je hebt er bovendien geen supercomputer voor nodig, zelfs op een aftandse pc vindt dit programma de oplossing in enkele seconden. Hier de link: http://kociemba.org/cube.htm

[analog_]

Het gaat om het feit dat je elke kubus kan oplossen in 26 zetjes niet gemiddeld maar maximum.