#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stddef.h>
#include <time.h>
#include <string.h>

 struct Noeud {
     int valx;
     int valy;
     int O[8];
     struct Noeud *radicaux[8];
     struct Noeud *psNoeud;
     struct Noeud *ppNoeud;
 };
 struct XNoeud {
     int T;
     int S;
     int valx;
     int valy;
     int O[8];
     struct XNoeud *radicaux[8];
     struct XNoeud *psNoeud;
     struct XNoeud *ppNoeud;
 };
 struct ENoeud {
     int niveau;
     int rang;       /* rang de traitement [0..nbpos] */
     int nbpos;      /* nb de possibilites X          */
     int T;
     int S;
     int valx;
     int valy;
     int O[8];
     struct ENoeud *radicaux[8];
     struct ENoeud *droite;
     struct ENoeud *gauche;
 };
#define BEL   '\007'             /* caractere ASCII de sonnerie      */
#define dk1   500000             /* nb d'iterations pour "l'exit"    */
#define dk2    50000             /* nb d'iterations en "pause"       */
/*********************** fonctions et Procedures *********************/
struct ENoeud *INIT_GENERATION0(struct Noeud *);
struct ENoeud *ajoutarbre(struct ENoeud *,
                          int,
                          int,
                          int,
                          int,
                          int,
                          int,
                          int,
                          int *,
                          struct ENoeud **);
void affarbre(struct ENoeud *);
void invarbre(struct ENoeud *);
void freearbre(struct ENoeud *);
void autogenearbre0(struct ENoeud *,struct ENoeud *);
void autogenearbre1(struct ENoeud *,
                    struct ENoeud *);
void autogenearbre2(struct ENoeud *,
                    struct ENoeud *);
int decompteX(struct XNoeud *);
int decompteN(struct  Noeud *);
int progressionG(struct Noeud *,struct ENoeud *,int);
int possibleG(struct Noeud *,struct ENoeud *);
int coherenceL(struct Noeud *);
void ECRIT_GRILLE(struct Noeud *,long);
void itoa(int,char *,int);
void inverser(char s[]);

/*********************************************************************
! Recherche automatique de la generation de points                   *
! maximum d'une grille potentielle.                                  *
! by Sibilla Jean-Jacques                                            *
!                                                                    *
! - version :22/01/2007                                              *
!    migration vers athlon i386 GNU/Linux                            *
! - version :26/11/2007                                              *
!   (create a permanent process)                                     * 
! - corrections (stat)  du : 03/07/2008 # 20/08/2008                 *
!   (normalisation)                                                  *
! - corrections cps du : 26/08/2008                                  *
! - implantation de la MAJ automatique du web  le 17/09/2008         *
!                           &  (statistiques)  le 23/09/2008         *
! - extension a 1..280 des resultats possibles le 08/10/2008         *
| - version a jour : 15/06/2009                                      *
! - normalisation de la numerotation de la grille                    *
!   le 31/08/2009                                                    *
! - implementation de l'initialisation (begin from nothing)          *
!   le 25/01/2010
!                                                                    *
!                           Institut de Physique du Globe de Paris   *
!                           Tel : 01.83.95.75.87                     *
!                           E-mail : sibilla@ipgp.fr                 *
!*********************************************************************/ 
int main()
{

FILE *fp,*fp0,*fp1,*fp2;
struct Noeud *TeteA,*pst1,*pst2;
struct Noeud  *ptr,*ptr1;

struct ENoeud *racine;

int id,nbNoeud;
int nmax,nmax_continuous;
int nbLiaison,i;
int rang,nbpos;
int xa,ya;
long bidon_ite,nb,cpt1,cpt2;
long ic,NTot,Stat[500+1];

double sic,N_Stat[500+1];

long compteur_init,compteur_total,compteur;
time_t *tp;

/**********************************************************************/
/*                                                                    */
/* INITIALISATION : initialisation du compteur de noeuds de base nmax */
/*                                                                    */
/**********************************************************************/
  fp=fopen("nb_grilles.ref","r");
  if(fp==NULL) {
     compteur_init=0;
     fp=fopen("nb_grilles.ref","w");
     fprintf(fp,"%d\n",compteur_init);  
     fclose(fp);
     fp=fopen("nb_grilles.ref","r");
  }
  fscanf(fp,"%ld\n",&compteur_init);
  fclose(fp);
/*==============================================*/ 
/* init random "aleatoire" indexe sur l'horaire */
/*==============================================*/  
  tp=(time_t *) malloc(sizeof(time_t));
  *tp=time(tp);
  srand((unsigned int) *tp);
  fp=fopen("rapport_grille.txt","a");
  fprintf(fp,"initiateur nb aleatoire = %d\n\n",*tp);
  fclose(fp);
  /*
  printf("initiateur nb aleatoire = %d\n\n",*tp);
  */
/*==============================================*/ 
  compteur=0;
  TeteA=(struct Noeud *) malloc(sizeof(struct Noeud));
  racine=INIT_GENERATION0(TeteA);
  for(ptr=TeteA;ptr!=NULL;ptr=ptr->psNoeud)   
   {
   xa=ptr->valx;
   ya=ptr->valy;
   for(ptr1=TeteA;ptr1!=NULL;ptr1=ptr1->psNoeud)
     {   
   if((xa==ptr1->valx)&&((ya+1)==ptr1->valy))
     {ptr->radicaux[0]=ptr1;}
   if(((xa-1)==ptr1->valx)&&((ya+1)==ptr1->valy))
     {ptr->radicaux[1]=ptr1;}
   if(((xa-1)==ptr1->valx)&&(ya==ptr1->valy))
     {ptr->radicaux[2]=ptr1;}
   if(((xa-1)==ptr1->valx)&&((ya-1)==ptr1->valy))
     {ptr->radicaux[3]=ptr1;}
   if((xa==ptr1->valx)&&((ya-1)==ptr1->valy))
     {ptr->radicaux[4]=ptr1;}
   if(((xa+1)==ptr1->valx)&&((ya-1)==ptr1->valy))
     {ptr->radicaux[5]=ptr1;}
   if(((xa+1)==ptr1->valx)&&(ya==ptr1->valy))
     {ptr->radicaux[6]=ptr1;}
   if(((xa+1)==ptr1->valx)&&((ya+1)==ptr1->valy))
     {ptr->radicaux[7]=ptr1;}
     }
   }
   autogenearbre1(racine,racine);
   nmax=decompteN(TeteA);
   for(pst1=TeteA;pst1!=NULL;pst1=pst2) {
       pst2=pst1->psNoeud;
       free(pst1);
   }    
   freearbre(racine); 
/************************************************
!                                               *
!       GENERATION de grilles aleatoires        *
!                                               *
!************************************************/
/*===========================*/
/* lecture des statistiques  */
/*===========================*/
  fp1=fopen("statB.dat","r");
  if(fp1==NULL) {
/*===========================*/
/* init des statistiques     */
/*===========================*/
  for(i=1;i<=280;i++) Stat[i]=0;
  fp1=fopen("statB.dat","w");
  fp2=fopen("statB_num.txt","w");
  for(i=1;i<=280;i++) {
     ic=Stat[i];
     fprintf(fp1,"%d\n",ic);
     fprintf(fp2,"%3d %12d\n",i,ic);
  }  
  fclose(fp2);
  }
  fclose(fp1);
  fp1=fopen("statB.dat","r");
  for(i=1;i<=280;i++) {
     fscanf(fp1,"%ld\n",&ic);
     Stat[i]=ic;
  } 
  fclose(fp1);
/*===========================*/
/* generation du fichier     */
/* normalise : N_statB.dat   */
/*===========================*/
  NTot=0;
  for(i=1;i<=280;i++) NTot=NTot+Stat[i]; 
  if(NTot>0) {
  for(i=1;i<=280;i++) N_Stat[i]=(double) Stat[i]/NTot; 
  fp2=fopen("N_statB.dat","w");
  for(i=1;i<=280;i++) {
     sic=N_Stat[i];
     fprintf(fp2,"%g\n",sic);
  }  
  fclose(fp2);
  } 
/*********************************/
  while(1) {
/*********************************/
  compteur=compteur+1;
  if(compteur%dk2 == 0 ) {
     /* 
     printf("%c\n",BEL);
     printf("nb de grilles testees = %d\n\n",compteur);
     */
     compteur_total=compteur_init+compteur;
     fp=fopen("rapport_grille.txt","a");
     fprintf(fp,"nb de grilles testees = %d\n\n",compteur_total);
     fclose(fp);
/*===============================*/
/* 1.- ecriture des statistiques */ 
/*===============================*/
     fp1=fopen("statB.dat","w");
     fp2=fopen("statB_num.txt","w");
     for(i=1;i<=280;i++) {
         fprintf(fp1,"%d\n",Stat[i]);
         fprintf(fp2,"%3d %12d\n",i,Stat[i]);
     } 
     fclose(fp1);
     fclose(fp2);
/*===============================*/
/* 2.- ecriture des statistiques */
/*     (normalisees)             */
/*===============================*/
     NTot=0;
     for(i=1;i<=280;i++) NTot=NTot+Stat[i];
     if(NTot>0) {
     for(i=1;i<=280;i++) N_Stat[i]= (double) Stat[i]/NTot;
     fp2=fopen("N_statB.dat","w");
     for(i=1;i<=280;i++) fprintf(fp2,"%g\n",N_Stat[i]);
     fclose(fp2);
     }
/*****************************************************/
/* Lecture/ecriture des quatre references            */
/* Maj (recriture) de la 3 eme en C                  */
/*                                                   */  
/*  - A. nb d'iterations (constante) pour MAJ        */
/*       a l'ecriture                                */           
/*  - B. nombre de Noeuds (max) a l'ecriture         */
/*  - C. nombre de grilles testees a l'ecriture      */
/*  - D. nombre de grilles en cours                  */
/*      (ici plus grande ou egal que -C.)            */
/*****************************************************/
    fp=fopen("nbs.ref","r");
    if(fp==NULL) {
     fp=fopen("nbs.ref","w");
     fprintf(fp,"%ld\n",0);
     fprintf(fp,"%ld\n",0);
     fprintf(fp,"%ld\n",0);
     fprintf(fp,"%ld\n",0); 
     fclose(fp);
    }
    fp=fopen("nbs.ref","r");
    fscanf(fp,"%ld\n",&bidon_ite);
    fscanf(fp,"%ld\n",&nb);
    fscanf(fp,"%ld\n",&cpt1);
    fscanf(fp,"%ld\n",&cpt2);
    fclose(fp);
    fp=fopen("nbs.ref","w");
    fprintf(fp,"%ld\n",dk2);
    fprintf(fp,"%ld\n",nb);
    fprintf(fp,"%ld\n",cpt1);
    fprintf(fp,"%ld\n",compteur_total);
    fclose(fp);
/*****************************************************/
/* - A. Sortie des 4 references                      */
/* - C. sortie des statistiques                      */
/* appels systeme du generateur IDL de la sortie ps  */
/* conversion en gif et Maj du web                   */
/*****************************************************/
    system("cshAC_MAJnbs>>/dev/null &");
  }
  if(compteur==dk1) {
/**********************************************************************/
/*                                                                    */
/* TERMINAISON : ecriture de la base des iterations locales           */
/*                                                                    */
/**********************************************************************/
  compteur_init+=compteur;
  fp=fopen("nb_grilles.ref","w");
  if(fp==NULL) {
     fp=fopen("nb_grilles.ref","w");
     fprintf(fp,"%ld\n",compteur_init);  
     fclose(fp);
     fp=fopen("nb_grilles.ref","w");
  }
  fprintf(fp,"%ld\n",compteur_init);
  fclose(fp);
  exit(0);
  }
  TeteA=(struct Noeud *) malloc(sizeof(struct Noeud)); 
  racine=INIT_GENERATION0(TeteA);
/************************************************
! generation automatique des liaisons radicales !
!***********************************************/
for(ptr=TeteA;ptr!=NULL;ptr=ptr->psNoeud)   
 {
 xa=ptr->valx;
 ya=ptr->valy;
 for(ptr1=TeteA;ptr1!=NULL;ptr1=ptr1->psNoeud)
   {   
 if((xa==ptr1->valx)&&((ya+1)==ptr1->valy))
   {ptr->radicaux[0]=ptr1;}
 if(((xa-1)==ptr1->valx)&&((ya+1)==ptr1->valy))
   {ptr->radicaux[1]=ptr1;}
 if(((xa-1)==ptr1->valx)&&(ya==ptr1->valy))
   {ptr->radicaux[2]=ptr1;}
 if(((xa-1)==ptr1->valx)&&((ya-1)==ptr1->valy))
   {ptr->radicaux[3]=ptr1;}
 if((xa==ptr1->valx)&&((ya-1)==ptr1->valy))
   {ptr->radicaux[4]=ptr1;}
 if(((xa+1)==ptr1->valx)&&((ya-1)==ptr1->valy))
   {ptr->radicaux[5]=ptr1;}
 if(((xa+1)==ptr1->valx)&&(ya==ptr1->valy))
   {ptr->radicaux[6]=ptr1;}
 if(((xa+1)==ptr1->valx)&&((ya+1)==ptr1->valy))
   {ptr->radicaux[7]=ptr1;}
    }
 }

/************************************************
! generation automatique des liaisons radicales !
! dans l'arbre de structure ENoeud              !
!************************************************/
   autogenearbre1(racine,racine);
/***********************************************/
/* generation des grilles                      */
/***********************************************/
   while(1) {
         nbNoeud=decompteN(TeteA);
         nbpos= possibleG(TeteA,racine);
         if(nbpos==-1) break;
         rang= 1 + (int) nbpos*(rand()/(RAND_MAX+1.0));
         id=progressionG(TeteA,racine,rang);
         }
         nbNoeud=decompteN(TeteA);
         Stat[nbNoeud-36]=Stat[nbNoeud-36]+1;
/************************************************************!
! ecriture de la grille chainee :                            !
! 1.- test reference (maximum) locale                        !
!*************************************************************/ 
     if(nbNoeud>nmax) {
        nmax=nbNoeud;
/*===========================================================!
! ecriture de la grille chainee :                            !
! 2.- si maximum local (nmax) alors test de la reference     !
!     globale (dans "Fichier_Grille.dat")                    !
!============================================================*/
        fp0=fopen("Fichier_Grille.dat","r");
        compteur_total=compteur_init+compteur;
        if(fp0==NULL) { 
           nbLiaison=coherenceL(TeteA); 
           fp1=fopen("rapport_grille.txt","a");
           fprintf(fp1,"nb de grilles testees = %d\n",compteur_total);
           fprintf(fp1,"coherenceL =%d\n",nbLiaison);  
           fprintf(fp1,"decompteN = %d\n\n",nbNoeud-36);
           fclose(fp1);
           ECRIT_GRILLE(TeteA,compteur_total);
           fp0=fopen("Fichier_Grille.dat","r");
        }
        fscanf(fp0,"%4i\n",&nmax_continuous);
        fclose(fp0);
        if(nmax>nmax_continuous) {
           nbLiaison=coherenceL(TeteA); 
           fp1=fopen("rapport_grille.txt","a");
           fprintf(fp1,"nb de grilles testees = %d\n",compteur_total);
           fprintf(fp1,"coherenceL =%d\n",nbLiaison);  
           fprintf(fp1,"decompteN = %d\n\n",nbNoeud-36);
           fclose(fp1);
           ECRIT_GRILLE(TeteA,compteur_total);
        }
       } 
/***********************************************!
! liberation des pointeurs                      !
!************************************************/
   for(pst1=TeteA;pst1!=NULL;pst1=pst2) {
       pst2=pst1->psNoeud;
       free(pst1);
   } 
   freearbre(racine);

}
}
/***********************************************
!                                              *
!       GENERATION de la grille initiale       *
!                                              *
!***********************************************/
struct ENoeud *INIT_GENERATION0(struct Noeud *TeteA) 
{

struct Noeud *pgrille0,*pgrille1;
struct Noeud *ptr;

struct ENoeud *racine;
struct ENoeud *p1,*p2;
struct ENoeud *radicaux[8];

int i,j,k;
int res;
int nbNoeud;
int xa,ya;
int nbLiaison;
int niveau,rang,nbpos,T,S;
int valx,valy;
int O[8];


