Il gioco della torre di Hanoi

Il rompicapo comincia con una pila di dischi di grandezza diversa infilati su un'asta, dal più largo in basso al più stretto in cima: è la configurazione iniziale. Lo scopo è ricostruire la stessa torre su un'altra asta. Le regole sono tre: si sposta un disco alla volta, si prende solo quello in cima a una pila e nessun disco va sopra un disco più piccolo.

Ogni asta ha un ruolo. L'asta di partenza, A, regge la torre all'inizio; l'asta di arrivo, C, è l'ultima a destra ed è segnata come «arrivo»; l'asta intermedia, B, fa da appoggio. Con quattro aste l'arrivo è la D. L'Enciclopedia della Matematica Treccani parla di dischetti forati e di tre pioli.

Sullo schermo si tocca un'asta per sollevare il disco in cima, poi l'asta su cui posarlo, oppure si trascina il disco. Da tastiera, dopo il tasto Tab, bastano i numeri o le lettere delle aste, ed Esc rimette giù il disco. Una mossa vietata non passa e il gioco spiega perché: «Il disco 2 non può andare sul disco 1».

Tre contatori seguono la partita: «Mosse», «Mosse minime» e «Tempo», che parte alla prima mossa. La prima partita ha 4 dischi, 15 mosse al minimo. Con tre aste si arriva a 10 dischi, con quattro a 8. Il limite è del sito: oltre, il suggerimento a quattro aste, che esamina ogni posizione, sarebbe troppo lento su un telefono.

Servono 2^n - 1 mosse, dove n è il numero dei dischi, e nessuna soluzione con tre aste ne usa meno: è il numero minimo di mosse. Con 3 dischi sono 7, con 5 sono 31, con 7 già 127. La successione 1, 3, 7, 15, 31 cresce così perché ogni disco in più raddoppia le mosse e ne aggiunge una, come notava Lucas nelle Récréations mathématiques.

Al ritmo di una mossa al secondo e senza errori, 4 dischi richiedono 15 s, 8 dischi 4 min 15 s e 10 dischi 17 min 3 s. Con i 64 dischi della leggenda le mosse diventano 18.446.744.073.709.551.615, un numero di 20 cifre. Il conto vale per una torre intera che parte da una sola asta: da una posizione mescolata possono bastarne meno.

Le fonti danno le stesse cifre: la tabella di Lucas 255 mosse per 8 dischi, l'Enciclopedia della Matematica Treccani 15 per 4 dischetti. Il gioco le ricontrolla nei casi verificati in fondo alla pagina.

La soluzione più breve con 5 dischi conta 31 mosse e comincia portando il disco più piccolo dall'asta A all'asta C. Il disco 5, il più grande, si muove una sola volta, alla mossa 16, mentre gli altri quattro sono impilati sull'asta B. Ecco la sequenza delle mosse completa; il disco 1 è il più piccolo.

Esiste anche una soluzione iterativa, che non chiede di ricordare a che punto si è. Il disco 1 si muove a mosse alterne e gira sempre nello stesso verso. Con un numero dispari di dischi va da A a C, poi a B e torna ad A. Con un numero pari va da A a B, poi a C.

Tra due mosse del disco 1 resta una sola mossa possibile che non lo tocca. Il minore dei due dischi in cima alle altre aste va sopra il maggiore, o sull'asta vuota. Treccani descrive questo metodo; Lucas lo attribuisce al nipote Raoul Olive, allievo del liceo Charlemagne.

Anche il disco da spostare a ogni passo segue una regola: 1, 2, 1, 3, 1, 2, 1, 4 e così via. È la sequenza del righello, la A001511 dell'enciclopedia OEIS. Alla mossa m si muove il disco che vale uno più il numero di zeri finali di m scritto in binario.

Lo stesso elenco compare sotto il tabellone, nel riquadro «La soluzione mossa per mossa», e si può stampare da solo. Con quattro aste segue la soluzione di Frame-Stewart, e ne esistono altre della stessa lunghezza.

Il disco più largo può muoversi solo quando gli altri sono tutti impilati sull'asta rimasta libera. Prima vanno quindi spostati n - 1 dischi, poi il disco di base fa la sua unica mossa, infine gli n - 1 dischi tornano sopra di lui. Ne nasce la relazione di ricorrenza M(n) = 2M(n - 1) + 1, con M(1) = 1.

La formula chiusa si dimostra per induzione. Con un disco basta una mossa, e 2^1 - 1 = 1. Se n - 1 dischi chiedono 2^(n-1) - 1 mosse, n dischi ne chiedono 2 × (2^(n-1) - 1) + 1 = 2^n - 1. Nessun metodo fa meglio, perché prima e dopo la mossa del disco di base gli altri devono comunque formare una torre su un'altra asta.

Lo stesso ragionamento si trova nella rivista Plus dell'Università di Cambridge e nel capitolo sulla ricorsione dell'Università di Princeton. L'enciclopedia OEIS elenca la successione alla voce A000225.

Contando disco per disco compaiono le potenze di due: il disco k si muove 2^(n-k) volte. Con 5 dischi le 31 mosse si dividono così, dal disco più piccolo al più grande: 16, 8, 4, 2 e 1. Per questo si parla di complessità esponenziale: con 20 dischi le mosse sono già 1.048.575, più di 291 ore a un secondo per mossa.

