Quante sono le combinazioni possibili del cubo di Rubik e il numero di mosse per risolverlo?

30 Dicembre 2011 | Giochi ed enigmi

Il cubo 3x3x3

Il cubo di Rubik è piuttosto recente tra i giochi di “rompicapo”: è nato nel 1974, a opera dell’ungherese Ernő Rubik (da cui prese il nome). Da quell’anno sono uscite diverse versioni del cubo, con una varietà crescente di quadretti per spigolo.

Prendiamo la versione 3x3x3 (cioè con tre quadretti per ogni spigolo), che il cubo più comune. È composto da 8 angoli con 3 facce ciascuno e da 12 spigoli con 2 facce ciascuno. Per trovare le combinazioni possibili dobbiamo tenere conto delle combinazioni di tutti gli angoli con ognuno degli spigoli presenti. Ogni facciata può essere ruotata con varie angolazioni (i tipi di rotazione sono 6, indicati in genere con delle lettere singole per facilitare la lettura degli algoritmi).

In base a questi dati avremo:
8! * 38 * 12! * 212
= 40.320 * 6.561 * 479.001.600 * 4.096
= 519.024.039.293.878.272.000

In realtà, questo numero è ben superiore alle reali combinazioni nel cubo. Infatti dobbiamo tenere presente che non tutte le combinazioni sono possibili: per esempio, un quadratino superiore non potrà mai scambiarsi con un quadratino sullo spigolo. Per trovare il calcolo esatto dobbiamo considerare che, anche smontando e rimontando casualmente i quadratini del cubo, avremo una possibilità su 12 di ricomporlo in modo che sia possibile risolverlo nuovamente: ci basta ricomporre in modo sbagliato un quadratino e ci risulterà sempre e comunque impossibile da risolvere.

Il numero di prima, quindi, deve essere diviso per 12. Il risultato è:

43.252.003.274.489.856.000

in pratica oltre 43 miliardi di miliardi di combinazioni. Ecco spiegato perché occorre seguire degli algoritmi (o avere una logica molto spiccata) per arrivare fino in fondo: a tentativi casuali risulta pressoché impossibile trovare l’unica soluzione all’interno di questa matassa.

Una curiosità: il numero massimo di mosse per risolvere un cubo di Rubik 3x3x3, tenendo conto di non sbagliare mai, è di appena 20 mosse (ma in genere ne bastano meno).

Cubi di gradi superiori

Naturalmente con cubi di grado superiore le combinazioni risultano progressivamente più alte. Per esempio, nel caso del 5x5x5 avremo (l’ho suddiviso su due righe per una più facile lettura):

282.870.942.277.741.856.536.180.333.107.150.328.
293.127.731.985.672.134.721.536.000.000.000.000.000

cioè circa 282 miliardi di miliardi di miliardi di miliardi di miliardi di miliardi di miliardi di miliardi di combinazioni.

In un articolo apparso sulla rivista New Scientist, Erik Demaine con i suoi compagni del MIT ha dimostrato come per un cubo di ordine n, il numero di mosse per risolverlo sia pari a:
n2/log n

Per esempio, il cubo 3x3x3 è risolvibile in media con:
32/log 3 = 9 / 0,477
= 18,86 mosse circa

Fonti principali
Articolo sul New Scientist. Dimostra come esista sempre una soluzione al cubo di Rubik, di qualsiasi grado sia.
Etichette
Etichette:,
Ultimi Commenti
  1. Daniele Vanoncini
  2. Daniele Vanoncini
      • Cesare
          • Cesare Svelto

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *

Questo sito usa Akismet per ridurre lo spam. Scopri come i tuoi dati vengono elaborati.