Deitel_C++_4.27 ( Ocho Reinas, Enfoque de Fuerza Bruta)

2.27 (Ocho Reinas: Métodos de fuerza bruta) En éste ejercicio, usted desarrollará diversos métodos para resolver el problema de las ocho reinas que presentamos en el ejercicio 4.26.
a) Resuelva el ejercicio de las ocho reinas, utilizando la técnica de la fuerza bruta aleatoria desarrollada en el Ejercicio 4.25
_____________________________________________________________________________________

Una solución al problema de las ocho reinas

SOLUCIÓN:
Esta es la version de fuerza bruta del problema de las ocho reinas. Puede encontrar en este mismo blog el problema resuelto de las Ocho Reinas, Versión Heurística. El proceso es bastante simple. Se generan casillas aleatorias cada vez mediante el lanzamiento de "dados" que determinan tanto la fila como la columna. Después se verifica si esa casilla es viable, es decir, si no esta atacada por otra reina o otra reina no ha sido puesta ya en ese lugar. El proceso se repite hasta completar las ocho (o N) reinas. En los comentarios del programa viene explicado el algoritmo y creo que es fácil de seguir y entender.

/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

       PROBLEMA DE LAS 8 (EN REALIDAD N) REINAS CON EL METODO DE FUERZA BRUTA
      
 ***********************************************************************************/

 /*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 *                              ALGORITMO                                          *
 * Mientras                                                                        *
 *              (contador_reinas < Numero solicitado de reinas)                    *
 *                                  &&                                             *              
 *                  Intentos fallidos < numero grande de fracasos                  *
 *                                                                                 *
 *Elegir aleatoriamente una casilla                                                *
 *                                                                                 *
 * verificar que la casilla este libre (no se haya colocado una reina ahi)         *
 *                                                                                 *
 * <Si la casilla ocupada>                                                         *
 *   incrementa el numero de fracasos                                              *
 *   elige otra casilla aleatoriamente                                             *
 *   y repite el proceso                                                           *
 *                                                                                 *
 * <Si la casilla no esta ocupada>                                                 *
 *  Verifica que la casilla no este atacada                                        * 
 * <Si la casilla esta atacada>                                                    *
 * (Esto se hace revisando que la columna y la fila de la casilla elegida no       *
 *  coincida con ninguna de las respectivas filas y columnas de las reinas ya      *
 *  colocadas, y que la distancia entre dicha fila y la de cualquier reina ya      *
 *  colocada no sea igual a la distancia entre la columna elegida y la columna     *
 *  de cualquier reina ya colocada                *                                *
 *  En otras palabras, si dos reinas se atacan en diagonal, forman un triangulo    *
 *  rectangulo isosceles)                                                          *
 *  igual que la distancia                                                         *
 *  incrementa el numero de fracasos                                               *
 *  elige otra casilla aleatoriamente                                              *
 *  y repite el proceso                                                            *
 * <Si la casilla no esta atacada>                                                 *
 *  coloca la reina ahi (en realidad el numero de contador_reinas ) y              *
 *  aumenta en uno el contador_reinas                                              *
 *                                                                                 *
 * OBSERVACION: Este algoritmo funciona para el problema de las n reinas en un     *
 * tablero de nxn                                                                  *
 *+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/

 #include <iostream>
 using namespace::std;
 #include <ctime>
 #include <cmath>
 #include <cstdlib> 
 const int TAMANO = 8; // Cambiar esta variable por N para resolver el caso de 
                       // las N reinas 
 int Fracasos_Requeridos = 1000;
 // Cambiar tambien esta variable ajunstandola segun un buen criterio para
 // el caso de las N reinas.
 int dado1;
 int dado2;
 int contador_reinas = 0;

 // Prototipos de funcion
 bool Verifica_Posicion( int B[][TAMANO + 1] );
 void Genera_Casilla();
 void Imprime( int C[][TAMANO +1] );

 ////////////////////////////////////////////////////////////////////////////
 // MAIN
 //////////////////////////////////////////////////////////////////////////// 

 int main()
 {      // Abre main
 srand(time(NULL));
 cout <<"\nEste programa resuelve el problema de las " << TAMANO <<" reinas.\n"<<endl;
 bool accesibilidad;
 int A[TAMANO + 1][TAMANO + 1] = {{0, 0, 0}, {0, 0}}; // El arreglo se establece a 0
 int fracasos = 0;
 
 while ( TAMANO > contador_reinas && fracasos < Fracasos_Requeridos )
 {  // Abre while
 Genera_Casilla();
 accesibilidad = Verifica_Posicion(A);
 if( false  == accesibilidad )
 fracasos++;
 else
 A[dado1][dado2] = ++contador_reinas; 
 
 }  // Cierra while
 if (TAMANO != contador_reinas)
 cout<<"\nLo siento. Solo se colocaron " << contador_reinas <<" reinas.\n";
 else
 cout<<"\nSE COLOCARON LAS " << TAMANO << " REINAS!" << endl; 
  
 // Se invoca la funcion Imprime
 Imprime(A);
 }      // Cierra main  

 ////////////////////////////////////////////////////////////////////////
 // GENERA_CASILLA
 ////////////////////////////////////////////////////////////////////////

 void Genera_Casilla()
 {   //Abre funcion Genera_Casilla
 dado1 = 1 + rand() % TAMANO;
 dado2 = 1 + rand() % TAMANO;
 }   // Cierra funcion Genera_Casilla

 /////////////////////////////////////////////////////////////////////////
 // VERIFICA_POSICION
 /////////////////////////////////////////////////////////////////////////

 bool Verifica_Posicion( int B[][TAMANO + 1] )
 {   // Abre Verifica Posicion
 bool estatus = true;
 // Al principio se supone que la casilla es valida
 // y se descartara en el siguiente if si no cumple
 // con ciertas condiciones

 if ( 0 == B[dado1][dado2] )
 // Si la casilla generada esta vacia
 {      // Abre if
 for ( int i = 1; i <= TAMANO; i++ )
 for ( int j = 1; j <= TAMANO; j++ ) 
 {  // Abre for
 // Si la casilla tiene una reina
 if ( 0 != B[i][j] )
 {  // Abre if

 // Si la reina ataca la misma fila o columna
 if (((dado1 == i) || (dado2 == j) ) || ( std::abs(dado1 - i) == std::abs(dado2 -j)))
 // Retorna negativo
 {  
 estatus = false;
 break;
 }
 }  // Cierra if
 }  // Cierra for 
 }  // Cierra if
 
 else
 // Si la casilla genrada no esta vacia, evidentemente no es valida
 estatus = false;

 return estatus;
 // Se retorna el estatus de la casilla, true: valida, 0: invalida

 }   // Cierra Verifica_Posicion 
 
 ///////////////////////////////////////////////////////////////////////////////
 //IMPRIME
 ///////////////////////////////////////////////////////////////////////////////
 
 void Imprime( int C[][TAMANO +1] )
 {    // Abre Imprime
 for ( int k = 1; k <= TAMANO; k++ )
 { 
 for ( int j = 1; j <= TAMANO; j++ )
 {
 cout <<"\t" << C[k][j];
 }
 cout <<"\n\n"<<endl;
 
 }
 }    // Cierra Imprime