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.

Reacties (147)

[Kahlan]

Blijft een zwaktebod dat bewijs door volledige enumeratie.

[mae-t.net]

Maar tot iemand erin slaagt deze prijs te winnen kan je soms niet om zulke brute force heen.

[sirdupre]

Nee, P = NP is hier eigenlijk niet aan gerelateerd, omdat de inputgrootte van het probleem vast staat (namelijk 3x3x3). Zodra de inputgrootte vast staat is het altijd worst case in constante tijd op te lossen (tenzij je probleem in de klasse van onoplosbare problemen zit), dus dan is de hele P=NP vraag* irrelevant geworden...

Zo is het ook prima mogelijk om een elegant bewijs te geven dat er in elke graaf van 3 knopen een 3-clique of een maximum independent set van 3 is, terwijl maximum clique en maximum independent set gewoon NP-volledig zijn. Zie ook: http://mathworld.wolfram.com/RamseyNumber.html

*Kort-door-de-bocht uitleg:
Problemen in P zijn problemen die we in polynomiale tijd in de inputgrootte van het probleem kunnen oplossen, zoals sorteren, optellen, kortste pad in een graaf, etc.
Problemen in NP zijn problemen, waarvan we gegeven het probleem en een antwoord op het probleem, in polynomiale tijd kunnen controleren of het antwoord klopt. Als iemand een oplossing voor de beslissingsvariant van het handelsreizigersprobleem geeft en daarbij beweert dat zijn oplossing lengte N heeft, dan kunnen we makkelijk controleren of de oplossing een tour is en lengte N heeft, maar we zijn niet in staat om gegeven een waarde van N die tour te vinden in polynomiale tijd.
Problemen in P zitten dus automatisch ook in NP (we kunnen immers controleren of een lijst een gesorteerd is), maar het blijft de grote open vraag of problemen in NP ook in P zitten (men vermoed van niet).

[coolmos]

Ik vraag me af of je hier gelijk hebt. Het handelsreizigersprobleem dat je zelf aanhaalt heeft ook een bekende inputgrootte.

Volgens mij gaat het erom dat je kunt bewijzen dat een bepaalde Rubik's Cube in 20 stappen of minder is op te lossen, maar is niet te bewijzen dat ELKE Rubik's Cube in 20 stappen of minder is op te lossen.

[Reactie gewijzigd door coolmos op 22 juli 2024 13:38]

[sirdupre]

De inputgrootte van het handelsreizigersprobleem is het aantal steden. Een handelsreizigersprobleem op de 10 grootste steden van Nederland zal minder tijd nodig hebben dan het handelsreizigersprobleem op heel Zweden (wat overigens ook is opgelost[1]), of dat van heel de wereld (wat nog niet is opgelost[2]). Maar je kunt altijd grotere handelsreizigers problemen blijven maken door extra steden te verzinnen.

Als NP niet gelijk is aan P, dan zal de tijd die je nodig hebt om een handelsreizigersprobleem altijd ten hoogste O(c^n * p(n)) tijd kosten, waar c > 1 een constante is, p(n) een vast polynoom in n, en n het aantal steden.

Dit geldt in feite ook voor de generieke Rubik's Cube: als je een kubus van 4x4x4, of 5x5x5 maakt, zal deze kubus moeilijker op te lossen zijn dan een kubus van 3x3x3. Je hebt ook oneidig veel Rubik's Cube's als je ze steeds groter gaat maken - je kunt daar immers oneindig meer door blijven gaan. Maar aangezien deze wetenschappers alleen hebben gekeken naar kubussen van grootte 3, hebben ze in feite een vaste waarde voor n beschouwd en is O(c^3 * p(3)) dus gewoon constant.

Edit: mijn reactie was op de opmerking dat je door de 'P=NP' kwestie soms niet om het brute forcen van dit soort problemen heen kan. Het is inderdaad niet te bewijzen dat elke Rubik's Cube in 20 stappen of minder is op te lossen: voor een 100x100x100 kubus met de helft van de vlakken gedraaid zal het niet moeilijk te bewijzen zjin dat je meer zetten nodig hebt dan 20. Maar de 'P=NP' kwestie heeft naar mijn idee weinig te maken met de vraag of het mogelijk is een eleganter bewijs dan een enumeratie te geven voor een 3x3x3 kubus.

