Abbiamo una serie di dischi di vario diametro impilati su un'asta,in ordine di grandezza decrescente (dal più grande al più piccolo,vedi figura sotto).Scopo del gioco è,muovendo un disco alla volta,portare tutti i dischi su una delle altre due aste (B o C).
Fino a 4-5 dischi la cosa è tranquillamente fattibile da un essere umano di media intelligenza, ma posso assicurare che dai 6 in su il rischio di una crisi di nervi è sempre in agguato anche per i solutori più abili ;)
Soluzione formale
------------------
Dato N = numero di dischi,supponendo di dover muovere gli N dischi da A a C,il problema delle Torri di Hanoi si può scomporre in questi tre passaggi fondamentali (vedi figura sotto, dove a titolo d'esempio N = 5):
1) sposta gli N-1 dischi più piccoli da A a B
2) sposta il disco più grande da A a C
3) sposta gli N-1 dischi più piccoli da B a C
Invece,l'operazione 1) può essere a sua volta scomposta in questi tre passaggi:
1) sposta gli (N-1)-1 dischi più piccoli da A a C
2) sposta il secondo disco più grande da A a B
3) sposta gli (N-1)-1 dischi più piccoli da C a B
1) sposta gli (N-1-1)-1 dischi più piccoli da A a B
2) sposta il terzo disco più grande da A a C
3) sposta gli (N-1-1)-1 dischi più piccoli da B a C
Ragionando esattamente nello stesso modo,si può scomporre l'operazione 3) di partenza nelle seguenti tre operazioni:
1) sposta gli (N-1)-1 dischi più piccoli da B a A
2) sposta il secondo disco più grande da B a C
3) sposta gli (N-1)-1 dischi più piccoli da A a C
1) sposta gli (N-1-1)-1 dischi più piccoli da B a C
2) sposta il terzo disco più grande da B a A
3) sposta gli (N-1-1)-1 dischi più piccoli da C a A
Anche qui,il processo di scomposizione termina quando ci si riduce all'operazione banale, ovvero quella di spostare un solo disco dall'asta A su una delle altre due aste.
Tutto questo popò di procedimento è implementabile con un programmino ricorsivo,in altre parole il problema della Torre di Hanoi si risolve con un qualsiasi computer scrivendo questa banale funzione C-like
void risolvi_hanoi(int N,char* A,char* B,char* C)
{
if(N==1)
printf("sposta il disco %d da %s a %s\n",N,A,C);
else
{
risolvi_hanoi(N-1,A,C,B);
printf("sposta il disco %d da %s a %s\n",N,A,C);
risolvi_hanoi(N-1,B,A,C);
}
}
Infatti,finchè N>1 il problema principale viene scomposto ricorsivamente nei suoi tre sottoproblemi,fino a che non ci si ritrova con un solo disco.A quel punto,il problema viene risolto banalmente spostando il disco dall'asta sorgente a quella di destinazione.
Se proviamo a chiamare la funzione con
risolvi_hanoi(5,"A","B","C");
sposta il disco 1 da A a C
sposta il disco 2 da A a B
sposta il disco 1 da C a B
sposta il disco 3 da A a C
sposta il disco 1 da B a A
sposta il disco 2 da B a C
sposta il disco 1 da A a C
sposta il disco 4 da A a B
sposta il disco 1 da C a B
sposta il disco 2 da C a A
sposta il disco 1 da B a A
sposta il disco 3 da C a B
sposta il disco 1 da A a C
sposta il disco 2 da A a B
sposta il disco 1 da C a B
sposta il disco 5 da A a C
sposta il disco 1 da B a A
sposta il disco 2 da B a C
sposta il disco 1 da A a C
sposta il disco 3 da B a A
sposta il disco 1 da C a B
sposta il disco 2 da C a A
sposta il disco 1 da B a A
sposta il disco 4 da B a C
sposta il disco 1 da A a C
sposta il disco 2 da A a B
sposta il disco 1 da C a B
sposta il disco 3 da A a C
sposta il disco 1 da B a A
sposta il disco 2 da B a C
sposta il disco 1 da A a C
Come vediamo servono ben 31 mosse per risolvere il rompicapo con 5 dischi.In generale, per risolvere una Torre di Hanoi a N dischi servono come minimo 2^N-1 mosse.Tra poco capiremo perchè :)
Soluzione su carta
------------------
Esiste una soluzione ancora più semplice al rompicapo delle Torri di Hanoi,infallibile (ci mancherebbe) e soprattutto,ricavabile senza bisogno di usare il computer, basta armarsi di carta, penna e ricordare poche,semplicissime regole.
A dire il vero,non so se qualche pazzoide sul web ci sia già arrivato ma anche se fosse (il che è probabile) io ve la espongo lo stesso perchè mi è costata ben due notti insonni :)
Supponiamo di voler risolvere una Torre di Hanoi a 5 dischi e che lo spostamento dei dischi debba avvenire dall'asta A all'asta C. Scriviamo sul foglio l'operazione di passaggio dei 5 dischi da A a C così
A->C
Abbiamo la nostra radice del problema.Dividiamo questa operazione in due derivazioni,
una superiore del tipo RS->x e una inferiore del tipo x->RD,dove RS è
l'asta sorgente nella radice,RD è l'asta destinazione nella radice e x è l'asta rimanente.
Nel nostro caso avremo
A->B
A->C
B->C
Abbiamo aggiunto un livello al nostro problema,facciamo la stessa cosa per le due
derivazioni della radice
A->C
A->B
C->B
A->C
B->A
B->C
A->C
E iterando sulle quattro nuove derivazioni avremo
A->B
A->C
B->C
A->B
C->A
C->B
A->B
A->C
B->C
B->A
C->A
B->C
A->B
A->C
B->C
Si prosegue così fino all'N-esimo livello,ottenendo per N = 5 un grafo così fatto
A->C
A->B
C->B
A->C
B->A
B->C
A->C
A->B
C->B
C->A
B->A
C->B
A->C
A->B
C->B
A->C
B->A
B->C
A->C
B->A
C->B
C->A
B->A
B->C
A->C
A->B
C->B
A->C
B->A
B->C
A->C
Bene,se ora leggi le operazioni in ordine crescente di riga avrai la soluzione della Torre di Hanoi con 5 dischi :DNon è tutto:se leggi la sequenza a partire dal livello 4 avrai la soluzione del problema con 4 dischi,se leggi la sequenza dal livello 3 avrai la soluzione con 3 dischi e così via. Viceversa,per avere la soluzione del problema con N+M dischi basta aggiungere al grafo M livelli.
Il risultato non sorprende,perchè risolvere il problema delle Torri di Hanoi a N dischi equivale a generare un albero binario a N livelli,dove ogni derivazione (radice compresa) corrisponde a una mossa ben precisa,ergo le mosse necessarie a completare la torre di Hanoi risultano essere come minimo 2^N-1.
Quindi,abbiamo due modi diversi di risolvere lo stesso problema?Non proprio.
Infatti,la funzione C vista prima altro non fa che generare ricorsivamente ciascuna radice con le sue derivazioni,per poi eseguirle in sequenza (esattamente come abbiamo fatto noi leggendo la sequenza generata dall'alto verso il basso).
Bene,è tutto per stasera.Passo e chiudo,Roger!