La torre di Hanoi • Softzone

La torre di Hanoi è un rompicapo proposto dal matematico francese Édouard Lucas nel 1883. Ci sono tre pioli e una pila di dischi di diametro decrescente infilati sul primo. Lo scopo è trasferire l’intera pila su un altro piolo rispettando due regole:

si sposta un solo disco alla volta, prendendolo dalla cima di una pila;
un disco non può mai essere appoggiato sopra un disco più piccolo.

Lucas accompagnò il gioco con una leggenda: in un tempio i monaci starebbero spostando una torre di 64 dischi d’oro, e quando avranno finito il mondo finirà. Come vedremo, si può stare tranquilli.

Soluzione ricorsiva

Il problema ha una struttura ricorsiva evidente. Per spostare k dischi dal piolo sorg al piolo dest, usando il terzo piolo dep come appoggio:

si spostano i k-1 dischi superiori da sorg a dep, usando dest come appoggio;
si sposta il disco più grande, ora libero, da sorg a dest;
si spostano i k-1 dischi da dep a dest, usando sorg come appoggio.

I passi 1 e 3 sono lo stesso problema con un disco in meno; il caso base è k = 0, in cui non c’è nulla da fare.

#define MAXEL 30

int disco[3][MAXEL];
int altezza[3];

void sposta(int k, int sorg, int dest, int dep) {
	if (k>0) {
		/* Sposta k-1 dischi da sorg a dep usando dest come deposito */
		sposta(k-1, sorg, dep, dest);
		/* Sposta un disco da sorg a dest */
		disco[dest][altezza[dest]++] = disco[sorg][--altezza[sorg]];
		printf("Sposto da %d a %d\n", sorg, dest);
		/* Sposta k-1 dischi da dep a dest usando sorg come deposito */
		sposta(k-1, dep, dest, sorg);
	}
}

I tre pioli sono rappresentati come pile: disco[p] contiene i dischi del piolo p dal basso verso l’alto e altezza[p] il loro numero. Lo spostamento di un disco è un pop dal piolo sorgente seguito da un push su quello di destinazione. Per la sola stampa delle mosse queste strutture non sarebbero necessarie, ma permettono di conoscere in ogni momento lo stato dei pioli.

Il main prepara la torre sul piolo 0 e avvia la ricorsione verso il piolo 1:

int main(int argc, char *argv[]) {
	int i;

	if (argc < 2) return 1;
	altezza[0] = atoi(argv[1]);
	if (altezza[0] > MAXEL) return 1;
	altezza[1] = altezza[2] = 0;
	for(i=0; i<altezza[0]; i++) disco[0][i] = altezza[0]-i;

	sposta(altezza[0], 0, 1, 2);
	return 0;
}

Con tre dischi l’output è:

% hanoi 3
Sposto da 0 a 1
Sposto da 0 a 2
Sposto da 1 a 2
Sposto da 0 a 1
Sposto da 2 a 0
Sposto da 2 a 1
Sposto da 0 a 1

Numero di mosse

Chiamiamo T(n) il numero di mosse necessarie per n dischi. Dalla ricorsione segue direttamente:

T(0) = 0
T(n) = 2·T(n-1) + 1

da cui T(n) = 2^n - 1: 7 mosse per 3 dischi, 1023 per 10, poco più di un milione per 20.

Questo numero è anche il minimo possibile. Il disco più grande deve muoversi almeno una volta, e nel momento in cui si muove tutti gli altri n-1 dischi devono trovarsi sul terzo piolo; servono quindi almeno T(n-1) mosse prima, una per il disco grande e almeno T(n-1) dopo per riportare gli altri sopra di esso.

Tornando alla leggenda: con 64 dischi le mosse sono 2^64 - 1, circa 1,8·10^19. A una mossa al secondo servirebbero circa 585 miliardi di anni.

Soluzione iterativa

La ricorsione non è l’unico modo di risolvere il problema. La sequenza ottimale ha una regolarità che permette di calcolare la mossa m-esima senza ricordare nulla delle precedenti: alla mossa m si sposta il disco che corrisponde al numero di zeri finali nella rappresentazione binaria di m (il disco più piccolo si muove nelle mosse dispari, il secondo ogni quattro mosse a partire dalla seconda, e così via), e il disco più piccolo percorre i pioli sempre nello stesso verso.

Da questa regolarità discende una formula compatta per i pioli di partenza e di arrivo della mossa m:

sorgente     = (m & (m - 1)) % 3
destinazione = ((m | (m - 1)) + 1) % 3

La formula porta la torre sul piolo 2 quando n è dispari e sul piolo 1 quando è pari; per ottenere sempre la stessa destinazione della versione ricorsiva basta scambiare le etichette dei pioli 1 e 2 nel caso dispari.

int main(int argc, char *argv[]) {
	int i, n, sorg, dest;
	unsigned long m, mosse;
	int piolo[3] = { 0, 1, 2 };

	if (argc < 2) return 1;
	n = atoi(argv[1]);
	if (n < 1 || n > MAXEL) return 1;
	altezza[0] = n;
	for (i = 0; i < n; i++) disco[0][i] = n - i;

	/* Con n dispari la sequenza porta la torre sul piolo 2:
	   scambiando i pioli 1 e 2 la destinazione diventa sempre 1 */
	if (n % 2) { piolo[1] = 2; piolo[2] = 1; }

	mosse = (1UL << n) - 1;
	for (m = 1; m <= mosse; m++) {
		sorg = (m & (m - 1)) % 3;
		dest = ((m | (m - 1)) + 1) % 3;
		muovi(piolo[sorg], piolo[dest]);
	}
	return 0;
}

dove muovi() esegue lo stesso pop/push della versione ricorsiva. Le due versioni producono esattamente la stessa sequenza di mosse.

La differenza sta nell’uso della memoria: la versione ricorsiva occupa uno stack proporzionale al numero di dischi, quella iterativa una quantità costante. Con 30 dischi la profondità di ricorsione resta comunque trascurabile; il vero limite pratico è il numero di mosse, che cresce esponenzialmente in entrambi i casi.

Nell’allegato sono presenti entrambi i sorgenti.

Allegati

hanoi.tar.gz