Backtracking.

[Dniel]

Buenas, qué tal:

Estoy intentando realizar cierto problema utilizando backtracking, dicho problema es el siguiente:

En un tablero de ajedrez de tamaño n×n se coloca un rey en una casilla arbitraria (x0 , y0). Cada casilla (xi , yi) del tablero tiene asignado un peso p(xi , yi) , de tal forma que a cada recorrido R=((x0 , y0),...,(xk , yk)) se le puede asignar un valor que viene determinado por la siguiente expresión:

P(R) = (Sumatorio desde i=1 hasta k) i p(xi , yi)

El problema consiste en buscar el recorrido de peso mínimo que visite todas las casillas del tablero sin repetir ninguna.

El siguiente algoritmo especifica los movimientos válidos del rey:

Código:

void MovimientosRey(int movX[8], int movY[8]){

    movX[1]=0; movY[1]=1;
    movX[2]=-1; movY[2]=1;
    movX[3]=-1; movY[3]=0;
    movX[4]=-1; movY[4]=-1;
    movX[5]=0; movY[5]=-1;
    movX[6]=1; movY[6]=-1;
    movX[7]=1; movY[7]=0;
    movX[8]=1; movY[8]=1;

}

El siguiente algoritmo calcula el peso:

Código:

int Peso(int tam, int t[TAM][TAM]){

    int i, j, p=0;

    for(i=0;i<tam;i++){
        for(j=0;j<tam;j++){
            p = p+t[i][j]*i*j;
        }
    }

    return p;

}

Y por último, el algoritmo backtracking:

Código:

int VueltaAtras(int movX[8], int movY[8], int tam, int t[TAM][TAM], int k, int x, int y){

    int orden=1, coste, u, v;
    int i, j;

    while(orden!=9){

        u = x+movX[orden];
        v = y+movY[orden];

        if((u>=1) && (u<=tam) && (v>=1) && (v<=tam) && (t[u][v]==0)){
            t[u][v]=k;
            if(k<tam*tam)
                VueltaAtras(movX, movY, tam, t, k+1, u, v);
            else{
                coste = Peso(tam, t);
                if(coste < minimo){
                    minimo = coste;
                    for(i=0;i<tam;i++){
                        for(j=0;j<tam;j++){
                            mejorSolucion[i][j] = t[i][j];
                        }
                    }
                }
            }
            t[u][v]=0;
        }

        orden++;

    }

    return minimo;

}

Siendo el programa principal el siguiente:

Código:

int main(){

    int movX[8], movY[8];
    int tam;

    minimo=1000000000;

    MovimientosRey(movX, movY);

    printf("Solicitando informacion del problema:\n");
    printf("1.- Introduzca el tamano del tablero: ");
    scanf("%d", &tam);
    printf("\tGenerando tablero %dx%d.\n", tam, tam);

    int t[tam][tam];
    int i, j, x, y;

    for(i=0;i<tam;i++){
        for(j=0;j<tam;j++){
            t[i][j]=0;
        }
    }

    printf("3.- Posicion inicial del rey:\n");
    printf("\ta.- Fila: ");
    scanf("%d", &x);
    printf("\tb.- Columna: ");
    scanf("%d", &y);
    printf("\tPosicion inicial del rey: (%d, %d).\n", x, y);
    t[x][y]=1;

    long int inicio, final;
    float divisor=1000, ms;
    int peso;

    printf("\tIniciando busqueda del recorrido minimo...\n");
    inicio = GetTickCount();
    peso = VueltaAtras(movX, movY, tam, t, 2, x, y);
    final = GetTickCount();
    ms = (final-inicio)/divisor;
    printf("\tBusqueda completada en t=%lf ms.\n", ms);
    printf("\tEl peso del recorrido minimo es %d.", peso);

    return 0;

}

Sin embargo, no funciona correctamente, por lo que si alguien tiene alguna idea sobre cómo funcionaría, que me lo comente si no es demasiada molestia.

Gracias de antemano.