Torre di Hanoi: domande frequenti

Ce n'è uno, ed è meccanico più che ingegnoso: a ogni mossa dispari, sposta il disco più piccolo di una torre nella stessa direzione — a sinistra se il numero di dischi è dispari, a destra se è pari, ricominciando dall'altro capo, così che con tre dischi la sua primissima mossa va da A a C. A ogni mossa pari c'è sempre una sola mossa valida che non tocca il disco più piccolo, quindi la fai senza pensarci. Alternando le due giochi una partita perfetta senza pianificare nemmeno un passo. La pagina delle strategie lo sviluppa.

Parti con l'intera pila sulla torre di sinistra, il disco più piccolo in cima. L'obiettivo è la stessa pila sulla torre di destra. Tre regole: un disco alla volta, sempre quello in cima a una torre, e mai un disco più grande su uno più piccolo. Con tre dischi la partita più breve sono sette mosse in tre gruppi: A→C, A→B, C→B costruisce i due dischi più piccoli sulla torre centrale; A→C fa passare il disco più grande; e B→A, B→C, A→C ricostruisce quei due sopra di lui. Come si gioca, con un tavolo di prova.

Facile da imparare, e difficile in un solo modo: diventa lunga il doppio a ogni disco che aggiungi. Tre dischi sono sette mosse, e la maggior parte delle persone — bambini dai sei anni circa — ci riesce al primo tentativo. Verso i cinque o sei dischi il procedere per tentativi smette di funzionare e serve un metodo, e la parte difficile del metodo è fidarsi di mosse che sembrano tornare indietro, come ammucchiare un'intera pila sulla torre centrale quando l'obiettivo è a destra. Una volta capita l'idea ricorsiva, ogni dimensione è lo stesso rompicapo. Perché l'idea ricorsiva è tutto il rompicapo.

Non esiste un ente che omologhi i record di velocità della Torre di Hanoi come accade per il cubo di Rubik, quindi i tempi dichiarati non sono confrontabili e di solito non dicono nemmeno con quanti dischi si è giocato, che è l'unico numero che conta. Meglio calcolarlo: una partita perfetta con n dischi richiede 2ⁿ − 1 mosse, e un giocatore allenato regge circa due mosse al secondo. Sono circa quattro secondi per tre dischi, sui nove minuti per dieci dischi e le loro 1.023 mosse, e circa quattro ore e mezza per 15 dischi e le loro 32.767. Il tavolo di questo sito ricorda il tuo minor numero di mosse per ogni numero di dischi nel browser e mostra il tuo tempo nella schermata del risultato. La calcolatrice dà il tempo per ogni dimensione.

2ⁿ − 1, ed è un limite dimostrato, non il miglior risultato noto. Tre dischi richiedono 7 mosse, quattro 15, cinque 31, dieci 1.023 e 15 32.767. La dimostrazione ha due metà: il metodo ricorsivo raggiunge quel numero, e nessuna soluzione può fare meglio, perché il disco più grande deve muoversi almeno una volta e tutti i dischi più piccoli sopra di lui vanno prima spostati sulla torre d'appoggio e poi riportati indietro. Entrambe le metà della dimostrazione, per intero.

T(n) = 2·T(n − 1) + 1, con T(0) = 0. Si legge direttamente dal metodo: per spostare n dischi togli di mezzo n − 1 dischi, porti un disco dall'altra parte e riporti quegli n − 1 dischi — due soluzioni più piccole più una singola mossa. Sviluppandola si ottiene T(n) = 2ⁿ − 1, che puoi verificare per induzione: se T(n − 1) = 2ⁿ⁻¹ − 1 allora T(n) = 2(2ⁿ⁻¹ − 1) + 1 = 2ⁿ − 1. Risolvere la ricorrenza, passo dopo passo.

