problema "8 reinas" creando una heuristica, en C (lenguajec)

[rackdon]

Buenos dias.
Se me ha planteado el siguiente problema.
(Ocho reinas) otro enigma para los amantes del ajedrez es el problema de las ocho reinas, el cual dice: ¿Es posible colocar ocho reinas en un tablero de ajedrez vacío, de tal manera que ninguna reina ataque a otra , es decir que dos reinas no estén en la misma fila, en la misma columna, o a lo largo de la misma diagonal?.
Tenía que desarrollar una heurística para obtener el máximo de posibilidades de éxito.

La solución era asignar un valor a cada cuadro del tablero, que indique cuántos cuadros de un tablero vacío son "eliminados" si se coloca una reina en ese cuadro. A cada una de las esquinas se les asignaría el valor 22. Una vez que estos "números de eliminación" se colocan en los 64 cuadros, una heurística adecuada podría ser: coloque la siguiente reina en el cuadro que contenga el número de eliminación más pequeño.

Hasta aquí todo correcto, el problema viene que al ejecutar el programa solo consigo colocar 7 reinas. ¿Alguien me podría decir que es lo que me falta para que pueda colocar las 8 reinas?
Pongo a continuación el código.

Código: [Seleccionar]

// Ejercicio 6.26: Ocho reinas (heurística) //

#include <stdio.h>