 pgrille0=TeteA;
 racine=NULL;
 /************/  
 /* Noeud 01 */
 /************/
 pgrille0->valx=3;
 pgrille0->valy=0;
 for(i=0;i<=7;i++) {
 pgrille0->O[i]=0;
 pgrille0->radicaux[i]=NULL;
 }
 pgrille0->ppNoeud=NULL;
 pgrille1=(struct Noeud *) malloc(sizeof(struct Noeud));
 pgrille0->psNoeud=pgrille1;
 /*initialisation de l'arbre ENoeud */
 niveau=1;
 nbpos=0;
 rang=0;
 T=0;
 S=0;
 valx=3;
 valy=0;
 for(i=0;i<=7;i++) {
 O[i]=0;
 radicaux[i]=NULL;
 }
 racine=ajoutarbre(racine,niveau,nbpos,rang,
                   T,S,valx,valy,O,radicaux);
 /************/
 /* Noeud 02 */
 /************/
 pgrille1->valx=4;
 pgrille1->valy=0; 
 for(i=0;i<=7;i++){
 pgrille1->O[i]=0;
 pgrille1->radicaux[i]=NULL;
 }
 pgrille1->ppNoeud=pgrille0;
 pgrille0=pgrille0->psNoeud;
 pgrille1=(struct Noeud *) malloc(sizeof(struct Noeud));
 pgrille0->psNoeud=pgrille1;
 /*initialisation de l'arbre ENoeud */
 niveau=2;
 nbpos=0;
 rang=0;
 T=0;
 S=0;
 valx=4;
 valy=0;
 for(i=0;i<=7;i++) {
 O[i]=0;
 radicaux[i]=NULL;
 }
 racine=ajoutarbre(racine,niveau,nbpos,rang,
                   T,S,valx,valy,O,radicaux);
 /************/
 /* Noeud 03 */
 /************/
 pgrille1->valx=5;
 pgrille1->valy=0;
 for(i=0;i<=7;i++){
 pgrille1->O[i]=0;
 pgrille1->radicaux[i]=NULL;
 } 
 pgrille1->ppNoeud=pgrille0;
 pgrille0=pgrille0->psNoeud;
 pgrille1=(struct Noeud *) malloc(sizeof(struct Noeud));
 pgrille0->psNoeud=pgrille1;
 /*initialisation de l'arbre ENoeud */
 niveau=3;
 nbpos=0;
 rang=0;
 T=0;
 S=0;
 valx=5;
 valy=0;
 for(i=0;i<=7;i++) {
 O[i]=0;
 radicaux[i]=NULL;
 }
 racine=ajoutarbre(racine,niveau,nbpos,rang,
                   T,S,valx,valy,O,radicaux);
 /************/
 /* Noeud 04 */
 /************/
 pgrille1->valx=6;
 pgrille1->valy=0;
 for(i=0;i<=7;i++){
 pgrille1->O[i]=0;
 pgrille1->radicaux[i]=NULL;
 } 
 pgrille1->ppNoeud=pgrille0;
 pgrille0=pgrille0->psNoeud;
 pgrille1=(struct Noeud *) malloc(sizeof(struct Noeud));
 pgrille0->psNoeud=pgrille1;
 /*initialisation de l'arbre ENoeud */
 niveau=4;
 nbpos=0;
 rang=0;
 T=0;
 S=0;
 valx=6;
 valy=0;
 for(i=0;i<=7;i++) {
 O[i]=0;
 radicaux[i]=NULL;
 }
 racine=ajoutarbre(racine,niveau,nbpos,rang,
                   T,S,valx,valy,O,radicaux);
 /************/
 /* Noeud 05 */
 /************/
 pgrille1->valx=3;
 pgrille1->valy=1;
 for(i=0;i<=7;i++){
 pgrille1->O[i]=0;
 pgrille1->radicaux[i]=NULL;
 } 
 pgrille1->ppNoeud=pgrille0;
 pgrille0=pgrille0->psNoeud;
 pgrille1=(struct Noeud *) malloc(sizeof(struct Noeud));
 pgrille0->psNoeud=pgrille1;
 /*initialisation de l'arbre ENoeud */
 niveau=5;
 nbpos=0;
 rang=0;
 T=0;
 S=0;
 valx=3;
 valy=1;
 for(i=0;i<=7;i++) {
 O[i]=0;
 radicaux[i]=NULL;
 }
 racine=ajoutarbre(racine,niveau,nbpos,rang,
                   T,S,valx,valy,O,radicaux);
 /************/
 /* Noeud 06 */
 /************/
 pgrille1->valx=6;
 pgrille1->valy=1;
 for(i=0;i<=7;i++){
 pgrille1->O[i]=0;
 pgrille1->radicaux[i]=NULL;
 } 
 pgrille1->ppNoeud=pgrille0;
 pgrille0=pgrille0->psNoeud;
 pgrille1=(struct Noeud *) malloc(sizeof(struct Noeud));
 pgrille0->psNoeud=pgrille1;
 /*initialisation de l'arbre ENoeud */
 niveau=6;
 nbpos=0;
 rang=0;
 T=0;
 S=0;
 valx=6;
 valy=1;
 for(i=0;i<=7;i++) {
 O[i]=0;
 radicaux[i]=NULL;
 }
 racine=ajoutarbre(racine,niveau,nbpos,rang,
                   T,S,valx,valy,O,radicaux);
 /************/
 /* Noeud 07 */
 /************/
 pgrille1->valx=3;
 pgrille1->valy=2;
 for(i=0;i<=7;i++){
 pgrille1->O[i]=0;
 pgrille1->radicaux[i]=NULL;
 } 
 pgrille1->ppNoeud=pgrille0;
 pgrille0=pgrille0->psNoeud;
 pgrille1=(struct Noeud *) malloc(sizeof(struct Noeud));
 pgrille0->psNoeud=pgrille1;
 /*initialisation de l'arbre ENoeud */
 niveau=7;
 nbpos=0;
 rang=0;
 T=0;
 S=0;
 valx=3;
 valy=2;
 for(i=0;i<=7;i++) {
 O[i]=0;
 radicaux[i]=NULL;
 }
 racine=ajoutarbre(racine,niveau,nbpos,rang,
                   T,S,valx,valy,O,radicaux);
 /************/
 /* Noeud 08 */
 /************/
 pgrille1->valx=6;
 pgrille1->valy=2;
 for(i=0;i<=7;i++){
 pgrille1->O[i]=0;
 pgrille1->radicaux[i]=NULL;
 } 
 pgrille1->ppNoeud=pgrille0;
 pgrille0=pgrille0->psNoeud;
 pgrille1=(struct Noeud *) malloc(sizeof(struct Noeud));
 pgrille0->psNoeud=pgrille1;
 /*initialisation de l'arbre ENoeud */
 niveau=8;
 nbpos=0;
 rang=0;
 T=0;
 S=0;
 valx=6;
 valy=2;
 for(i=0;i<=7;i++) {
 O[i]=0;
 radicaux[i]=NULL;
 }
 racine=ajoutarbre(racine,niveau,nbpos,rang,
                    T,S,valx,valy,O,radicaux);
 /************/
 /* Noeud 09 */
 /************/
 pgrille1->valx=0;
 pgrille1->valy=3;
 for(i=0;i<=7;i++){
 pgrille1->O[i]=0;
 pgrille1->radicaux[i]=NULL;
 } 
 pgrille1->ppNoeud=pgrille0;
 pgrille0=pgrille0->psNoeud;
 pgrille1=(struct Noeud *) malloc(sizeof(struct Noeud));
 pgrille0->psNoeud=pgrille1;
 /*initialisation de l'arbre ENoeud */
 niveau=9;
 nbpos=0;
 rang=0;
 T=0;
 S=0;
 valx=0;
 valy=3;
 for(i=0;i<=7;i++) {
 O[i]=0;
 radicaux[i]=NULL;
 }
 racine=ajoutarbre(racine,niveau,nbpos,rang,
                   T,S,valx,valy,O,radicaux);
 /************/
 /* Noeud 10 */
 /************/
 pgrille1->valx=1;
 pgrille1->valy=3;
 for(i=0;i<=7;i++){
 pgrille1->O[i]=0;
 pgrille1->radicaux[i]=NULL;
 } 
 pgrille1->ppNoeud=pgrille0;
 pgrille0=pgrille0->psNoeud;
 pgrille1=(struct Noeud *) malloc(sizeof(struct Noeud));
 pgrille0->psNoeud=pgrille1;
 /*initialisation de l'arbre ENoeud */
 niveau=10;
 nbpos=0;
 rang=0;
 T=0;
 S=0;
 valx=1;
 valy=3;
 for(i=0;i<=7;i++) {
 O[i]=0;
 radicaux[i]=NULL;
 }
 racine=ajoutarbre(racine,niveau,nbpos,rang,
                   T,S,valx,valy,O,radicaux);
 /************/
 /* Noeud 11 */
 /************/
 pgrille1->valx=2;
 pgrille1->valy=3;
 for(i=0;i<=7;i++){
 pgrille1->O[i]=0;
 pgrille1->radicaux[i]=NULL;
 } 
 pgrille1->ppNoeud=pgrille0;
 pgrille0=pgrille0->psNoeud;
 pgrille1=(struct Noeud *) malloc(sizeof(struct Noeud));
 pgrille0->psNoeud=pgrille1;
 /*initialisation de l'arbre ENoeud */
 niveau=11;
 nbpos=0;
 rang=0;
 T=0;
 S=0;
 valx=2;
 valy=3;
 for(i=0;i<=7;i++) {
 O[i]=0;
 radicaux[i]=NULL;
 }
 racine=ajoutarbre(racine,niveau,nbpos,rang,
                   T,S,valx,valy,O,radicaux);
 /************/
 /* Noeud 12 */
 /************/
 pgrille1->valx=3;
 pgrille1->valy=3;
 for(i=0;i<=7;i++){
 pgrille1->O[i]=0;
 pgrille1->radicaux[i]=NULL;
 } 
 pgrille1->ppNoeud=pgrille0;
 pgrille0=pgrille0->psNoeud;
 pgrille1=(struct Noeud *) malloc(sizeof(struct Noeud));
 pgrille0->psNoeud=pgrille1;
 /*initialisation de l'arbre ENoeud */
 niveau=12;
 nbpos=0;
 rang=0;
 T=0;
 S=0;
 valx=3;
 valy=3;
 for(i=0;i<=7;i++) {
 O[i]=0;
 radicaux[i]=NULL;
 }
 racine=ajoutarbre(racine,niveau,nbpos,rang,
                   T,S,valx,valy,O,radicaux);
 /************/
 /* Noeud 13 */
 /************/
 pgrille1->valx=6;
 pgrille1->valy=3;
 for(i=0;i<=7;i++){
 pgrille1->O[i]=0;
 pgrille1->radicaux[i]=NULL;
 } 
 pgrille1->ppNoeud=pgrille0;
 pgrille0=pgrille0->psNoeud;
 pgrille1=(struct Noeud *) malloc(sizeof(struct Noeud));
 pgrille0->psNoeud=pgrille1;
 /*initialisation de l'arbre ENoeud */
 niveau=13;
 nbpos=0;
 rang=0;
 T=0;
 S=0;
 valx=6;
 valy=3;
 for(i=0;i<=7;i++) {
 O[i]=0;
 radicaux[i]=NULL;
 }
 racine=ajoutarbre(racine,niveau,nbpos,rang,
                   T,S,valx,valy,O,radicaux);
 /************/
 /* Noeud 14 */
 /************/
 pgrille1->valx=7;
 pgrille1->valy=3;
 for(i=0;i<=7;i++){
 pgrille1->O[i]=0;
 pgrille1->radicaux[i]=NULL;
 } 
 pgrille1->ppNoeud=pgrille0;
 pgrille0=pgrille0->psNoeud;
 pgrille1=(struct Noeud *) malloc(sizeof(struct Noeud));
 pgrille0->psNoeud=pgrille1;
 /*initialisation de l'arbre ENoeud */
 niveau=14;
 nbpos=0;
 rang=0;
 T=0;
 S=0;
 valx=7;
 valy=3;
 for(i=0;i<=7;i++) {
 O[i]=0;
 radicaux[i]=NULL;
 }
 racine=ajoutarbre(racine,niveau,nbpos,rang,
                   T,S,valx,valy,O,radicaux);
 /************/
 /* Noeud 15 */
 /************/
 pgrille1->valx=8;
 pgrille1->valy=3;
 for(i=0;i<=7;i++){
 pgrille1->O[i]=0;
 pgrille1->radicaux[i]=NULL;
 } 
 pgrille1->ppNoeud=pgrille0;
 pgrille0=pgrille0->psNoeud;
 pgrille1=(struct Noeud *) malloc(sizeof(struct Noeud));
 pgrille0->psNoeud=pgrille1;
 /*initialisation de l'arbre ENoeud */
 niveau=15;
 nbpos=0;
 rang=0;
 T=0;
 S=0;
 valx=8;
 valy=3;
 for(i=0;i<=7;i++) {
 O[i]=0;
 radicaux[i]=NULL;
 }
 racine=ajoutarbre(racine,niveau,nbpos,rang,
                   T,S,valx,valy,O,radicaux);
 /************/
 /* Noeud 16 */
 /************/
 pgrille1->valx=9;
 pgrille1->valy=3;
 for(i=0;i<=7;i++){
 pgrille1->O[i]=0;
 pgrille1->radicaux[i]=NULL;
 } 
 pgrille1->ppNoeud=pgrille0;
 pgrille0=pgrille0->psNoeud;
 pgrille1=(struct Noeud *) malloc(sizeof(struct Noeud));
 pgrille0->psNoeud=pgrille1;
 /*initialisation de l'arbre ENoeud */
 niveau=16;
 nbpos=0;
 rang=0;
 T=0;
 S=0;
 valx=9;
 valy=3;
 for(i=0;i<=7;i++) {
 O[i]=0;
 radicaux[i]=NULL;
 }
 racine=ajoutarbre(racine,niveau,nbpos,rang,
                   T,S,valx,valy,O,radicaux);
 /************/
 /* Noeud 17 */
 /************/
 pgrille1->valx=0;
 pgrille1->valy=4;
 for(i=0;i<=7;i++){
 pgrille1->O[i]=0;
 pgrille1->radicaux[i]=NULL;
 } 
 pgrille1->ppNoeud=pgrille0;
 pgrille0=pgrille0->psNoeud;
 pgrille1=(struct Noeud *) malloc(sizeof(struct Noeud));
 pgrille0->psNoeud=pgrille1;
 /*initialisation de l'arbre ENoeud */
 niveau=17;
 nbpos=0;
 rang=0;
 T=0;
 S=0;
 valx=0;
 valy=4;
 for(i=0;i<=7;i++) {
 O[i]=0;
 radicaux[i]=NULL;
 }
 racine=ajoutarbre(racine,niveau,nbpos,rang,
                   T,S,valx,valy,O,radicaux);
 /************/
 /* Noeud 18 */
 /************/
 pgrille1->valx=9;
 pgrille1->valy=4;
 for(i=0;i<=7;i++){
 pgrille1->O[i]=0;
 pgrille1->radicaux[i]=NULL;
 } 
 pgrille1->ppNoeud=pgrille0;
 pgrille0=pgrille0->psNoeud;
 pgrille1=(struct Noeud *) malloc(sizeof(struct Noeud));
 pgrille0->psNoeud=pgrille1;
 /*initialisation de l'arbre ENoeud */
 niveau=18;
 nbpos=0;
 rang=0;
 T=0;
 S=0;
 valx=9;
 valy=4;
 for(i=0;i<=7;i++) {
 O[i]=0;
 radicaux[i]=NULL;
 }
 racine=ajoutarbre(racine,niveau,nbpos,rang,
                   T,S,valx,valy,O,radicaux);
 /************/
 /* Noeud 19 */
 /************/
 pgrille1->valx=0;
 pgrille1->valy=5;
 for(i=0;i<=7;i++){
 pgrille1->O[i]=0;
 pgrille1->radicaux[i]=NULL;
 } 
 pgrille1->ppNoeud=pgrille0;
 pgrille0=pgrille0->psNoeud;
 pgrille1=(struct Noeud *) malloc(sizeof(struct Noeud));
 pgrille0->psNoeud=pgrille1;
 /*initialisation de l'arbre ENoeud */
 niveau=19;
 nbpos=0;
 rang=0;
 T=0;
 S=0;
 valx=0;
 valy=5;
 for(i=0;i<=7;i++) {
 O[i]=0;
 radicaux[i]=NULL;
 }
 racine=ajoutarbre(racine,niveau,nbpos,rang,
                   T,S,valx,valy,O,radicaux);
 /************/
 /* Noeud 20 */
 /************/
 pgrille1->valx=9;
 pgrille1->valy=5;
 for(i=0;i<=7;i++){
 pgrille1->O[i]=0;
 pgrille1->radicaux[i]=NULL;
 } 
 pgrille1->ppNoeud=pgrille0;
 pgrille0=pgrille0->psNoeud;
 pgrille1=(struct Noeud *) malloc(sizeof(struct Noeud));
 pgrille0->psNoeud=pgrille1;
 /*initialisation de l'arbre ENoeud */
 niveau=20;
 nbpos=0;
 rang=0;
 T=0;
 S=0;
 valx=9;
 valy=5;
 for(i=0;i<=7;i++) {
 O[i]=0;
 radicaux[i]=NULL;
 }
 racine=ajoutarbre(racine,niveau,nbpos,rang,
                   T,S,valx,valy,O,radicaux);
 /************/
 /* Noeud 21 */
 /************/
 pgrille1->valx=0;
 pgrille1->valy=6;
 for(i=0;i<=7;i++){
 pgrille1->O[i]=0;
 pgrille1->radicaux[i]=NULL;
 } 
 pgrille1->ppNoeud=pgrille0;
 pgrille0=pgrille0->psNoeud;
 pgrille1=(struct Noeud *) malloc(sizeof(struct Noeud));
 pgrille0->psNoeud=pgrille1;
 /*initialisation de l'arbre ENoeud */
 niveau=21;
 nbpos=0;
 rang=0;
 T=0;
 S=0;
 valx=0;
 valy=6;
 for(i=0;i<=7;i++) {
 O[i]=0;
 radicaux[i]=NULL;
 }
 racine=ajoutarbre(racine,niveau,nbpos,rang,
                   T,S,valx,valy,O,radicaux);
 /************/
 /* Noeud 22 */
 /************/
 pgrille1->valx=1;
 pgrille1->valy=6;
 for(i=0;i<=7;i++){
 pgrille1->O[i]=0;
 pgrille1->radicaux[i]=NULL;
 } 
 pgrille1->ppNoeud=pgrille0;
 pgrille0=pgrille0->psNoeud;
 pgrille1=(struct Noeud *) malloc(sizeof(struct Noeud));
 pgrille0->psNoeud=pgrille1;
 /*initialisation de l'arbre ENoeud */
 niveau=22;
 nbpos=0;
 rang=0;
 T=0;
 S=0;
 valx=1;
 valy=6;
 for(i=0;i<=7;i++) {
 O[i]=0;
 radicaux[i]=NULL;
 }
 racine=ajoutarbre(racine,niveau,nbpos,rang,
                   T,S,valx,valy,O,radicaux);
 /************/
 /* Noeud 23 */
 /************/
 pgrille1->valx=2;
 pgrille1->valy=6;
 for(i=0;i<=7;i++){
 pgrille1->O[i]=0;
 pgrille1->radicaux[i]=NULL;
 } 
 pgrille1->ppNoeud=pgrille0;
 pgrille0=pgrille0->psNoeud;
 pgrille1=(struct Noeud *) malloc(sizeof(struct Noeud));
 pgrille0->psNoeud=pgrille1;
 /*initialisation de l'arbre ENoeud */
 niveau=23;
 nbpos=0;
 rang=0;
 T=0;
 S=0;
 valx=2;
 valy=6;
 for(i=0;i<=7;i++) {
 O[i]=0;
 radicaux[i]=NULL;
 }
 racine=ajoutarbre(racine,niveau,nbpos,rang,
                   T,S,valx,valy,O,radicaux);
 /************/
 /* Noeud 24 */
 /************/
 pgrille1->valx=3;
 pgrille1->valy=6;
 for(i=0;i<=7;i++){
 pgrille1->O[i]=0;
 pgrille1->radicaux[i]=NULL;
 } 
 pgrille1->ppNoeud=pgrille0;
 pgrille0=pgrille0->psNoeud;
 pgrille1=(struct Noeud *) malloc(sizeof(struct Noeud));
 pgrille0->psNoeud=pgrille1;
 /*initialisation de l'arbre ENoeud */
 niveau=24;
 nbpos=0;
 rang=0;
 T=0;
 S=0;
 valx=3;
 valy=6;
 for(i=0;i<=7;i++) {
 O[i]=0;
 radicaux[i]=NULL;
 }
 racine=ajoutarbre(racine,niveau,nbpos,rang,
                   T,S,valx,valy,O,radicaux);
 /************/
 /* Noeud 25 */
 /************/
 pgrille1->valx=6;
 pgrille1->valy=6;
 for(i=0;i<=7;i++){
 pgrille1->O[i]=0;
 pgrille1->radicaux[i]=NULL;
 } 
 pgrille1->ppNoeud=pgrille0;
 pgrille0=pgrille0->psNoeud;
 pgrille1=(struct Noeud *) malloc(sizeof(struct Noeud));
 pgrille0->psNoeud=pgrille1;
 /*initialisation de l'arbre ENoeud */
 niveau=25;
 nbpos=0;
 rang=0;
 T=0;
 S=0;
 valx=6;
 valy=6;
 for(i=0;i<=7;i++) {
 O[i]=0;
 radicaux[i]=NULL;
 }
 racine=ajoutarbre(racine,niveau,nbpos,rang,
                   T,S,valx,valy,O,radicaux);
 /************/
 /* Noeud 26 */
 /************/
 pgrille1->valx=7;
 pgrille1->valy=6;
 for(i=0;i<=7;i++){
 pgrille1->O[i]=0;
 pgrille1->radicaux[i]=NULL;
 } 
 pgrille1->ppNoeud=pgrille0;
 pgrille0=pgrille0->psNoeud;
 pgrille1=(struct Noeud *) malloc(sizeof(struct Noeud));
 pgrille0->psNoeud=pgrille1;
 /*initialisation de l'arbre ENoeud */
 niveau=26;
 nbpos=0;
 rang=0;
 T=0;
 S=0;
 valx=7;
 valy=6;
 for(i=0;i<=7;i++) {
 O[i]=0;
 radicaux[i]=NULL;
 }
 racine=ajoutarbre(racine,niveau,nbpos,rang,
                   T,S,valx,valy,O,radicaux);
 /************/
 /* Noeud 27 */
 /************/
 pgrille1->valx=8;
 pgrille1->valy=6;
 for(i=0;i<=7;i++){
 pgrille1->O[i]=0;
 pgrille1->radicaux[i]=NULL;
 } 
 pgrille1->ppNoeud=pgrille0;
 pgrille0=pgrille0->psNoeud;
 pgrille1=(struct Noeud *) malloc(sizeof(struct Noeud));
 pgrille0->psNoeud=pgrille1;
 /*initialisation de l'arbre ENoeud */
 niveau=27;
 nbpos=0;
 rang=0;
 T=0;
 S=0;
 valx=8;
 valy=6;
 for(i=0;i<=7;i++) {
 O[i]=0;
 radicaux[i]=NULL;
 }
 racine=ajoutarbre(racine,niveau,nbpos,rang,
                   T,S,valx,valy,O,radicaux);
 /************/
 /* Noeud 28 */
 /************/
 pgrille1->valx=9;
 pgrille1->valy=6;
 for(i=0;i<=7;i++){
 pgrille1->O[i]=0;
 pgrille1->radicaux[i]=NULL;
 } 
 pgrille1->ppNoeud=pgrille0;
 pgrille0=pgrille0->psNoeud;
 pgrille1=(struct Noeud *) malloc(sizeof(struct Noeud));
 pgrille0->psNoeud=pgrille1;
 /*initialisation de l'arbre ENoeud */
 niveau=28;
 nbpos=0;
 rang=0;
 T=0;
 S=0;
 valx=9;
 valy=6;
 for(i=0;i<=7;i++) {
 O[i]=0;
 radicaux[i]=NULL;
 }
 racine=ajoutarbre(racine,niveau,nbpos,rang,
                   T,S,valx,valy,O,radicaux);
 /************/
 /* Noeud 29 */
 /************/
 pgrille1->valx=3;
 pgrille1->valy=7;
 for(i=0;i<=7;i++){
 pgrille1->O[i]=0;
 pgrille1->radicaux[i]=NULL;
 } 
 pgrille1->ppNoeud=pgrille0;
 pgrille0=pgrille0->psNoeud;
 pgrille1=(struct Noeud *) malloc(sizeof(struct Noeud));
 pgrille0->psNoeud=pgrille1;
 /*initialisation de l'arbre ENoeud */
 niveau=29;
 nbpos=0;
 rang=0;
 T=0;
 S=0;
 valx=3;
 valy=7;
 for(i=0;i<=7;i++) {
 O[i]=0;
 radicaux[i]=NULL;
 }
 racine=ajoutarbre(racine,niveau,nbpos,rang,
                   T,S,valx,valy,O,radicaux);
 /************/
 /* Noeud 30 */
 /************/
 pgrille1->valx=6;
 pgrille1->valy=7;
 for(i=0;i<=7;i++){
 pgrille1->O[i]=0;
 pgrille1->radicaux[i]=NULL;
 } 
 pgrille1->ppNoeud=pgrille0;
 pgrille0=pgrille0->psNoeud;
 pgrille1=(struct Noeud *) malloc(sizeof(struct Noeud));
 pgrille0->psNoeud=pgrille1;   
 /*initialisation de l'arbre ENoeud */
 niveau=30;
 nbpos=0;
 rang=0;
 T=0;
 S=0;
 valx=6;
 valy=7;
 for(i=0;i<=7;i++) {
 O[i]=0;
 radicaux[i]=NULL;
 }
 racine=ajoutarbre(racine,niveau,nbpos,rang,
                   T,S,valx,valy,O,radicaux);
 /************/
 /* Noeud 31 */
 /************/
 pgrille1->valx=3;
 pgrille1->valy=8;
 for(i=0;i<=7;i++){
 pgrille1->O[i]=0;
 pgrille1->radicaux[i]=NULL;
 } 
 pgrille1->ppNoeud=pgrille0;
 pgrille0=pgrille0->psNoeud;
 pgrille1=(struct Noeud *) malloc(sizeof(struct Noeud));
 pgrille0->psNoeud=pgrille1;
 /*initialisation de l'arbre ENoeud */
 niveau=31;
 nbpos=0;
 rang=0;
 T=0;
 S=0;
 valx=3;
 valy=8;
 for(i=0;i<=7;i++) {
 O[i]=0;
 radicaux[i]=NULL;
 }
 racine=ajoutarbre(racine,niveau,nbpos,rang,
                   T,S,valx,valy,O,radicaux);
 /************/
 /* Noeud 32 */
 /************/
 pgrille1->valx=6;
 pgrille1->valy=8;
 for(i=0;i<=7;i++){
 pgrille1->O[i]=0;
 pgrille1->radicaux[i]=NULL;
 } 
 pgrille1->ppNoeud=pgrille0;
 pgrille0=pgrille0->psNoeud;
 pgrille1=(struct Noeud *) malloc(sizeof(struct Noeud));
 pgrille0->psNoeud=pgrille1;
 /*initialisation de l'arbre ENoeud */
 niveau=32;
 nbpos=0;
 rang=0;
 T=0;
 S=0;
 valx=6;
 valy=8;
 for(i=0;i<=7;i++) {
 O[i]=0;
 radicaux[i]=NULL;
 }
 racine=ajoutarbre(racine,niveau,nbpos,rang,
                   T,S,valx,valy,O,radicaux);
 /************/
 /* Noeud 33 */
 /************/
 pgrille1->valx=3;
 pgrille1->valy=9;
 for(i=0;i<=7;i++){
 pgrille1->O[i]=0;
 pgrille1->radicaux[i]=NULL;
 } 
 pgrille1->ppNoeud=pgrille0;
 pgrille0=pgrille0->psNoeud;
 pgrille1=(struct Noeud *) malloc(sizeof(struct Noeud));
 pgrille0->psNoeud=pgrille1;
 /*initialisation de l'arbre ENoeud */
 niveau=33;
 nbpos=0;
 rang=0;
 T=0;
 S=0;
 valx=3;
 valy=9;
 for(i=0;i<=7;i++) {
 O[i]=0;
 radicaux[i]=NULL;
 }
 racine=ajoutarbre(racine,niveau,nbpos,rang,
                   T,S,valx,valy,O,radicaux);
 /************/
 /* Noeud 34 */
 /************/
 pgrille1->valx=4;
 pgrille1->valy=9;
 for(i=0;i<=7;i++){
 pgrille1->O[i]=0;
 pgrille1->radicaux[i]=NULL;
 } 
 pgrille1->ppNoeud=pgrille0;
 pgrille0=pgrille0->psNoeud;
 pgrille1=(struct Noeud *) malloc(sizeof(struct Noeud));
 pgrille0->psNoeud=pgrille1;
 /*initialisation de l'arbre ENoeud */
 niveau=34;
 nbpos=0;
 rang=0;
 T=0;
 S=0;
 valx=4;
 valy=9;
 for(i=0;i<=7;i++) {
 O[i]=0;
 radicaux[i]=NULL;
 }
 racine=ajoutarbre(racine,niveau,nbpos,rang,
                   T,S,valx,valy,O,radicaux);
 /************/
 /* Noeud 35 */
 /************/
 pgrille1->valx=5;
 pgrille1->valy=9;
 for(i=0;i<=7;i++){
 pgrille1->O[i]=0;
 pgrille1->radicaux[i]=NULL;
 } 
 pgrille1->ppNoeud=pgrille0;
 pgrille0=pgrille0->psNoeud;
 pgrille1=(struct Noeud *) malloc(sizeof(struct Noeud));
 pgrille0->psNoeud=pgrille1;
 /*initialisation de l'arbre ENoeud */
 niveau=35;
 nbpos=0;
 rang=0;
 T=0;
 S=0;
 valx=5;
 valy=9;
 for(i=0;i<=7;i++) {
 O[i]=0;
 radicaux[i]=NULL;
 }
 racine=ajoutarbre(racine,niveau,nbpos,rang,
                   T,S,valx,valy,O,radicaux);
 /************/
 /* Noeud 36 */
 /************/
 pgrille1->valx=6;
 pgrille1->valy=9;
 for(i=0;i<=7;i++){
 pgrille1->O[i]=0; 
 pgrille1->radicaux[i]=NULL;
 } 
 pgrille1->ppNoeud=pgrille0;
 pgrille1->psNoeud=NULL;
 /*initialisation de l'arbre ENoeud */
 niveau=36;
 nbpos=0;
 rang=0;
 T=0;
 S=0;
 valx=6;
 valy=9;
 for(i=0;i<=7;i++) {
 O[i]=0;
 radicaux[i]=NULL;
 }
 racine=ajoutarbre(racine,niveau,nbpos,rang,
                   T,S,valx,valy,O,radicaux);

