martes, 25 de octubre de 2011

Deitel_Java_7.23 a) ( Circuito del Caballo en Java, Método de Fuerza Bruta)

Una solución al recorrido del caballo

7.23 (Paseo del Caballo: Métodos de Fuerza Bruta) En la parte c del ejercicio 7.22 desarrollamos una solución al problema del paseo del caballo. El método utilizado, llamado "heurística de accesibilidad", genera muchas soluciones y se ejecuta con eficiencia. A medida que se incremente de manera continua la potencia de las computadoras, seremos capaces de resolver más problemas con menos potencia y algoritmos relativamente menos sofisticados. A éste le podemos llamar el método de la "fuerza bruta" para resolver problemas.

a) Utilice la generación de números aleatorios para permitir que el caballo se desplace a lo largo del tablero (mediante sus movimientos legítimos en L) en forma aleatoria. Su aplicación debe ejecutar un paseo e imprimir el tablero final. ¿Qué tan lejos llegó el caballo?
_____________________________________________________________________________________
SOLUCIÓN:
En este programa el caballo llega tan lejos como el usuario quiera. Se ha puesto un ciclo while que corre el algoritmo tantas veces como sean necesarias para que se obtengan las casillas deseadas. En los comentarios del programa viene bien explicado de qué se trata. Pero debo decir que este algoritmo es bastante simple. La clase Caballo, que es la que hace el trabajo, tiene, con comentarios, 176 líneas de código. He visto soluciones más complicadas, y yo mismo tengo en este blog unas muy rebuscadas. La idea es muy sencilla. El caballo empieza en una casilla la (1,1) en este caso pero puede ser cualquiera, a partir de ahí ¿a dónde mover? Ya que el problema va a ser resuelto mediante la fuerza bruta suponemos que un mono lanza un par de dados que tienen caras del 1 al 8. El primero de ellos decide la linea y el siguiente la columna. Si antes no ha pasado el caballo por ahí, lo cual se indica con un numero, entonces el mono procede a medir la distancia entre la posicion actual en x y la coordenada x de la casilla, si es 1 o 2 se analiza la distancia en y, la cual debe ser 2 o 1, respectivamente. Si se cumplen estas condiciones entonces se escribe el número de casillas que lleva recorridas el caballo y se sigue adelante. El caballo puede llegar a un punto muerto. Si después de un cierto número de lanzamientos de dados (1000 en este programa) no se ha incrementado el número de casillas recorridas, entonces se deja de intentar. El programa pregunta cuántas casillas quiere que recorra el caballo. Es bueno iniciar con pocas, pero en realidad la única que tarda un poco ( unos cinco minutos en promedio en mi máquina bastante vieja ) es 64. El recorrido de la figura fue obtenido en unos dos minutos aproximadamente.
Más importante aún, con cambiar 8 por cualquier otro número se puede encontrar recorridos para tableros de nxn y resolver el problema general. En teoría de grafos este problema consiste en encontrar el circuito de Hamilton, aquel que pasa por todas las aristas del grafo.

Este código debe guardarse con el nombre UsaCaballo.java

public class UsaCaballo

{  // Abre  UsaCaballo

public static void main(String args[])
{     // Abre main
Caballo miObjeto = new Caballo();
miObjeto.Recibe();
}     // Cierra main

}  // Cierra UsaCaballo

El siguiente código debe guardarse con el nombre Caballo.java

