Informatica Avanzada .

Problema de las

Torres de Hanoi.

Manuel I. Barrera C.

mbarrera@inf.uach.cl

Valdivia, Mayo de 1999.

Indice

Introducción o Descripción del Problema Pág.

Alternativas de Solución Pág.

Discusión de la Solución Pág.

Arquitectura Pág.

Desarrollo e Implementación Pág.

Pruebas Pilotos Pág.

Conclusiones Pág.

Anexo (Código Fuente) Pág.

Introducción o Descripción del Problema :

Según una leyenda, los monjes del templo de una antigua ciudad de la India tienen que mover una torre de 64 discos sagrados de un sitio a otro. Pero los discos son frágiles así que solo uno de ellos puede moverse a la vez. Ningún disco puede colocarse encima de otro mas pequeño. Y únicamente existe otro lugar en el templo (además del sitio original y el destino) lo suficientemente sagrado para que una torre de discos pueda ponerse ahí.

La leyenda dice además que antes de que los mojes realicen el último movimiento para completar la torre en su nuevo lugar, el templo se reducirá a cenizas y el mundo se acabará. Quizá esta leyenda tenga razón debido a la cantidad de movimientos necesarios para cambiar de lugar los 64 discos.

El Problema de las torres de Hanoi se considerará con solo 3 discos, y manteniendo claro esta la cantidad de pilares (3 torres) que se utilizan para dejar los discos, esto para facilitar el desarrollo y reducir la cantidad de movimientos y por ende de recursos que se necesitarían para desarrollar el problema original de la leyenda.

El objetivo es mover todos los discos de la torre 1 a la torre 3. La torre 2 es para almacenamiento temporal. Manteniendo las leyes del problema original, solo se permite realizar movimientos válidos, así que no puede moverse un disco encima de otro de menor diámetro.

Alternativas de Solución

Para el desarrollo de este problema se debe considerar en un principio un estado inicial(la torre 1 con los 3 discos, la torre 2 y 3 vacías) y desde ahí realizar una serie de movimientos válidos (una combinación de estados posibles y válidos) para lograr llegar a un estado final o estado objetivo (la torre 3 con los 3 discos, la torre 1 y 2 vacías).

Para el desarrollo del problema de las Torres de Hanoi se considero 2 tipos de solución, aquella que le dará el jugador y que solamente depende el y otra propia del software y para la cual se utilizó un principio matemático.

Para el desarrollo del programa se utilizo la herramienta JAVA, esta opción se tomo por sobre la de usar JESS, ya que el manejo actual que se tiene de Java es un poco mayor y en esta herramienta se logro con satisfacción el desarrollo del problema, utilizando además el algoritmo basado en principios matemáticos el cual permite al computador resolver el problema en un mínimo de movidas( para el caso de 3 discos se necesitan solo 7movidas).

Discusión de la Solución

Como se dijo anteriormente, la solución por la que se opto fue la de desarrollar el programa en el lenguaje JAVA, aprovechando las ventajas de la herramienta y como es por el momento mas manejable que la herramienta JESS, la cual era la segunda opción válida para el desarrollo de este problema.

Utilizando la herramienta JAVA, se pudo implementar una parte gráfica para tener una mayor visión del problema y de los avances que se van logrando en éste. Aquí también esta desarrollado todo el “algoritmo” que permite al computador resolver el problema con un mínimo de movidas y también (utilizando el mouse) el jugador podrá hacer cualquier movida válida para llegar al estado final o estado objetivo.

Arquitectura

Desarrollo e Implementación

Pruebas Pilotos

Como se dispone de 3 discos la solución mínima es de 7 movidas, esta solución se representa en la siguiente secuencia de movidas :

Estado Inicial	Primera Movida
Segunda Movida	Tercera Movida
Cuarta Movida	Quinta Movida
Sexta Movida	Séptima Movida - Estado Final

Como al jugar, cualquier usuario puede hacer una secuencia independientes de movidas que siempre serán como mínimo 7 y el resultado (estado final) será siempre el mismo es que se ilustra solo la solución mínima.

Conclusiones

Anexo

Código Fuente :

import java.awt.*;

import java.applet.*;

public class Hanoi extends Applet

