Muy buenas tardes.
Alguno me podria ayudar a terminar de desarrollar este ejercicio.
de este libro:
http://es.slideshare.net/freevirtualworld/como-programar-en-java-novena-edicin-en-espaol-pdfpaginas: 334 hasta 336.
Ejercicio 7.22 / Actualmente voy en la parte c.
- Lo que necesito son consejos de como podria continuar con el ejercicio. Ps simplemente no me ago la idea de como continuar con el arreglo de accesibilidad.. xD
Enunciado: 7.22 (Paseo del caballo) Un enigma interesante para los entusiastas del ajedrez es el problema del Paseo del caballo, propuesto originalmente por el matemático Euler. ¿Puede la pieza de ajedrez, conocida como caballo, moverse alrededor de un tablero de ajedrez vacío y tocar cada una de las 64 posiciones una y sólo una vez?. A continuación estudiaremos este intrigante problema con detalle.
El caballo realiza solamente movimientos en forma de L (dos espacios en una dirección y uno en una dirección perpendicular). Por lo tanto, como se muestra en la figura 7.30, desde una posición cerca del centro de un tablero de ajedrez vacío, el caballo (etiquetado como C) puede hacer ocho movimientos distintos (numerados del 0 al 7).
a) Dibuje un tablero de ajedrez de ocho por ocho en una hoja de papel, e intente realizar un Paseo del caballo en forma manual. Ponga un 1 en la posición inicial, un 2 en la segunda posición, un 3 en la tercera y así en lo sucesivo. Antes de empezar el paseo, estime qué tan lejos podrá avanzar, recuerde que un paseo completo consta de 64 movimientos. ¿Qué tan lejos llegó? ¿Estuvo esto cerca de su estimación?
b) Ahora desarrollaremos una aplicación para mover el caballo alrededor de un tablero de ajedrez. El tablero estará representado por un arreglo bidimensional de ocho por ocho, llamado tablero. Cada posición se inicializa con cero. Describiremos cada uno de los ocho posibles movimientos en términos desús componentes horizontales y verticales. Por ejemplo, un movimiento de tipo 0, como se muestra en la figura 7.30, consiste en mover dos posiciones en forma horizontal a la derecha y una posición vertical hacia arriba. Un movimiento de tipo 2 consiste en mover una posición horizontalmente a la izquierda y dos posiciones verticales hacia arriba. Los movimientos horizontal a la izquierda y vertical hacia arriba se indican con números negativos. Los ocho movimientos
pueden describirse mediante dos arreglos unidimensionales llamados horizontal y vertical, de la siguiente manera:
horizontal[ 0 ] = 2 vertical[ 0 ] = -1
horizontal[ 1 ] = 1 vertical[ 1 ] = -2
horizontal[ 2 ] = -1 vertical[ 2 ] = -2
horizontal[ 3 ] = -2 vertical[ 3 ] = -1
horizontal[ 4 ] = -2 vertical[ 4 ] = 1
horizontal[ 5 ] = -1 vertical[ 5 ] = 2
horizontal[ 6 ] = 1 vertical[ 6 ] = 2
horizontal[ 7 ] = 2 vertical[ 7 ] = 1
Deje que las variables filaActual y columnaActual indiquen la fila y columna, respectivamente, de la posición actual del caballo. Para hacer un movimiento de tipo numeroMovimiento, en donde numeroMovimiento puede estar entre 0 y 7, su programa debe utilizar las instrucciones:
filaActual += vertical[ numeroMovimiento ];
columnaActual += horizontal[ numeroMovimiento];
Escriba una aplicación para mover el caballo alrededor del tablero de ajedrez. Utilice un contador que varíe de 1 a 64. Registre la última cuenta en cada posición a la que se mueva el caballo. Evalúe cada movimiento potencial para ver si el caballo ya visitó esa posición. Pruebe cada movimiento potencial para asegurarse que el caballo no se salga del tablero de ajedrez. Ejecute la aplicación. ¿Cuántos movimientos hizo el caballo?
c) Después de intentar escribir y ejecutar una aplicación de Paseo del caballo, probablemente haya desarrollado algunas ideas valiosas. Utilizaremos estas ideas para desarrollar una heurística (o regla empírica) para mover el caballo. La heurística no garantiza el triunfo, pero una heurística desarrollada con cuidado mejora de manera
considerable la probabilidad de tener éxito. Tal vez usted ya observó que las posiciones extemas son más difíciles que las cercanas al centro del tablero. De hecho, las posiciones más difíciles o inaccesibles son las cuatro esquinas.
La intuición sugiere que usted debe intentar mover primero el caballo a las posiciones más problemáticas y dejar pendientes aquellas a las que sea más fácil llegar, de manera que cuando el tablero se congestione cerca del final del paseo, habrá una mayor probabilidad de éxito.
Podríamos desarrollar una “heurística de accesibilidad” al clasificar cada una de las posiciones de acuerdo a qué tan accesibles son y luego mover siempre el caballo (usando los movimientos en L) a la posición más inaccesible. Etiquetaremos un arreglo bidimensional llamado accesibilidad con números que indiquen desde cuántas posiciones es accesible una posición determinada. En un tablero de ajedrez en blanco, cada una
de las 16 posiciones más cercanas al centro se clasifican con 8; cada posición en la esquina se clasifica con 2; y las demás posiciones tienen números de accesibilidad 3, 4 o 6, de la siguiente manera:
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
Escriba una nueva versión del Paseo del caballo, use la heurística de accesibilidad. El caballo deberá moverse siempre a la posición con el número de accesibilidad más bajo. En caso de un empate, el caballo podrá moverse a cualquiera de las posiciones empatadas. Por lo tanto, el paseo puede empezar en cualquiera de las cuatro esquinas. [Nota: al ir moviendo el caballo alrededor del tablero, su aplicación deberá reducir los
números de accesibilidad a medida que se vayan ocupando más posiciones. De esta manera y en cualquier momento dado durante el paseo, el número de accesibilidad de cada una de las posiciones disponibles seguirá siendo igual al número preciso de posiciones desde las que se puede llegar a esa posición.] Ejecute esta versión
de su aplicación. ¿Logró completar el paseo? Modifique el programa para realizar 64 paseos, en donde cada uno empiece desde una posición distinta en el tablero. ¿Cuántos paseos completos logró realizar?
d) Escriba una versión del programa del Paseo del caballo que, al encontrarse con un empate entre dos o más posiciones, decida qué posición elegir, más adelante busque aquellas posiciones que se puedan alcanzar desde las posiciones “empatadas”. Su aplicación debe mover el caballo a la posición empatada para la cual el siguiente
movimiento lo lleve a una posición con el número de accesibilidad más bajo.
Codigo realizado por miP.D: - Los campos estaticos son creados solo por comodidad.
- El arreglo booleano primero fue usado para marcar las posiciones desplazadas.
- El arreglo entero fue creado para enumerar secuencialmente las posiciones desplazadas.
public class PaseoDelCaballo {
static final int horizontal[] = {2, 1, -1, -2, -2, -1, 1, 2};
static final int vertical[] = {-1, -2, -2, -1, 1, 2, 2, 1};
static final int filas = 8, columnas = 8;
static final int casillas = filas * columnas;
static boolean tablero[][] = new boolean[filas][columnas];
static int posiciones[][] = new int[filas][columnas];
static int filaActual = 3, columnaActual = 4;
static int numeroMovimiento = 0;
public static void main(String[] Smiith) {
int filaAnterior;
int columnaAnterior ;
int movimiento = 0;
tablero[filaActual][columnaActual] = true;
posiciones[filaActual][columnaActual] = ++movimiento;
for (int ciclo = 1; ciclo <= casillas; ciclo++) {
if (tablero[filaActual][columnaActual] == true) {
int controlDoWhile = 0;
do {
if (controlDoWhile++ >= 8) {
break; // detiene el ciclo while
} // fin de if
filaAnterior = filaActual;
columnaAnterior = columnaActual;
filaActual = fila(filaActual += vertical[numeroMovimiento]);
columnaActual = columna(columnaActual += horizontal[numeroMovimiento]);
if (filaActual == filaAnterior || columnaActual == columnaAnterior) {
filaActual = filaAnterior;
columnaActual = columnaAnterior;
if (numeroMovimiento++ == 7) {
numeroMovimiento = 0;
} // fin de if interno
} // fin de if externo
else {
if (tablero[filaActual][columnaActual] == true) {
filaActual = filaAnterior;
columnaActual = columnaAnterior;
if (numeroMovimiento++ == 7) {
numeroMovimiento = 0;
} // fin de if interno
} // fin de if externo
} // fin de else
} while (filaActual == filaAnterior || columnaActual == columnaAnterior);
// si no hubo movimientos posibles asigna false a la casilla actual
if (controlDoWhile > 8) {
tablero[filaActual][columnaActual] = false;
posiciones[filaActual][columnaActual] = 0;
} // fin de if
// si hubo movimientos posibles, asigna true a la casilla actual
else {
tablero[filaActual][columnaActual] = true;
posiciones[filaActual][columnaActual] = ++movimiento;
} // fin de else
} // fin de if
else {
tablero[filaActual][columnaActual] = true;
posiciones[filaActual][columnaActual] = movimiento;
break;
} // fin de else
} // fin de for
imprimirRecorrido();
} // fin del metodo main
private static void imprimirMovimientos(int movimientos) {
System.out.println("--------------------------------------------------");
System.out.println("La cantidad de movimientos realizados fue de: " + movimientos);
System.out.println("--------------------------------------------------");
} // fin del metodo ImprimirMovimientos
private static void imprimirRecorrido() {
int movimientos = 0; // almacena la cantidad de movimientos realizados
for (int fila = 0; fila < filas; fila++) {
for (int columna = 0; columna < columnas; columna++) {
System.out.printf("%2s ", posiciones[fila][columna] != 0 ? posiciones[fila][columna] : 0);
// cuenta la cantidad de movimientos en el recorrido
if (posiciones[fila][columna] != 0) {
movimientos++;
} // fin de if interno
} // fin de for interno
System.out.println(); // salto de linea
} // fin del ciclo for externo
imprimirMovimientos(movimientos);
} // fin del metodo imprimirRecorrdio
private static int columna(int columnaActual) {
if (columnaActual < 0 || columnaActual >= columnas) {
columnaActual -= horizontal[numeroMovimiento];
} // fin de if externo
return columnaActual; // devuelve el valor de la columna actual
} // fin del metodo columna
private static int fila(int filaActual) {
if (filaActual < 0 || filaActual >= filas) {
filaActual -= vertical[numeroMovimiento];
} // fin de if
return filaActual; // devuelve el valor de la fila actual
} // fin del metodo fila
} // fin de la clase PaseoDelCaballo
Tema: Ejercicio 7.22 Paseo del caballo - Como programar en java Deitel Pearson Educa (Leído 13433 veces)
RSS -
WAP2