Torres de Hanoi

Torres de Hanoi

Tipus	joc matemàtic, trencaclosques mecànic i enigma matematica (oc)
Data de creació	1883
Epònim	Hanoi
Origen	Tercera República Francesa

Les torres de Hanoi és un trencaclosques o joc matemàtic. Consisteix en tres varetes verticals i un nombre indeterminat de discs de mides diferents escalonades que determinen la complexitat de la solució i que poden inserir-se a les varetes lliscant-hi lliurement.

A l'inici, els discs estan col·locats de més gran a més petit en la primera vareta formant una estructura cònica. El joc consisteix a passar tots els discs a la tercera vareta tenint en compte les regles següents:

1. Cada moviment consisteix a agafar un dels discos superiors d'una de les torres i situar-lo a una de les altres torres.
2. Els discs petits han d'estar sempre situats sobre els grans.

Amb 3 discos, el trencaclosques es pot resoldre en 7 moviments. El nombre mínim de moviments necessaris per resoldre'l amb n discs és de ${\displaystyle 2^{n}-1}$.

Aquest joc és usat típicament en matemàtiques i informàtica com a exemple de recursivitat.

Invenció i llegenda

Aquest joc va ser inventat pel matemàtic francès Édouard Lucas el 1883. El mateix Lucas va escriure la següent llegenda per ambientar el joc:

Al gran temple de Benarés, per sota de la cúpula que marca el centre del món, hi ha tres agulles. En una d'aquestes agulles, un déu va posar als inicis dels segles, seixanta-quatre discos d'or pur, el més gran sota de tots i els altres, cada vegada més petits, sobre seu. Nit i dia, els monjos treballen movent els discos d'or sense desviar-se de les regles immutables imposades pels déus. Quan hagin aconseguit traslladar tota la torre a la tercera agulla, arribarà la fi del món.^[1]

Resolució, nombre moviments necessaris

La solució de les torres de Hanoi és senzilla en el cas de 3 o 4 discs, com mostren les imatges calen 7 i 15 moviments respectivament.

El càlcul dels moviments mínims necessaris a mesura que augmenta el nombre de discos, es fa típicament de forma inductiva (també anomenada recursiva). Això vol dir que partim del coneixement dels moviments mínims que cal fer per moure ${\displaystyle k}$ discos (posem que són ${\displaystyle m_{k}}$moviments) per pensar els moviments per moure una torre amb ${\displaystyle k+1}$ discs.

La forma de fer-ho és moure els ${\displaystyle k}$ discs superiors de la primera a la segona vareta (${\displaystyle m_{k}}$ moviments), el disc de base de la primera a la tercera vareta (1 moviment) i a continuació els ${\displaystyle k}$ discs de la segona a la tercera vareta (${\displaystyle m_{k}}$ moviments un altre cop). Així que els moviments per moure una torre de ${\displaystyle k+1}$ discs són:

${\displaystyle m_{k+1}=2*m_{k}+1}$

Ara, tenint en compte el cas base ${\displaystyle m_{1}=1}$, trobem que:

${\displaystyle m_{k}=2^{k}-1}$

El nombre de moviments creix doncs exponencialment de forma sorprenent per un joc tan senzill.

En la versió de la llegenda, amb 64 discs, caldrien ${\displaystyle 2^{64}-1=18446744073709551615}$ moviments; suposant que els monjos fossin capaços d'efectuar un moviment per segon (i per tant, ${\displaystyle 31536000}$ moviments per any), trigarien més de mig bilió d'anys en fer tots els moviments.

Resolució iterativa

El problema es pot resoldre de forma iterativa. Concretament, pot ser resolt de la manera més eficient possible comptant en binari i associant el ritme d'aquest recompte a un ritme determinat de moviments dels discs.^[2] Per fer-ho, es comença comptant des de 0, i s'associa un valor ordenat a cada disc, essent el més petit 0. Sempre que en continuar el recompte només es giri aquest darrer bit de 0 a 1, es mou el disc 0 d'una clavilla cap a la dreta. Si ja estava a la clavilla de més la dreta, es retorna a la primera clavilla. Si el bit de la següent posició canvia de 0 a 1, és el disc 1 el que es mou seguint la mateixa pauta, i així successivament.

El trencaclosques té una versió restringida segons la qual els discs només es poden moure a la clavilla adjacent;^[3] aquesta versió pot ser resolta de manera similar a la d'abans, però utilitzant una base ternària. Aquesta solució no només és la més eficient, sinó que passa per cada possible configuració vàlida per aquell nombre de discs una vegada.

Si es crea un graf amb totes les possibles configuracions de discs connectades quan el moviment d'una a l'altra és vàlid en la versió no restringida, s'obté el triangle de Sierpinski.^[4] El mètode de recompte ternari que permet passar per cada possible configuració un cop, correspon a la corba de punta de fletxa de Sierpinski.^[5]

Implementació en informàtica

Si tenim n discos, un procediment recursiu en C++ com el següent imprimeix a la pantalla la seqüència de moviments a seguir.

#include <iostream>

using namespace std;

void hanoi(int n, char origen, char desti, char aux) {
 if(n != 0) {
 hanoi(n-1,origen,aux,desti);
 cout << origen << " => " << desti << endl;
 hanoi(n-1,aux, desti, origen); 
 }
}

int main() {
 int n;
 cout << "Introdueix el nombre de discs: ";
 cin >> n;
 cout << "Els moviments que s'han de fer:\n";
 hanoi(n,'A','C','B'); // transfereix n discos de A a C utilitzant B
}

Vegeu també

• Recursivitat

Enllaços externs

• Simulació javascript del joc (anglès)
• Applet java (anglès)
• Matemàtiques rere les Torres de Hanoi Arxivat 2007-05-31 a Wayback Machine. (castellà)
• Documents d'Edouard Lucas comentant el joc (anglès) (francès)

Referències