Voor de leuk:
[1] http://www.tsp.gatech.edu/sweden/
[2] http://www.tsp.gatech.edu/world/

[Reactie gewijzigd door sirdupre op 22 juli 2024 13:38]

[coolmos]

Volgens mij gaat het juist daarom. Ik ben geen wiskundige, maar hoe interpreteer jij dit:

The question P = NP? basically asks: if 'yes'-answers to a 'yes'-or-'no'-question can be verified "quickly" can the answers themselves also be computed "quickly"? The theoretical notion of "quick" used here is that of an algorithm that runs in polynomial time, which usually but not always corresponds to an algorithm that is fast in practice.

Van Wikipedia Simple

[sirdupre]

De verwarring zit denk ik het gebruik van "question" en "answers". Wiskundigen gebruiken vaak het woord "probleem" of "problem" voor een hele klasse van problemen. Een specifieke invulling van zo'n probleem wordt vaak een probleem-instantie genoemd.
Ik interpreteer dit dan ook als "als een 'ja'-antwoord op een ja/nee-probleem-instantie 'snel' gecontroleerd kan worden, kunnen alle instanties van het probleem dan ook snel opgelost worden?".

Je kunt sorteren bijvoorbeeld als een probleem zien: je krijgt een ongesorteerde lijst als input en het 'probleem' is het vinden van de gesorteerde lijst. Let hierbij op dat ik dus geen aannames doe over de lengte of de inhoud van de lijst. Wiskundige zouden hier zeggen dat 'sorteren' het probleem is, en de lijst [4,2,7,5,3] een probleem instantie is, met [2,3,4,5,7] als antwoord. Je kunt je denk ik wel voorstellen dat er oneindig veel mogelijke lijsten zijn en dus ook oneindig veel probleem-instanties van "sorteren". Je kunt je denk ik ook wel voorstellen dat het langer duurt om een lijst van 10 getallen te sorteren, dan om een lijst van 10.000 getallen te sorteren. Waar het woord 'snelheid' hier op duidt, is de vraag hoeveel tijd je extra kwijt bent, als je een getal aan de lijst toevoegt (bij sorteren is dit niet echt dramatisch te noemen, terwijl het bij de NP-volledige problemen dus explodeert, tenzij P=NP).

Omdat deze wetenschappers alleen kubussen van 3x3x3 (en dus een eindig aantal configuraties) bekeken hebben, is er niet sprake van "alle instanties", maar slechts een eindige deelverzameling van "alle instanties".

[Reactie gewijzigd door sirdupre op 22 juli 2024 13:38]

[J.J.J. Bokma]

De vraag is: als je kan kontroleren in korte tijd of een antwoord korrekt is, kan je dan ook in korte tijd op het antwoord zelf komen. Het voorbeeld dat Wikipedia geeft is: je kan van een deelverzameling van gehele getallen (positief en negatief) in korte tijd kontroleren of de som 0 is (optellen, wat voor n getallen n stappen is), maar om zo'n deelverzameling te vinden in een verzameling kan (i.h.a.) niet in korte tijd.

Ander voorbeeld: met het handelsreizigersprobleem, om een route van, zeg k km te vinden moet je alle mogelijkheden verbindingen tussen de steden aflopen (n!, dwz 1 x 2 x 3 x 4 x ... x n-2 x n - 1 x n) maar het kontroleren van de oplossing kan in korte tijd door gewoon de afstand van de gevonden deelroute tussen elke stad op te tellen.

[airell]

P, NP ?! Ik gebruik F2L met een beetje van mezelf en een beetje van internet.

[MicroWhale]

Wat is de uitdaging aan dit "probleem"?

1. Plot alle 400 studenten

Voor elke "incompatible pair":
2. Leg een verbinding tussen beide studenten die "incompatibel met elkaar zijn"

Herhaal het volgende 100 keer:
3. Kies een student (X)
4. Streep alle studenten weg waarmee (X) in de eerste graad verbonden is

