Las Torres de Hanói es un rompecabezas matemático que consiste en tres varillas y un número determinado de discos de diferentes tamaños, los cuales pueden deslizarse sobre cualquier varilla. El juego comienza con todos los discos apilados en una varilla en orden decreciente de tamaño, formando una forma cónica. El objetivo es trasladar toda la pila a otra varilla, siguiendo estas reglas:
1. Mover un solo disco a la vez.
2. Un disco de mayor tamaño no puede colocarse sobre uno más pequeño.
3. Cada movimiento consiste en tomar el disco superior de una de las pilas y colocarlo en la parte superior de otra pila.
Origen del juego torres de hanói
El rompecabezas fue inventado en 1883 por el matemático francés Édouard Lucas. Lucas presentó el juego bajo el seudónimo de «N. Claus (de Siam)», un anagrama de «Lucas d’Amiens». Junto con el juego, se difundió una leyenda que narraba cómo sacerdotes en un templo de Benarés estaban encargados de mover una torre sagrada compuesta por 64 discos de oro según las reglas del juego, y que cuando completaran la tarea, el mundo llegaría a su fin.
Resolución algorítmica
El problema de las Torres de Hanói se resuelve eficientemente mediante un enfoque recursivo. La estrategia consiste en descomponer el problema en subproblemas más pequeños, siguiendo estos pasos:
1. Mover los primeros n−1n-1n−1 discos de la varilla origen a una varilla auxiliar.
2. Mover el disco restante (el más grande) directamente a la varilla destino.
3. Mover los n−1n-1n−1 discos desde la varilla auxiliar a la varilla destino.
Este enfoque se basa en la idea de que, para trasladar una pila de nnn discos, primero se mueve una subpila de n−1n-1n−1 discos, lo que reduce el problema a una versión más simple de sí mismo. El caso base ocurre cuando solo hay un disco, que se mueve directamente a la varilla destino.
Implementación en C
A continuación, se presenta una implementación en el lenguaje de programación C que resuelve el problema de las Torres de Hanói utilizando recursividad:
#include <stdio.h>
void moverDiscos(int n, char origen, char destino, char auxiliar) {
if (n == 1) {
printf("Mover disco 1 de %c a %c\n", origen, destino);
return;
}
moverDiscos(n - 1, origen, auxiliar, destino);
printf("Mover disco %d de %c a %c\n", n, origen, destino);
moverDiscos(n - 1, auxiliar, destino, origen);
}
int main() {
int numDiscos = 3; // Número de discos
moverDiscos(numDiscos, 'A', 'C', 'B');
return 0;
}En este código, la función moverDiscos maneja la lógica recursiva para trasladar los discos entre las varillas. El programa inicia con main, donde se define el número de discos y se llama a moverDiscos con las varillas etiquetadas como ‘A’ (origen), ‘C’ (destino) y ‘B’ (auxiliar).
Esta implementación muestra paso a paso los movimientos necesarios para resolver el rompecabezas, proporcionando una solución clara y eficiente al problema de las Torres de Hanói.