Problema del caballo de Ajedrez

Peinacabras #1 Mar '14

Como dice el titulo estoy resolviendo este problema con backtracking, para quien no sepa de que se trata aqui dejo el link:

Problema del caballo

El código es el siguiente:

#include <iostream>
using namespace std;

const int TAM_TABLERO = 8;

void caballoLoco(int tablero[][TAM_TABLERO], int TAM_TABLERO, int x, int y,int mov, int incx[], int incy[]);

int main(int argc, const char * argv[])
{
    

int tablero[TAM_TABLERO][TAM_TABLERO];
int mov = 1;
int incx[8] = {-1,1,2,2,1,-1,-2,-2};
int incy[8] = {-2,-2,-1,1,2,2,1,-1};

for(int i=0; i<TAM_TABLERO; i++){
    for(int j=0; j<TAM_TABLERO; j++){
        tablero[i][j] = 0;
    }
}

caballoLoco(tablero,TAM_TABLERO,0,0,mov,incx, incy);


return 0;
}

void caballoLoco(int tablero[][TAM_TABLERO], int TAM_TABLERO, int x, int y, int mov, int incx[], int incy[]){
    

   

int nx, ny;

nx = 0;
ny = 0;

tablero[x][y] = mov;

if(mov==TAM_TABLERO*TAM_TABLERO){
    for(int i=0; i<TAM_TABLERO; i++){
        for(int j=0; j<TAM_TABLERO; j++){
            cout<<tablero[i][j]<<" ";
        }
        cout<<"n";
    }
}else{
    for(int i=0; i<8; i++){
        nx = x + incx[i];
        ny = y + incy[i];
        if((nx>=0 && nx<8) && (ny>=0 && ny<8) && (tablero[nx][ny]==0)){
         caballoLoco(tablero, TAM_TABLERO, nx, ny, mov+1,incx,incy);
        }
    }
}
tablero[x][y] = 0;
}

Y lleva 8 minutos ejecutandose y como que creo que no debería tardar tanto, ¿Sugerencias? Gracias.

B

[Borrado] #2 Mar '14

¿Por qué no debería tardar tanto? Tienes 410⁵¹ secuencias posibles según la wikipedia de las cuales sólo 210¹³ según la wikipedia de nuevo cierran el ciclo.

1 respuesta

Peinacabras #3 Mar '14

#2 ¿Entonces es normal que tarde tanto? Lo he pausado a los 10 minutos, sino cuando salga esta noche lo dejo enchufado.

1 respuesta

B

[Borrado] #4 Mar '14

#3 no soy un experto pero el problema de encontrar un ciclo hamiltoniano en un grafo es NP-hard en general, añade que la recursión va (al menos siempre que he probado yo) más lenta que el uso de bucles en C... Y por qué usas back tracking? Hay heurísticas más sencillas creo y que funcionan. Aunque claro con tu programa encontrará todas las soluciones (unos dos trillones xD), si lo entiendo bien.

1 respuesta

B

[Borrado] #5 Mar '14

doblepost porque estoy desde el móvil. Los números que digo son para todas las posiciones de partida, con una posición fija hay menos pero igualmente son 64 capas anidadas y cada una con 64 opciones más, deunido como decimos en bcn!

Peinacabras #6 Mar '14

#4 Uso el algoritmo de backtracking porque el ejercicio me han pedido que lo solucione asi, un coñazo, gracias por contestar! y si, la gracia es que encuentre todas las soluciones jajaja

eXtreM3 #7 Mar '14

Con este gif te ayudo en algo?

Si divides el tablero en 4 tableros de 4x4, puedes observar como pisa 4 casillas de esos cuadros pequeños y en el 4º salto cambia de cuadro. Esto se repite en todas las series (en este caso 4).

1 respuesta

B

[Borrado] #8 Mar '14

#7 esa es una solución, pero #1 las quiere todas.

Peinacabras #9 Mar '14

Hable con el profesor y me dijo de variar el tamaño del tablero a 5x5, efectivamente sale a los 5 segundos, me tarda tanto porque tiene muchisimos ciclos que hacer, aqui por si alguien alguna vez lo intenta dejo la solución con N = 5

#include <iostream>
using namespace std;

const int TAM_TABLERO = 5;

void caballoLoco(int tablero[][TAM_TABLERO], int TAM_TABLERO, int x, int y,int mov, int incx[], int incy[]);

int main(int argc, const char * argv[])
{
    

int tablero[TAM_TABLERO][TAM_TABLERO];
int mov = 1;
int incx[8] = {-1,1,2,2,1,-1,-2,-2};
int incy[8] = {-2,-2,-1,1,2,2,1,-1};

for(int i=0; i<TAM_TABLERO; i++){
    for(int j=0; j<TAM_TABLERO; j++){
        tablero[i][j] = 0;
    }
}

caballoLoco(tablero,TAM_TABLERO,0,0,mov,incx, incy);


return 0;
}

void caballoLoco(int tablero[][TAM_TABLERO], int TAM_TABLERO, int x, int y, int mov, int incx[], int incy[]){


int nx, ny;

nx = 0;
ny = 0;

tablero[x][y] = mov;

if(mov==TAM_TABLERO*TAM_TABLERO){
    for(int i=0; i<TAM_TABLERO; i++){
        for(int j=0; j<TAM_TABLERO; j++){
            cout<<tablero[i][j]<<" ";
        }
        cout<<"\n";
        
    }
    exit(0);
}else{
    for(int i=0; i<8; i++){
        nx = x + incx[i];
        ny = y + incy[i];
        if((nx>=0 && nx<5) && (ny>=0 && ny<5) && (tablero[nx][ny]==0)){
         caballoLoco(tablero, TAM_TABLERO, nx, ny, mov+1,incx,incy);
        }
    }
}
tablero[x][y] = 0;
}

Con ese codigo sale una solución, quitadle el exit(0) y salen todas, un saludo y gracias.

1

Problema del caballo de Ajedrez

Usuarios habituales

Tags