Om de oplossingsruimte zo groot mogelijk te houden is het bij 3 aan te raden om een student te pakken met zo weinig mogelijk relaties.

[Reactie gewijzigd door MicroWhale op 22 juli 2024 13:38]

[coolmos]

Natuurlijk kun je hier een oplossing vinden. Dat is de vraag niet.

Hoe kun je hier simpel alle oplossingen vinden? Daar gaat het om.

EDIT: Van Wikipedia:

The question P = NP? basically asks: if 'yes'-answers to a 'yes'-or-'no'-question can be verified "quickly" can the answers themselves also be computed "quickly"? The theoretical notion of "quick" used here is that of an algorithm that runs in polynomial time, which usually but not always corresponds to an algorithm that is fast in practice.

[Reactie gewijzigd door coolmos op 22 juli 2024 13:38]

[MicroWhale]

Dat is dan een veel helderdere uitleg van het probleem, want op de door mae-t.net gegeven pagina lees ik het alsof er naar één mogelijke oplossing gevraagd wordt.

Het berekenen van alle mogelijke oplossingen voor een dergelijk probleem is tot nu toe altijd een probleem gebleken.

[sirdupre]

Op deze manier vindt je wel een maximal independent set (een set studenten waar je geen student meer aan kunt toevoegen zonder dat je twee naburige studenten in je set hebt), maar geen maximum independent set (de maximal independent set met het grootst mogelijke aantal studenten).

Het gaat fout bij stap 3: als je een arbitraire student kiest kan je de foute keuze maken.

Een simpel tegenvoorbeeldje:

4 studenten, A, B, C en D, en verbindingen tussen (A,B), (A,C) en (A,D). Je algoritme zou nu student A kunnen kiezen en hiermee studenten B,C en D wegstrepen en eindigen met een independent set {A} van grootte 1. Als het algoritme echter zou beginnen met student B, dan zou het student A wegstrepen, vervolgens C en D kiezen en eindigen met een independent set {B,C,D} van grootte 3, wat de maximum indepedent set is.
En hoewel het in dit geval goed zou gaan als je een student met de kleinste graad kiest, kun je ook voorbeelden verzinnen waarbij die vlieger niet op gaat.

[MicroWhale]

Je kunt inderdaad voorbeelden verzinnen waarvoor nul oplossingen zijn, of 1, of meer.

Punt van mijn laatste opmerking (pak een persoon met zo weinig mogelijk relaties) is dat je regels moet verzinnen om efficiënt tot een oplossing te komen. Er zijn waarschijnlijk regels te verzinnen die het mogelijk maken om meer garantie te krijgen voor een oplossing, maar dan lever je wel in op rekentijd.

[coolmos]

Daar is Vinay Deolalikar aardig druk mee bezig.

Hier zijn bewijs.

En hier alvast wat problemen met zijn bewijsvoering.

[Dr. Strangelove]

Ik ben geen puzzelaar. Ik vind het oplossen van zo'n ding gelijk aan zwarte magie.

In plaats van 20 stappen zou ik er 91.365.146.187.124.313 stappen over doen vermoed ik.

[himlims_]

1x Android Systeempje/ARM + 1001 lego blokjes = oplossing [2]

[Reactie gewijzigd door himlims_ op 22 juli 2024 13:38]

[Plymp]

Daar heb je Android niet eens voor nodig, alleen lego is al genoeg: http://tiltedtwister.com/tiltedtwistervideo.html (je moet wel wat meer geduld hebben).

Als je wat meer haast hebt moet je dit bouwen: http://www.youtube.com/wa...o&feature=player_embedded (toch nog langzamer dan de snelste mens).

@hieronder: ligt aan je definitie van lego natuurlijk. Voor het eerste filmpje worden alleen onderdelen gebruikt die onder de naam lego verkocht worden. Het feit dat de NXT Intelligent Brick een ARM processor bevat doet daar niks aan af, het kan nog steeds als een raar gevormde lego steen gebruikt worden. Het grote verschil met het eerdere filmpje is dat je geen onderdelen nodig hebt die niet onder de noemer lego verkocht worden.

[Reactie gewijzigd door Plymp op 22 juli 2024 13:38]

[kozue]

