rubiks cube

[Verwijderd]

Ik kwam laatst op een raar idee. We hebben allemaal wel eens met de rubicks cube gespeeld. Toen dat kreng uitkwam gingen er de meest wilde verhalen over het aantal cobinaties in de rondte hoeveel verschillende posities er wel niet waren. Niemand wist het. En volgens mij weet nog steeds niemand dat preces. Er is wel wiskundig onderzoek naar gedaan en heel veel boeken over vol geschreven maar niemand weet het echt zeker. We *denken* nu dat het maximaal aantal kwart draaiingen 20 is om de kubus op te lossen. Zie http://www.popsci.com/sci...-any-rubiks-cube-position

Dat getal is steeds opnieuw bijgesteld tot dat we op 20 zijn uitgekomen. Maar is het wel bewezen dat het minstens 20 is, maar volgens mij zou het wellicht nog sneller kunnen. In alle eerlijkheid: Ik begrijp de code niet die bij het artikel hoort.

Dus wat was mijn plan nu: laten we een algoritme proberen te maken dat alles uitprobeert en een database aanlegt met *alle* mogelijke rotaties (90 graden draaien is een rotatie, 180 graden 2 rotaties).

Nu zegt er een klein stemmetje in mij dat er heel veel doublures in zullen zitten en dat het daarom minder enorm veel data oplevert. Waarom: LR geeft hetzelfde resultaat op als RL Dus hebben we het aantal al gehalveert. Ook is LLR hetzelfde als RLL en LRL. Het zelfde geldt voor LRR,RLR,RRL dus wederom een factor 9 minder. En er zijn vast veel andere doublures te ontdekken, al heb ik daar geen enkel bewijs voor, nogmaals klein stemmetje in mij.

Nu is het probleem dat het wel heel veel resultaten oplevert. Er van uitgaan dat er 20 draaiingen nodig zijn levert dat (12^20)/18 posities op. En dat zijn er maar liefst 638959998741245853696.

Als we op Wikipedia kijken dan staat er bij het aantal mogelijke posities 43252003274489856000. En dat is grofweg een factor 5 minder dan het aantal mogelijkheden. Er zit hier en daar dus nog veel ruimte in de voorspellingen.

Nu heb ik het volgende programmatje (in pseudocode) een keertje in python uitgeschreven.

code:

type
   stand = array(48)
   draaiingen = string(20)

Procedure write( posities:stand, rot:draaiingen)
   zoek(stand)
   if not found
      appendtodatabase stand,draaiingen
   fi
endproc

function boven( inp;stand) uitvoer:stand
 uitvoer[  1] = inp[ 3]
 uitvoer[  2] = inp[ 6]
 uitvoer[  3] = inp[ 9]
 uitvoer[  4] = inp[ 2]
 uitvoer[  5] = inp[ 3]
 uitvoer[  6] = inp[ 1]
 uitvoer[  7] = inp[ 9]
 uitvoer[  8] = inp[ 4]
 uitvoer[  9] = inp[ 7]
 
 *etcetera voor de overige kleuren hier alleen de bovenste gedaan 
return uitvoer

(dit ook voor rechts, links, onder, voor, achter, contrarechts, contralinks, contraonder, contraboven, contravoor en contraachter)

