/*
+-----------------+
| LAS OCHO REINAS |
+-----------------+

        El  problema  de  las  ocho  reinas  consiste en situar ocho
reinas en  un tablero de ajedrez,  de forma que ninguna  reina pueda
actuar sobre cualquiera de las otras.

        El pseudocódigo de la función ensayar() es el siguiente:

  <PRINCIPIO ensayar> (i: entero)
    inicializar el conjunto de posiciones de la reina i-ésima
    +-REPETIR hacer la selección siguiente
    | +-SI segura ENTONCES
    | | poner reina
    | | +-SI i < 8 ENTONCES
    | | | LLAMAR ensayar (i + 1)
    | | | +-SI no acertado ENTONCES
    | | | |   quitar reina
    | | | +-FINSI
    | | +-FINSI
    | +-FINSI
    +-HASTA acertada O no hay más posiciones
  <FIN>

        Observaciones sobre el código:

    1) Estudiar la función ensayar() a partir de este pseudocódigo.

    2) Vectores utilizados:

       int posiciones_en_columna[8];          RANGO: 1..8 
       BOOLEAN reina_en_fila[8];              RANGO: 1..8 
       BOOLEAN reina_en_diagonal_normal[15];  RANGO: -7..7
       BOOLEAN reina_en_diagonal_inversa[15]; RANGO: 2..16

       En C, el primer elemento de  cada vector tiene índice 0, esto
es fácil solucionarlo con las siguientes macros:

       #define c(i) posiciones_en_columna[(i)-1]
       #define f(i) reina_en_fila[(i)-1]
       #define dn(i) reina_en_diagonal_normal[(i)+7]
       #define di(i) reina_en_diagonal_inversa[(i)-2]

       Significado de los vectores:

       c(i) : la posición de la reina en la columna i
       f(j) : indicativo de que no hay reina en la fila j-ésima
       dn(k): indicativo de  que no hay reina en  la diagonal normal
             (\) k-ésima
       di(k):  indicativo  de  que  no  hay  reina  en  la  diagonal
             invertida (/) k-ésima

       Dado que se  sabe, por las reglas del  ajedrez, que una reina
actúa sobre  todas las piezas situadas  en la misma columna,  fila o
diagonal del tablero se deduce que cada columna puede contener una y
sólo  una reina,  y que  la  elección  de la  situación de  la reina
i-ésima puede restringirse a los cuadros de la columna i. Por tanto,
el parámetro i  se convierte en el índice de  columna, y por ello el
proceso  de  selección  de  posiciones  queda  limitado  a  los ocho
posibles valores del índice de fila j.

       A  partir   de  estos  datos,   la  línea  poner   reina  del
pseudocódigo es:

         c (i) = j; f (j) = di (i + j) = dn (i - j) = FALSE;

       y la línea quitar reina del pseudocódigo:

         f (j) = di (i + j) = dn (i - j) = TRUE;

       y la condición segura del pseudocódigo:

         f (i) && di (i + j) && dn (i - j)
*/

/* Ficheros a incluir: */

#include <stdio.h>  /* printf () */
#include <conio.h>  /* getch () */

/* Macros: */

#define BOOLEAN int
#define TRUE    1
#define FALSE   0

/* Variables globales: */

BOOLEAN acertado;

int posiciones_en_columna[8];
BOOLEAN reina_en_fila[8];
BOOLEAN reina_en_diagonal_normal[15];
BOOLEAN reina_en_diagonal_inversa[15];

#define c(i) posiciones_en_columna[(i)-1]
/* rango de índice: 1..8  */
#define f(i) reina_en_fila[(i)-1]
/* rango de índice: 1..8  */
#define dn(i) reina_en_diagonal_normal[(i)+7]
/* rango de índice: -7..7 */
#define di(i) reina_en_diagonal_inversa[(i)-2]
/* rango de índice: 2..16 */

/* Prototipos de las funciones: */

void proceso (void);
void ensayar (int i);

/* Definiciones de las funciones: */

void main (void)
{
  printf ("\n\nPROBLEMA DE LAS OCHO REINAS:\n  ");
  proceso ();
  printf ("\n\nPulsa cualquier tecla para finalizar. ");
  getch ();
}

void proceso (void)
{
  register int i,j;

  for (i = 1; i <= 8; i++)
    f (i) = TRUE;
  for (i = 2; i <= 16; i++)
    di (i) = TRUE;
  for (i = -7; i <= 7; i++)
    dn (i) = TRUE;

  ensayar (1);

  if (acertado)
    for (printf ("\n\nLA SOLUCION ES:\n\n"), i = 1; i <= 8; i++)
      {
        for (j = 1; j <= 8; j++)
          printf ("%2d", c (j) == i ? 1 : 0);
        printf ("\n");
      }
  else
    printf ("\n\nNO HAY SOLUCION.\n");
}

void ensayar (int i)
{
  int j = 0;

  do
    {
      j++;
      acertado = FALSE;
      if (f (j) && di (i + j) && dn (i - j))
        {
          c (i) = j;
          f (j) = di (i + j) = dn (i - j) = FALSE;
          if (i < 8)
            {
              ensayar (i + 1);
              if (! acertado)
                f (j) = di (i + j) = dn (i - j) = TRUE;
            }
          else
            acertado = TRUE;
        }
    } while (! acertado && j != 8);
}