Torre di Hanoi
La Torre di Hanoi (anche conosciuta come Torre di Lucas dal nome del suo inventore) è un rompicapo matematico composto da tre paletti e un certo numero di dischi di grandezza decrescente, che possono essere infilati in uno qualsiasi dei paletti.
Il gioco inizia con tutti i dischi incolonnati su un paletto in ordine decrescente, in modo da formare un cono. Lo scopo del gioco è portare tutti i dischi su un paletto diverso, potendo spostare solo un disco alla volta e potendo mettere un disco solo su un altro disco più grande, mai su uno più piccolo.
Indice
Origini[modifica | modifica wikitesto]
Il gioco fu inventato nel 1883[1] dal matematico francese Édouard Lucas che diffuse il gioco sotto lo pseudonimo di N. Claus de Siam, mandarino del collegio di Li-Sou-Stian.[2] La leggenda secondo la quale in un tempio Indù alcuni monaci sono costantemente impegnati a spostare su tre colonne di diamante 64 dischi d'oro secondo le regole della Torre di Hanoi (a volte chiamata Torre di Brahmā), è stata inventata dalla ditta che per prima ha messo in commercio il rompicapo. La leggenda narra che quando i monaci completeranno il lavoro, il mondo finirà. Esistono anche versioni videoludiche del rompicapo.[3][4][5][6]
Soluzione[modifica | modifica wikitesto]
La proprietà matematica base è che il numero minimo di mosse necessarie per completare il gioco è , dove n è il numero di dischi. Ad esempio avendo 3 dischi, il numero di mosse minime è 7. Di conseguenza, secondo la leggenda, i monaci di Hanoi dovrebbero effettuare almeno 18.446.744.073.709.551.615 mosse prima che il mondo finisca, essendo . In altre parole, anche supponendo che i monaci facciano una mossa al secondo il mondo finirà tra 5.845.580.504 secoli, un tempo così lungo che quando il sole diverrà una gigante rossa e brucerà la Terra, il gioco non sarà stato completato.[7]
La soluzione generale è data dall'algoritmo seguente.
Algoritmo ricorsivo[modifica | modifica wikitesto]
La soluzione base del gioco della torre di Hanoi si formula in modo ricorsivo.[8][9]
Siano i paletti etichettati con A, B e C, e i dischi numerati da 1 (il più piccolo) a n (il più grande). L'algoritmo si esprime come segue:
- Sposta i primi n-1 dischi da A a B. (Questo lascia il disco n da solo sul paletto A)
- Sposta il disco n da A a C
- Sposta n-1 dischi da B a C
Per spostare n dischi si richiede di compiere un'operazione elementare (spostamento di un singolo disco) ed una complessa, ossia lo spostamento di n-1 dischi. Tuttavia anche questa operazione si risolve nello stesso modo, richiedendo come operazione complessa lo spostamento di n-2 dischi. Iterando questo ragionamento si riduce il processo complesso ad uno elementare, ovvero lo spostamento di n-(n-1)=1 disco.
Questo è un algoritmo ricorsivo,[8] di complessità esponenziale.
È interessante notare che il rompicapo è risolvibile per qualsiasi "n", con una dimostrazione per ricorrenza: Supponiamo di avere una torre in A composta da N dischi, e supponiamo che N sia il numero massimo di dischi ammessi per risolvere il gioco. Al termine dello spostamento della torre da A a B, aggiungiamo un ulteriore disco ad A, di grandezza pari a N+1, e ipotizziamo che questo disco sia stato fermo tutto il tempo sotto gli altri. A questo punto, spostiamo semplicemente il disco da A a C, e certamente riusciremo a spostare la torre da B a C, seguendo gli stessi passaggi che si sono resi necessari per spostarla da A a B. Avendo dimostrato che una torre di N dischi è spostabile da una colonna all'altra, è dimostrato che si può spostare anche una torre di N+1 dischi.
Note[modifica | modifica wikitesto]
- ^ (EN) Lucas summary, su www-history.mcs.st-and.ac.uk.
- ^ (EN) The Tower of Hanoi, su cs.wm.edu.
- ^ (EN) Hanoi: Sega Dreamcast Game Console (Animated), su kernelthread.com.
- ^ (EN) Hanoi: Nintendo Gameboy Advance Handheld (Animated), su kernelthread.com.
- ^ Francesco Sblendorio, Torri di Hanoi per MS-DOS & Windows, su sblendorio.eu, 1996.
- ^ (EN) Francesco Sblendorio, Towers of Hanoi - CP/M generic version and C128 specific, su github.com, 2015.
- ^ Progetto Polymath - La torre di Hanoi, su areeweb.polito.it.
- ^ a b (EN) Tower of Hanoi, su cut-the-knot.org.
- ^ www.matematicamente.it (PDF), su matematicamente.it.
Bibliografia[modifica | modifica wikitesto]
- Martin Gardner, Il gioco dell'icosaedro e la torre di Hanoi, in Enigmi e giochi matematici, Milano, Rizzoli, 2001 [1959], ISBN 88-17-12747-7.
Voci correlate[modifica | modifica wikitesto]
- Test della torre di Londra, test di tipo neuropsicologico con similarità al rompicapo
- Problema del lupo, della capra e dei cavoli
- Torre di Babele
Altri progetti[modifica | modifica wikitesto]
Wikimedia Commons contiene immagini o altri file su Torre di Hanoi
Collegamenti esterni[modifica | modifica wikitesto]
- (EN) Hanoimania, più di 100 implementazioni del problema della Torre di Hanoi, su kernelthread.com. URL consultato il 21 novembre 2004 (archiviato dall'url originale l'11 febbraio 2004).
- (EN) Tower of Hanoi (3-10 pedine, HTML dinamica)
- Gioco sulle Torri di Hanoi, su giochieflash.it.
- Programma in C Risolutivo Algoritmo Torri di Hanoi, su digilander.libero.it.
- Prestazioni di PHP, JavaScript, Ruby, Java e C++ a confronto nella soluzione della Torre di Hanoi, su marcovisona.it.
- Gioco Torri di Hanoi max 8 pedine, su comunedasa.it.
- Torri di Hanoi per MS-DOS & Windows, su sblendorio.eu.
- (EN) Towers of Hanoi - CP/M version, su github.com.
- Playable Tower of Hanoi in BASIC for Olivetti M10 / Tandy TRS-80 Model 100, su github.com.