Non in senso computazionale, nonostante il numero esponenziale di mosse. L'algoritmo è lungo poche righe, decidere la mossa successiva richiede tempo costante, e la soluzione è esponenzialmente lunga solo perché lo è la risposta: stampare 2ⁿ − 1 mosse non si può fare in meno di 2ⁿ − 1 passi. Non è NP-difficile, e anche trovare il percorso più breve tra due posizioni valide qualsiasi su tre pioli si risolve in modo efficiente. La versione davvero difficile è quella a quattro pioli, la cui soluzione ottimale fu congetturata nel 1941 e dimostrata solo nel 2014 da Thierry Bousch. L'algoritmo e quanto costa.

Con il metodo di Frame–Stewart. Con quattro pioli non sposti più n − 1 dischi in blocco: scegli un taglio k, porti i k dischi in alto su un piolo libero usando tutti e quattro i pioli, porti i restanti n − k dischi all'arrivo usando solo tre pioli — quello libero è occupato, quindi questa parte è il rompicapo classico — e poi rimetti sopra i k dischi. Provando ogni k e tenendo il migliore si ottiene il conteggio ottimale, che crolla in modo spettacolare: 15 dischi scendono da 32.767 mosse su tre pioli a 129 su quattro. Gioca al rompicapo a quattro pioli.

Divide et impera, espresso come ricorsione. La soluzione standard è una sola funzione — sposta n − 1 dischi dalla partenza al piolo libero, sposta il disco n dalla partenza all'arrivo, sposta quegli n − 1 dischi dal libero all'arrivo — con un caso base che non fa nulla quando n arriva a zero. Esiste un algoritmo iterativo equivalente che non usa affatto la ricorsione: spostare ripetutamente il disco più piccolo di una torre in una direzione fissa e poi fare l'unica altra mossa valida. Entrambi producono esattamente la stessa sequenza di mosse, perché la soluzione ottimale è unica. L'algoritmo, riga per riga.

Una funzione ricorsiva e tre parametri: void hanoi(int n, char from, char to, char via) — se n è zero, return; altrimenti chiama hanoi(n − 1, from, via, to), stampa la mossa from → to e poi chiama hanoi(n − 1, via, to, from). Invocala come hanoi(3, 'A', 'C', 'B'). Raccogli le mosse in un std::vector<std::pair<char, char>> invece di stamparle se chi chiama ne ha bisogno, e lascia n come semplice int: con un parametro senza segno, un conteggio negativo passato per errore diventa in silenzio circa quattro miliardi, e la ricorsione va avanti fino a far traboccare lo stack invece di fallire un semplice controllo n &lt; 0. Il programma C++ completo, spiegato riga per riga.

Sono due usi diversi di uno stack, e conviene tenerli separati. I pioli sono stack: ogni torre è last-in-first-out, tocchi sempre solo il disco in cima, e una mossa è un pop da una torre e un push su un'altra — ed è per questo che il controllo della regola è un unico confronto con la cima della destinazione. A parte, uno stack esplicito può sostituire la ricorsione: inserisci l'intero lavoro (n, from, to, via), poi ripeti: estrai un lavoro e, se ha ancora dischi, inserisci le sue tre parti in ordine inverso: il secondo trasferimento, la singola mossa del disco n, poi il primo trasferimento. L'ordine inverso conta perché uno stack restituisce per primo l'ultimo elemento inserito. È esattamente ciò che il runtime del linguaggio fa per te nella versione ricorsiva. La soluzione senza alcuna ricorsione.

Nell'IA il rompicapo è un problema di ricerca, non una formula. Ogni stato è un'assegnazione di ogni disco a un piolo, quindi ce ne sono 3ⁿ, e le mosse valide sono gli archi tra di essi; una ricerca — in ampiezza, A* o IDA* con un'euristica come il numero di dischi non ancora sul piolo di arrivo — trova il percorso più breve dallo stato iniziale all'obiettivo. È un problema di prova classico fin dal General Problem Solver di Newell, Shaw e Simon, perché è un esempio pulito di analisi mezzi-fini e di scomposizione degli obiettivi: il sotto-obiettivo «spostare il disco più grande» si raggiunge solo soddisfacendo prima un sotto-obiettivo che sembra annullare i progressi. Nota: l'algoritmo ricorsivo non è una ricerca — è la soluzione nota, e non esplora mai uno stato che non userà. Lo stesso rompicapo come compito psicologico.