 return racine;
}
/**********************************************
! Fonction                                    !
! progression elementaire (+1) sur une grille !
! et MAJ de l'arbre d'ETAT                    !
!*********************************************/
int progressionG(struct Noeud *pAgrille,struct ENoeud *racine,
                 int rang)
{

 void echange(struct XNoeud *,struct XNoeud *);

 struct Noeud *px,*py;
 struct Noeud *ptr,*ptr1;
 struct Noeud *pRESULTAT;

 struct ENoeud *pNOEUDETAT;
 struct ENoeud *pz;
 struct ENoeud *radicaux[8];

 struct XNoeud *pos;
 struct XNoeud *pts;
 struct XNoeud *pts1,*pts2,*pts3;
 struct XNoeud *p1,*p2;
 struct XNoeud *TeteC,*TeteD,*pfixe;

 int i,j,i1,j1;
 int igene0,igene1;
 int v[500],t[500];
 int xa,ya;
 int xmin,ymin;
 int ok,trouve;

 int Tmin,Smin;
 int T1,S1,x1,y1;
 int T2,S2,x2,y2;
 int Tp,Sp,xp,yp;

 int niveau,nbpos,T,S;
 int valx,valy;
 int O[8];

 /*************************************************/
 /* chaine de tous les Noeuds possibles valorises */
 /*************************************************/
 p1=NULL; 
 pos=(struct XNoeud *) malloc(sizeof(struct XNoeud));
 TeteC=pos;
 for(px=pAgrille;px!=NULL;px=px->psNoeud) {
   igene1=0;   
/********************************************************************/
/*********************** Noeuds aux extremitees *********************/
/********************************************************************/
   for(j=0;j<=7;j++) {
   igene0=1;
   py=px;  
/*==================================================*/
/* traitement des radicaux et des liaisons octales  */
/*==================================================*/
   if(py->radicaux[(j+4)%8]==NULL) {
   for(i=1;i<=4;i++) {
     if(i<=3) {
     if(py->radicaux[j]==NULL) {
     igene0=0;
     break;
     }
     if((py->O[j]==1)||(py->O[(j+4)%8]==1)){
     igene0=0;
     break;
     }
     py=py->radicaux[j];
     }
     if(i==4) {
     if(py->O[(j+4)%8]==1){
     igene0=0;
     break;
     }
     }
   }
   }
   else igene0=0;

/*=============================*/
   if(igene0==1){
      t[igene1]=1;
      v[igene1]=j;
      igene1=igene1+1;  
   }
   }         
/**********************************************************************/
/***********************    Noeuds aux centres    *********************/   
/**********************************************************************/
   /*igene1=0;*/
   for(j=0;j<=7;j++) {
   igene0=1;
   py=px;  
/*==================================================*/
/* traitement des radicaux et des liaisons octales  */
/*==================================================*/
   if(py->radicaux[(j+4)%8]==NULL) {
   for(i=1;i<=2;i++) {
     if(i<=1) {
     if(py->radicaux[j]==NULL) {
     igene0=0;
     goto fintest1;
     }
     if((py->O[j]==1)||(py->O[(j+4)%8]==1)){
     igene0=0;
     goto fintest1;
     }
     py=py->radicaux[j];
     }
     if(i==2) {
     if(py->O[(j+4)%8]==1){
     igene0=0;
     goto fintest1;
     }
     }
   }
   }
     else { igene0=0;
            goto fintest1;
     }
            
     /* on recentre */

 xa=px->valx;
 ya=px->valy;
 for(ptr=pAgrille;ptr!=NULL;ptr=ptr->psNoeud)
   {   
     ok=0;
     igene0=1;
     if(ptr->radicaux[j]==NULL){
       if(j==0){
         if((xa==ptr->valx)&&(ya-2==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==1){
         if((xa+2==ptr->valx)&&(ya-2==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==2){
         if((xa+2==ptr->valx)&&(ya==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==3){
         if((xa+2==ptr->valx)&&(ya+2==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==4){
         if((xa==ptr->valx)&&(ya+2==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==5){
         if((xa-2==ptr->valx)&&(ya+2==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==6){
         if((xa-2==ptr->valx)&&(ya==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==7){
         if((xa-2==ptr->valx)&&(ya-2==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
     for(i=1;i<=2;i++) {
     if(i<=1) {
     if(py->radicaux[(j+4)%8]==NULL) {
     igene0=0;
     break;
     }
     if((py->O[j]==1)||(py->O[(j+4)%8]==1)){
     igene0=0;
     break;
     }
     py=py->radicaux[(j+4)%8];
     }
     if(i==2) {
     if(py->O[j]==1){
     igene0=0;
     break;
     }
     }
   }
   if(ok==1) break;  
   }   
   } 
   if(ptr==NULL) igene0=0;
/*=============================*/
fintest1:
   if(igene0==1){
      t[igene1]=2;
      v[igene1]=j;
      igene1=igene1+1;  
   }
   }          
/**********************************************************************/
/*********************  Noeuds decentres droit    *********************/   
/**********************************************************************/
   /*igene1=0;*/
   for(j=0;j<=7;j++) {
   igene0=1;
   py=px;  
/*==================================================*/
/* traitement des radicaux et des liaisons octales  */
/*==================================================*/
   if(py->radicaux[(j+4)%8]==NULL) {
     if(py->O[(j+4)%8]==1){
     igene0=0;
     goto fintest2;
     }
   }
     else { igene0=0;
            goto fintest2;
     }
            
     /* on recentre */

 xa=px->valx;
 ya=px->valy;
 for(ptr=pAgrille;ptr!=NULL;ptr=ptr->psNoeud)
   {   
     ok=0;
     igene0=1;
     if(ptr->radicaux[j]==NULL){
       if(j==0){
         if((xa==ptr->valx)&&(ya-2==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==1){
         if((xa+2==ptr->valx)&&(ya-2==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==2){
         if((xa+2==ptr->valx)&&(ya==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==3){
         if((xa+2==ptr->valx)&&(ya+2==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==4){
         if((xa==ptr->valx)&&(ya+2==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==5){
         if((xa-2==ptr->valx)&&(ya+2==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==6){
         if((xa-2==ptr->valx)&&(ya==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==7){
         if((xa-2==ptr->valx)&&(ya-2==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
     for(i=1;i<=3;i++) {
     if(i<=2) {
     if(py->radicaux[(j+4)%8]==NULL) {
     igene0=0;
     break;
     }
     if((py->O[j]==1)||(py->O[(j+4)%8]==1)){
     igene0=0;
     break;
     }
     py=py->radicaux[(j+4)%8];
     }
     if(i==3) {
     if(py->O[j]==1){
     igene0=0;
     break;
     }
     }
   }
   if(ok==1) break;  
   }   
   } 
   if(ptr==NULL) igene0=0;
/*=============================*/
fintest2:
   if(igene0==1){
      t[igene1]=3;
      v[igene1]=j;
      igene1=igene1+1;  
   }
   } 
/**********************************************************************/
/*********************  Noeuds decentres gauche   *********************/   
/**********************************************************************/
   /*igene1=0;*/
   for(j=0;j<=7;j++) {
   igene0=1;
   py=px;  
/*==================================================*/
/* traitement des radicaux et des liaisons octales  */
/*==================================================*/
   if(py->radicaux[(j+4)%8]==NULL) {
   for(i=1;i<=3;i++) {
     if(i<=2) {
     if(py->radicaux[j]==NULL) {
     igene0=0;
     goto fintest3;
     }
     if((py->O[j]==1)||(py->O[(j+4)%8]==1)){
     igene0=0;
     goto fintest3;
     }
     py=py->radicaux[j];
     }
     if(i==3) {
     if(py->O[(j+4)%8]==1){
     igene0=0;
     goto fintest3;
     }
     }
   }
   }
     else { igene0=0;
            goto fintest3;
     }
            
     /* on recentre */

 xa=px->valx;
 ya=px->valy;
 for(ptr=pAgrille;ptr!=NULL;ptr=ptr->psNoeud)
   {   
     ok=0;
     igene0=1;
     if(ptr->radicaux[j]==NULL){
       if(j==0){
         if((xa==ptr->valx)&&(ya-2==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==1){
         if((xa+2==ptr->valx)&&(ya-2==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==2){
         if((xa+2==ptr->valx)&&(ya==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==3){
         if((xa+2==ptr->valx)&&(ya+2==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==4){
         if((xa==ptr->valx)&&(ya+2==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==5){
         if((xa-2==ptr->valx)&&(ya+2==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==6){
         if((xa-2==ptr->valx)&&(ya==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==7){
         if((xa-2==ptr->valx)&&(ya-2==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
     if(py->O[j]==1){
     igene0=0;
     }
   if(ok==1) break;  
   }   
   } 
   if(ptr==NULL) igene0=0;
/*=============================*/
fintest3:
   if(igene0==1){
      t[igene1]=4;
      v[igene1]=j;
      igene1=igene1+1;  
   }
   }                   
/*============================*/ 
/* chaine des nouveaux Noeuds */
/*============================*/
   for(j1=0;j1<igene1;j1++) {
   if(v[j1]==0){
   pos->valx=px->valx;
   pos->valy=px->valy-1;
   }
   if(v[j1]==1){
   pos->valx=px->valx+1;
   pos->valy=px->valy-1;
   }
   if(v[j1]==2){
   pos->valx=px->valx+1;
   pos->valy=px->valy;
   }
   if(v[j1]==3){
   pos->valx=px->valx+1;
   pos->valy=px->valy+1;
   }
   if(v[j1]==4){
   pos->valx=px->valx;
   pos->valy=px->valy+1;
   }
   if(v[j1]==5){
   pos->valx=px->valx-1;
   pos->valy=px->valy+1;
   }
   if(v[j1]==6) {
   pos->valx=px->valx-1;
   pos->valy=px->valy;
   }
   if(v[j1]==7){
   pos->valx=px->valx-1;
   pos->valy=px->valy-1;
   }
/*=======================*/
/* MAJ des termes T et S */
/*=======================*/
   pos->T=t[j1];
   pos->S=v[j1];  
/*==============================================*/
   pos->ppNoeud=p1;
   p2=(struct XNoeud *) malloc(sizeof(struct XNoeud));
   pos->psNoeud=p2;
   p1=pos;
   pos=pos->psNoeud;
   }
   }
 /* je fais un pas en arriere */
   pos=p1;
   if(pos!=NULL) {
      pos->psNoeud=NULL;
      free(p2); 
   }
   /**********************************/
   /* Mise a -1 des neuds en double */
   /**********************************/
   if(pos!=NULL) { 
   for(pts1=TeteC;pts1!=NULL;pts1=pts1->psNoeud)
   {
     T1=pts1->T;
     S1=pts1->S;
     x1=pts1->valx;
     y1=pts1->valy;
     for(pts2=pts1->psNoeud; pts2!=NULL;pts2=pts2->psNoeud)
     {
     T2=pts2->T;
     S2=pts2->S;
     x2=pts2->valx;
     y2=pts2->valy;
     if((T1==T2)&&(S1==S2)&&(x1==x2)&&(y1==y2)) { 
        pts1->T=-1;
        pts1->S=-1;
        pts1->valx=-1;
        pts1->valy=-1;
     }
     if(((S1+4)%8==S2)&&(T2==2)&&(x1==x2)&&(y1==y2)) {
        pts1->T=-1;
        pts1->S=-1;
        pts1->valx=-1;
        pts1->valy=-1;
     }
     }
   }
   /**********************************/
   /* suppression des "-1" intercale */
   /* dans la chaine des noeuds ok   */
   /**********************************/
   TeteD=TeteC;
   i=0;j=0;
   for(pts1=TeteC;pts1!=NULL;pts1=pts2)
   {
     T1=pts1->T;
     S1=pts1->S;
     x1=pts1->valx;
     y1=pts1->valy; 
     pts3=pts1->ppNoeud; 
     pts2=pts1->psNoeud;
     if((T1==-1)&&(S1==-1)&&(x1==-1)&&(y1==-1)) {
       if(pts3!=NULL) { 
              pts3->psNoeud=pts2;
              free(pts1);
        } else {
              pts2->ppNoeud=NULL;
              TeteD=TeteD->psNoeud;
        }
        if(pts2!=NULL) pts2->ppNoeud=pts3;
        else {
              pts3->psNoeud=NULL;
              TeteD=TeteD->ppNoeud;
        }    
        i++;
     }
     j++;     
   }
   /*
   printf("1.i= %d\n",i);
   printf("1.j= %d\n",j);
   */
   /**********************************/
   /* Tri des noeuds selectionnes &  */
   /* selection du noeud incremental */
   /**********************************/
   trouve=1;
   pRESULTAT=(struct Noeud *) malloc(sizeof(struct Noeud));
   for(pts1=TeteD;pts1!=NULL;pts1=pts1->psNoeud)
   { 
     for(pts2=pts1->psNoeud;pts2!=NULL;pts2=pts2->psNoeud){
         if(pts2->valy<pts1->valy)   { echange(pts1,pts2);}        
         else if(pts2->valy==pts1->valy) {
	   if(pts2->valx<pts1->valx) { echange(pts1,pts2);}   
           else if(pts2->valx==pts1->valx) {
	     if(pts2->T<pts1->T)     { echange(pts1,pts2);}   
             else if(pts2->T==pts1->T) {
	       if(pts2->S<pts1->S)   { echange(pts1,pts2);}   
	     }
	   }
	 }
      } 
    }
/***********************************************/
/* selection du noeud incremental :            */
/* positionnement au rang                      */
/***********************************************/
      pfixe=TeteD;
      nbpos=decompteX(pfixe);
      if(nbpos>=rang) { 
      for(i=1;i<rang;pfixe=pfixe->psNoeud,i++){}
      Tmin=pfixe->T;
      Smin=pfixe->S;
/************************************************/
/* Initialisation du noeud selectione           */      
/************************************************/
   pRESULTAT->valx=pfixe->valx;
   pRESULTAT->valy=pfixe->valy;
   for(i=0;i<=7;i++){
   pRESULTAT->O[i]=0;
   pRESULTAT->radicaux[i]=NULL;
   }
   /*
    printf("xmin=%d\n",pRESULTAT->valx);
    printf("ymin=%d\n",pRESULTAT->valy);
   */
/************************************************/
/* liberation des pointeurs obsoletes           */
/* on ne garde que les deux necessaires         */
/************************************************/ 
   for(pts1=TeteC;pts1!=NULL;pts1=pts2)
   { 
       pts2=pts1->psNoeud;
       free(pts1);
   }
/*==============================================*/    
/* generation des liaisons octales              */
/*==============================================*/
   if(Tmin==1) {
     pRESULTAT->O[Smin]=1;
   }
   if(Tmin==2) {
     pRESULTAT->O[Smin]=1;
     pRESULTAT->O[(Smin+4)%8]=1;
   }
   if(Tmin==3) {
     pRESULTAT->O[Smin]=1;
     pRESULTAT->O[(Smin+4)%8]=1;
   }
   if(Tmin==4) {
     pRESULTAT->O[Smin]=1;
     pRESULTAT->O[(Smin+4)%8]=1;
   }
/*===============================================*/    
/* generation automatique des liaisons radicales */
/* du seul noeud selectionne : pRESULTAT         */
/*===============================================*/ 
 xa=pRESULTAT->valx;
 ya=pRESULTAT->valy;
 for(ptr=pAgrille;ptr!=NULL;ptr=ptr->psNoeud)
   {   
 if((xa==ptr->valx)&&((ya+1)==ptr->valy))
   {pRESULTAT->radicaux[0]=ptr;}
 if(((xa-1)==ptr->valx)&&((ya+1)==ptr->valy))
   {pRESULTAT->radicaux[1]=ptr;}
 if(((xa-1)==ptr->valx)&&(ya==ptr->valy))
   {pRESULTAT->radicaux[2]=ptr;}
 if(((xa-1)==ptr->valx)&&((ya-1)==ptr->valy))
   {pRESULTAT->radicaux[3]=ptr;}
 if((xa==ptr->valx)&&((ya-1)==ptr->valy))
   {pRESULTAT->radicaux[4]=ptr;}
 if(((xa+1)==ptr->valx)&&((ya-1)==ptr->valy))
   {pRESULTAT->radicaux[5]=ptr;}
 if(((xa+1)==ptr->valx)&&(ya==ptr->valy))
   {pRESULTAT->radicaux[6]=ptr;}
 if(((xa+1)==ptr->valx)&&((ya+1)==ptr->valy))
   {pRESULTAT->radicaux[7]=ptr;}
   }
/************************************************/
/* Valorisation du noeud (ENoeud) NOEUDETAT     *
/* a ajouter a l'arbre d'ETAT                   */
/************************************************/
/*================*
/* initialisation *
/*================*/
   pNOEUDETAT=(struct ENoeud *) malloc(sizeof(struct ENoeud)); 
   pNOEUDETAT->nbpos=nbpos;
   pNOEUDETAT->T=Tmin;
   pNOEUDETAT->S=Smin;
   pNOEUDETAT->valx=pRESULTAT->valx;
   pNOEUDETAT->valy=pRESULTAT->valy;
   for(i=0;i<=7;i++){
   pNOEUDETAT->O[i]=pRESULTAT->O[i];
   }
   /* affarbre(racine); */
   autogenearbre0(racine,pNOEUDETAT);
   /*affarbre(racine); */
/**************************************************/
/* 1. Mise A Jour de la grille incrementee        */
/**************************************************/
   igene0=1; 
   py=pRESULTAT;  
   /*******/
   /* T=1 */
   /*******/
   if(Tmin==1) {
     for(i=1;i<=5;i++) {
     if(i<5) {
     if(py->radicaux[Smin]==NULL) goto erreur1;
     }
     if((i>1)&&(i<5)) {
     py->O[Smin]=1;
     py->O[(Smin+4)%8]=1;
     }
     if(i<5) {
     py=py->radicaux[Smin];
     }
     if(i==5) {
     py->O[(Smin+4)%8]=1;
     }
     }
   }
   /*******/
   /* T=2 */
   /*******/
   if(Tmin==2) {
     for(i=1;i<=3;i++) {
     if(i<3) {
     if(py->radicaux[Smin]==NULL) goto erreur1;     
     }
     if(i==2) {
     py->O[Smin]=1;
     py->O[(Smin+4)%8]=1;
     }
     if(i<3) {
     py=py->radicaux[Smin];
     }
     if(i==3) {
     py->O[(Smin+4)%8]=1;
     }
     }    
/* on recentre */
     py=pRESULTAT;
     for(i=1;i<=3;i++) {
     if(i<3) {
     if(py->radicaux[(Smin+4)%8]==NULL) goto erreur1;
     }
     if(i==2) {
     py->O[Smin]=1;
     py->O[(Smin+4)%8]=1;
     }
     if(i<3) {
     py=py->radicaux[(Smin+4)%8];
     }
     if(i==3) {
     py->O[Smin]=1;
     }
     }
   }
   /*******/
   /* T=3 */
   /*******/
   if(Tmin==3) {
     for(i=1;i<=2;i++) {
     if(i==1) {
     if(py->radicaux[Smin]==NULL) goto erreur1;     
     }
     if(i==1) {
     py=py->radicaux[Smin];
     }
     if(i==2) {
     py->O[(Smin+4)%8]=1;
     }       
     }
/* on recentre */
     py=pRESULTAT;
     for(i=1;i<=4;i++) {
     if(i<4) {
     if(py->radicaux[(Smin+4)%8]==NULL) goto erreur1;     
     }
     if((i>1)&&(i<4)) {
     py->O[Smin]=1;
     py->O[(Smin+4)%8]=1;
     }
     if(i<4) {
     py=py->radicaux[(Smin+4)%8];
     }
     if(i==4) {
     py->O[Smin]=1;
     }
     }
   }
   /*******/
   /* T=4 */
   /*******/
   if(Tmin==4) {
     for(i=1;i<=4;i++) {
     if(i<4) {
     if(py->radicaux[Smin]==NULL) goto erreur1;
     }
     if((i>1)&&(i<4)) {
     py->O[Smin]=1;
     py->O[(Smin+4)%8]=1;
     }
     if(i<4) {
     py=py->radicaux[Smin];
     }
     if(i==4) {
     py->O[(Smin+4)%8]=1;
     }
     }
/* on recentre */
     py=pRESULTAT;
     for(i=1;i<=2;i++) {
     if(i==1) {
     if(py->radicaux[(Smin+4)%8]==NULL) goto erreur1;
     }
     if(i==1) {
     py=py->radicaux[(Smin+4)%8];
     }
     if(i==2) {
     py->O[Smin]=1;
     }       
     }
   }
/**************************************************/
/* 2. Mise A Jour de l'arbre d'ETAT incrementee   */
/**************************************************/
   igene0=1; 
   pz=pNOEUDETAT;
   /*******/
   /* T=1 */
   /*******/
   if(Tmin==1) {
     for(i=1;i<=5;i++) {
     if(i<5) {
     if(pz->radicaux[Smin]==NULL) goto erreur2;
     }
     if((i>1)&&(i<5)) {
     pz->O[Smin]=1;
     pz->O[(Smin+4)%8]=1;
     }
     if(i<5) {
     pz=pz->radicaux[Smin];
     }
     if(i==5) {
     pz->O[(Smin+4)%8]=1;
     }
     }
   }

   /*******/
   /* T=2 */
   /*******/
   if(Tmin==2) {
     for(i=1;i<=3;i++) {
     if(i<3) {
     if(pz->radicaux[Smin]==NULL) goto erreur2;
     }
     if(i==2) {
     pz->O[Smin]=1;
     pz->O[(Smin+4)%8]=1;
     }
     if(i<3) {
     pz=pz->radicaux[Smin];
     }
     if(i==3) {
     pz->O[(Smin+4)%8]=1;
     }
     }    
/* on recentre */
     pz=pNOEUDETAT;
     for(i=1;i<=3;i++) {
     if(i<3) {
     if(pz->radicaux[(Smin+4)%8]==NULL) goto erreur2;
     }
     if(i==2) {
     pz->O[Smin]=1;
     pz->O[(Smin+4)%8]=1;
     }
     if(i<3) {
     pz=pz->radicaux[(Smin+4)%8];
     }
     if(i==3) {
     pz->O[Smin]=1;
     }
     }
   }
   /*******/
   /* T=3 */
   /*******/
   if(Tmin==3) {
     for(i=1;i<=2;i++) {
     if(i==1) {
     if(pz->radicaux[Smin]==NULL) goto erreur2;     
     }
     if(i==1) {
     pz=pz->radicaux[Smin];
     }
     if(i==2) {
     pz->O[(Smin+4)%8]=1;
     }       
     }
/* on recentre */
     pz=pNOEUDETAT;
     for(i=1;i<=4;i++) {
     if(i<4) {
     if(pz->radicaux[(Smin+4)%8]==NULL) goto erreur2;     
     }
     if((i>1)&&(i<4)) {
     pz->O[Smin]=1;
     pz->O[(Smin+4)%8]=1;
     }
     if(i<4) {
     pz=pz->radicaux[(Smin+4)%8];
     }
     if(i==4) {
     pz->O[Smin]=1;
     }
     }
   }
   /*******/
   /* T=4 */
   /*******/
   if(Tmin==4) {
     for(i=1;i<=4;i++) {
     if(i<4) {
     if(pz->radicaux[Smin]==NULL) goto erreur2;    
     }
     if((i>1)&&(i<4)) {
     pz->O[Smin]=1;
     pz->O[(Smin+4)%8]=1;
     }
     if(i<4) {
     pz=pz->radicaux[Smin];
     }
     if(i==4) {
     pz->O[(Smin+4)%8]=1;
     }
     }
/* on recentre */
     pz=pNOEUDETAT;
     for(i=1;i<=2;i++) {
     if(i==1) {
     if(pz->radicaux[(Smin+4)%8]==NULL) goto erreur2;
     }
     if(i==1) {
     pz=pz->radicaux[(Smin+4)%8];
     }
     if(i==2) {
     pz->O[Smin]=1;
     }       
     }
   }
/************************************************/
/* ajout du noeud trouve dans la grille         */
/************************************************/  
     for(px=pAgrille;px->psNoeud!=NULL;px=px->psNoeud){};
     px->psNoeud=pRESULTAT;
     pRESULTAT->ppNoeud=px;
     pRESULTAT->psNoeud=NULL;
/************************************************
! generation automatique des liaisons radicales !
! genralise a toute la grille compte tenu de    !
! l'ajout du nouveau noeud                      !
!***********************************************/
for(ptr=pAgrille;ptr!=NULL;ptr=ptr->psNoeud)   
 {
 xa=ptr->valx;
 ya=ptr->valy;
 for(ptr1=pAgrille;ptr1!=NULL;ptr1=ptr1->psNoeud)
   {   
 if((xa==ptr1->valx)&&((ya+1)==ptr1->valy))
   {ptr->radicaux[0]=ptr1;}
 if(((xa-1)==ptr1->valx)&&((ya+1)==ptr1->valy))
   {ptr->radicaux[1]=ptr1;}
 if(((xa-1)==ptr1->valx)&&(ya==ptr1->valy))
   {ptr->radicaux[2]=ptr1;}
 if(((xa-1)==ptr1->valx)&&((ya-1)==ptr1->valy))
   {ptr->radicaux[3]=ptr1;}
 if((xa==ptr1->valx)&&((ya-1)==ptr1->valy))
   {ptr->radicaux[4]=ptr1;}
 if(((xa+1)==ptr1->valx)&&((ya-1)==ptr1->valy))
   {ptr->radicaux[5]=ptr1;}
 if(((xa+1)==ptr1->valx)&&(ya==ptr1->valy))
   {ptr->radicaux[6]=ptr1;}
 if(((xa+1)==ptr1->valx)&&((ya+1)==ptr1->valy))
   {ptr->radicaux[7]=ptr1;}
    }
  }
/************************************************/
/* MAJ du noeud (ENoeud) NOEUDETAT a ajouter    *
/* a l'arbre d'ETAT                             */
/************************************************/
  pNOEUDETAT->niveau=decompteN(pAgrille);
/************************************************/
/* MAJ de l'arbre d'ETAT de structure ENoeud    *
/************************************************/
  nbpos=pNOEUDETAT->nbpos;
  T=pNOEUDETAT->T;
  S=pNOEUDETAT->S;
  valx=pNOEUDETAT->valx;
  valy=pNOEUDETAT->valy;
  niveau=pNOEUDETAT->niveau;
  for(i=0;i<=7;i++){
   O[i]=pNOEUDETAT->O[i];
  }
  racine=ajoutarbre(racine,niveau,nbpos,rang,T,S,valx,valy,O,radicaux);
  /* affarbre(racine); */
/************************************************
! generation automatique des liaisons radicales !
! dans l'arbre de structure ENoeud              !
!************************************************/
  autogenearbre1(racine,racine); 
/**********************************************/  
 }  
   else  trouve=0;
 }
   else  trouve=0;
  
 free(pNOEUDETAT);
 /*    
       free(pos);  
       nbpos=decompteX(pfixe); 
       if(pos!=NULL) free(pos); */
 /*
 for(pts=pos;pts!=NULL;pts=pts1) {
     pts1=pts->psNoeud;
     free(pts);
     }
 */
 if(trouve==0) {
 for(pts=pos;pts!=NULL;pts=pts1) {
 pts1=pts->psNoeud;
 free(pts);
 }
 }
 free(ptr); free(ptr1); 		       
 return trouve;

 erreur1:
 printf("erreur de coherence sur la grille\n");
 exit(2);

 erreur2:
 printf("erreur de coherence sur l'arbre d'etat\n");
 exit(2);
}
/**********************************************
! Fonction                                    !
! calcul du nombre des possibilites           !
! pour la grille suivante a partir d'un etat  !
! donne de la grille                          !    
!*********************************************/
int possibleG(struct Noeud *pAgrille,struct ENoeud *racine)
{

 void echange(struct XNoeud *,struct XNoeud *);

 struct Noeud *px,*py;
 struct Noeud *ptr,*ptr1; 

 struct XNoeud *pos;
 struct XNoeud *pts;
 struct XNoeud *pts1,*pts2,*pts3;
 struct XNoeud *p1,*p2;
 struct XNoeud *TeteC,*TeteD,*pfixe;

 int i,j,i1,j1;
 int igene0,igene1;
 int v[500],t[500];
 int xa,ya;
 int xmin,ymin;
 int ok,trouve;

 int Tmin,Smin;
 int T1,S1,x1,y1;
 int T2,S2,x2,y2;
 int Tp,Sp,xp,yp;

 int niveau,nbpos,T,S;
 int valx,valy;
 int O[8];
 /*************************************************/
 /* chaine de tous les Noeuds possibles valorises */
 /*************************************************/
 p1=NULL; 
 pos=(struct XNoeud *) malloc(sizeof(struct XNoeud));
 TeteC=pos;
 for(px=pAgrille;px!=NULL;px=px->psNoeud) {
   igene1=0;   
/********************************************************************/
/*********************** Noeuds aux extremitees *********************/
/********************************************************************/
   for(j=0;j<=7;j++) {
   igene0=1;
   py=px;  
/*==================================================*/
/* traitement des radicaux et des liaisons octales  */
/*==================================================*/
   if(py->radicaux[(j+4)%8]==NULL) {
   for(i=1;i<=4;i++) {
     if(i<=3) {
     if(py->radicaux[j]==NULL) {
     igene0=0;
     break;
     }
     if((py->O[j]==1)||(py->O[(j+4)%8]==1)){
     igene0=0;
     break;
     }
     py=py->radicaux[j];
     }
     if(i==4) {
     if(py->O[(j+4)%8]==1){
     igene0=0;
     break;
     }
     }
   }
   }
   else igene0=0;

/*=============================*/
   if(igene0==1){
      t[igene1]=1;
      v[igene1]=j;
      igene1=igene1+1;  
   }
   }         
/**********************************************************************/
/***********************    Noeuds aux centres    *********************/   
/**********************************************************************/
   /*igene1=0;*/
   for(j=0;j<=7;j++) {
   igene0=1;
   py=px;  
/*==================================================*/
/* traitement des radicaux et des liaisons octales  */
/*==================================================*/
   if(py->radicaux[(j+4)%8]==NULL) {
   for(i=1;i<=2;i++) {
     if(i<=1) {
     if(py->radicaux[j]==NULL) {
     igene0=0;
     goto fintest1;
     }
     if((py->O[j]==1)||(py->O[(j+4)%8]==1)){
     igene0=0;
     goto fintest1;
     }
     py=py->radicaux[j];
     }
     if(i==2) {
     if(py->O[(j+4)%8]==1){
     igene0=0;
     goto fintest1;
     }
     }
   }
   }
     else { igene0=0;
            goto fintest1;
     }
            
     /* on recentre */

 xa=px->valx;
 ya=px->valy;
 for(ptr=pAgrille;ptr!=NULL;ptr=ptr->psNoeud)
   {   
     ok=0;
     igene0=1;
     if(ptr->radicaux[j]==NULL){
       if(j==0){
         if((xa==ptr->valx)&&(ya-2==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==1){
         if((xa+2==ptr->valx)&&(ya-2==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==2){
         if((xa+2==ptr->valx)&&(ya==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==3){
         if((xa+2==ptr->valx)&&(ya+2==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==4){
         if((xa==ptr->valx)&&(ya+2==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==5){
         if((xa-2==ptr->valx)&&(ya+2==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==6){
         if((xa-2==ptr->valx)&&(ya==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==7){
         if((xa-2==ptr->valx)&&(ya-2==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
     for(i=1;i<=2;i++) {
     if(i<=1) {
     if(py->radicaux[(j+4)%8]==NULL) {
     igene0=0;
     break;
     }
     if((py->O[j]==1)||(py->O[(j+4)%8]==1)){
     igene0=0;
     break;
     }
     py=py->radicaux[(j+4)%8];
     }
     if(i==2) {
     if(py->O[j]==1){
     igene0=0;
     break;
     }
     }
   }
   if(ok==1) break;  
   }   
   } 
   if(ptr==NULL) igene0=0;
/*=============================*/
fintest1:
   if(igene0==1){
      t[igene1]=2;
      v[igene1]=j;
      igene1=igene1+1;  
   }
   }          
/**********************************************************************/
/*********************  Noeuds decentres droit    *********************/   
/**********************************************************************/
   /*igene1=0;*/
   for(j=0;j<=7;j++) {
   igene0=1;
   py=px;  
/*==================================================*/
/* traitement des radicaux et des liaisons octales  */
/*==================================================*/
   if(py->radicaux[(j+4)%8]==NULL) {
     if(py->O[(j+4)%8]==1){
     igene0=0;
     goto fintest2;
     }
   }
     else { igene0=0;
            goto fintest2;
     }
            
     /* on recentre */

 xa=px->valx;
 ya=px->valy;
 for(ptr=pAgrille;ptr!=NULL;ptr=ptr->psNoeud)
   {   
     ok=0;
     igene0=1;
     if(ptr->radicaux[j]==NULL){
       if(j==0){
         if((xa==ptr->valx)&&(ya-2==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==1){
         if((xa+2==ptr->valx)&&(ya-2==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==2){
         if((xa+2==ptr->valx)&&(ya==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==3){
         if((xa+2==ptr->valx)&&(ya+2==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==4){
         if((xa==ptr->valx)&&(ya+2==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==5){
         if((xa-2==ptr->valx)&&(ya+2==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==6){
         if((xa-2==ptr->valx)&&(ya==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==7){
         if((xa-2==ptr->valx)&&(ya-2==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
     for(i=1;i<=3;i++) {
     if(i<=2) {
     if(py->radicaux[(j+4)%8]==NULL) {
     igene0=0;
     break;
     }
     if((py->O[j]==1)||(py->O[(j+4)%8]==1)){
     igene0=0;
     break;
     }
     py=py->radicaux[(j+4)%8];
     }
     if(i==3) {
     if(py->O[j]==1){
     igene0=0;
     break;
     }
     }
   }
   if(ok==1) break;  
   }   
   } 
   if(ptr==NULL) igene0=0;
/*=============================*/
fintest2:
   if(igene0==1){
      t[igene1]=3;
      v[igene1]=j;
      igene1=igene1+1;  
   }
   } 
/**********************************************************************/
/*********************  Noeuds decentres gauche   *********************/   
/**********************************************************************/
   /*igene1=0;*/
   for(j=0;j<=7;j++) {
   igene0=1;
   py=px;  
/*==================================================*/
/* traitement des radicaux et des liaisons octales  */
/*==================================================*/
   if(py->radicaux[(j+4)%8]==NULL) {
   for(i=1;i<=3;i++) {
     if(i<=2) {
     if(py->radicaux[j]==NULL) {
     igene0=0;
     goto fintest3;
     }
     if((py->O[j]==1)||(py->O[(j+4)%8]==1)){
     igene0=0;
     goto fintest3;
     }
     py=py->radicaux[j];
     }
     if(i==3) {
     if(py->O[(j+4)%8]==1){
     igene0=0;
     goto fintest3;
     }
     }
   }
   }
     else { igene0=0;
            goto fintest3;
     }
            
     /* on recentre */

 xa=px->valx;
 ya=px->valy;
 for(ptr=pAgrille;ptr!=NULL;ptr=ptr->psNoeud)
   {   
     ok=0;
     igene0=1;
     if(ptr->radicaux[j]==NULL){
       if(j==0){
         if((xa==ptr->valx)&&(ya-2==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==1){
         if((xa+2==ptr->valx)&&(ya-2==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==2){
         if((xa+2==ptr->valx)&&(ya==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==3){
         if((xa+2==ptr->valx)&&(ya+2==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==4){
         if((xa==ptr->valx)&&(ya+2==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==5){
         if((xa-2==ptr->valx)&&(ya+2==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==6){
         if((xa-2==ptr->valx)&&(ya==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
       if(j==7){
         if((xa-2==ptr->valx)&&(ya-2==ptr->valy)) {
           py=ptr;
           ok=1;
	 }
       }
     if(py->O[j]==1){
     igene0=0;
     }
   if(ok==1) break;  
   }   
   } 
   if(ptr==NULL) igene0=0;
/*=============================*/
fintest3:
   if(igene0==1){
      t[igene1]=4;
      v[igene1]=j;
      igene1=igene1+1;  
   }
   }                   
/*============================*/ 
/* chaine des nouveaux Noeuds */
/*============================*/
   for(j1=0;j1<igene1;j1++) {
   if(v[j1]==0){
   pos->valx=px->valx;
   pos->valy=px->valy-1;
   }
   if(v[j1]==1){
   pos->valx=px->valx+1;
   pos->valy=px->valy-1;
   }
   if(v[j1]==2){
   pos->valx=px->valx+1;
   pos->valy=px->valy;
   }
   if(v[j1]==3){
   pos->valx=px->valx+1;
   pos->valy=px->valy+1;
   }
   if(v[j1]==4){
   pos->valx=px->valx;
   pos->valy=px->valy+1;
   }
   if(v[j1]==5){
   pos->valx=px->valx-1;
   pos->valy=px->valy+1;
   }
   if(v[j1]==6) {
   pos->valx=px->valx-1;
   pos->valy=px->valy;
   }
   if(v[j1]==7){
   pos->valx=px->valx-1;
   pos->valy=px->valy-1;
   }
/*=======================*/
/* MAJ des termes T et S */
/*=======================*/
   pos->T=t[j1];
   pos->S=v[j1];  
/*==============================================*/
   pos->ppNoeud=p1;
   p2=(struct XNoeud *) malloc(sizeof(struct XNoeud));
   pos->psNoeud=p2;
   p1=pos;
   pos=pos->psNoeud;
   }
   }

 /* je fais un pas en arriere */
   pos=p1;
   if(pos!=NULL) {
      pos->psNoeud=NULL;
      free(p2); 
   }

   /**********************************/
   /* Mise a -1 des neuds en double  */
   /**********************************/
   if(pos!=NULL) { 
   for(pts1=TeteC;pts1!=NULL;pts1=pts1->psNoeud)
   {
     T1=pts1->T;
     S1=pts1->S;
     x1=pts1->valx;
     y1=pts1->valy;
     for(pts2=pts1->psNoeud; pts2!=NULL;pts2=pts2->psNoeud)
     {
     T2=pts2->T;
     S2=pts2->S;
     x2=pts2->valx;
     y2=pts2->valy;
     if((T1==T2)&&(S1==S2)&&(x1==x2)&&(y1==y2)) {
        pts1->T=-1;
        pts1->S=-1;
        pts1->valx=-1;
        pts1->valy=-1; 
     }
     if(((S1+4)%8==S2)&&(T2==2)&&(x1==x2)&&(y1==y2)) {
        pts1->T=-1;
        pts1->S=-1;
        pts1->valx=-1;
        pts1->valy=-1;
     }
     }
   }
   /**********************************/
   /* suppression des "-1" intercale */
   /* dans la chaine des noeuds ok   */
   /**********************************/
   TeteD=TeteC;
   i=0;j=0;
   for(pts1=TeteC;pts1!=NULL;pts1=pts2)
   {
     T1=pts1->T;
     S1=pts1->S;
     x1=pts1->valx;
     y1=pts1->valy; 
     pts3=pts1->ppNoeud; 
     pts2=pts1->psNoeud;
     if((T1==-1)&&(S1==-1)&&(x1==-1)&&(y1==-1)) {
        if(pts3!=NULL) pts3->psNoeud=pts2;
        else {
              pts2->ppNoeud=NULL;
              TeteD=TeteD->psNoeud;
        }
        if(pts2!=NULL) pts2->ppNoeud=pts3; 
        else {
              pts3->psNoeud=NULL;
              TeteD=TeteD->ppNoeud;
        }  
        i++;
        free(pts1);
     }
     j++;     
   }
   /*
   printf("2.i= %d\n",i);
   printf("2.j= %d\n",j);
   */
   /**********************************/
   /* Tri des noeuds selectionnes &  */
   /* selection du noeud incremental */
   /**********************************/
   trouve=1;
   for(pts1=TeteD;pts1!=NULL;pts1=pts1->psNoeud)
   { 
     for(pts2=pts1->psNoeud;pts2!=NULL;pts2=pts2->psNoeud){
         if(pts2->valy<pts1->valy)   { echange(pts1,pts2);}        
         else if(pts2->valy==pts1->valy) {
	   if(pts2->valx<pts1->valx) { echange(pts1,pts2);}   
           else if(pts2->valx==pts1->valx) {
	     if(pts2->T<pts1->T)     { echange(pts1,pts2);}   
             else if(pts2->T==pts1->T) {
	       if(pts2->S<pts1->S)   { echange(pts1,pts2);}   
	     }
	   }
	 }
      } 
    }

/***********************************************/
/* selection du noeud incremental :            */
/* positionnement au rang                      */
/***********************************************/
      pfixe=TeteD;
      nbpos=decompteX(pfixe);
      for(pts=TeteD;pts!=NULL;pts=pts1) {
      pts1=pts->psNoeud;
      free(pts);
      }  
      return nbpos;
   }   

 /*
 for(pts=TeteC;pts!=NULL;pts=pts1) {
 pts1=pts->psNoeud;
 free(pts);
 }
 */
 return -1;

 erreur1:
 printf("erreur de coherence sur la grille\n");
 exit(2);

 erreur2:
 printf("erreur de coherence sur l'arbre d'etat\n");
 exit(2);
}
/******************************************************************
*                                                                 *
* ECRITURE de la grille chainee dans des fichiers referentiels    *
*                                                                 *
******************************************************************/
#define Max1 100
#define Max2   5
#define Long1 11
#define Long2  4
void ECRIT_GRILLE(struct Noeud *pAgrille,long compteur_total)
{

 int decompteN(struct Noeud *);
 void itoa(int,char *,int l);
 void inverser(char s[]);

 FILE *fp; 

 /*
 struct Noeud {
     int valx;
     int valy;
     int O[8];
     struct Noeud *radicaux[8];
     struct Noeud *psNoeud;
     struct Noeud *ppNoeud;
 }
*/

  char strcompteur[Max1];
  char strnbNoeud[Max2];
  char strpostfix[Max1+Max2];
  char NomFic_ref[strlen("Fichier_Grille.#1234AAAA#123456789012345.dat")];

  struct Noeud *px,*py;
  int xd1,yd1;
  int xd2,yd2;
  int nbNoeud;
  int i,n;
  int d1,d2;

  /*****************************************************/
  nbNoeud=decompteN(pAgrille);
  /*****************************************************/
  /* 1. Ecriture du fichier UPTODATE referentiel .dat  */
  /* nb de grilles (minimum) et nb de Noeuds (maximum) */ 
  /*****************************************************/
  fp=fopen("Fichier_Grille.dat","w");
  n=0;
  fprintf(fp,"%4i\n",nbNoeud);
  for(px=pAgrille;px!=NULL;px=px->psNoeud) {
    n++;
    xd1=px->valx;
    yd1=px->valy;
    fprintf(fp,"%04i\n",n);
    fprintf(fp,"%04i    %04i\n",xd1,yd1);
    for(i=0;i<=7;i++) {
    fprintf(fp,"%1i\n",i);
    d1=px->O[i];
    fprintf(fp,"%1i   %04d   %04d\n",d1,xd1,yd1);
    /* connectivite 8 directions */
    py=px->radicaux[i];
    d2=0;
    xd2=0;yd2=0;
    if(py!=NULL){
       d2=py->O[(i+4)%8];
       xd2=py->valx;
       yd2=py->valy;
       }
    fprintf(fp,"%1i   %04d   %04d\n",d2,xd2,yd2);
    }  
  }
    fclose(fp);
  /*****************************************************/
  /* 2. Ecriture des quatre references                 */
  /*  - A. nb d'iterations (constante) pour MAJ        */
  /*       a l'ecriture                                */ 
  /*  - B. nombre de Noeuds (max) a l'ecriture         *
  /*  - C. nombre de grilles testees a l'ecriture      */
  /*  - D. nombre de grilles en cours (ici egal au -C.)*/
  /*****************************************************/
    fp=fopen("nbs.ref","w");
    fprintf(fp,"%ld\n",dk2);
    fprintf(fp,"%ld\n",nbNoeud-36);
    fprintf(fp,"%ld\n",compteur_total);
    fprintf(fp,"%ld\n",compteur_total);
    fclose(fp);
  /*****************************************************/
  /* 3. Ecriture du fichier des donnees referentielle  */
  /* nb de grilles, nb de Noeuds (maximum)             */ 
  /* (trace du des resultats d'etapes)                 */
  /*****************************************************/
  itoa(compteur_total,strcompteur,Long1);
  itoa(nbNoeud-36,strnbNoeud,Long2);
  /*==========================*/
  /* construction du prefixe  */
  /*==========================*/
  strcpy(strpostfix,"");
  strcat(strpostfix,strnbNoeud);
  strcat(strpostfix,"#");
  strcat(strpostfix,strcompteur);
  /*==========================*/
  strcpy(NomFic_ref,"Fichier_Grille.#");
  strcat(NomFic_ref,strpostfix);
  strcat(NomFic_ref,".dat");
  /*===================================================*/
  fp=fopen(NomFic_ref,"w");
  n=0;
  fprintf(fp,"%4i\n",nbNoeud-36);
  for(px=pAgrille;px!=NULL;px=px->psNoeud) {
    n++;
    xd1=px->valx;
    yd1=px->valy;
    fprintf(fp,"%04i\n",n);
    fprintf(fp,"%04i    %04i\n",xd1,yd1);
    for(i=0;i<=7;i++) {
    fprintf(fp,"%1i\n",i);
    d1=px->O[i];
    fprintf(fp,"%1i   %04d   %04d\n",d1,xd1,yd1);
    /* connectivite 8 directions */
    py=px->radicaux[i];
    d2=0;
    xd2=0;yd2=0;
    if(py!=NULL){
       d2=py->O[(i+4)%8];
       xd2=py->valx;
       yd2=py->valy;
       }
    fprintf(fp,"%1i   %04d   %04d\n",d2,xd2,yd2);
    }  
  }
    fclose(fp);
  /*****************************************************/
  /* -A. sortie des 4 references                       */
  /* appels systeme du generateur IDL de la sortie ps  */
  /* conversion en gif et Maj du web                   */
  /* -B. sortie de la Grille record                    */
  /* appels systeme du generateur IDL de la sortie ps  */
  /* conversion en gif et Maj du web                   */
  /*****************************************************/
    system("cshAB_MAJnbs>>/dev/null &");
  /*====================================================*/
}

/***********************************************
! procedure itoa                               !
! convertit n (entier) en chaine de caracteres !
!**********************************************/
void itoa(int n,char s[],int l)
{
  int i=0;
  do {
    s[i++]=n%10 +'0';
  } while ((n/=10) !=0);
  for(;l-i>0;i++) s[i]='0'; 
  s[i++]='\0';
  inverser(s);
}
void inverser(char s[])
{
  int i,j;
  char c;
  for(i=0,j=strlen(s)-1;j>i;i++,j--) {
    c=s[i];
    s[i]=s[j];
    s[j]=c;
  }
}
/***********************************************
! Fonction                                     !
! decompteN des noeuds de la grille            !
!**********************************************/
int decompteN(struct Noeud *pAgrille)
{ 
  struct Noeud *px;
  int n;
  
  n=0;
  for(px=pAgrille;px!=NULL;px=px->psNoeud) {
  n++;
  }
  return n;
}
/**********************************************
! Fonction                                    !
! decompteX des noeuds X possibles            !
!*********************************************/
int decompteX(struct XNoeud *pXgrille)
{ 
  struct XNoeud *px;
  int n;
  
  n=0;
  for(px=pXgrille;px!=NULL;px=px->psNoeud) {
  n++;
  }
  return n;
}
/**********************************************
! Fonction                                    !
! de coherence du nb de liaisons de la grille !
!*********************************************/
int coherenceL(struct Noeud *pAgrille)
{ 
  struct Noeud *px;
  int i,l;
  
  l=0;
  for(px=pAgrille;px!=NULL;px=px->psNoeud) {
    for(i=0;i<=7;i++) {
        if(px->O[i]==0) l++;
     }
  }
  return l;
}
/**********************************************
! procedure ajoutarbre :                      !
! ajoute un ENoeud au niveau p ou en dessous  !
!*********************************************/
/*
 struct ENoeud {
     int niveau;
     int rang;       ** rang de traitement [0..nbpos] **
     int nbpos;      ** nb de possibilite X           **
     int T;
     int S;
     int valx;
     int valy;
     int O[8];
     struct ENoeud *radicaux[8];
     struct ENoeud *droite;
     struct ENoeud *gauche;
*/
struct ENoeud *ajoutarbre(struct ENoeud *p,
                          int niveau,
                          int nbpos,
                          int rang,
                          int T,
                          int S,
                          int valx,
                          int valy,
                          int O[8],
                          struct ENoeud *radicaux[8])
{

  int i;
 
  if(p==NULL) {               /* cree un nouveau noeud */
     p=(struct ENoeud *) malloc(sizeof(struct ENoeud));
     p->gauche=NULL;
     p->droite=NULL;
     /*=========================*/
     /* affectation des valeurs */
     /*=========================*/
     p->niveau=niveau;
     p->nbpos=nbpos;
     p->rang=rang;
     p->T=T;
     p->S=S;
     p->valx=valx;
     p->valy=valy;
     for(i=0;i<=7;i++) p->O[i]=O[i];
     for(i=0;i<=7;i++) p->radicaux[i]=radicaux[i];
     /*==========================*/
  }
  else {
     if(niveau < p->niveau) { p->gauche=ajoutarbre(p->gauche,
                                     niveau,
                                     nbpos,
                                     rang,
                                     T,
                                     S,
                                     valx,
                                     valy,
                                     O,
                                     radicaux);
     }
     else if(niveau == p->niveau) {
          if(valy > p->valy) { p->gauche=ajoutarbre(p->gauche,
                                     niveau,
                                     nbpos,
                                     rang,
                                     T,
                                     S,
                                     valx,
                                     valy,
                                     O,
                                     radicaux);
          }
          else if(valy == p->valy) {
               if(valx > p->valx) { p->gauche=ajoutarbre(p->gauche,
                                     niveau,
                                     nbpos,
                                     rang,
                                     T,
                                     S,
                                     valx,
                                     valy,
                                     O,
                                     radicaux);
	       }
          else if(valx == p->valx) {
               if(T > p->T) { p->gauche=ajoutarbre(p->gauche,
                                     niveau,
                                     nbpos,
                                     rang,
                                     T,
                                     S,
                                     valx,
                                     valy,
                                     O,
                                     radicaux);
	       }
          else if(T == p->T) {
               if(S > p->S) { p->gauche=ajoutarbre(p->gauche,
                                     niveau,
                                     nbpos,
                                     rang,
                                     T,
                                     S,
                                     valx,
                                     valy,
                                     O,
                                     radicaux);
	  }
          else {p->droite=ajoutarbre(p->droite,
                                     niveau,
                                     nbpos,
                                     rang,
                                     T,
                                     S,
                                     valx,
                                     valy,
                                     O,
                                     radicaux);
          }
          }
          else {p->droite=ajoutarbre(p->droite,
                                     niveau,
                                     nbpos,
                                     rang,
                                     T,
                                     S,
                                     valx,
                                     valy,
                                     O,
                                     radicaux);

	  }
          }
          else {p->droite=ajoutarbre(p->droite,
                                     niveau,
                                     nbpos,
                                     rang,
                                     T,
                                     S,
                                     valx,
                                     valy,
                                     O,
                                     radicaux);
          }
          }
          else {p->droite=ajoutarbre(p->droite,
                                     niveau,
                                     nbpos,
                                     rang,
                                     T,
                                     S,
                                     valx,
                                     valy,
                                     O,
                                     radicaux);
          }
          }
          else {p->droite=ajoutarbre(p->droite,
                                     niveau,
                                     nbpos,
                                     rang,
                                     T,
                                     S,
                                     valx,
                                     valy,
                                     O,
                                     radicaux);
          }
  }

  return p;
}

/**********************************************
! procedure affarbre :                        !
! affiche l'arbre p dans l'ordre              !
!*********************************************/
void affarbre(struct ENoeud *p)
{
  struct ENoeud *q;
  int i;

  if(p!=NULL) {
     affarbre(p->gauche);
     printf("niveau = %4d\n",p->niveau);
     printf("nbpos =  %4d\n",p->nbpos);
     printf("rang =  %4d\n",p->rang);
     printf("valx =   %4d\n",p->valx);
     printf("valy =   %4d\n",p->valy);
     affarbre(p->droite);
  }
  return;
}
/**********************************************
! procedure invarbre :                        !
! affiche l'arbre p dans l'ordre decroissant  !
!*********************************************/
void invarbre(struct ENoeud *p)
{
  if(p!=NULL) {
     invarbre(p->droite);
     printf("niveau = %4d\n",p->niveau);
     printf("nbpos =  %4d\n",p->nbpos);
     printf("rang =  %4d\n",p->rang);
     printf("valx =   %4d\n",p->valx);
     printf("valy =   %4d\n",p->valy);
     invarbre(p->gauche);
  }
  return;
}
/**********************************************
! procedure liberation arbre :                !
! libere l'arbre p dans l'ordre               !
!*********************************************/
void freearbre(struct ENoeud *p)
{
  struct ENoeud *q1,*q2;
  int i;

  if(p!=NULL) {
     freearbre(p->gauche);
     free(p);
     freearbre(p->droite); 
  }
  return;
}
/*************************************************!
! procedure autogenearbre0 :                      ! 
! generation automatique des liaisons radicales   !
! du seul noeud selectionne : pNOEUDETAT          !
!**************************************************/
void autogenearbre0(struct ENoeud *ptr,struct ENoeud *pNOEUDETAT)
{
 int xa,ya;

 xa=pNOEUDETAT->valx;
 ya=pNOEUDETAT->valy;
 if(ptr!=NULL) {
   autogenearbre0(ptr->gauche,pNOEUDETAT);
 if((xa==ptr->valx)&&((ya+1)==ptr->valy))
   {pNOEUDETAT->radicaux[0]=ptr;}
 if(((xa-1)==ptr->valx)&&((ya+1)==ptr->valy))
   {pNOEUDETAT->radicaux[1]=ptr;}
 if(((xa-1)==ptr->valx)&&(ya==ptr->valy))
   {pNOEUDETAT->radicaux[2]=ptr;}
 if(((xa-1)==ptr->valx)&&((ya-1)==ptr->valy))
   {pNOEUDETAT->radicaux[3]=ptr;}
 if((xa==ptr->valx)&&((ya-1)==ptr->valy))
   {pNOEUDETAT->radicaux[4]=ptr;}
 if(((xa+1)==ptr->valx)&&((ya-1)==ptr->valy))
   {pNOEUDETAT->radicaux[5]=ptr;}
 if(((xa+1)==ptr->valx)&&(ya==ptr->valy))
   {pNOEUDETAT->radicaux[6]=ptr;}
 if(((xa+1)==ptr->valx)&&((ya+1)==ptr->valy))
   {pNOEUDETAT->radicaux[7]=ptr;}
   autogenearbre0(ptr->droite,pNOEUDETAT);
  }
  return;
}
/***********************************************!
! procedures autogenearbre1/2 :                 !
! 2 procedures emboitees pour la generation     !
! automatique des liaisons radicales dans       ! 
! l'arbre de structure ENoeud                   !
!************************************************/
void autogenearbre1(struct ENoeud *pk,
                    struct ENoeud *p1)
{
  if(p1!=NULL) {
     autogenearbre1(pk,p1->gauche);
     autogenearbre2(p1,pk);
     autogenearbre1(pk,p1->droite);
   }
 return;
 }
void autogenearbre2(struct ENoeud *p1,
                    struct ENoeud *p2)
{
  int xa,ya;
  
     if(p2!=NULL) {
     autogenearbre2(p1,p2->gauche);
     xa=p1->valx;
     ya=p1->valy; 
      if((xa==p2->valx)&&((ya+1)==p2->valy))
       {p1->radicaux[0]=p2;}
      if(((xa-1)==p2->valx)&&((ya+1)==p2->valy))
        {p1->radicaux[1]=p2;}
      if(((xa-1)==p2->valx)&&(ya==p2->valy))
        {p1->radicaux[2]=p2;}
      if(((xa-1)==p2->valx)&&((ya-1)==p2->valy))
        {p1->radicaux[3]=p2;}
      if((xa==p2->valx)&&((ya-1)==p2->valy))
        {p1->radicaux[4]=p2;}
      if(((xa+1)==p2->valx)&&((ya-1)==p2->valy))
        {p1->radicaux[5]=p2;}
      if(((xa+1)==p2->valx)&&(ya==p2->valy))
        {p1->radicaux[6]=p2;}
      if(((xa+1)==p2->valx)&&((ya+1)==p2->valy))
        {p1->radicaux[7]=p2;}
     autogenearbre2(p1,p2->droite);
     }
 return;
 }
/*==========================*/
/* permutation de pointeurs */
/*==========================*/
 void echange(struct XNoeud *ptsa , struct XNoeud *ptsb)
{
 int Tp,Sp,xp,yp;

   Sp=(*ptsa).S;
   Tp=(*ptsa).T;
   xp=(*ptsa).valx;
   yp=(*ptsa).valy;
   (*ptsa).S=(*ptsb).S;
   (*ptsa).T=(*ptsb).T;
   (*ptsa).valx=(*ptsb).valx;
   (*ptsa).valy=(*ptsb).valy;
   (*ptsb).T=Tp;
   (*ptsb).S=Sp;
   (*ptsb).valx=xp;
   (*ptsb).valy=yp; 
 return;
}