Torre di Hanoi

Gioca alla Torre di Hanoi online

Il tavolo in cima a questa pagina è un gioco gratuito della Torre di Hanoi che funziona nel tuo browser: niente da scaricare, nessun account da creare. Scegli da 3 a 15 dischi e sposta l'intera pila dalla torre di sinistra a quella di destra.

• Telefono o tablet: tocca una torre per sollevare il disco in cima, poi toccane un'altra per posarlo.
• Mouse: trascina un disco, oppure fai clic su una torre e poi su un'altra.
• Tastiera: ← e → scelgono la torre, ↑ solleva e ↓ posa; 1, 2 e 3 vanno direttamente alle torri A, B e C, e Esc rimette giù il disco.

Sbagliare non costa nulla. Annulla riprende la tua ultima mossa, Ricomincia riparte con la stessa dimensione e Suggerimento solleva il disco che la soluzione più breve muoverebbe dopo e dice dove va. Una mossa la gioca al posto tuo. E se preferisci guardare, Risolvi in automatico completa il rompicapo da dove si trova il tavolo, non solo dall'inizio.

Non si conta nulla finché non muovi. Dopo la prima mossa il pannello mostra:

• le tue mosse, un cronometro e un punteggio di efficienza: la tua partita come percentuale di una perfetta;
• se sei ancora sul percorso ottimale, o di quante mosse te ne sei allontanato.

La cronologia sotto il tavolo registra l'intera partita. Torna a qualsiasi posizione precedente, o riproducila a 0,5×, 1×, 2× o 4×; la stessa velocità scandisce Risolvi in automatico. La modalità concentrazione toglie di mezzo tutto tranne le torri, e la pagina ricorda con quanti dischi hai giocato l'ultima volta. Alla fine, la schermata del risultato confronta le tue mosse con il minimo e ti propone un disco in più.

Il problema della Torre di Hanoi

Il problema parte da tre torri e da una pila di dischi di dimensioni diverse su una di esse, il più grande in basso. L'obiettivo è spostare l'intera pila su un'altra torre, rispettando tre regole:

1. Si sposta un disco alla volta.
2. Si può muovere solo il disco in cima a una torre.
3. Un disco più grande non può mai stare su uno più piccolo.

Questo è tutto il rompicapo, e si impara in circa un minuto. È la terza regola a renderlo difficile: ogni disco deve aspettare in un posto consentito mentre si spostano quelli sotto, e con sole tre torri lo spazio non basta mai. Come si gioca alla Torre di Hanoi le mostra per immagini, con un tavolo di prova e un esempio svolto.

Il matematico francese Édouard Lucas pubblicò il rompicapo nel 1883. Un anno dopo, un articolo di rivista che lo presentava aggiunse la leggenda che lo ha reso famoso: sacerdoti bramini che spostano sessantaquattro dischi d'oro, e la fine del mondo quando avranno finito. A una mossa al secondo ci vorrebbero circa 585 miliardi di anni.

Mosse minime e la formula 2ⁿ − 1

Il numero minimo di mosse per una Torre di Hanoi con n dischi è 2ⁿ − 1, spesso scritto 2^n − 1. Tre dischi richiedono 7 mosse, quattro ne richiedono 15, e la Torre di Hanoi con 5 dischi richiede almeno 31 mosse. È un limite dimostrato, non un record: per nessuna dimensione esiste una soluzione più breve, ed è il numero con cui ti misura il punteggio di efficienza del tavolo.

L'equazione dietro la formula

L'equazione discende direttamente dalle regole. Prima che il disco più grande possa muoversi, gli n − 1 dischi sopra di lui devono essere impilati sulla torre d'appoggio; poi attraversa; poi quei dischi tornano sopra di lui. Scrivendo T(n) per il minor numero di mosse che fa tutto questo:

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

Ogni dimensione costa il doppio di quella sotto, più uno: 1, 3, 7, 15, 31, 63. Ognuno di questi numeri è una potenza di due meno uno, ed è da qui che viene la forma chiusa T(n) = 2ⁿ − 1. La dimostrazione che 2ⁿ − 1 è il minimo affronta entrambe le metà dell'affermazione — perché quel numero di mosse basta sempre e perché meno è impossibile — e la calcolatrice delle mosse minime dà il conteggio esatto per qualsiasi numero di dischi fino a sessantaquattro.

Mosse minime per numero di dischi

Ogni dimensione rimanda alla sua soluzione completa, con tutte le mosse elencate e giocate su un tavolo. La partita più grande qui è di 15 dischi, cioè 32.767 mosse: ogni disco aggiunto raddoppia la durata della partita, più una mossa.

L'algoritmo della Torre di Hanoi e la ricorsione

L'equazione qui sopra è anche l'algoritmo, letta come istruzioni. Per spostare n dischi da una torre di partenza a una di arrivo:

1. Sposta n − 1 dischi dalla partenza alla torre d'appoggio.
2. Sposta il disco più grande dalla partenza all'arrivo.
3. Sposta gli n − 1 dischi dalla torre d'appoggio all'arrivo.

