Risolutore della Torre di Hanoi

Come funziona il risolutore

Il metodo è la logica del rompicapo stesso, eseguita in avanti. Perché il disco più grande possa posarsi sulla sua torre di arrivo, tutti i dischi più piccoli devono trovarsi altrove: per la precisione, impilati sull'unica torre rimasta. Così il risolutore chiede prima che quella pila più piccola vada là, fa passare il disco grande e poi chiede che la pila piccola torni sopra di esso. Ognuna di queste richieste è lo stesso problema con un disco in meno, fino a un solo disco, che si sposta in un passo.

Ciò che distingue questo risolutore da quelli che trattano solo una pila completa è una riga di ragionamento in più: se il disco più grande è già sulla sua torre di arrivo, per lui non c'è nulla da fare e l'intero problema si riduce ai dischi che stanno sopra. È proprio questo caso a permettergli di risolvere da una partita a metà invece di costringerti a ricominciare — ed è il motivo per cui le mosse che riporta da una posizione personalizzata sono meno di 2ⁿ − 1, spesso molte meno in una partita già avviata.

1. 1Sposta gli n−1 dischi che ha sopra sulla torre d'appoggio. Finché non sono tolti di mezzo, non può succedere nient'altro.

2. 2Il disco più grande ora è libero e la sua torre di arrivo è vuota. Passa con una sola mossa, l'unica che serve in questa fase.

3. 3Ricostruisci sopra di esso la pila di n−1 dischi. È lo stesso problema con un disco in meno, fino ad arrivare a un solo disco che si sposta in una mossa.

Leggere una soluzione

Ogni riga indica una mossa: quale disco, da quale torre parte e su quale arriva. Il disco 1 è il più piccolo. Non devi mai verificare se una mossa è valida: per come è costruito l'elenco, ogni mossa lo è già.

Da una pila completa saltano subito all'occhio due regolarità:

• Il disco più piccolo si muove una volta su due — le mosse 1, 3, 5 e così via — e gira sempre nello stesso verso fra le tre torri.
• Ogni mossa intermedia è l'unica mossa valida che non tocca il disco più piccolo.

Questo è tutto il metodo iterativo, e si legge direttamente in qualsiasi soluzione che parta da una pila completa. Da una posizione personalizzata l'elenco resta il più breve, ma è cucito insieme da trasferimenti più piccoli, quindi il disco più piccolo può cambiare verso a metà strada. La soluzione iterativa mostra perché il metodo funziona, e la guida alle strategie lo trasforma in qualcosa con cui giocare. Per la ricorsione vera e propria, seguita riga per riga in sei linguaggi, vedi l'algoritmo della Torre di Hanoi.

Anche le dimensioni più comuni hanno una pagina ciascuna, con tutte le mosse e ciò che è particolare di quella dimensione: le soluzioni da 3 a 10 dischi e i 64 dischi della leggenda.

Portare via una soluzione

La barra degli indirizzi descrive sempre le torri che vedi. Un trasferimento completo si legge ?disks=5&from=A&to=C; una posizione personalizzata aggiunge un codice come pos=CBBAA, una lettera per disco a partire dal più piccolo. Copia quel link e riapre esattamente questo rompicapo — che è anche il modo di mandare a qualcuno la posizione in cui sei bloccato invece di una sua descrizione.

L'elenco delle mosse si copia negli appunti, oppure si scarica come file di testo da leggere accanto a un rompicapo vero e come CSV da aprire in un foglio di calcolo. Il download non ha il limite della tabella stampata: a quindici dischi il file contiene ancora tutte le 32.767 mosse.

Perché l'elenco si ferma a 12 dischi

Le soluzioni raddoppiano a ogni disco. Dodici dischi sono 4095 mosse: una tabella lunga ma utilizzabile. Tredici sono 8191, venti sono 1.048.575, e nessun browser trasforma una tabella da un milione di righe in qualcosa di usabile. Oltre i dodici dischi questa pagina dà il conteggio esatto e mantiene le torri animate — e i download qui sopra contengono comunque ogni mossa, quindi la soluzione resta tua: semplicemente non viene stampata. Se ti servono solo i numeri, la calcolatrice arriva a sessantaquattro dischi e oltre.

Domande frequenti

Che cosa fa il risolutore della Torre di Hanoi?

Stampa la più breve sequenza di mosse possibile che raccoglie tutti i dischi su una torre. Dagli un numero di dischi e risolve il classico trasferimento completo; dagli una posizione a metà e risolve da lì, che è proprio la parte che la maggior parte dei risolutori non sa fare.

La soluzione è la più breve?

Sì. Il risolutore non è solo corretto ma dimostrabilmente ottimale: da una pila iniziale completa produce esattamente 2ⁿ − 1 mosse, e da qualsiasi altra posizione valida produce il vero percorso più breve verso l'obiettivo. Non esiste una sequenza con meno mosse.

Può risolvere da una posizione che ho già iniziato?

Sì, è proprio a questo che serve la posizione iniziale personalizzata. Metti ogni disco sulla torre in cui si trova adesso e il risolutore finirà il lavoro nel minor numero di mosse possibile da lì, di solito molte meno che ricominciare.

Posso condividere o salvare una soluzione?

Sì. La barra degli indirizzi contiene sempre le torri che stai guardando: /it/solver/?disks=5&from=A&to=C è un trasferimento completo di cinque dischi, e una posizione personalizzata aggiunge un codice come pos=CBBAA, una lettera per disco a partire dal più piccolo. Copia il link e riapre esattamente quel rompicapo.

Posso scaricare l'elenco delle mosse?

Sì, come semplice file .txt o come .csv con una riga per mossa, accanto al pulsante di copia. Il download funziona anche per le soluzioni lunghissime che la pagina non stampa come tabella, quindi anche una risposta a 15 dischi resta tua.

Come si legge l'elenco delle mosse?

Ogni riga indica una mossa: il numero del disco, la torre che lascia e la torre su cui arriva. Il disco 1 è il più piccolo. Giocale in ordine e il rompicapo si risolve da sé; non devi mai chiederti quale disco sia valido, perché ogni mossa elencata lo è già.

Perché l'elenco delle mosse si ferma a 12 dischi?

Una soluzione a 12 dischi è di 4095 mosse. A 20 dischi sarebbero 1.048.575 righe, che nessun browser mostra in modo utile: oltre i 12 dischi la pagina dà il conteggio esatto e la formula al posto dell'elenco, e le torri animate continuano a riprodurre la soluzione.