Tre pioli, una torre di dischi e pochissime regole: la Torre di Hanoi è un gioco in cui imparare a pianificare conta più della velocità. È anche un esempio concreto di ricorsione: risolvere un problema utilizzando la soluzione dello stesso problema, ma più piccolo.
Apri il laboratorio della Torre di Hanoi: gioca da 1 a 10 dischi
Prova prima con pochi dischi, poi confronta il tuo percorso con la soluzione animata.
Obiettivo e regole del gioco
I pioli si chiamano A, B e C. All’inizio tutti i dischi sono su A, dal più grande in basso al più piccolo in alto. Devi trasferire la torre intera su C; B è un appoggio temporaneo.
- Sposta un solo disco per volta.
- Puoi prendere soltanto il disco in cima a un piolo.
- Non puoi mai appoggiare un disco grande sopra uno più piccolo. Un piolo vuoto, invece, può ricevere qualsiasi disco.
Numeriamo i dischi dal più piccolo, 1, al più grande, n. Nei prossimi esempi le liste si leggono dal basso verso l’alto: [3, 2, 1] è la torre completa, mentre [] indica un piolo vuoto. Una mossa è il trasferimento di un disco, non ciascun clic dell’interfaccia.
Partiamo dal caso più semplice
Un disco: basta una mossa
Il disco 1 passa direttamente da A a C. Non c’è niente da liberare: questo è il più piccolo caso non vuoto del gioco.
Due dischi: prima libera quello grande
Non puoi spostare subito il disco 2 perché il disco 1 gli sta sopra. Ecco le tre mosse necessarie:
- Disco 1: A → B.
- Disco 2: A → C.
- Disco 1: B → C.
Il piolo d’appoggio non è una destinazione finale: serve per lasciare libero il disco che vuoi muovere.
Tre dischi: tutte le sette mosse
Per liberare il disco 3, trasferisci prima la piccola torre [2, 1] da A a B, usando C come appoggio. Poi porta il disco 3 su C e infine ricostruisci sopra di lui la torre [2, 1]. Il procedimento per due dischi è lo stesso, ma i pioli cambiano ruolo.
| Mossa | Disco | Trasferimento | A | B | C |
|---|---|---|---|---|---|
| 0 | — | Partenza | [3, 2, 1] | [] | [] |
| 1 | 1 | A → C | [3, 2] | [] | [1] |
| 2 | 2 | A → B | [3] | [2] | [1] |
| 3 | 1 | C → B | [3] | [2, 1] | [] |
| 4 | 3 | A → C | [] | [2, 1] | [3] |
| 5 | 1 | B → A | [1] | [2] | [3] |
| 6 | 2 | B → C | [1] | [] | [3, 2] |
| 7 | 1 | A → C | [] | [] | [3, 2, 1] |
La riga 0 descrive la partenza: non è una mossa. Dalla riga 1 alla riga 7 ogni riga trasferisce esattamente un disco e rispetta tutte le regole.
La strategia generale: un problema dentro il problema
Supponi di saper già trasferire una torre di n−1 dischi. Per trasferirne n da A a C:
- Porta gli n−1 dischi superiori da A a B, usando C come appoggio.
- Sposta il disco n da A a C.
- Porta gli n−1 dischi da B a C, usando A come appoggio.
![Tre configurazioni successive: A=[3], B=[2,1]; poi B=[2,1], C=[3]; infine C=[3,2,1]. I pioli non indicati sono vuoti.](/assets/images/editorial/hanoi-recursion-stages.svg)
«Trasferisci n−1 dischi» non significa spostarli in blocco: significa ripetere questa stessa ricetta con un disco in meno, fino al caso più semplice. Ogni trasferimento effettivo riguarda sempre un solo disco.
Questo pseudocodice rende espliciti i ruoli dei pioli. Con zero dischi non c’è nulla da spostare: è la condizione che ferma le chiamate ricorsive.
Hanoi(n, partenza, arrivo, appoggio):
se n = 0: termina
Hanoi(n−1, partenza, appoggio, arrivo)
sposta il disco n da partenza ad arrivo
Hanoi(n−1, appoggio, arrivo, partenza)La chiamata iniziale è Hanoi(n, A, C, B). A ogni chiamata cambiano i ruoli di partenza, arrivo e appoggio, non le regole del gioco.
Perché non si può fare meglio di 2ⁿ − 1?
Chiamiamo M(n) il minimo di mosse per trasferire una torre completa di n dischi tra due pioli. Prima di muovere per la prima volta il disco più grande, tutti gli altri devono stare insieme sul terzo piolo: servono almeno M(n−1) mosse. Il disco grande richiede almeno una mossa. Dopo il suo ultimo arrivo sul piolo finale, i dischi piccoli devono essere trasferiti dal terzo piolo sopra di lui: almeno altre M(n−1) mosse. Eventuali deviazioni non possono eliminare questi due trasferimenti obbligatori.
La strategia descritta realizza esattamente questi tre passaggi, senza mosse aggiuntive. Quindi il limite è raggiunto:
M(0) = 0
M(n) = 2 × M(n−1) + 1 = 2n − 1
Per verificare l’ultima uguaglianza, sostituisci M(n−1) con 2n−1 − 1: ottieni 2 × (2n−1 − 1) + 1 = 2n − 1. La base M(0) = 0 completa il ragionamento per induzione.
| Dischi | Minimo di mosse |
|---|---|
| 1 | 1 |
| 2 | 3 |
| 3 | 7 |
| 4 | 15 |
| 5 | 31 |
| 6 | 63 |
| 7 | 127 |
| 8 | 255 |
| 9 | 511 |
| 10 | 1023 |
Un disco in più quasi raddoppia il lavoro. A una mossa al secondo, 10 dischi richiedono 1023 secondi, cioè 17 minuti e 3 secondi, senza pause. Il numero di mosse cresce esponenzialmente: una regola breve può descrivere una procedura molto lunga.
Come usare il laboratorio
Entra nel laboratorio interattivo della Torre di Hanoi
- Scegli da 1 a 10 dischi: tutti i livelli sono disponibili subito.
- Tocca il piolo di partenza e poi quello di arrivo. Da tastiera usa Tab, Invio o Spazio.
- Con «Annulla mossa» correggi l’ultimo trasferimento; con «Ricomincia livello» riparti da zero.
- «Indizio» suggerisce senza spostare; «Un passo» esegue una mossa; «Avvia soluzione» mostra il percorso animato alla velocità scelta.
- La soluzione guidata continua dalla posizione attuale, anche dopo un tuo percorso diverso. «Pausa» lascia terminare la mossa già iniziata.
«Minimo iniziale» riguarda la torre di partenza; «Minimo ancora necessario» riguarda la posizione attuale. Se fai una deviazione, la somma delle mosse già fatte e di quelle ancora necessarie può superare il minimo iniziale. I record vengono aggiornati solo nelle partite manuali senza aiuti e rimangono in questo browser: non vengono inviati al sito.
Tre sfide prima di guardare la risposta
1. Con quattro dischi, qual è il minimo di mosse?
Mostra la soluzione ragionata
Con tre dischi servono 7 mosse. Per quattro ne servono 7 per liberare il disco 4, una per muoverlo e 7 per ricostruire la torre: 7 + 1 + 7 = 15. Anche la formula dà 2⁴ − 1 = 15.
2. Con tre dischi da A a C, perché conviene iniziare con il disco 1 da A a C, e non da A a B?
Mostra la soluzione ragionata
Prima devi trasferire [2, 1] da A a B. Per riuscirci in tre mosse, il disco 1 deve andare su C, poi il disco 2 su B e infine il disco 1 su B. A → B come prima mossa non è vietata, ma non permette di completare l’intera torre nel minimo di 7 mosse.
3. Hai fatto 4 mosse e il laboratorio ne indica almeno altre 5. Puoi finire in 7 mosse complessive?
Mostra la soluzione ragionata
No: dalla posizione attuale il miglior totale possibile è 4 + 5 = 9. La soluzione guidata ottimizza il percorso che resta, ma non cancella le mosse già fatte. Puoi annullare una deviazione o ricominciare per tentare il minimo iniziale.
Che cosa insegna questo gioco?
La Torre di Hanoi mostra come scomporre un compito, riconoscere un sottoproblema e fissare una condizione di arresto. La ricorsione non è un trucco per saltare passaggi: è un modo preciso per organizzarli, rispettando a ogni mossa lo stesso vincolo.
Riferimento per le regole, la strategia ricorsiva e il minimo di mosse: NIST — Dictionary of Algorithms and Data Structures: Towers of Hanoi.