Calcolatrice della Torre di Hanoi

Quanto tempo è davvero

I numeri qui sopra sono esatti e, da soli, non insegnano quasi nulla: passati alcuni miliardi, un numero enorme somiglia molto a un altro. Quello che l'aritmetica sta davvero facendo si vede meglio di quanto si racconti. Poiché ogni disco in più raddoppia il lavoro, un righello con i dischi a distanze uguali è un righello con intervalli di tempo che si moltiplicano — e tutta la distanza fra una pausa caffè (dieci dischi, diciassette minuti) e l'età dell'universo (cinquantanove dischi) risulta essere di circa cinquanta passi.

• 1 disco — 1 mossa — 1 secondo: la prima dimensione che arriva a un secondo.
• 6 dischi — 63 mosse — 1 minuto: la prima dimensione che arriva a un minuto.
• 12 dischi — 4095 mosse — 1 ora: la prima dimensione che arriva a un'ora.
• 17 dischi — 131.071 mosse — 1 giorno: la prima dimensione che arriva a un giorno.
• 25 dischi — 33.554.431 mosse — 1 anno: la prima dimensione che arriva a un anno.
• 32 dischi — 4.294.967.295 mosse — 136 anni: la prima dimensione che arriva a una vita umana.
• 38 dischi — 274.877.906.943 mosse — 8,71 mila anni: la prima dimensione che arriva a tutta la storia scritta.
• 59 dischi — 576.460.752.303.423.487 mosse — 18,3 miliardi di anni: la prima dimensione che arriva a l'età dell'universo.

La fascia ombreggiata vicino a sinistra è tutto ciò che qui puoi davvero giocare. Undici dischi sono una seduta lunga; venticinque sono un anno di mosse ininterrotte; cinquantanove superano l'età dell'universo. Lungo quell'asse le regole non cambiano mai: cambia solo il conteggio.

La formula

Una partita perfetta di n dischi richiede esattamente 2ⁿ − 1 mosse — la formula della Torre di Hanoi, che si scrive anche 2^n − 1 dove gli esponenti non sono a portata di mano. Non è il record di qualcuno: è un limite inferiore dimostrato. Perché il disco più grande possa muoversi, tutti i dischi più piccoli devono essere impilati fuori strada sulla torre d'appoggio, e una volta che è passato devono tornare tutti sopra di lui. Due trasferimenti completi di n − 1 dischi, più una mossa:

T(n) = 2·T(n − 1) + 1, a partire da T(0) = 0: senza dischi, nessuna mossa.

1. 1Sposta gli n−1 dischi che ha sopra sulla torre d'appoggio. Finché non sono tolti di mezzo, non può succedere nient'altro.

2. 2Il disco più grande ora è libero e la sua torre di arrivo è vuota. Passa con una sola mossa, l'unica che serve in questa fase.

3. 3Ricostruisci sopra di esso la pila di n−1 dischi. È lo stesso problema con un disco in meno, fino ad arrivare a un solo disco che si sposta in una mossa.

Srotolandola si ottiene 1, 3, 7, 15, 31, 63 — ognuno il doppio del precedente più uno, cioè la successione dei numeri che stanno appena sotto una potenza di due. Ogni disco aggiunto fa poco più che raddoppiare il lavoro, ed è per questo che il rompicapo passa da una pausa caffè a più di quanto l'universo sia esistito in meno di cinquanta passi.

La stessa ricorrenza è all'origine della fama del rompicapo nei corsi di informatica. Poiché il lavoro raddoppia a ogni disco, la soluzione ricorsiva gira in tempo O(2ⁿ) — e dietro non si nasconde nessun algoritmo più furbo, visto che il numero di mosse è esso stesso esponenziale e ogni mossa va prodotta. Quello che non costa è memoria: la ricorsione scende un disco alla volta, quindi tiene O(n) record di attivazione — uno per disco più uno per il caso base: sedici per le torri più grandi qui, sessantacinque per la leggenda. La derivazione completa, e il motivo per cui questa non è una ricorrenza a cui si applica il Teorema Master, sono nella pagina dell'algoritmo della Torre di Hanoi.

Mosse minime per numero di dischi