main
   write( beginstand, "")
   recordnumber = 1
   repeat 
      readfromdatabase( inputstand, rotaties)
      write( rechts( inputstand, rotaties+"r" )
      (dit ook voor links, onder, boven, voor, achter)
      
      write( contrarechts (inputstand, rotaties+"R")
      (dit ook voor contralinks, contraonder, contraboven, contravoor, contraachter)
      
      recordnumber++
      gotorecord recordnumber
   until endofdatabase
end.

Nu heb ik dit programmatje in Python uitgeschreven en het werkt! Dit deed ik op een VM die op mijn lappie draait. Als database gebruikte ik MySQL. Wel was ik heel snel door mijn diskspace heen en stopte de test

De complete output zou een databse zijn met alle draaiingen en posities. Een kleine letter is een draaiing met de klok mee en een hoofdletter een draaiing tegen de klok in. Vanuit een willekeurige stand is het daarna deze op te zoeken in de database en de draaiingen in omgekeerde volgorde uitvoeren.

Echter zijn er veel optimalisaties te bedenken. De grootste optimalisatie is een andere taal dan python die wel goed naar efficiente code is te compileren. Nu spreek ik een aardig woordje c en pascal. Maar ik weet niet hoe ik een database kan aanspreken. Daarvoor is het te lang geleden dat ik programmeur was. Andere optimalisaties zijn multi threaded maken zodat elke draaiing door een andere core kan worden uitgevoerd. Ook kan de database, een non-sql db als cassandra zou vast veel sneller gaan, effectiever op een andere machine draaien. Ook weet ik niet hoe ik de uitkomst van een draaiing kan comprimeren. Nu is het een array van 48 karakters terwijl ik maar 6 kleuren (en dus 6 verschillende karakters) gebruik, daar is vast heel veel winst te behalen. Net als bij de 20 karakters van de draaiing zelf.

De laaste is natuurlijk resources. Thuis kan niet! Daarvoor is mijn storage te klein. Echter heeft de auteur die ik eerder heb aangehaald een vriendje bij Google die het wel geinig vond om eens op een datacentre uit te proberen. Als we een goed algorithme hebben kunnen we wellicht kijken of we dat kunnen herhalen, of op een machine van een universiteit vragen te laten draaien.

Of is alles gewoonweg te groot en gecompliceerd. Kan ook en ben ik te optimistisch.

[bwerg]

Je hebt het over storage en rekentijd, en hoe je dat sneller kan krijgen. Maar dat lijken vooral constante factoren te zijn, geen verbeteringen in complexiteit. Als je van python naar C gaat haal je misschien een factor 5 winst, waarmee je de rekentijd van 100.000 jaar verkort naar de véél betere 20.000 jaar, bij wijze van spreken. En hetzelfde geldt voor de hoeveelheid opslag. Als elke stand 1 bit zou kosten, dan kosten 43252003274489856000 standen 4,7 exabyte. Maar een stand kost meer dan 1 bit, dus de storage zal groter moeten zijn dan googles gehele opslagcapaciteit. Niet echt realistisch.

Je bent nu een extreem groot probleem aan het brute-forcen. Het nemen van een andere taal of een groter datacenter heeft daarbij gewoon geen zin en is een verspilling van tijd, geld en ruimte. Er zijn trouwens efficientere manieren - ik weet niet hoe, maar ik kan me programmaatjes herinneren die een redelijke oplossing gaf, en die je op je pc kan runnen binnen seconden, in plaats van op het grootste datacenter van google. Dat is veel zinniger - en een hele afdeling onderzoek laten doen naar een rubiks-kubus is nog altijd goedkoper dan 30 exabyte aan data opslaan.

[Marzman]

Is het niet maximaal 20 keer draaien vanuit al die 43,252,003,274,489,856,000 posities? Dus ja sneller kan vaak wel, maar sommige posities hebben die 20 bewegingen nodig.



http://www.dailymail.co.u...Only-20-moves-needed.html

[ Voor 186% gewijzigd door Marzman op 09-06-2015 20:37 ]

[Megamind]

Hier was door Google toch al onderzoek naar gedaan?

http://www.cube20.org/

[ajakkes]

Het is 'bewezen' dat er precies 1 positie is die 26× 90° draaien nodig heeft. En geen enkele die meer dan 26 draaien nodig heeft om opgelost te worden. Het getal 20 gaat er van uit dat een draai van 2×90° 1 draai is. Het heeft de onderzoeker 35 cpu(2,8GHz×4cores) jaar gekost dit te bewijzen. Door het gebruik van servers is dit terug gebracht tot enkele weken rekentijd.

Het zelfstandig bepalen van een efficiënte methode om dit uit te rekenen is een leuke uitdaging. Maar een code review op je voorgangers zou handiger zijn.