Sei idee grandi, ognuna con un cubo vivo da guardare e girare. I cubi si trascinano con il dito o il mouse. Tutti i numeri della pagina vengono calcolati da un vero simulatore, non scritti a mano.
Il 4×4 sembra un altro gioco. Ma se prima si accoppiano i centri e poi gli spigoli, ogni gruppo di adesivi si comporta come un solo pezzo: il 4×4 diventa un 3×3 con i pezzi “grassi”. Da lì si usa ciò che si sa già.
Matematici e programmatori lavorano così: non risolvono da zero, riportano il problema a uno noto.
R U R' U' è codice: istruzioni precise eseguite in ordine. Chi gira il cubo fa il computer. Stesso cubo di partenza e stesse mosse danno sempre lo stesso risultato.
Ripetendo una sequenza abbastanza volte, il cubo torna risolto. Quel numero di ripetizioni è il periodo della sequenza.
R U contando ad alta voce. Poi R U R' U'. Prima di guardare la tabella, provate a indovinare.| Sequenza | Periodo |
|---|
Smontate un 3×3 e rimontatelo con un solo spigolo girato. Non si risolverà mai, con nessun algoritmo.
Il motivo è un invariante: con una regola fissa si contano gli spigoli “girati”. Ogni mossa ne gira 0 oppure 4, mai uno solo. Il numero cambia, ma se parte pari resta pari, se parte dispari resta dispari. Partendo dispari, non si arriva mai a zero.
Sul 4×4, dopo la riduzione, può capitare proprio questo: un solo spigolo doppio girato, situazione impossibile su un 3×3. È la “parità” del 4×4, e per sistemarla serve un algoritmo speciale che gira anche gli strati interni.
Un commutatore ha la forma A B A' B': fai A, fai B, disfa A, disfa B. Quasi tutto torna al suo posto e si muovono solo pochi pezzi. Molti algoritmi nascono proprio così.
Qui A = R' D' R e B = U'. Su 20 pezzi mobili se ne spostano 3, segnati con un bollino.
Il 2×2 ha circa 3,7 milioni di stati. Il 3×3 circa 43 miliardi di miliardi. Controllandone uno al secondo dal Big Bang a oggi, ne avreste visto appena l’1%.
Eppure ogni 3×3 si risolve in al massimo 20 mosse (contando anche una mezza rotazione come una mossa). È il “numero di Dio”, dimostrato nel luglio 2010 da Rokicki, Kociemba, Davidson e Dethridge con circa 35 anni di calcolo di un processore, donati da Google e svolti in poche settimane.
Per un computer il cubo è un elenco di 54 adesivi, ognuno con posizione e colore. Una mossa è una funzione: prende un cubo e restituisce un cubo nuovo. Qui sotto vedi i dati cambiare a ogni mossa.
Il programma Python a fianco è completo e funziona. Calcola anche i periodi della sezione 2. In Scratch: una lista di 54 elementi e un blocco personalizzato per ogni mossa.
"""cubo.py - un cubo di Rubik 3x3 in poche righe.
Il cubo e' un DATO: un dizionario (posizione, normale) -> colore.
Le mosse sono FUNZIONI: prendono un cubo e ne restituiscono uno nuovo.
Stesso input, stesso output. Sempre.
"""
import random
# normale della faccia -> nome (e colore) della faccia
FACCE = {(0, 1, 0): "U", (0, -1, 0): "D", (1, 0, 0): "R",
(-1, 0, 0): "L", (0, 0, 1): "F", (0, 0, -1): "B"}
# faccia -> (asse, verso): x=0, y=1, z=2
ASSE = {"U": (1, 1), "D": (1, -1), "R": (0, 1),
"L": (0, -1), "F": (2, 1), "B": (2, -1)}
def risolto():
cubo = {}
for n, faccia in FACCE.items():
i = n.index(1) if 1 in n else n.index(-1)
for a in (-1, 0, 1):
for b in (-1, 0, 1):
p = [a, b]
p.insert(i, n[i]) # il pezzo sta sulla faccia n
cubo[(tuple(p), n)] = faccia
return cubo
def ruota90(v, i):
"""Rotazione di +90 gradi attorno all'asse i (regola della mano destra)."""
x, y, z = v
return ((x, -z, y), (z, y, -x), (-y, x, z))[i]
def mossa(cubo, m):
"""Applica una mossa (es. "R", "U'", "F2") e restituisce un nuovo cubo."""
i, verso = ASSE[m[0]]
giri = 3 if verso == 1 else 1 # orario visto dalla faccia
if m.endswith("'"):
giri = 4 - giri
elif m.endswith("2"):
giri = 2
nuovo = {}
for (p, n), colore in cubo.items():
if p[i] == verso: # il pezzo e' nello strato che gira
for _ in range(giri):
p, n = ruota90(p, i), ruota90(n, i)
nuovo[(p, n)] = colore
return nuovo
def esegui(cubo, sequenza):
for m in sequenza.split():
cubo = mossa(cubo, m)
return cubo
def e_risolto(cubo):
return all(FACCE[n] == colore for (p, n), colore in cubo.items())
def periodo(sequenza):
"""Quante volte ripetere la sequenza prima di tornare al cubo risolto."""
cubo, volte = esegui(risolto(), sequenza), 1
while not e_risolto(cubo):
cubo, volte = esegui(cubo, sequenza), volte + 1
return volte
def mescola(n=20):
mosse, ultima = [], ""
while len(mosse) < n:
f = random.choice("UDRLFB")
if f != ultima:
mosse.append(f + random.choice(["", "'", "2"]))
ultima = f
return " ".join(mosse)
if __name__ == "__main__":
for s in ["R", "R U", "R U R' U'", "R U2"]:
print(f"{s:10} -> periodo {periodo(s)}")
m = mescola()
c = esegui(risolto(), m)
print("mescolato:", m, "| risolto?", e_risolto(c))