Alleen lego? Lijkt me niet hoor. Er zal ergens een cpu moeten zitten die de transities uitrekent. Lego op zichzelf weet niet eens wat een kubus is.

[Aham brahmasmi]

Misschien is de CPU met al zijn transistoren ook in Lego opgebouwd?

[Mellow Jack]

Uuuhm je eerst filmpje heeft wel een geprogrammeerde control unit oftewel iets met dezelfde functie als android bij het vorige filmpje

[Maikelvu]

Op het filmpje is te zien dat deze echt veel meer als 20 stappen nodig heeft om te de oplossing te komen. Met het nieuwe algoritme zou dit dus in veel minder stappen kunnen. De vraag is of het ook sneller is, door de rekentijd die nodig is voor het nieuwe algoritme.

[Xirt]

In principe kan door deze wetenschap in het algoritme opgenomen worden dat er gestopt moet worden met zoeken na de 20e stap (indien er geen oplossing is) i.p.v. na de 22e stap (eerder kennis): op die manier zouden sommige bestaande algoritmes dus sneller moeten kunnen worden lijkt mij.

[CyBeR]

In principe kan door deze wetenschap in het algoritme opgenomen worden dat er gestopt moet worden met zoeken na de 20e stap (indien er geen oplossing is) i.p.v. na de 22e stap (eerder kennis): op die manier zouden sommige bestaande algoritmes dus sneller moeten kunnen worden lijkt mij.

Ik denk alleen wel dat als je bestaande algo 't in 21 stappen gaat doen, dat dan na 20 stappen ophouden en opnieuw beginnen niet sneller is.

[iceheart]

hangt er van af hoeveel "gokjes" er in het bestaande algoritme zitten.

[Hyronymus]

Ik zou dit algorithme dan weleens in praktijk willen zien: begin met een verwarde kubus en laat de computer maar aangeven welke stappen je moet doen.

[Proxx]

http://www.youtube.com/wa...4clQJ3VuA&feature=related

21 zit er toch niet veel naast =]

[Jorgen]

Dat is een gaaf filmpje! Lijkt me leuk om zoiets thuis te hebben (en dat die dan ook andere dingen kan oplossen. De afwas, of stofzuigen, bijv.).

[GerritGekke]

dat filmpje is echt super.

[kmf]

Er zijn stappen die je kan nemen om het makkelijk te maken. Veel methodes mogelijk. Sommigen leren alle stappen voor de problemen uit hun hoofd, anderen doen het "strategischer".

Hier een paar voorbeelden:
http://www.rubikssolver.com/
http://peter.stillhq.com/jasmine/rubikscubesolution.html

[topaj]

Of een online solver (die het nog niet in 20 stappen kan doen ):
http://www.wrongway.org/cube/solve.html

[Dorgaldir]

In 20 lukt het me ook niet maar zoveel heb ik er ook niet voor nodig
Ik vind het wel zeer boeiend om te lezen dat men zich met zulke "nutteloze" weetjes bezig houd, alhoewel dit wel niet echt nutteloos zal zijn. Volgens mij kunnen ze deze wetenschap voor andere doeleinden wel gebruiken.

Maar blijft het boeiend vinden dat mensen zich bezig kunnen houden met zulks een onderzoek

[wootah]

Ach ik heb wel eens wat onnuttigere onderzoeken gezien
bijvoorbeeld die ene wiskunde student (geloof ik) die bewezen had dat vampieren niet konden bestaan omdat dan de mensheid al was uitgeroeid

maarja, dit zal echt wel ergens misschien nuttig zijn... een goede rubik oplosser bijvoorbeeld
naja, weer een misterie opgelost

[OpenMinded]

Hoezo nutteloos?
Voordat het ding er was waren deze oplossingen er niet.
Het draagt dus bij aan kennis over dergelijke complexe puzzels.

[Anoniem: 366402]

Ik loste die dingen vroeger altijd in 1 stap op. (met gebruik van een kruiskop)
Heb daar echt het geduld niet voor.

[stresstak]

Het was inderdaad even pulken, maar uiteindelijk had ik alle plakkertjes op een leuke plek teruggezet.

[Ilya]

