Torre di Hanoi: il numero minimo di mosse

Tre pioli e una regola sulle dimensioni

Sposta tutti i dischi sul piolo di destra. Puoi sollevare solo il disco in cima, spostarne uno alla volta e posarlo su un piolo vuoto o su un disco più grande. Un disco grande non può mai stare su uno più piccolo.

Qui puoi iniziare con una torre completa di tre, quattro, cinque, sei o sette dischi a sinistra. La modalità Mescolata è diversa: cinque dischi sono distribuiti sui tre pioli. La destinazione resta la stessa, ma il percorso minimo dipende dalla disposizione iniziale.

Puoi trascinare un disco in cima, selezionare un disco e la sua destinazione oppure usare la tastiera. I tasti 1, 2 e 3 selezionano i pioli. Anche le frecce e Invio consentono di spostarti tra loro. Una mossa rifiutata lascia invariata la posizione.

Perché il minimo raddoppia e aggiunge uno

Per una torre completa, sposta prima tutti i dischi tranne il più grande sul piolo libero. Porta il più grande a destinazione, poi ricostruisci la torre piccola sopra di esso. Prima di muovere il disco grande, sia lui sia il piolo di destinazione devono essere liberi dai dischi piccoli: la preparazione è indispensabile.

Se la torre piccola richiede T mosse, l'intero lavoro ne richiede T + 1 + T. Partendo da un disco e una mossa, ottieni 3, 7, 15, 31, 63 e 127 mosse per torri da due a sette dischi. La formula del minimo per una torre completa è 2ⁿ − 1, dove n è il numero di dischi.

Gli appunti di matematica discreta di Cambridge presentano questa costruzione ricorsiva e attribuiscono il rompicapo a Édouard Lucas nel 1883. La formula descrive una torre iniziale completa su un piolo, non ogni posizione parziale o mescolata.

Risolvi il caso di tre dischi

Chiama i dischi piccolo, medio e grande. Per spostare tutta la torre da sinistra a destra, libera prima il disco grande:

• Sposta il piccolo da sinistra a destra, il medio da sinistra al centro e il piccolo da destra al centro. I due dischi piccoli formano ora una torre sul piolo libero.
• Sposta il grande da sinistra a destra. Le prime tre mosse preparavano proprio questa.
• Sposta il piccolo dal centro a sinistra, il medio dal centro a destra e il piccolo da sinistra a destra.

Sono tre mosse, una mossa e altre tre: sette in tutto. Con quattro dischi, lo stesso piano usa una torre di tre dischi come sottoproblema. Non devi inventare una sequenza completamente diversa.

Cosa registra l'esercizio

Il risultato mostra le tue mosse, il minimo per la posizione iniziale, i suggerimenti usati e il tempo attivo. Il minimo è calcolato dalle posizioni legali del rompicapo, non dai risultati altrui. Ogni posizione mescolata ha un minimo esatto: non riceve automaticamente 31 mosse solo perché contiene cinque dischi.

Annulla sottrae una mossa dal conteggio visualizzato. Il numero finale descrive quindi il percorso rimasto dopo gli annullamenti, non tutti i tentativi fatti. Il cronometro parte con la prima mossa e si ferma quando la scheda è in secondo piano. Il tempo trascorso a studiare la posizione iniziale intatta è escluso.

Un suggerimento esegue una mossa lungo un percorso minimo dalla posizione attuale. La mossa conta e l'uso del suggerimento resta registrato anche se la annulli. Una soluzione aiutata può essere salvata localmente come risolta, ma è esclusa dai confronti sui tempi. Abbandonare una posizione irrisolta non salva un risultato completato.

Leggi questi dettagli insieme. Quindici mosse con un suggerimento descrivono una soluzione a quattro dischi diversa da quindici senza aiuti. Nessuno dei due risultati, da solo, dice come affronterai un rompicapo nuovo.

Cosa ha interessato i ricercatori

In The functional equivalence of problem solving skills (1975), Herbert Simon usò la Torre di Hanoi per studiare modi diversi di risolvere lo stesso problema. Descrisse quattro grandi classi di strategie, con richieste diverse per memoria, percezione e apprendimento.

Il punto utile qui è circoscritto: arrivare alla stessa destinazione non implica lo stesso lavoro mentale. Chi applica un metodo ricorsivo appreso e chi trova la strada mossa per mossa può ottenere numeri simili. Il contatore non distingue quale processo li abbia prodotti e non valuta una capacità generale di pianificazione.

Esercita il prossimo sotto-obiettivo, non l'intera sequenza

Prima di muovere, individua il disco più grande che deve spostarsi subito dopo. Chiediti dove deve attendere la torre piccola perché quella mossa diventi legale. Tieni a mente la destinazione temporanea: allontanare un disco piccolo dal piolo finale può essere proprio la preparazione giusta.

Se ti blocchi, usa un suggerimento e spiega cosa ha reso possibile prima di chiederne un altro. Ricominciare dalla stessa posizione permette di riprovare quel sotto-obiettivo. Consideralo un nuovo tentativo su una posizione familiare, non una nuova misura indipendente.

La lezione Sposta prima la torre piccola (in inglese) illustra questa struttura. L'esercizio della Torre di Hanoi inizia con tre dischi e permette di scegliere una torre più grande o una posizione mescolata quando vuoi un altro problema.