/*********************************************************/
/*                                                       */
/*           Projet d'Heuristiques et C.S.P.             */
/*                                                       */
/*          Maitrise Informatique 2001 - 2002            */
/*                                                       */
/*                Saint Pierre - Papin                   */
/*                                                       */
/*********************************************************/

static int VRAI=(0==0);
static int FAUX=(0!=0);

static int echiq[4096]; /* tableau permettant de coder un echiquier */
static int ligne[4096];
static int diag_up[8192];
static int diag_down[8192];
static int nbr; /* nbr est le nombre de reine traité dans le probleme en cours */
static int total = 0;

static int affech;
static int afftot;
static int calctout;

int echiq_affiche() /* affiche l'échiquier courant */
{
 int i,j;

/* for(i=1;i<=nbr;i++)
 {
  printf("%d ",echiq[i]);
 } */

 for(i=1;i<=nbr;i++)
 {
  for(j=1;j<=nbr;j++)
  {
   if(echiq[j]==i)
   {
    printf("O");
   }
   else
   {
    printf(".");
   }
  }
  printf("\n");
 }
 printf("\n");
}

int echiq_place_reine(int i,int j)
{
 echiq[i]=j;
 ligne[j]=diag_up[i+j-1]=diag_down[nbr+i-j]=VRAI;
 return 0;
}

int echiq_enleve_reine(int i,int j)
{
 echiq[i]=0;
 ligne[j]=diag_up[i+j-1]=diag_down[nbr+i-j]=FAUX;
 return 0;
}

int echiq_case_non_menacee(int i,int j)
{
 return ( !(ligne[j]) && !(diag_up[i+j-1]) && !(diag_down[nbr+i-j]) );
}

int backtracking(int i)
{
  int j;
  if (i>nbr)
  {
   total++;
   if ( affech ) { echiq_affiche(); }
   if (calctout) return 0; else return -1;
  }
  for(j=1;j<=nbr;j++)
  {
   if ( echiq_case_non_menacee(i,j) )
   {
    echiq_place_reine(i,j);
    if (backtracking(i+1) == -1) return -1;
    echiq_enleve_reine(i,j);
   }
  }
}

int main(int argc,char *argv[])
   
{
  int i,s,suiv;

  if ( argc != 2 )
    {
      printf("Ce programme prend un et un seul argument en parametre\n");
      printf("     use : \"nom_du_prog nb_de_reines\" ...");
      return 1;
    }
  else
    {
      nbr=atoi(argv[1]);
      if ( ( nbr <= 3 ) || ( nbr >=4096 ) )
      {
       printf("Ce programme ne traite le probleme que pour un nombre\n");
       printf("de reines compris entre 4 et 4095 : \n");
       printf("   - il n'y a pas de solution pour 1, 2 ou 3 reines\n");
       printf("   - ce programme ne peut gérer plus de 1023 reines\n");
      }
      else
      {

       for(i=0;i<2047;i++)
       {
        echiq[i]=0;
        ligne[i]=FAUX;
        diag_up[i]=FAUX;
        diag_up[i+2048]=FAUX;
        diag_down[i]=FAUX;
        diag_down[i+2048]=FAUX;
       }

       total=-1;

       printf("\n\n Bonjour et bienvenu\n\nCalculs possibles pour %d Dames\n\n",nbr);
       printf("1 - Afficher seulement la premiere solution\n");
       printf("2 - Afficher toutes les solutions et le nombre de solutions\n");
       printf("3 - Afficher uniquement le nombre de solutions\n");
       printf("4 - Sortir\n");
       printf("Votre choix ? : ");
       scanf("%d",&s);
       printf("\n\n");

       switch(s)
       {
        case 1 : affech=VRAI;
                 afftot=FAUX;
                 calctout=FAUX;
                 total++;
                 break;
        case 2 : affech=VRAI;
                 afftot=VRAI;
                 calctout=VRAI;
                 total++;
                 break;
        case 3 : affech=FAUX;
                 afftot=VRAI;
                 calctout=VRAI;
                 total++;
                 break;
        default : printf("Au revoir !");
                  break;
        }

       if (total==0)
       {
        backtracking(1);
        if ( afftot )
        {
         printf("Soit un total de %d solutions.\n",total);
         printf("Ces solutions ne sont pas forcement distincts. \nIl faudra supprimer les symetries");
        }
       }
      }
      return 0;
    }
}