public class UsaCaballo

{  // Abre  UsaCaballo

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

}  // Cierra UsaCaballo 

 /*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
  *                                                                        *
  *                                                                        *
  *                            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 

int[][] accesibilidad = {
            {2, 3, 4, 4, 4, 4, 3, 2},
            {3, 4, 6, 6, 6, 6, 4, 3},
            {4, 6, 8, 8, 8, 8, 6, 4},
            {4, 6, 8, 8, 8, 8, 6, 4},
            {4, 6, 8, 8, 8, 8, 6, 4},
            {4, 6, 8, 8, 8, 8, 6, 4},
            {3, 4, 6, 6, 6, 6, 4, 3},
            {2, 3, 4, 4, 4, 4, 3, 2}
                                };