Hoe definiëren ze die 35 jaar computerrekentijd ?

[Marcelloz]

Meestal koop je die in bij Google, Amazon, MS Azure. Die rekenen af per uur. Blijkbaar heeft het dus 35 jaar aan cpu power gekost. Beetje abstract.

[update]
35 jaar is ongeveer 306792 uur (inclusief 8 schrikkeldagen)
1 uurtje power bij Windows Azure kost $0.12 dus in totaal $ 36.815,04

zoiets zal het ook wel bij Google kosten. Dat hebben ze dus gedoneerd.
(uiteraard enkel cpu power, geen data opslag / transfer kosten etc)

[Reactie gewijzigd door Marcelloz op 22 juli 2024 13:38]

[Jasper Janssen]

De vraag is inderdaad, welke cpu, en heden ten dage ook, is dat per core of per chip en met hoeveel cores dan?

Edit: Wat ze in de bron zeggen is dat het gaat om 35 jaar rekentijd van een quadcore nehalem 2.8. Google heeft gewoon idle cycles van een x miljoen servers gedoneerd, dus dat zijn geen compute bakken maar gewoon hun idle tijd en kan dus niet per uur afgerekend worden.

[Reactie gewijzigd door Jasper Janssen op 22 juli 2024 13:38]

[DarkKnight]

"Lots of Computers
Finally, we were able to distribute the 55,882,296 cosets of H among a large number of computers at Google and complete the computation in just a few weeks. 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."
bron: hun website...

Maar dat zou betekenen dat het in totaal 4.4miljard core-seconden is, dus ~1.2mln core uren. Zeg dat ze gemiddeld 50000 cores hadden (ik vermoed dat Google er wel iets meer heeft, maar lastig om daar achter te komen en ze moeten natuurlijk ook idle zijn, ook hun snelheid etc zijn ze nogal vaag over in het algemeen), dan hebben die 50000 cores maar 24.4 uur staan rekenen. Voor de duidelijkheid: dit is erg weinig voor computationele berekeningen.

Uiteindelijk valt het wel mee als je het omzet in core uren voor een 2.8Ghz Nehalem core.

Oh, zie nu pas dat er staat dat het een paar weken duurde. Zeg 2 weken, dus 14 dagen. Dan zou een mogelijkheid zijn: 5000 cores op een equivalent van ~2.0Ghz Nehalem. Dat is eigenlijk peanuts...

[Reactie gewijzigd door DarkKnight op 22 juli 2024 13:38]

[Marcelloz]

Ze hadden het over enkele weken dus dat zullen er wat minder dan 50.000 zijn geweest. Stel dat ze 25 dagen aan het rekenen zijn geweest, dan hebben ze het met 2000 cores gedaan.

[J.J.J. Bokma]

Net als je manuren definieerd ;-)

Het kost 1 computer 35 jaar
Het kost 35 computers 1 jaar
Het kost 350 computers 1/10 jaar, enz.

Het zegt dus niks over welke processor, e.d. (Net als een manuur niks zegt over de kwaliteit van de man/vrouw die het werk doet).

[Anoniem: 48923]

1 commodore 64 voor 35 jaar laten rekenen... ze hadden ook een zware pc kunnen nemen maar dan zou het maar 2 dagen duren..

[fevenhuis]

Met behulp van heel veel kleine stappen.

[HerrPino]

Ik meen ooit gelezen te hebben dat het minimaal aantal stappen 17 of 18 was... of is dat een theoretisch minimum?

[MadButcher]

Wat dacht je van alle mogelijk toestanden minus de uiteindelijke toestand (originele staat), wat dan het minimaal aantal stappen is: 1!
Maar 1x draaien natuurlijk!
Dat is toch niet moeilijk lijkt me?

[Paultje3181]

Nee, hoor. Je hebt ze zelfs waarbij het aantal 1 stap is... Het theoretisch minimum is 1, lijkt me best logisch...

[Anoniem: 200498]

Volgens mij bedoel je een theoretisch maximum aantal stappen, voor het oplossen van elke mogelijke toestand

[Reactie gewijzigd door Anoniem: 200498 op 22 juli 2024 13:38]