I passi 1 e 3 sono lo stesso problema con un disco in meno, quindi l'algoritmo li risolve chiamando se stesso, e una chiamata senza dischi da spostare semplicemente ritorna. Questa è la ricorsione della Torre di Hanoi al completo, ed è per questo che quasi ogni corso di informatica usa questo rompicapo per insegnare la ricorsione. Il trucco è non cercare di immaginare tutte le mosse insieme: fidati che la chiamata più piccola faccia il suo lavoro, e i tre passi sono l'intera soluzione.

Poiché l'algoritmo fa esattamente 2ⁿ − 1 mosse, il suo tempo di esecuzione è O(2ⁿ), e niente può fare di meglio: ognuna di quelle mosse va fatta. La memoria che usa è invece solo O(n). La pagina dell'algoritmo della Torre di Hanoi esegue il codice riga per riga accanto a un tavolo dal vivo e disegna l'albero delle chiamate man mano, e la soluzione iterativa produce le stesse mosse con due regole e un ciclo.

La Torre di Hanoi in Python, Java e altri linguaggi

I tre passi si traducono quasi parola per parola in codice. La Torre di Hanoi in Python è una funzione di sette righe: un caso base per zero dischi, due chiamate ricorsive e l'unica riga tra le due che stampa una mossa. La Torre di Hanoi in Java è lo stesso metodo dentro una classe, e il posto dove scoprire perché il conteggio per sessantaquattro dischi non entra in un long. Ci sono programmi completi anche in C, C++, C# e JavaScript.

Ogni listato è stato eseguito e il suo output verificato con il risolutore di questo sito, e ognuno è accompagnato da una spiegazione che dice perché ogni riga è lì, non che cosa fa la sintassi.

Altri modi di giocare e di imparare

Quando tre torri e una pila completa ti sembreranno facili, c'è altro da provare:

• La sfida del giorno — una posizione mescolata, uguale per tutti, nuova a mezzanotte UTC. Risolvila senza il risolutore per tenere viva la serie.
• Il risolutore — ogni mossa della soluzione più breve da qualsiasi posizione valida, compresa quella in cui sei bloccato su questo tavolo.
• Strategie — l'unica idea che si ripete dietro ogni dimensione, e una regola che ti dice la mossa successiva senza pianificare.
• Varianti — quattro torri invece di tre, un anello dove i dischi girano in un solo senso, due colori da separare e una posizione iniziale casuale.
• Per insegnanti — una lezione da 45 minuti, una scheda stampabile con le soluzioni e un tavolo da incorporare in una pagina del corso.

Domande frequenti

Che cos'è la Torre di Hanoi?

La Torre di Hanoi è un rompicapo con tre torri e una pila di dischi di dimensioni diverse. Si sposta l'intera pila da una torre a un'altra, un disco alla volta, e un disco più grande non può mai stare su uno più piccolo. Lo pubblicò il matematico francese Édouard Lucas nel 1883.

Posso giocare gratis alla Torre di Hanoi online?

Sì. Il tavolo di questa pagina è gratuito, funziona in qualsiasi browser moderno su telefono, tablet o computer, e non richiede download né account. Il numero di dischi dell'ultima partita e i tuoi record vengono salvati nel tuo browser, non su un server.

Qual è il numero minimo di mosse nella Torre di Hanoi?

Una partita perfetta con n dischi richiede 2ⁿ − 1 mosse. Tre dischi ne richiedono 7, cinque 31 e 15 dischi 32.767. Non esiste una soluzione più breve, quindi quel numero è un limite fisso, non solo un obiettivo.

Come si risolve la Torre di Hanoi?

Ogni soluzione è la stessa idea ripetuta: per portare una pila di n dischi all'arrivo, togli prima di mezzo gli n − 1 dischi in alto spostandoli sulla torre d'appoggio, porta dall'altra parte il disco più grande, poi riporta quegli n − 1 dischi sopra di lui. La pila più piccola obbedisce esattamente alla stessa regola, ed è per questo che un solo metodo risolve ogni dimensione.

C'è una scorciatoia per sapere la mossa successiva?

Sì. A ogni mossa dispari, sposta il disco più piccolo di una torre in una direzione fissa: a sinistra se il numero di dischi è dispari, a destra se è pari, ricominciando dall'altro capo — con tre dischi, la sua primissima mossa va quindi da A a C. A ogni mossa pari, fai l'unica mossa valida che non tocca il disco più piccolo. Alternando le due giochi una partita perfetta senza pianificare nulla.

Con quanti dischi posso giocare qui?

Da 3 a 15 dischi. Comincia con 3 per capire la forma della soluzione, poi aggiungine uno alla volta: ogni disco in più raddoppia più o meno il lavoro.

Posso annullare una mossa o rivedere la partita?

Sì. C'è un pulsante per annullare, e ogni partita conserva anche una cronologia completa: torna a qualsiasi posizione precedente e il tavolo mostra esattamente quello stato, oppure riproduci la partita a quattro velocità per vedere dove hai lasciato il percorso ottimale.