businessinsider.com, 5 febbraio 2019
Il cubo di Rubik si risolve sempre in massimo 20 mosse
Il Cubo di Rubik è un rompicapo famosissimo.Ma è matematicamente complicato – possiede 43 quintilioni (43 x 1 000 000 000 000 000 000 000 000 000 000, ossia 43×1030) di configurazioni possibili.Dopo più di trent’anni dall’invenzione del Cubo, un gruppo di matematici ha dimostrato, tramite una serie di supercomputer di Google, che il Cubo può essere risolto sempre con un massimo di 20 mosse.Il Cubo di Rubik è un classico rompicapo inventato nel 1974 dal professore di architettura e design ungherese Erno Rubik.
Il gioco consiste in un cubo composto da 27 cubi più piccoli disposti in un reticolo 3x3x3 con adesivi colorati sulle facce esterne dei cubi più piccoli. Si acquista nella sua configurazione “risolta” con le facce più piccole su ognuno delle sei facce più grandi che condividono lo stesso colore. Ognuna delle sei facce del cubo può essere ruotata liberamente spostando così i cubi più piccoli.
Guarda anche
Lo scopo del Cubo di Rubik è quello di iniziare con una configurazione del cubo mischiata a caso per tornare allo schema risolto iniziale con ognuna delle sei facce di un unico colore.
È risaputo che risolvere il rompicapo è davvero difficile. Dopo averlo inventato, lo stesso Erno Rubik ci ha impiegato un mese a risolverlo.
Diversi metodi e tecniche sono stati sviluppati da allora per la sua soluzione, come questa semplice strategia presentata sul sito ufficiale del Cubo di Rubik. I solutori esperti possono completare il rompicapo in pochi secondi; l’attuale detentore del record ha impiegato 3,47 secondi.
I rompicapi come il Cubo di Rubik sono il genere di cosa che affascina i matematici. La natura geometrica del gioco si presta perfettamente all’analisi matematica.
Al Cubo possono essere applicate 18 mosse base:
ruotare una delle sei facce – fronte, retro, su, giù, sinistra o destra – sia a 90° in senso orario, sia a 90° in senso antiorario, oppure di 180°.
Ogni soluzione per qualsiasi configurazione particolare del Cubo di Rubik può quindi essere considerata come l’elenco delle mosse base necessarie per far tornare quella configurazione allo stato iniziale risolto.
Una domanda ovvia e immediata, che risale all’invenzione originale del cubo, è: data una particolare configurazione, qual è il numero di mosse minimo necessario per risolvere il rompicapo? E conseguentemente: qual è il numero di mosse minimo necessario per risolvere qualsiasi configurazione del Cubo di Rubik, numero che gli appassionati del cubo definiscono “Numero di dio”?
Come detto da Erno Rubik in una recente intervista rilasciata a Business Insider, la domanda è “collegata ai problemi matematici del cubo”.
Sorprendentemente, ci sono voluti 36 anni dall’invenzione del gioco per trovare la risposta. Nel 2010, un gruppo di matematici e di programmatori informatici ha dimostrato che il Cubo di Rubik può essere risolto in, al massimo, 20 mosse.
Leggi anche: 10 abilità impressionanti che potete padroneggiare in una settimana
Un motivo per cui ci è voluto così tanto per risolvere questo quesito apparentemente semplice è rintracciabile nella sorprendente complessità del Cubo di Rubik. Un’analisi di tutte le possibili combinazioni in cui possono disporsi i cubi più piccoli che lo costituiscono (spesso definiti “cubetti”) dimostra che esistono circa 43 quintilioni (cioè 43.000.000.000.000.000.000.000.000.000.000) — di configurazioni possibili del Cubo di Rubik.
Affrontare e cercare di trovare la soluzione più rapida per ognuna di queste configurazioni è quindi praticamente impossibile. La chiave per rispondere alla domanda circa il minor numero di mosse per risolvere qualsiasi configurazione è quella di avvalersi delle relazioni tra le diverse configurazioni.
Nel 1995, il matematico Michael Reid ha scoperto una configurazione del Cubo di Rubik indicata come “superflip” e ha dimostrato che per risolverla ci volevano almeno 20 mosse, ponendo così un limite inferiore al possibile “Numero di dio”. Restava la domanda se ci fossero configurazioni la cui soluzione necessitava più di 20 mosse.
Nel corso dei decenni sono stati dimostrati vari limiti superiori. Uno dei primi analisti matematici del cubo, Morwen Thistlethwaite, riuscì a dimostrare che ogni configurazione poteva essere risolta al massimo in 52 mosse.
Il programmatore informatico Tomas Rokicki scoprì una strategia per trovare soluzioni relativamente veloci per le configurazioni del Cubo di Rubik. Questa si basava su uno dei primi lavori sviluppati da matematico Herbert Kociemba che divise la soluzione di un cubo in due passaggi basandosi su una serie speciale di circa 19,5 miliardi di configurazioni parzialmente risolte note per avere soluzioni relativamente veloci.
Fase uno: muovere il cubo in una di queste configurazioni e,fase due, usare la soluzione veloce per questa configurazione parzialmente risolta.L’algoritmo di Kociemba è la base di molti risolutori robotici di cubo operati da computer, come quello del video seguente:
I lavori precedenti che impiegavano questa strategia dimostrarono che ci sarebbero volute almeno 30 mosse per risolvere qualsiasi configurazione: ognuna delle configurazioni della più piccola serie speciale necessitava al massimo di 18 mosse per essere risolta e ogni configurazione del cubo impiega almeno 12 passi per arrivare a uno degli stati speciali.
Rokicki portò la strategia a un livello superiore raggruppando le configurazioni tramite un insieme di configurazioni parzialmente risolte. Il che voleva essenzialmente dire che si era capaci di risolvere insieme 19,5 miliardi di configurazioni. Come detto da Rokicki e dai suoi colleghi sul loro sito, hanno “ripartito le posizioni in 2.217.093.120 insiemi di 19.508.428.800 posizioni ognuno”.
In questo modo, la strategia di Rokicki implicava l’affrontare circa 2,2 miliardi di problemi invece degli originali 43 quintilioni: comunque un immane compito informatico! Nel 2010, però, Rokicki e i suoi colleghi hanno impiegato una serie di supercomputer di Google per dimostrare infine che 20 era effettivamente il numero magico.
Ovviamente, il fatto che per rispondere alla domanda ci siano voluti oltre tre decenni, oltre all’ausilio di matematici esperti e di un insieme di supercomputer suggerisce che per il giocatore occasionale questo non sia proprio l’approccio più pratico alla soluzione del cubo. In compenso è proprio il tipo di problema per cui i matematici vanno matti.