/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
  *                                                                        *
  *                                                                        *
  *                            DEITEL 7.23 a)                              *
  *                                                                        *
  *  Este programa intenta el recorrido del caballo en un tablero de       *
  *  ajedrez mediante la fuerza bruta.                                     *
  *                                                                        *
  *                                                                        *
  *++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/

  /*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
   *                                                                       *
   *                               ALGORITMO:                              * 
   *                               __________                              *
   *                                                                       * 
   *  La idea de este algorimo es bastante simple:                         *
   *                                                                       *
   * PASO 1: El tablero de ajedrez (arreglo de 8x8) se llena con 0 en todas*
   * las entradas exepto en la esquina superior derecha, que se coloca un 1*
   * De ahi es de donde parte el caballo.                                  *
   *                                                                       *  
   * PASO 2: Se lanza un par de "dados" de ocho caras El primer dado decide*
   * el renglon, el siguiente decide la columna.                           *
   *                                                                       *
   *PASO 3: Es necesario verificar que el caballo no haya pasado antes por *
   *ahi, o que la casilla seleccionada tenga un 0 Si no es asi se repite el*
   *Paso2. Si efectivamente es un 0, entonces se verifica que la casilla   *
   *elegida al azar sea "legal" o este en forma de L Para esto se verifican*
   *las distancias en X y en Y. Si el valor absoluto de la diferencia entre*
   *la casilla elegida por el dado1 y la casilla x actual es igual a 2 o  1*
   *se procede a checar el valor absoluto de la distancia entre dado2 y Y. *
   *1 para el primer caso y 2 para el segundo, indican que la casilla es   *
   *valida. Se procede a poner el numero  2 ( o 3 o 4 o el que sea)  en la *
   *casilla, lo cual indica que esa es la siguiente parada del caballo. Se *
   *incrementa la variable contador y se procede de esa manera.            * 
   *                                                                       * 
   *                                                                       *  
   *Eso es todo. Esa es la idea central. Lo demas consiste en decirle al   *
   *programa cuando ya no es posible encontrar mas casillas, y por lo      * 
   *tanto se ha llegado a un rincon sin salida. Para eso se introduce una  *
   *variable que cuenta el numero de veces que se ha lanzado los dos dados *
   *sin cambiar de casilla.  Si se cumplen estos el programa entiende que  *
   *no hay salida y deja de intentar buscarla. Esto significa que 15 de    *
   *cada 1000 veces dejara de intentar cuando en realidad hay una casilla  *
   *a la cual mover. Se puede cambiar y poner un limite mas grande, pero   *
   *como he puesto un ciclo mas grande afuera que permite al usuario pedir *
   *una cuota minima de recorrido, hacerlo significa mas tiempo.           *
   *                                                                       *
   *                                                                       *
   *+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/

import java.util.Scanner;
import java.util.Random;

public class Caballo
{  // Abre clase Caballo
private int x = 1;  // El caballo inicia en la casilla superior izquierda
private int y = 1;
private int tamano = 8; // El arreglo es de ocho x ocho
private int contador = 1; // Esta variable lleva la cuenta de las casillas
                           // recorridas
int ciclos = 0;           // Esta variable cuenta los ciclos que se inten
                           // tan antes de determinar que ya no hay lugares
                           // a los cuales ir                            
int intentos_fallidos = 0; // Esta variable cuenta cuantos ciclos se inte
  //tan antes de obtener el que pidio el usuario para 64 pueden ser varios
  // millones

Scanner entrada = new Scanner(System.in);
 
public void Recibe() 
{  // Abre Recibe
Random aleatorio = new Random();

int Arreglo[][] = new int[tamano + 1][tamano +1];
// Se define el arreglo de 9*9 para evitar el 0 
Arreglo[1][1] = 1;
int dado1;
int dado2;
int casillas_requeridas = 0;
  
System.out.println("\nCuantas casillas quiere que recorra por lo menos?");
System.out.printf("\nAdvertencia: Si pide mas de %d el programa no terminara nunca:\n", tamano*tamano);
  casillas_requeridas = entrada.nextInt();
  
// Debido a que se usara la fuerza bruta de la computacion para encontrar un
// recorrido completo se anade este while

while ( contador < casillas_requeridas )
{
intentos_fallidos++;  // Se incrementa cada que inicia un intento
contador = 1;    // Dado que ya se ha colocado al caballo en (1,1), se  
                   // inicia el contador en 1
int ciclos = 0;   // Se inicia con 0 ciclos o lanzamientos de dados infructuosos 
// Cada vez que se aborta un intento han de limipiarse las casillas, con el siguiente
//par de ciclos se establecen a 0 nuevamente.

for ( int s = 0; s <= tamano; s++ )
{       // Abre for
for ( int t = 0; t <= tamano; t++ )
Arreglo[s][t] = 0; 
}       // cierra for 
 
//Se ha de colocar el caballo en la esquina superior izquierda cada vez
// desde luego se puede poner en cualquier parte
x = 1;
y = 1;
 
Arreglo[1][1] = 1;
// Mientras no se encuentre un lugar para poner al caballo

while ( 1000 != ciclos)
// Este ciclo while basicamente hace el PASO 3 del algoritmo
{  // Abre while
ciclos++;
dado1 = 1 + aleatorio.nextInt(8);
dado2 = 1 + aleatorio.nextInt(8);

if ( Math.abs(Math.abs(x) - Math.abs(dado1)) == 2) 
{ // Abre if
if ( Math.abs(Math.abs(y) - Math.abs(dado2)) == 1  )
 
if ( 0 == Arreglo[dado1][dado2])
{   // Abre if
Arreglo[dado1][dado2] = ++contador;   
x = dado1;
y = dado2;
ciclos = 0;
}  // Cierra if 
}  //Cierra if 

 
if ( Math.abs(Math.abs(x) - Math.abs(dado1)) == 1) 
{  // abre if
if ( Math.abs(Math.abs(y) - Math.abs(dado2)) == 2  )
if ( 0 == Arreglo[dado1][dado2] )
{    // Abre if 
Arreglo[dado1][dado2] = ++contador; 
x = dado1;
y = dado2;
ciclos = 0;
}  // Cierra if
}  // Cierra if
 
}  // Cierra while anidado
}    // Cierra while

System.out.println("\nLISTO!");
System.out.printf("\nSe recorrieron %d casillas.\n", contador);
System.out.printf("\nSe intentaron %d circuitos antes de obtener el requerido.\n", intentos_fallidos); 
Imprime( Arreglo );

}   // Cierra Recibe

/*El metodo siguiente despliega el tablero de ajedrez */

