jueves, 4 de marzo de 2010

Proyecto 2

Problema de las ocho reinas


El problema consiste en colocar 8 reinas en un tablero de ajedrez (8×8) de manera tal que ninguna de ellas amenace (pueda comerse) a ninguna de las demás. Una reina amenaza a los cuadrados de la misma columna, fila y de las mismas diagonales.

Es lógico que cada reina debe ir en una fila distinta. Por tanto, en un array se guarda la posición de cada reina en la columna que se encuentre. Ejemplo: si en la tercera fila hay una reina situada en la quinta columna, entonces la tercera posición del array guardará un 5. A este array se le llamará col.
Hace falta otro array que determine si hay puesta una reina en la fila j-ésima. A este array se le llamará fila.
Por último se utilizan dos arrays más para determinar las diagonales libres, y se llamarán diagb y diagc.

Para poner una reina se utiliza esta instrucción:
col[i] = j ; fila[j] = diagb[i+j] = diagc[7+i-j] = FALSE;

Para quitar una reina esta otra:
fila[j] = diagb[i+j] = diagc[7+i-j] = TRUE;

Se considera válida la posición para este caso:
if (fila[j] && diagb[i+j] && diagc[7+i-j]) entonces proceder ...

Aquí esta el código completo en C. Se han utilizado tipos enumerados para representar los valores booleanos.

#include 
 
enum bool {FALSE, TRUE};
typedef enum bool boolean;
 
void ensayar(int i, boolean *q, int col[], boolean fila[], boolean diagb[], boolean diagc[]);
 
int main(void)
{
  int i;
  boolean q;
 
  int col[8];
  boolean fila[8],diagb[15], diagc[15];
 
  for (i = 0; i <>
  for (i = 0; i <>
 
  ensayar(0,&q,col,fila,diagb,diagc);
  if (q) {
    printf("\nSolucion:");
    for (i = 0; i <>
  } else printf("\nNo hay solucion");
 
  return 0;
}
 
void ensayar(int i, boolean *q, int col[], boolean fila[], boolean diagb[], boolean diagc[])
{
  int j;
 
  j = 0;
  *q = FALSE;
  do {
    if (fila[j] && diagb[i+j] && diagc[7+i-j]) {
      col[i] = j; fila[j] = diagb[i+j] = diagc[7+i-j] = FALSE;
      if (i <>
        ensayar(i+1,q,col,fila,diagb,diagc);
        if (!*q)
          fila[j] = diagb[i+j] = diagc[7+i-j] = TRUE;
      } else *q = TRUE; /* encuentra la solucion */
    }
    j++;
  } while (!*q && j <>
}
 

Algoritmo del problema

Procedimiento

reinas(k, col, diag45, diag135)

//sol 1...k es k-prometedor//

//col={soli - i+1 | 1≤ i ≤ k}//


//diag45={soli - i +1 | 1≤ i ≤ k}//

//diag135={soli + i -1 | 1 ≤ i ≤ k}//

si k = 8 entonces // un vector 8 – prometedor es una solucion//

escribir sol

si no // explorar las extensiones (k+1) –prometedoras de sol//

para j← 1 hasta 8 hacer

si j no pertenece a coly j – k no pertenece a diag45y j +

k no pertenece a diag135 entonces

solk+1 ← j // sol1...k+1 es (k+1)-prometedor//

reinas (k+1, col U {j}, diag45 U {j-k}, diag135 U {j+k})


El algoritmo comprueba primero si k = 8, si esto es cierto resulta que tenemos ante nosotros un vector 8-prometedor,

lo cual indica que cumple todas las restricciones originando una solución.

Si k es distinto de 8, el algoritmo explora las extensiones

(k + 1)-prometedoras, para ello realiza un bucle, el cual va de 1 a 8, debido al número de reinas.

Este es un problema de satisfacción de restricciones o CSP, estos problemas

son importantes ya que pueden ser usados para modelar problemas combinatorios,

tales como programación de horarios e inventarios, inteligencia artificial, procesamiento de imágenes

y visión computarizada.

Los CSP son problemas NP-completos, por lo que no pueden existir

solvers completos y eficientes para CSP arbitrarios.


Aqui esta una imagen de una solucion..