main()
{
      int tablero[8][8] = {0};
      int heuristica[8][8] = {22,22,22,22,22,22,22,22,
                              22,24,24,24,24,24,24,22,
                              22,24,26,26,26,26,24,22,
                              22,24,26,28,28,26,24,22,
                              22,24,26,28,28,26,24,22,
                              22,24,26,26,26,26,24,22,
                              22,24,24,24,24,24,24,22,
                              22,22,22,22,22,22,22,22 };
     
      int filaActual = 0;
      int columnaActual = 0;
      int reina = 0;
      int mejor = 30;
      int horizontal, vertical;
      int vertical_positivo, vertical_negativo;// variables para la diagonal //
      int casillas = 0; //variable para comprobar si está todo el tablero ocupado //
     
      while (casillas < 64)
      {
          casillas = 0;
          // revisa todo el tablero para ver la mejor posibilidad (se podría hacer función) //
            for(filaActual = 0; filaActual < 8; filaActual++)
            {
               for(columnaActual = 0; columnaActual < 8; columnaActual++)
               {
                    if( tablero[filaActual][columnaActual] == 0)
                    {
                        if( heuristica[filaActual][columnaActual] < mejor)
                        {
                            mejor = heuristica[filaActual][columnaActual];
                            horizontal = filaActual;
                            vertical = columnaActual;
                        }
                    }
               }
            }
            // fin revisar tablero //
           
            tablero[horizontal][vertical] = 5; // situa la reina en el tablero //
           
            for(columnaActual = 0; columnaActual < 8; columnaActual++)// marca el ataque horizontal de la reina actual (deja las casillas//
            {   
                if(tablero[horizontal][columnaActual] != 5 )
                {                                                     // horizontales ocupadas) //
                   tablero[horizontal][columnaActual] = 1;
                }
            }
           
            for(filaActual = 0; filaActual < 8; filaActual++) // marca el ataque vertical de la reina actual (deja las casillas verticales ocupadas) //
            {
                if ( tablero[filaActual][vertical] != 5 )
                {
                tablero[filaActual][vertical] = 1;
                }
            }
           
            // marca el ataque diagonal de la reina actual (deja las diagonales ocupadas //
           vertical_positivo = vertical;
           vertical_negativo = vertical;
           for(filaActual = horizontal - 1; filaActual >= 0; filaActual--)
            {
              vertical_positivo++;
              vertical_negativo--;
              if (vertical_positivo <= 7 && tablero[filaActual][vertical_positivo] != 5)
              {
                 tablero[filaActual][vertical_positivo] = 1;
              }
              if (vertical_negativo >= 0 && tablero[filaActual][vertical_negativo] != 5)
              {
                 tablero[filaActual][vertical_negativo] = 1;
              } 
            }
           
           vertical_positivo = vertical;
           vertical_negativo = vertical;
           for(filaActual = horizontal + 1; filaActual <= 7; filaActual++)
            {
              vertical_positivo++;
              vertical_negativo--;
              if (vertical_positivo <= 7 && tablero[filaActual][vertical_positivo] != 5)
              {
                 tablero[filaActual][vertical_positivo] = 1;
              }
              if (vertical_negativo >= 0 && tablero[filaActual][vertical_negativo] != 5)
              {
                 tablero[filaActual][vertical_negativo] = 1;
              } 
            }
            // fin ataque diagonal //
           
            // ajustar heuristica//
           
          for(filaActual = 0; filaActual < 8; filaActual++)
          {
            for(columnaActual = 0; columnaActual < 8; columnaActual++)
            {
               heuristica[filaActual][columnaActual] = 0;
            }
          }
           
            for (horizontal = 0; horizontal <= 7; horizontal++)
            {
                for(vertical = 0; vertical <= 7; vertical++)
                {
                   if (tablero[horizontal][vertical] != 1 && tablero[horizontal][vertical] != 5)
                   {
                        for(columnaActual = 0; columnaActual < 8; columnaActual++)// marca el ataque horizontal de la reina actual (deja las casillas horizontales ocupadas) //
                        {   
                            if(tablero[horizontal][columnaActual] != 5 && tablero[horizontal][columnaActual] != 1 )
                            {                                                     
                               heuristica[horizontal][vertical]++;
                            }
                        }
                       
                        for(filaActual = 0; filaActual < 8; filaActual++) // marca el ataque vertical de la reina actual (deja las casillas verticales ocupadas) //
                        {
                            if ( tablero[filaActual][vertical] != 5 && tablero[filaActual][vertical] != 1 )
                            {
                              heuristica[horizontal][vertical]++;
                            }
                        }
                       
                        // marca el ataque diagonal de la reina actual (deja las diagonales ocupadas //
                       vertical_positivo = vertical;
                       vertical_negativo = vertical;
                       for(filaActual = horizontal - 1; filaActual >= 0; filaActual--)
                        {
                          vertical_positivo++;
                          vertical_negativo--;
                          if (vertical_positivo <= 7 && tablero[filaActual][vertical_positivo] != 5 && tablero[filaActual][vertical_positivo] != 1)
                          {
                             heuristica[horizontal][vertical]++;
                          }
                          if (vertical_negativo >= 0 && tablero[filaActual][vertical_negativo] != 5 && tablero[filaActual][vertical_negativo] != 1)
                          {
                             heuristica[horizontal][vertical]++;
                          } 
                        }
                       
                       vertical_positivo = vertical;
                       vertical_negativo = vertical;
                       for(filaActual = horizontal + 1; filaActual <= 7; filaActual++)
                        {
                          vertical_positivo++;
                          vertical_negativo--;
                          if (vertical_positivo <= 7 && tablero[filaActual][vertical_positivo] != 5 && tablero[filaActual][vertical_positivo] != 1)
                          {
                             heuristica[horizontal][vertical]++;
                          }
                          if (vertical_negativo >= 0 && tablero[filaActual][vertical_negativo] != 5 && tablero[filaActual][vertical_negativo] != 1)
                          {
                             heuristica[horizontal][vertical]++;
                          } 
                        }
                        // fin ataque diagonal //
                   }
                             
                }
            } // fin ajustar heuristica //
           
           
            mejor = 30; // reinicia 'mejor' para una nueva reina //
            reina++;
            // revisa el tablero para ver si estan todas las casillas ocupadas //
            for(filaActual = 0; filaActual < 8; filaActual++)
            {
               for(columnaActual = 0; columnaActual < 8; columnaActual++)
               {
                  if (tablero[filaActual][columnaActual] != 0)
                     casillas++;
               }
            } // fin revisar tablero//
           
      }
      // muestra el tablero //
      for(filaActual = 0; filaActual < 8; filaActual++)
      {
        for(columnaActual = 0; columnaActual < 8; columnaActual++)
        {
           printf("%d ",tablero[filaActual][columnaActual] );
        }
        printf("\n");
      }
     
      // muestra la heuristica //
      printf("\n");
     
      for(filaActual = 0; filaActual < 8; filaActual++)
      {
        for(columnaActual = 0; columnaActual < 8; columnaActual++)
        {
           printf("%2d ",heuristica[filaActual][columnaActual] );
        }
        printf("\n");
      }
     
     
      system("pause");
      return 0;
}