[badflower]

dan vraag ik me af, als je begint aan het oplossen van deze Kubus, wat is dan eigenlijk de kans dat je hem oplost?

iemand?

[Anoniem: 222214]

Als je zomaar iets doet? Zoals infinite monkey? Als je gerichter te werk wil gaan dan google je een oplossingsalgoritme, ga oefenen. Het is me gelukt hem binnen 2 minuten op te lossen, gebruikte wel een erg inefficiente methode

[Jasper Janssen]

Mij is het ook regelmatig binnen de minuut gelukt, maar veel verder dan dat ben ik nog niet gekomen.

[martennis]

vrij groot.. er is gewoon een algoritme voor namelijk
blijft alleen de vraag hoeveel tijd je erin wilt steken om dat (zo snel mogelijk) op te lossen

[Flozem]

onbekend dus, omdat niet alle variabelen / randvoorwaarden bekend zijn...

[Reactie gewijzigd door Flozem op 22 juli 2024 13:38]

[zordaz]

Als je hem aan mij geeft is de kans 100% (en nee, geen stickertjes plakken of uit elkaar halen). En 90% kans dat ie binnen 5 minuten klaar is.

[Reactie gewijzigd door zordaz op 22 juli 2024 13:38]

[ikt]

Kubusje? Als je een paar algoritmes kent kun je hem makkelijk oplossen. je komt dan wel over de 100 stappen heen. Ik kan zo'n ding ook oplossen binnen 1 minuut. Maar dan moet je wel als een gek gaan draaien. Knap dat ze weer wat stappen minder hebben uitgevogeld. Maar dan is dit wel het limiet denk ik.

[Anoniem: 97031]

Het wereldrecord staat op 7.08 seconden.

[Nibbz]

Ik zag een tijdje geleden op youtube een filmpje van een kerel die ook een rubik cube oplost door er een algoritme op te laten..

Part 1

Part 2

Wel gaaf

[VolvoGek]

Ik was vroeger heel populair op school. Draaide voor iedereen het ding weer goed.
Maar koste mij nooit meer dan een minuut.
Mijn record 43 seconden, zat ooit in de buurt van wereldrecord. Maar zoek even op youtube en google en zie daar een aantal filmpjes van eenkennige chinees die echt onmogelijke snelheden haalt bij het inelkaar draaien.

Ik was 10 toen ik 'm voor de eerste keer maakte, dat is lang geleden, en ik kan het nog steeds, maar niet meer zo snel..
en filmpjes met turbo chinezen doen je beseffen.....

[morten]

Nu nog even alle mogelijke "GO" combinaties gaan berekenen...

[blorf]

Poging: 19 X 19 posities die zwart, wit of niks zijn, dus 19 X 19^3 = 47045881.
Het valt mee, 47 miljoen mogelijke combinaties. Daar moet je dan nog de combinaties af halen die in een partij nooit voor kunnen komen

Ik denk dat bij schaken het aantal fink groter wordt.

[Tom-Z]

@HerrPino 18 was inderdaad een theoretisch _minimum_. Dat getal krijg je als je de 4.3*10^19 combinaties vergelijkt met het aantal verschillende draaivolgordes. Het blijkt dat je met 17 draaien niet genoeg verschillende draaivolgordes kan maken om aan dat aantal combinaties te komen. Daaruit kon men dus bepalen dat het maximum aantal draaien minstens 18 moest zijn. Omdat verschillende draaicombinaties toch dezelfde positie kunnen opleveren zou het maximum toch hoger dan 18 kunnen zijn.
Later heeft iemand van een bepaalde positie bewezen dat het minimum aantal draaien 20 was. Deze onderzoekers hebben nu aangetoond dat er geen posities zijn die 21 draaien nodig hebben. Dus nu weten we dat het maximum aantal draaien dat minimaal nodig is, 20 is.

Ik ben een soort "fan" van Rubik en ik hou me bezig met het zelf ontwerpen en bouwen variaties op de Kubus van Rubik. Erg leuk dat het ze eindelijk gelukt is om het maximaal aantal zetten te bepalen. Ik hoop dat ze ooit nog een puur wiskundige uitleg vinden.