{

static final int XDOTS = 400;

static final int YDOTS = 200;

static final int NULL = -1;

static final int MAX = 20;

static final int MIN = 3;

static final int MAXCOLS = 6;

static final int MINCOLS = 3;

static final Color cfondo=new Color(228,233,243);

static final Color cbarra=Color.black;

static final Color cfin =Color.red;

static final Color ctorre=Color.blue;

boolean first=true;

int origen,destino;

int movimientos;

int h[] = new int[MAXCOLS];

int Ficha[][] = new int[MAXCOLS][MAX];

int Centorr[] = new int[MAXCOLS];

Button B[] = new Button[MAXCOLS];

TextField TFTorres, TFCols, TFMovimientos;

int numtorres=5, numcols=3;

void Parametros()

{

String param;

param = getParameter("TORRES");

if (param != null) numtorres = Integer.parseInt(param);

param = getParameter("COLS");

if (param != null) numcols = Integer.parseInt(param);

}

public void init()

{

int i;

setBackground(cfondo);

resize(XDOTS,YDOTS);

if (first)

{

Parametros();

Herramientas();

first=false;

}

for (i=0; i< MAXCOLS; i++)

if (i< numcols) B[i].enable();

else B[i].disable();

for (i=0; i< numcols; i++)

Centorr[i]=(XDOTS/(numcols+1))*(i+1);

h[0]=numtorres;

for (i=1; i< numcols; i++)

h[i]=0;

for (i=0; i< numtorres; i++)

Ficha[0][i]=numtorres-i;

movimientos=0;

origen=destino=NULL;

}

public void Herramientas()

{

setLayout(new BorderLayout());

Panel p= new Panel();

p.setBackground(cfondo);

for (int i=0; i< MAXCOLS; i++)

p.add(B[i]=new Button(Integer.toString(i+1));

p.add(new Button("Cancelar"));

p.add(new Button("Resolver"));

p.add(new Button("Nueva"));

add("South",p);

Panel g= new Panel();

g.setBackground(cfondo);

g.add(new Label("Columnas"));

g.add(TFCols= new TextField(Integer.toString(numcols));

g.add(new Label("Torres"));

g.add(TFTorres=new TextField(Integer.toString(numtorres));

g.add(new Label("Movimientos"));

TFMovimientos=new TextField("0",8);

TFMovimientos.disable();

g.add(TFMovimientos);

add("North",g);

}

public void Dibujar_Torres (Graphics g, Color coltorr)

{

int x,y, Long;

int l,k;

int anchomin=(Centorr[1]-Centorr[0])/numtorres;

int altotorre=(YDOTS-85)/numtorres;

g.setColor(cbarra);

for (k=0; k< numcols; k++)

g.fillRect(Centorr[k]-1, 35, 2, YDOTS-75);

g.setColor(coltorr);

for (k=0; k< numcols; k++)

for (l=0; l< h[k]; l++)

{

Long=anchomin*Ficha[k][l];

x=(Centorr[k]-(Long/2));

y=YDOTS-60-l*altotorre;

g.fillRect(x,y,Long,altotorre-altotorre/3);

}

}

public void paint(Graphics g)

{

Dibujar_Torres(g, ctorre);

TFMovimientos.setText(Integer.toString(movimientos));

for (int i=1; i< numcols; i++)

if (h[i]==numtorres) Final();

}

public void Final()

{

Dibujar_Torres(getGraphics(), cfin);

}

boolean valido(int origen, int destino)

{

if (origen==NULL || destino==NULL || origen==destino) return false;

if (h[origen]==0) return false;

if (h[destino]==0) return true;

if (Ficha[destino][h[destino]-1]< Ficha[origen][h[origen]-1]) return false;

return true;

}

public void Resolver()

{

Mover(numtorres,0,1,numcols-1);

}

void Desplazar(int origen, int destino)

{

h[origen]--;

Ficha[destino][h[destino]]=Ficha[origen][h[origen]];

h[destino]++;

movimientos++;

}

void Mover(int Numero, int Comienzo, int Auxiliar, int Final)

{

int varaux;

for (int i=Numero; i>0; i--)

{

Mover(i-1,Comienzo,Final,Auxiliar);

Desplazar(Comienzo,Final);

update(getGraphics());

varaux=Comienzo;

Comienzo=Auxiliar;

Auxiliar=varaux;

}

}

public boolean action(Event e, Object o)

{

if (e.target instanceof Button)

{

int i;

for (i=0 ; i< numcols; i++)

if ((Integer.toString(i+1)).equals(e.arg))

{

if (origen==NULL)

{

origen=i;

B[origen].disable();

}

else

{

destino=i;

for (i=0; i< numcols; i++)

B[i].enable();

}

break;

}

if( "Nueva".equals(e.arg) || "Resolver".equals(e.arg))

{

numtorres=Integer.parseInt(TFTorres.getText());

numcols =Integer.parseInt(TFCols.getText());

if (numtorres< MIN) numtorres=MIN;

else if (numtorres>MAX) numtorres=MAX;

if (numcols< MINCOLS) numcols=MINCOLS;

else if (numcols>MAXCOLS) numcols=MAXCOLS;

TFTorres.setText(Integer.toString(numtorres));

TFCols.setText(Integer.toString(numcols));

TFMovimientos.setText("0");

init();

}

if( "Cancelar".equals(e.arg))

{

origen=destino=NULL;

for (i=0; i< numcols; i++)

B[i].enable();

}

if( "Resolver".equals(e.arg)) Resolver();

if (valido(origen,destino))

{

Desplazar(origen,destino);

origen=destino=NULL;

}

repaint();

return true;

}

return false;

}

public String getAppletInfo()

{

return "Nombre : Torres de Hanoi\r\n" +

"Autor : Manuel Barrera \r\n" +

"e-mail : mbarrera@inf.uach.cl.\r\n";

}

}

INFORMATICA AVANZADA TORRES DE HANOI

1

12

Manuel Barrera Cerna

INFO - 263

Universidad Austral de Chile.

Faculta de Ciencias de la Ingeniería. Escuela de Ingeniería Civil en Informática.