[Alex Rodríguez]

Voy a mirarlo, pero tengo que hacerlo con calma pues me da la impresión de que no es algo que se pueda ver en un minuto; en cuanto vaya teniendo alguna información la iré posteando...

[rackdon]

ok. Muchisimas gracias

[Alex Rodríguez]

Te comento después de analizar el código lo que he visto.

Hay cosas en el código que no acabo de entender, quizás tengan explicación pero yo no la alcanzo a ver.

Todo el apartado denominado // ajustar heuristica// no acabo de entender ¿qué es lo que pretendes con ese código?


Aparte del apartado que te he comentado que aparentemente genera una distorsión en la lógica del programa, tenemos el asunto del planteamiento del problema.

El algoritmo planteado está considerando las casillas que son amenazadas desde una posición y eligiendo para colocar la reina la casilla donde se amenazan menos posiciones (que cabe entender es la más prometedora porque permitirá a posteriori más posiciones para colocar otras reinas). ¿Qué es lo que haces en caso de empate? Elegir la primera casilla del conjunto de casillas empatadas.

Así, para colocar la primera reina tienes esta heurística:

                             {22,22,22,22,22,22,22,22,
                            22,24,24,24,24,24,24,22,
                            22,24,26,26,26,26,24,22,
                            22,24,26,28,28,26,24,22,
                            22,24,26,28,28,26,24,22,
                            22,24,26,26,26,26,24,22,
                            22,24,24,24,24,24,24,22,
                            22,22,22,22,22,22,22,22
                           };

Donde el mejor valor posible es 22, existiendo 30 casillas empatadas, de las cuales el algoritmo elige la primera.

Para colocar la segunda reina existen aproximadamente 14 casillas empatadas, eligiéndose la casilla de la segunda fila y última columna.

Y así sucesivamente...

En principio los problemas que presenta este planteamiento son:

a) Suponer que elegir la casilla más prometedora (que amenaza menos casillas) nos lleva a una solución del problema. ¿Estamos seguros de que esta suposición es correcta?

b) Elegir la primera casilla en caso de empate múltiple ¿Y si en vez de elegir la primera fuera mejor elegir la segunda empatada? ¿Y la tercera? ¿Y la cuarta? ¿Y la quinta? ... ¿Y la n?

[Alex Rodríguez]

Para ver que el algoritmo propuesto no sería correcto podríamos analizar qué ocurriría con 4 reinas.

Considera el problema de 4 reinas. El tablero tendría este aspecto:

x x x x
x x x x
x x x x
x x x x

Y el valor heurístico de las casillas tendría este aspecto:

10 10 10 10
10 12 12 10
10 12 12 10
10 10 10 10

Colocamos la primera reina según el algoritmo propuesto:

R  XX XX XX
XX XX 12 10
XX 12 XX 10
XX 10 10 XX

Colocamos la segunda reina según el algoritmo propuesto:

R  XX XX XX
XX XX 12 R
XX 12 XX XX
XX XX 10 XX

Colocamos la tercera reina según el algoritmo propuesto:

R  XX XX XX
XX XX 12 R
XX XX XX XX
XX XX R  XX

Aquí hemos llegado a la situación de que el problema ha ido colocando las reinas según el algoritmo propuesto pero ya no puede colocar la cuarta reina porque todas las casillas están atacadas.

Sin embargo el problema sí tiene solución:

x x R x
R x x x
x x x R
x R x x

Y además más de una solución. Por ejemplo esta es otra:

x R x x
x x x R
R x x x
x x R x

(Esta solución y otras pueden considerarse simetrías. En este caso puede considerarse la visión en espejo de la anterior solución)

Aquí vemos que hay otro factor que resulta importante: si colocamos la primera reina en la primera posición, estamos eligiendo una casilla que amenaza a pocas casillas, pero a su vez estamos eliminando muchas casillas que son prometedoras debido a que quedan atacadas por esa reina.

En resumen:

El algoritmo propuesto está tratando de aplicar una estrategia voraz para resolver el problema: ir tomando decisiones que se consideran las mejores sin posibilidad de vuelta atrás. Esta estrategia no funciona con este problema (no sé si hay alguna forma más avanzada que pudiera hacerla funcionar, pero tal y como está propuesto parece que no).

Este problema se suele poner como ejemplo de aplicación de búsqueda en un espacio de estados: todas las posibles combinaciones de reinas. Las posibilidades se pueden reducir teniendo en cuenta ciertos criterios. La resolución normalmente se basa en backtracking o ramificación y poda y esto tiene su complejidad a la hora de crear un algoritmo que lo implemente (que normalmente será recursivo).

[Alex Rodríguez]

He intentado describir lo que he visto, pero si tuviera que decirlo en una frase sería: el programa no coloca las 8 reinas porque después de colocar unas cuantas reinas ya no puede colocar más porque no le quedan casillas sin atacar, y el motivo para ello es que la lógica que trata de aplicar no es válida.

Saludos.

[rackdon]

Muchas gracias.
el ajuste de heurística que me preguntabas antes, lo que hace es disminuir el número de la heurística en las casillas restantes en función de las que ya se han ocupado.
Por ejemplo, en el caso de las 4 reinas que me propusiste, al poner la primera reina quedaría lo siguiente:
R   XX XX XX
XX XX  4   2
XX  3  XX  4
XX  2   4  XX

Pero ya había pensado en que hubiera un fallo en el planteamiento.
El problema está en que el planteamiento es el propuesto en el ejercicio 6.26 del libro "Como programar c/c++ y java" de Deitel&Deitel. Se supone que según el ejercicio, con este planteamiento se podría solucionar. Ya había pensado en algo recursivo, pero me parecía algo demasiado complejo y lo descarté, pensando que el ejercicio no sería tan dificil. De todas formas, intentaré solucionarlo recursivamente, a ver si lo consigo.

Muchisimas gracias por todo
Un saludo

[Alex Rodríguez]

Sigo sin entender en qué se basa ese ajuste de la heurística.

No digo que sea obligado resolverlo recursivamente, lo que sí es verdad es que en los cursos de algoritmia suele ponerse como ejemplo de ejercicio de recursividad y estrategia de backtracking, pero como en casi todos los problemas hay distintas vías para resolverlo. Incluso es posible que se pueda resolver con una estrategia similar a la planteada, habría que estudiarlo en profundidad.

[rackdon]

Con el ajuste de la heurística, lo que consigo es delimitar mejor las opciones de donde colocar la reina, ya que al colocar una reina, hay muchas casillas que disminuyen drásticamente la cantidad de casillas que eliminarían si se pusiera una reina en esa casilla.
Creo que lo que se consigue es refinar un poco más las posibilidades de colocar la siguiente reina en la casilla que menos casillas elimine.

En cuanto a la recursividad, acabo de ver que en uno de los siguientes ejercicios me plantean resolver este mismo problema a través de la recursividad.