Regresar a Proyectos y artículos
Recorridos del Caballo de Ajedréz
Articulo enviado por: José Ronald Flores Huanca.
Este artículo se compone de tres apartados, de los cuales el primero
lo constituye la implemetacion del algoritmo que buscara un posible recorrido
del caballo. En el apartado 2 buscaremos, utilizando el algoritmo realizado
en el apartado anterior, todas las casillas iniciales para los que el algoritmo
encuentra solución.El apartado 3 describe los resultados obtenidos del
apartado anterior encontrando el patron general de las soluciones del recorrido
del caballo.
Dado un tablero de ajedrez y una casilla inicial, queremos decidir si es posible
que un caballo recorra todos y cada uno de los escaques sin duplicar ninguno,
en la gerga del ajedrez, el problema consiste en mover 64 veces el caballo sin
repetir las casillas visitadas. No es necesario en este problema que el caballo
vuelva al escaque de partida. Un posible algoritmo ávido decide, en cada
iteración, colocar el caballo en la casilla desde la cual domina el menor
número posible de casillas aún no visitadas, laPieza del caballo
de ajedres se mueve un cuadro en una direccion y luego una posicion en diagonal.
para lo cual realizaremos los siguientes pasos.
- Implementaremos dicho algoritmo, a partir de un tamaño de tablero
nxn y una casilla inicial (x0,y0).
- Buscaremos, utilizando el algoritmo realizado en el apartado anterior, todas
las casillas iniciales para los que el algoritmo encuentra solución.
- Basándose en los resultados del apartado anterior, encontrar el patrón
general de las soluciones del recorrido del caballo.
Applet de demostración
Diagrama de clases
E l siguiente es el diagrama de clases del programa en Java.
Codigo fuente de la clase caballo.
public class Caballo
{
int n; // tama帽o del tablero
public int [][] tablero;
boolean exito;
int[] movX = {2,1,-1,-2,-2,-1,1,2};
int[] movY = {1,2,2,1,-1,-2,-2,-1};
int [][] acces;
MiCanvas canvas;
Thread anima=null;
// aqui inciamos nuestros campos de la clase
public Caballo (int tam, MiCanvas canvas1) {
n = tam;
tablero = new int [n][n];
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
tablero[i][j] = 0;
acces=calculaAccesibilidad();
canvas=canvas1;
if(anima==null){
anima=new Thread();
anima.start();
}
}
/*
Una posible implementaci贸n del algoritmo viene dada por la funci
贸n encuentraSolucion(int u, int v) que se muestra a continuaci贸n,
la cual, dado un tablero, su dimensi贸n n y una posici贸n
inicial (u,v), decide si el caballo recorre todo el tablero o no.
*/
public void encuentraSolucion(int u, int v){
Pos pos;
tablero[u][v]=1;
canvas.ver(u,v, tablero);
for (int salto = 2; salto <= n * n; salto++) {
try{
anima.sleep(150);
}
catch(InterruptedException ex){
break;
}
pos = sigSalto(u, v);
u = pos.u;
v = pos.v;
tablero[u][v] = salto;
canvas.ver(u, v, tablero);
}
}
/*
La funci贸n sigSalto(int x, int y), es la que va a ir
calculando la nueva casilla a la que salta el
caballo siguiendo la indicaci贸n del enunciado,
devolviendo la posicion siguiente ha moverse
*/
public Pos sigSalto(int x, int y){
Pos pos=new Pos();
int u,v;
int uSig, vSig, menorAccesibilidad;
int[] accesibilidad= new int[8];
int[] soluciones=new int [8];
for(int i=0; i<8; i++){
u=x+movX[i];
v=y+movY[i];
if(u>=0 && u<n && v>=0 && v<n && tablero[u][v]==0)
accesibilidad[i]=acces[u][v];
else
accesibilidad[i]=10;
}
//buscamos la menor accesibilidad
menorAccesibilidad=100;
for(int j=0; j<8; j++)
if(accesibilidad[j] < menorAccesibilidad)
menorAccesibilidad=accesibilidad[j];
for(int k=0,cont=0; k<8; k++)
if(accesibilidad[k]== menorAccesibilidad){
soluciones[cont++]=k;
}
if(accesibilidad[soluciones[0]]<10){
uSig = x + movX[soluciones[0]];
vSig = y + movY[soluciones[0]];
pos.u = uSig;
pos.v = vSig;
for (int i = 0; i < 8; i++) {
u = x + movX[i];
v = y + movY[i];
if (u >= 0 && u < n && v >= 0 && v < n)
acces[u][v] -= 1;
}
}
return pos;
}
/*
Para la implementaci贸n de sigSalto necesitamos una funcion auxiliar:
calculaAccesibilidad(),esta ultima llena la matriz acces, colocando
en cada casilla el numero de casillas accesibles desde la coordenada
actual intentando los movimientos en el orden en que se muestra en
la figura:
*/
public int[][] calculaAccesibilidad(){
int[][] accesibilidad =new int[n][n];
int i ,j, k, u, v, cuenta=0;
for(i=0; i<n/2; i++){
for(j=0; j<n/2; j++){
for(k=0; k>8; k++){
u=i+movX[k];//movimiento horizontal
v=j+movY[k];//movimiento vertical
if(u>=0 && u<n && v>=0 && v<n)
cuenta++;
}
accesibilidad[i][j]=cuenta;
accesibilidad[i][n-1-j]=cuenta;
accesibilidad[n-1-i][n-1-j]=cuenta;
accesibilidad[n-1-i][j]=cuenta;
cuenta=0;
}
}
if(n%2==1){
cuenta=0;
for(i=0; i<n/2; i++){
for(k=0; k<8; k++){
u=n/2+movX[k];//movimiento horizontal
v=i+movY[k];//movimiento vertical
if(u>=0 && u<n && v>=0 && v<n)
cuenta++;
}
accesibilidad[n/2][i]=cuenta;
accesibilidad[i][n/2]=cuenta;
accesibilidad[n/2][n-1-i]=cuenta;
accesibilidad[n-1-i][n/2]=cuenta;
cuenta=0;
}
accesibilidad[n/2][n/2]=8;
}
return accesibilidad;
}
class Pos{
public int u, v;
}
}
Para resolver esta cuesti贸n necesitamos un programa que nos permita ir recorriendo
todas las posibilidades e imprimiendo aquellas casillas iniciales desde donde
se consigue soluci贸n:
public void buscaSolucionTodas(){
int i, j;
for(i=0; i<n; i++)
for(j=0; j<n; j++)
encuentraSolucion(i,j);
}
La salida del programa anterior nos permite inferir un patr贸n general para
las soluciones del problema.
- Para n = 4, el problema no tiene soluci贸n.
- Para n > 4, n par, el problema tiene soluci贸n para cualquier casilla inicial.
- Para n > 4, n impar, el problema tiene soluci贸n para aquellas casillas iniciales
(x0,y0) que verifiquen que x0 + y0 sea par, es decir, si el caballo comienza
su recorrido en una escaque blanco.
Pero observemos que el algoritmo implementado no ha encontrado soluci贸n en todas
estas situaciones. Por ejemplo, para n = 5, x0 = 5 e y0 = 3 el programa dice
que no la hay. Sin embargo, s铆 la encuentra para n = 5, x0 = 1 e y0 = 3, para
n = 5, x0 = 3 e y0 = 1 y para n = 5, x0 = 3 e y0 = 5, que son casos sim茅tricos.
De existir soluci贸n para alguno de ellos, por simetr铆a se obtiene para los otros.
驴Por qu茅 no la encuentra nuestro algoritmo?
La respuesta a esta pregunta se encuentra en c贸mo buscamos la siguiente casilla
a donde saltar. Por la forma en la que funciona el programa, siempre probamos
las ocho casillas en el sentido de las agujas del reloj, siguiendo la pauta
mostrada en la funci贸n Salto. Esto hace que nuestro algoritmo no sea sim茅trico.
En resumen, estamos ante un algoritmo 谩vido que no funciona para todos los casos.
|
Inicio 
Artículos 
Recursos 
Foros 
