Caballo del Ajedrez en JAVA

[Kacoae]

Hola amigos:

Bueno era para ver si me podrian ayudar en esto:

Ya tengo el ejercicio en la cual el caballo se mueve en las 64 casillas sin repetir en JAVA, pero entonces ahora necesito hacer en JAVA un algoritmo que me diga cuantas posibilidades de movimiento tiene el caballo en un lugar N cualquiera que se coloque.

La máxima posibilidades son 8 movimientos (Cuando esta en el centro)
La minima posibilidades serian 2 movimientos (Cuando se ponga en las esquinas)

Espero me puedan ayudar y les dejo el código por si sirve de algo:

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

Código [Seleccionar] Expandir

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

Código [Seleccionar] Expandir

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

Muchas gracias por su atención y ayuda.

[NikNitro!]

Busca información sobre vuelta atrás (Bactracking). Eso te dará la solucion

Salud

[gordo23]

Hmm, te conviene crear un arreglo de enteros que represente el tablero, es decir 8 x 8, y que en cada posición coloques el valor de las posibilidades que tenés para moverte a este, por ejemplo:

Código [Seleccionar] Expandir

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}
                                };

Esto te daria las posibilidades que tiene el caballo de acceder desde cada posición hacía otra. Ahora lo que tendrías que hacer es actualizar este arreglo por cada paso del caballo. Si empiezas en la esquina izquierda, a esta le tendrias que colocar 0 porque ya no puedes acceder a esta, y a TODAS las posiciones a las que tienes acceso desde esta le restas 1. Esto es porque de ahora en más esas posiciones van a poder ser accedidas desde menos lugares.

En fin, creo que esto resolvería tu duda, no se si me explique bien, cualquier cosa me dices.