#include <stdio.h>

int ** echiquier;
void cherche(int);
int * reine;
int nbSolutions = 0;
int dim;

int main (void)
{
  int i, j;

  printf("quelle la taille de l'echiquier ? ");
  scanf("%d", &dim);
  reine = (int *) malloc(dim * sizeof(int));
  echiquier = (int **) malloc(dim * sizeof(int *));
  for (i = 0; i < dim; i++)
    echiquier[i] = (int *) malloc(dim * sizeof(int));
  for (i = 0; i < dim; i++)
    for (j = 0; j < dim; j++) echiquier[i] [j]= dim;
  cherche(0);
  for (i = 0; i < dim; i++) free(echiquier[i]);
  free(echiquier);
  return 0;
}

/* Losque l'on rentre dans la fonction cherche avec le parametre 
   qui vaut "colonne", les reines des colonnes 0, 1, ..., colonne - 1 
   sont deja placees. Cette fonction cherche toutes les solutions 
   possibles avec les reines des colonnes 0, 1, ..., colonne - 1 
   placees comme actuellement. Si colonne vaut dim - 1, les solutions
   sont affichees au fur et à mesure ou elles sont trouvees. Sinon, 
   pour chaque case libre de la colonne d'indice colonne :
   - on positionne une reine dans cette case ;
   - on note à "droite" de cette case les cases nouvellement interdites 
   par la reine que l'on vient de positionner en y mettant un entier e
   gal à colonne ;
   - on appelle la fonction cherche avec le parametre egal à colonne + 1 ;
   - on retire la reine que l'on vient de positionner ce qui signifie 
   qu'on "libère" les cases interdites par cette reine. */
void cherche(int colonne)
{
  int i, j, k;

  if (colonne == dim - 1)
    {
      for (i = 0; i < dim; i++)
	if (echiquier[i][colonne] == dim)
	  {
	    nbSolutions++;
	    reine[dim - 1] = i;
	    printf("\nsolution numero %d\n", nbSolutions);
	    for (j = 0; j < dim; j++)
	      printf("une reine sur la ligne %d et la colonne %d\n",
		     reine[j], j);
	  }
      return;
    }
  for (i = 0; i < dim; i++)
    if (echiquier[i][colonne] > colonne)
      {
	reine[colonne] = i; 
	for (j = 1; j < dim - colonne; j++)
	  {
	    if ((j <= i) && 
		(echiquier[i - j][colonne + j] > colonne))
	      echiquier[i - j][colonne + j] = colonne;
	    if (echiquier[i][colonne + j] > colonne)
	      echiquier[i][colonne + j] = colonne;
	    if ((j < dim - i) &&
		(echiquier[i + j][colonne + j] > colonne))
	      echiquier[i + j][colonne + j] = colonne;
	  }
	cherche(colonne + 1);
	for (j = 1; j < dim - colonne; j++)
	  {
	    if ((j <= i) && 
		(echiquier[i - j][colonne + j] == colonne))
	      echiquier[i - j][colonne + j] = dim;
	    if (echiquier[i][colonne + j] == colonne)
	      echiquier[i][colonne + j] = dim;
	    if ((j < dim - i) &&
		(echiquier[i + j][colonne + j] == colonne))
	      echiquier[i + j][colonne + j] = dim;
	  }
      }
}