Queste sono le dimensioni giocabili qui. La fascia di difficoltà è la stessa che le torri mostrano accanto al selettore dei dischi, e ogni numero di dischi porta all'elenco di mosse che lo risolve.

Oltre le torri

Oltre i 15 dischi il rompicapo smette di essere qualcosa da giocare e diventa qualcosa da calcolare. I conteggi restano esatti — semplicemente non sono più raggiungibili in una vita umana.

Questi numeri hanno un nome

Un numero che sta appena sotto una potenza di due è un numero di Mersenne, scritto M_n = 2ⁿ − 1 — quindi ogni cifra nelle tabelle qui sopra lo è, e il numero di mosse di una partita della Torre di Hanoi non è mai altro. Quando un numero di Mersenne si dà il caso che sia primo, è un primo di Mersenne, e sono proprio questi i numeri su cui da decenni corre la caccia ai primi da record, perché 2ⁿ − 1 è molto più economico da verificare di un numero qualsiasi della stessa taglia.

M_n può essere primo solo quando è primo anche n, ma da solo non basta — e il controesempio è una partita che puoi giocare qui. Undici è primo; le sue 2047 mosse non lo sono, dato che 2047 = 23 × 89. Fra le dimensioni di queste torri, quelle il cui numero di mosse è primo sono 3, 5, 7 e 13 dischi. OEIS A000225 è la successione completa.

La leggenda dei sessantaquattro dischi

Il rompicapo andò in vendita nel 1883 e, nel giro di un anno, aveva già la sua storia: in un tempio di Benares alcuni sacerdoti spostano sessantaquattro dischi d'oro fra tre aghi di diamante, e quando l'ultimo disco sarà posato il mondo finirà. L'aritmetica rassicura. Sessantaquattro dischi richiedono 18.446.744.073.709.551.615 mosse e, a una mossa al secondo, fanno 585 miliardi di anni — circa quaranta volte l'età attuale dell'universo.

Domande frequenti

Quante mosse richiede la Torre di Hanoi?

Il minimo è 2ⁿ − 1 mosse per n dischi. Tre dischi ne richiedono 7, cinque 31, dieci 1023 e venti 1.048.575. Ogni disco in più fa poco più che raddoppiare il totale, perché risolvere n dischi significa risolvere n − 1 dischi due volte con una mossa in mezzo.

Perché la formula è 2ⁿ − 1?

Per spostare n dischi bisogna prima togliere di mezzo gli n − 1 sopra, poi spostare una volta il disco più grande, poi riportare quegli n − 1 sopra di lui. Ne viene T(n) = 2·T(n−1) + 1 con T(1) = 1, e srotolandola si ottiene 1, 3, 7, 15, 31 — ognuno il doppio del precedente più uno, cioè esattamente 2ⁿ − 1.

Qual è la complessità temporale della Torre di Hanoi?

O(2ⁿ). Ogni disco raddoppia il lavoro, quindi la soluzione ricorsiva fa 2ⁿ − 1 mosse, e nessun algoritmo può fare meglio: le mosse stesse vanno prodotte, e sono tante quante sono. Lo spazio è solo O(n): la ricorsione scende un disco alla volta, quindi tiene al massimo n + 1 record di attivazione insieme — ed è per questo che una chiamata a 64 dischi esaurirebbe la tua pazienza molto prima dello stack.

Quanto ci vorrebbe con 64 dischi?

Sessantaquattro dischi richiedono 18.446.744.073.709.551.615 mosse. A una mossa al secondo fanno 585 miliardi di anni — molto più dell'età attuale dell'universo, che è esattamente il senso della leggenda associata al rompicapo nel 1884.

Una soluzione può essere più breve di 2ⁿ − 1?

No. 2ⁿ − 1 è un limite inferiore dimostrato, non il miglior risultato noto: il disco più grande deve muoversi almeno una volta e, prima che possa farlo, tutti i dischi più piccoli non devono essere né sopra di lui né sulla sua destinazione. Questo impone i due sotto-trasferimenti, e l'argomento si ripete fino in fondo.

La calcolatrice vale per una partita già a metà?

Non questa pagina: 2ⁿ − 1 presuppone che tutti i dischi partano da una sola torre. Per la soluzione più breve da una posizione già avviata usa il risolutore, che calcola il percorso ottimale da qualsiasi disposizione valida. Apri il risolutore →