//////////////////////////////////////////
// Imprime
///////////////////////////////////////////
 
public void Imprime(int B[][])
{     // Abre imprime
for ( int k = 1; k <= 8; k++ )
{
for ( int j = 1; j <= 8; j++)
{
System.out.printf("%5d", B[k][j]);
 
}  
System.out.println("\n");
}
}     // Cierra imprime
}    // Cierra clase Caballo

17 comentarios:

  1. Para mi lo mejor ha sido hacer este ejercicio a partir de lo que dice en el enunciado del ejercicio 7.22 de la 7a edición del libro.

    ResponderEliminar
  2. ¡Hola!No sé a qué te refieres exactamente con mejor. La versión que dices es la heurística, que es más difícil de hacer. Si a eso te refieres, sí, es cierto, esa es más interesante; en esta entrada tengo una solución heurística en C++, aunque no me ha gustado mucho. La versión en fuerza bruta, es mucho más corta y fácil de entender. Pasa lo mismo en el problema de las ocho reinas. Incluso por concepto, la fuerza bruta tiene que ser más fácil que la heurística.
    Muchos saludos y gracias por el comentario.

    ResponderEliminar
  3. Hola amigo. Dice que: Advertencia: Si pide mas de 64 el programa no terminara nunca:

    Yo ingreso 64 o 63, pero no sale nada :s

    Gracias

    ResponderEliminar
    Respuestas
    1. Eso tiene que ver con que probablemente no estás dejando tiempo suficiente. Empieza con número bajo. 63 podría sacarlos en unos 15 minutos una computadora mala. Una sugerencia para que veas que el algoritmo está bien: cambia las variables para que el tablero sea de 5*5 y pídele que recorra 25, vas a ver que se hace ràpido.
      Saludos.

      Eliminar
  4. Hola:

    No entiendo una cosa, me dice:
    Cuantas casillas quiere que recorra por lo menos?

    Advertencia: Si pide mas de 64 el programa no terminara nunca:

    ENTONES YO INGRESO 2 Y SE SUPONE QUE DEBERIA MOVERSE 3 CASILLAS PUES YA QUE INICIA DESDE 0, PERO ME SALE LO SIGUIENTE:

    Se recorrieron 34 casillas.

    Se intentaron 1 circuitos antes de obtener el requerido.
    1 0 33 0 27 0 0 0

    34 0 26 29 0 7 0 0

    0 2 19 32 13 28 0 6

    0 25 12 3 30 17 8 0

    0 20 31 18 11 14 5 0

    24 0 22 0 4 0 16 9

    21 0 0 0 15 10 0 0

    0 23 0 0 0 0 0 0

    Porque 34 casillas? que es eso de circuitos.

    Gracias.

    ResponderEliminar
    Respuestas
    1. Por eso dice "por lo menos". Recorrer pocas casillas es fàcil, lo difìcil es cuando se quiere que recorra 50 o màs. Entonces pueden pasar miles de intentos antes de se obtengan. Por esto està el ciclo que intenta hasta que se cumpla el nùmero deseado. 34 casillas son las que se recorrieron antes de que no hubiera màs opciones. ¿Por què no intentas hacerlo en un tablero para que lo entiendas mejor? lo de 1 circuito es porque si pides 2, no requieres màs que 1 intento para obtenerlo.

      Eliminar
    2. Si mi amigo, pero es que si yo solo quiero 3 movimientos deberia salir 1, 2 y 3 y ya, y lo demás en cero. Eso es lo que no entiendo del porque se me va a muchos movimientos. Perdon depronto mi ignorancia, y trato de editar el código, pero nada.

      Eliminar
  5. Amigo me pide Cuantas casillas quiere que recorra por lo menos?, ingreso dos y me sale que: Se recorrieron 27 casillas.

    Se intentaron 1 circuitos antes de obtener el requerido.

    No entiendo :S

    ResponderEliminar
  6. hola es que no entiendo ese de los dados y cuando inserto el numero de movimientos como por ejm 8 me sale que se recorrieron 33 casillas y se intentaron 1 circuitos antes de obtener el requerido. Tampoco entiendo eso de circuitos. gracias

    ResponderEliminar
  7. Sugerencia: hay que intentar éste problema en un tablero de ajedrez antes de resolver el programa.

    ResponderEliminar
  8. Ya lo he probado con prueba de escritorio y todo, pero entonces cuando lanzo que el movimiento sea solo de 3 sale desplazándose 34 y así...>

    ResponderEliminar
    Respuestas
    1. Es que es imposible que no se recorra más de 3 en un tablero de 8*8. Para ponerlo fácil. Supón que la computadora eres tú y tratas de hacer un recorrido completo, y que te piden que por lo menos recorras 3 casillas, "POR LO MENOS", vas a ver que es muy fácil hacer más de 3, de hecho si lo intentas TÚ vas a llegar a más de 30, el problema es cuando en lugar de 3 te piden 61 o 62, entonces vas a ver que tienes que intentar muchas miles de veces antes de lograrlo. Si no le hubiera puesto la condición de que por lo menos recorriera x número de casillas, entonces para obtener uno con 58, 59 o 64 tendrías que ejecutar el programa miles, cientos de miles, de veces, antes de obtener el número deseado. Lo que hago es poner un ciclo que corra el programa original tantas veces como sea necesario para obtener las casillas que se piden. Si le pides que recorra 1 casilla, pues ya está, porque empieza en la esquina superior izquierda.

      Eliminar
  9. Si entiendo, en las esquinas solo se pueden hacer 2 movimientos posibles, pero pense que el algoritmo hacia los recorridos como deberia ser. Gracias
    Otra pregunta: Que es eso de circuito? Gracias!

    ResponderEliminar
  10. Amistad una pregunta usted no tendria un algoritmo del caballo del ajedrez que:

    Cuando el caballo se coloque en una posición nXn diga cuantas posibilidades de movimientos tiene y ya.

    Le agradezco su ayuda
    Salu2!

    ResponderEliminar
  11. No tendria un algoritmo igual a este del caballo ajedrez, pero en una posición nxn y no siempre en la esquina?

    Gracias

    ResponderEliminar
  12. como harias un tablero de ajedrez mediante una array

    ResponderEliminar
  13. Como hacerlo con recursividad?

    ResponderEliminar

Related Posts Plugin for WordPress, Blogger...