Nieuwe resultaten: Gods getal is 26 in de kwartslagmetriek! Elke positie van Rubik’s Cube

Met ongeveer 35 CPU-jaren aan inactieve computertijd geschonken door Google, heeft een team van onderzoekers in wezen elke positie van de Rubik’s Cube ™ opgelost en aangetoond dat geen enkele positie meer dan twintig zetten vereist. We beschouwen elke draaiing van een gezicht als één beweging (dit staat bekend als de halve draai-metriek).

Elke oplosser van de kubus gebruikt een algoritme, een reeks stappen om de kubus op te lossen. Het ene algoritme kan een reeks zetten gebruiken om het bovenvlak op te lossen, dan een andere reeks zetten om de middelste randen te positioneren, enzovoort. Er zijn veel verschillende algoritmen, variërend in complexiteit en aantal benodigde bewegingen, maar degene die door een sterveling kunnen worden onthouden, vereisen doorgaans meer dan veertig zetten.

Je zou kunnen veronderstellen dat God een veel efficiënter algoritme zou gebruiken, een algoritme dat altijd de kortste reeks zetten gebruikt; dit staat bekend als Gods algoritme. Het aantal zetten dat dit algoritme in het ergste geval zou uitvoeren, wordt Gods nummer genoemd. Eindelijk is aangetoond dat Gods Aantal 20 is.

Het duurde vijftien jaar na de introductie van de Kubus om de eerste positie te vinden waarvoor aantoonbaar twintig zetten nodig waren om op te lossen; het is gepast dat we vijftien jaar daarna bewijzen dat twintig zetten voor alle functies voldoende zijn.

Een geschiedenis van Gods nummer
Tegen 1980 was er een ondergrens van 18 voor God’s Number vastgesteld door het aantal effectief verschillende zettenreeksen van 17 of minder zetten te analyseren en te ontdekken dat er minder van dergelijke reeksen waren dan kubusposities. De eerste bovengrens lag waarschijnlijk rond de 80 of zo van het algoritme in een van de vroege oplossingsboekjes. Deze tabel vat de volgende resultaten samen.

Hoe we het hebben gedaan
Hoe hebben we alle 43.252.003.274.489.856.000 posities van de Kubus opgelost?
We hebben de posities verdeeld in 2.217.093.120 sets van elk 19.508.428.800 posities.
We hebben het aantal sets dat we moesten oplossen teruggebracht tot 55.882.296 met symmetrie en setbedekking.
We hebben niet voor elke positie optimale oplossingen gevonden, maar alleen oplossingen met een lengte van 20 of minder.
We schreven een programma dat een enkele set in ongeveer 20 seconden oploste.
We hebben ongeveer 35 CPU-jaren gebruikt om oplossingen te vinden voor alle posities in elk van de 55.882.296 sets.

Verdeling
We hebben het probleem opgesplitst in 2.217.093.120 kleinere problemen, elk bestaande uit 19.508.428.800 verschillende posities. Elk van deze subproblemen was klein genoeg om in het geheugen van een moderne pc te passen, en de manier waarop we ze opsplitsten (wiskundig gezien, met nevenklassen van de groep gegenereerd door {U, F2, R2, D, B2, L2} of meer kort gezegd, nevenklassen van H) lieten ons toe om elke reeks snel op te lossen.

Symmetrie
Als je een Scrambled Cube neemt en deze ondersteboven draait, heb je het niet moeilijker gemaakt; er zijn nog steeds hetzelfde aantal zetten nodig om op te lossen. In plaats van beide posities op te lossen, kunt u eenvoudig de ene oplossen en vervolgens de oplossing ondersteboven keren voor de andere. Er zijn 24 verschillende manieren waarop u de kubus in de ruimte kunt oriënteren, en nog een factor twee met behulp van een spiegel, voor een totale vermindering van een factor van ongeveer 48 in het aantal op te lossen posities. Door vergelijkbare symmetrie-argumenten te gebruiken en door een oplossing te vinden voor een groot “set cover” -probleem, konden we het aantal sets dat moest worden opgelost terugbrengen van 2.217.093.120 naar 55.882.296.

Goede versus optimale oplossingen
Willekeurige posities Cosets of H
Optimaal 0,36 2.000.000
20 zetten of minder 3.900 1.000.000.000
Oplossingspercentage, in posities / seconde
Een optimale oplossing voor een positie is er een die niet meer bewegingen vereist dan nodig is. Aangezien een stelling waarvoor 20 zetten nodig waren al bekend was, hoefden we niet elke stelling optimaal op te lossen; we moesten alleen een oplossing vinden van 20 zetten of minder voor elke reeks. Dit is aanzienlijk eenvoudiger; de tabel links toont de snelheid van een goede desktop-pc bij het oplossen van willekeurige posities.
Fast Coset-oplossingsprogramma
Door een combinatie van wiskundige trucs en zorgvuldige programmering te gebruiken, waren we in staat om een ​​volledige nevenwaarde van H op te lossen, hetzij optimaal, hetzij met reeksen van twintig zetten of minder, op een enkele desktop-pc, met de snelheden die in de tabel links worden weergegeven.

Veel computers
Eindelijk waren we in staat om de 55.882.296 nevenklassen van H over een groot aantal computers bij Google te verdelen en de berekening in slechts een paar weken te voltooien. Google geeft geen informatie vrij over hun computersystemen, maar een goede desktop-pc (Intel Nehalem, vier-core, 2,8 GHz) zou 1,1 miljard seconden of ongeveer 35 CPU-jaren nodig hebben om deze berekening uit te voeren.

rubiks kubus