Deitel_Java_7_25 (Ocho Reinas: Método de Fuerza Bruta)

Una solución al problema de las Ocho Reinas

7.25 (Ocho reinas: método de fuerza bruta) En este ejercicio usted desarrollará varios métodos de fuerza bruta para resolver el problema de las Ocho Reinas que presentamos en el ejercicio 7.24
a) Utilice la técnica de fuerza bruta aleatoria desarrollada en el ejercicio 7.23, para resolver el problema de las Ocho Reinas.
b)Utilice una técnica exhaustiva (es decir, pruebe todas las combinaciones posibles de las ocho reinas en el tablero para resolver el problema de las Ocho Reinas.
c) Por qué el método de la fuerza bruta exhaustiva podría no ser apropiado para resolver el problema del paseo del caballo?
d) Compare y contraste el problema de la fuerza bruta aleatoria con el de la fuerza bruta exhaustiva.

El problema de las N reinas, un caso particular.

Solución
El enfoque de este problema es parecido al circuito del caballo por medio de la fuerza bruta

El método es bastante simple y el código tiene como 150 líneas. En los comentarios se presenta el seudocódigo, que es bastante fácil de seguir. Cambiando un par de variables, indicadas en el programa, se puede de manera sencilla hacer que este programa resuelva el problema de las n reinas en un tablero de nxn. En la imagen lateral puede verse el caso de un tablero de 5x5.

Este código debe guardarse con el nombre de UsaOchoReinas.java

public class UsaOchoReinas

{  // Abre UsaOchoReinas
public static void main(String args[])
{        // Abre main
Ocho_Reinas miObjeto = new Ocho_Reinas();
miObjeto.Principal(); 
}        // Cierra main
}  // Cierra UsaOchoReinas

Este código debe guardarse con el nombre de Ocho_Reinas.java

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

       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                                                                  *
 *+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
 import java.util.Scanner;
 import java.util.Random;

 public class Ocho_Reinas

 {        // Abre clase Ocho_Reinas
 Scanner entrada = new Scanner(System.in);
 Random aleatorio = new Random();
 private int Tamano;
 // Cambiar la variable Tamano para resolver el problema de las
 // n reinas
 private int Fracasos_Requeridos = 1000;
 // Cambiar tambien esta variable ajustandola segun un buen criterio
 // para un Tamano grande
 private int dado1;
 private int dado2;
 private int contador_reinas = 0;

 ///////////////////////////////////////////////////////////
 // Metodo Principal
 ///////////////////////////////////////////////////////////

 public void Principal()
 {    // Abre metodo Principal
 int accesibilidad;

 System.out.println("\nEste programa resuelve el problema de las ocho reinas.");
 System.out.print("\nPor favor introduzca el numero de casillas del tablero.\n");
 Tamano = entrada.nextInt();
 int fracasos = 0;
 int A[][] = new int[Tamano + 1][Tamano + 1];

 while ( Tamano > contador_reinas && fracasos < Fracasos_Requeridos)
 {
 Genera_Casilla(); 
 accesibilidad =  Verifica_Posicion(A);
 if ( 0 == accesibilidad )
 fracasos++;
 else
 A[dado1][dado2] = ++contador_reinas;
 }

 if ( Tamano != contador_reinas)
 System.out.printf("\nLo siento. Solo se colocaron %d reinas\n", contador_reinas);
 else
 System.out.printf("\nSE COLOCARON LAS %d REINAS!\n", Tamano);

 // Se invoca al metodo Imprime
 Imprime(A);

 }    // Cierra metodo Principal

 ///////////////////////////////////////////////////////////////
 // Metodo Genera_Casilla
 ///////////////////////////////////////////////////////////////
 
 public void Genera_Casilla()
 {         // Abre metodo Genera_Casilla
 dado1 = aleatorio.nextInt(Tamano) + 1;
 dado2 = aleatorio.nextInt(Tamano) + 1;
 }        // Cierra metodo Genera_Casilla

 ////////////////////////////////////////////////////////////
 // Metodo Verifica_Posicion
 ////////////////////////////////////////////////////////////  

 public int Verifica_Posicion(int B[][] )
 {         // Abre metodo Verifica_Posicion
 int estatus = 1;
 // 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 ))  || (Math.abs(dado1 - i) == Math.abs(dado2 - j )) )
 // Retorna Negativo
 {
 estatus = 0;
 break;
 }
 }       // Cierra if 
 }   // Cierra for  

 }       // Cierra if
 else
 // Si la casilla generada no esta vacia, evidentemente
 // no es viable
 estatus = 0;

 return estatus;
 // Se retorna el estatus de la casilla
 // 1: valida, 0: invalida
 }         // Cierra metodo Verifica_Posicion

 /////////////////////////////////////////////////////////////
 // Metodo Imprime
 /////////////////////////////////////////////////////////////

 public void Imprime(int C[][])
 {      // Abre Imprime

 for ( int k = 1; k <= Tamano; k++ )
 {
 for ( int j = 1; j <= Tamano; j++)
 {
 System.out.printf("%5d", C[k][j]);
 } 
 System.out.println("\n");
 }
 }     // Cierra imprime

} // Cierra clase Ocho_Reinas