L'algoritmo ricorsivo riduce la torre a un sottoproblema identico, con un disco in meno. Per spostare n dischi da A a C si portano n - 1 dischi su B, usando C come appoggio. Poi il disco maggiore va su C, infine gli n - 1 dischi passano da B a C. Ogni spostamento di n - 1 dischi segue la stessa regola, fino a un disco solo.

Con 3 dischi la ricorsione dà proprio le 7 mosse della soluzione. Le prime 3 portano i due dischi piccoli su B e la quarta sposta il disco 3 da A a C. Le ultime 3 rimettono i piccoli sopra di lui.

La torre è così un esempio classico di ricorsione, la tecnica in cui una procedura richiama sé stessa su un caso più piccolo. La usano il capitolo di Princeton e le dispense di Fondamenti di Informatica T-1 dell'Università di Bologna, che ne presentano la soluzione ricorsiva. Un progetto d'esame dell'Università degli Studi di Milano, «Il gioco delle torri di Hanoi», chiama aste i tre paletti.

Con la partenza casuale i dischi sono sparsi sulle aste e vanno riuniti in una torre sull'asta di arrivo. Ogni disposizione è ugualmente probabile, ma il disco più grande non parte mai già sull'arrivo, quindi deve muoversi. Servono così almeno 2^(n-1) mosse e al massimo 2^n - 1.

Con 4 dischi il minimo va da 8 a 15 mosse, 12,7 in media sulle partenze ammesse. Su tutte le 81 posizioni, comprese quelle con il disco grande già a destinazione, la media è 10, due terzi di 15. È un conteggio esaustivo del sito. La posizione entra nel link, così chi lo riceve gioca la stessa partenza.

In generale n dischi su tre aste hanno 3^n disposizioni: 243 con 5 dischi, 59.049 con 10. Se ogni posizione è un punto e ogni mossa una linea, il grafo somiglia sempre più al triangolo di Sierpinski a ogni disco aggiunto. Lo spiega la rivista Plus, e ne trattano Hinz, Klavžar e Petr nel libro The Tower of Hanoi: Myths and Maths.

«Suggerimento» indica la prossima mossa di una strada più breve verso l'arrivo, ovunque siano i dischi, e illumina le due aste. «Risolvi» completa la partita da solo, da 0,9 a 0,045 secondi per mossa, con pausa, una mossa per volta e «Continua tu». «Annulla» toglie le mosse una a una, senza limiti.

Perché così la chiamò il suo inventore, Édouard Lucas, che nel 1883 la presentò come «la Tour d'Hanoï, véritable casse-tête annamite». Il nome richiama Hanoi, oggi capitale del Vietnam, ma il gioco è nato a Parigi.

La scatola diceva che l'aveva portato dal Tonchino il «professeur N. Claus (de Siam), mandarin du collège Li-Sou-Stian». Lo riferisce il Journal des Débats del 27 dicembre 1883, citato da Allardice e Fraser. Secondo il sito MacTutor dell'Università di St Andrews, N. Claus de Siam è l'anagramma di Lucas d'Amiens e Li-Sou-Stian quello di Saint Louis, il liceo dove Lucas insegnava.

Lucas stesso, nelle Récréations mathématiques del 1893, scrive che il gioco non viene dal Tonchino, «quoi qu'en dise le prospectus». Gioco e leggenda, aggiunge, sono nati al numero 56 di rue Monge, a Parigi. Secondo Treccani, Lucas era nato ad Amiens nel 1842 e morì a Parigi nel 1891. Nelle stesse Récréations descrisse anche il gioco dei quadratini, che qui si gioca come punti e linee.

La leggenda era già sul foglio del 1883. Nel grande tempio di Benares, in India, i bramini spostano giorno e notte la sacra torre di Brahma: 64 dischi d'oro puro su tre aghi di diamante. Muovono un disco per volta, mai uno grande su uno piccolo. Quando avranno finito, torre e bramini crolleranno e verrà la fine del mondo.

È un racconto inventato da Lucas, non una tradizione antica. L'anno seguente Henri de Parville lo riprese sulla rivista La Nature, come ricorda W. W. Rouse Ball nelle Mathematical Recreations and Essays. Per finire, i bramini dovrebbero fare 18.446.744.073.709.551.615 mosse.

Gli psicologi usano i compiti a torre per studiare la pianificazione e la soluzione dei problemi, perché ogni mossa rende visibile una scelta. Un articolo della rivista Plus, «The Tower of Hanoi: where maths meets psychology», lo riassume così: con questo rompicapo si vede la gente pensare.

Nel 1982 Tim Shallice descrisse un compito di pianificazione in uno studio sui disturbi specifici di questa capacità. Per uno studio dell'Università Erasmus di Rotterdam la Torre di Londra è uno strumento molto usato per misurarla. La meta-analisi di Sullivan, Riccio e Castillo (2009) esamina i compiti a torre come misure delle funzioni esecutive negli adulti.

Spesso ci si chiede che cosa potenzi la torre di Hanoi. Le fonti citate usano questi compiti per osservare la pianificazione, non per allenarla, e questo gioco non promette effetti sulla memoria. Non misura l'intelligenza né altre capacità e i suoi risultati non hanno valore clinico: è un rompicapo. Un altro classico della psicologia sperimentale si prova nel test di Stroop.