/*
 * Module ID: crossadd.cpp
 * Title    : Solveur de jeu d'additions croisees
 * Purpose  : Solution du probleme #10 du concours FCI 95
 *            (http://www.gel.usherbrooke.ca/fci/fci_95/problemes/prob10.html)
 *
 * Author   : Olivier Langlois <olivier@olivierlanglois.net>
 * Date     : September 1, 1996
 *
 * Revision :
 *
 * 001        21-May-2006 - Olivier Langlois
 *            Code clean-up by replacing pointers array management code with
 *            vector objects.
 */

#include <fstream>
#include <strstream>
#include <stdlib.h>
#include "signon.h"
#include "diagdos.h"
#include "collect/set.h"
#include "debug.h"
#include "collect/vector.h"

#define IFILE "p10.ent"
#define OFILE "p10.sor"

#define NB_COL 8
#define NB_ROW 10

#define GAUCHE 0
#define DROITE 1
#define HAUT   2
#define BAS    3

#define BLANCHE(a,b)      l_grille[a][b].u.case_blanche
#define PTRSOMME(a,b,c)   ((s_Liste_cases **)BLANCHE(a,b).ptr_somme)[c]
#define PTRSOMPAREIL(a,b) static_cast<s_Liste_cases *>(((a)->somme_pareil)[b])

DiagOutDOS diagout(cerr);
DiagOutput *SETImpl::SetOut = &diagout;

enum CrossAdd_Error
{
  CA_ALLOC,
  CA_MISMATCH,
  CA_BOUNDS,
  CA_CORRUPT,
  CA_FILE
};

/******************************************************************************
 *
 * Nom       : CaEx
 *
 * Utilite   : Definit la classe d'exception pour le programme crossadd
 *
 ****************************************************************************/
class CaEx : public ExceptionBase
{
  public:
     CaEx(
        CrossAdd_Error err
        )
     {
        Error = err;
     }

/******************************************************************************
 *
 * Nom       : Explain
 *
 * Utilite   : Explique la cause de l'exception.
 *
 * Reference : diagnose.h
 *
 ****************************************************************************/
    virtual void Explain(DiagOutput &diag);

 private:
    CrossAdd_Error Error;
};

void CaEx::Explain(DiagOutput &diag)
{
  switch(Error)
  {
     case CA_ALLOC:
        diag.DisplayMsg("Add: Memory allocation error",
                             DIAG_ERROR);
        break;
     case CA_MISMATCH:
        diag.DisplayMsg("Add: Kakuro grid case type invalid",
                             DIAG_ERROR);
        break;
     case CA_FILE:
        diag.DisplayMsg("Add: Error relative to file access",
                             DIAG_ERROR);
        break;
     case CA_BOUNDS:
        diag.DisplayMsg("Add: Possible value out of range",
                             DIAG_WARNING);
        break;
     case CA_CORRUPT:
        diag.DisplayMsg("Add: Corrupted structure found",
                             DIAG_FATAL);
  }
}

/*
 * Declarations incompletes
 */
struct s_Liste_cases;

typedef void* voidPTR;
GVectordeclare(voidPTR);
GVectorimplement(voidPTR);

typedef struct
{
  int             val;
  SET<1>         *pos_val;

  /*
    * ptr_somme est en realite un pointeur de structure s_Liste_cases
    * mais puisque la definition s_Case_blanche est utilisee dans celle
    * de s_Liste_cases, il a fallue utiliser le type void* pour definir
    * ptr_somme car s_Liste_cases n'est pas encore defini.
    *
    * 30 Novembre 1997 - Corrige par une declaration incomplete
    */
    s_Liste_cases **ptr_somme;
    unsigned       nb_somme;
} s_Case_blanche;

struct s_Liste_cases
{
  unsigned         nb_csblanche;
  unsigned         nb_csvide;
  s_Case_blanche  *csblanche[8];

  voidPTRGVector   discrimset;
  voidPTRGVector   intdisc;

  int              tmp_val;
  SET<1>          *pos_val;

  SET<1>          *val_trouvee;

  Flag             pareil;
  voidPTRGVector   somme_pareil;
};

typedef struct
{
  int            val[4];
  s_Liste_cases *liste[4];

  unsigned       col;
  unsigned       ligne;
} s_Somme;

typedef struct
{
  unsigned type;
  union
  {
     s_Somme        somme;
     s_Case_blanche case_blanche;
  } u;
} s_Case_jeu;

/*
 * Variante des nombres de Fibonacci: coef[pos] = coef[pos-1] + pos
 * utilisee dans la fonction f_set_set.
 */
static const Byte coef[] = { 0, 1, 3, 6, 10, 15, 21, 28, 36 };

static s_Case_jeu l_grille[NB_ROW][NB_COL];

/*
 * Il y a au moins 1 case blanche associee a chaque case somme.
 */
static s_Somme   *l_liste_sommes[NB_ROW*NB_COL/2];
static unsigned   nb_somme = 0;

/*
 * Declaration des fonctions locales.
 */
static void f_init          ( void );
static void f_calcul        ( void );
static void f_recalcule     ( int, int );
static void f_elimine       ( int, int );
static void f_init_cases    ( void );
static void f_init_pareil   ( void );
static void f_set_pareil    ( s_Liste_cases *const, s_Liste_cases *const );
static void f_set_discrimset( s_Liste_cases *const, unsigned );
static void f_set_set( s_Liste_cases *const, unsigned, unsigned, unsigned );
static void f_terminate     ( void );

/******************************************************************************
 *
 * Name       : main
 *
 ****************************************************************************/
void __cdecl main( void )
{
  signon("CrossAdd");
  try
  {
     f_init();
     f_calcul();
     f_terminate();
  }
  catch( ExceptionBase &error )
  {
     error.Explain( *SET<1>::SetOut );
  }
  D( SET<1>::ShowStatistics(cout); )
}

/******************************************************************************
 *
 * Nom       : f_init
 *
 ****************************************************************************/
static void f_init( void )
{
  int col, ligne;
  /*
   * ios::nocreate does not exist in the new iostreams.
   */
  ifstream infile( IFILE, ios::in/*|ios::nocreate*/  );

  if( !infile )
  {
     cerr << DEBUGTAG << endl;
     throw CaEx( CA_FILE );
  }

  memset( l_liste_sommes, 0, (NB_ROW*NB_COL)/2 * sizeof(s_Somme *) );
  memset( l_grille, 0, NB_ROW * NB_COL * sizeof(s_Case_jeu) );

  for( ligne = 0; ligne < NB_ROW; ligne++ )
  {
     for( col = 0; col < NB_COL; col++ )
     {
        infile >> l_grille[ligne][col].type;
        switch( l_grille[ligne][col].type )
        {
          case 0:
             // Initialise l'ensemble des valeurs possibles de la case blanche
             BLANCHE(ligne,col).pos_val = new SET<1>;

             // Allocation de memoire pour les pointeurs sur les sommes.
             if( (((s_Liste_cases **)BLANCHE(ligne, col).ptr_somme)
                 =(s_Liste_cases **)malloc(2*sizeof(s_Liste_cases *))) == NULL )
                throw CaEx( CA_ALLOC );

             // Initialise l'ensemble avec tous ses elements a 1.
             BLANCHE(ligne, col).pos_val->FILL();

             BLANCHE(ligne, col).nb_somme = 0;
          case 2:
             infile.ignore( 256, '\n' ); // Ignore le reste de la ligne
             break;

          case 1: // case somme
             infile.ignore( 2 ); // Ignore la valeur V
             infile >> l_grille[ligne][col].u.somme.val[GAUCHE]
                      >> l_grille[ligne][col].u.somme.val[DROITE]
                      >> l_grille[ligne][col].u.somme.val[HAUT]
                      >> l_grille[ligne][col].u.somme.val[BAS];
             l_grille[ligne][col].u.somme.ligne = ligne;
             l_grille[ligne][col].u.somme.col   = col;
             l_liste_sommes[nb_somme++] = &l_grille[ligne][col].u.somme;
             break;

          default:
             cerr << DEBUGTAG << '[' << ligne << "][" << col << "] = "
                    << l_grille[ligne][col].type << endl;
             throw CaEx( CA_MISMATCH );
        }
     }
  }
  f_init_cases();
  f_init_pareil();
}

/******************************************************************************
 *
 * Nom       : f_init_cases
 *
 ****************************************************************************/
static void f_init_cases( void )
{
  unsigned i;
  int j;
  int ligne, col;

  D( cerr << "Entre dans f_init_cases()" << endl; )
  for( i = 0; i < nb_somme; i++ )
  {
     for( j = 0; j < 4; j++ )
     {
        if( l_liste_sommes[i]->val[j] )
        {
          ligne = l_liste_sommes[i]->ligne;
          col   = l_liste_sommes[i]->col;
          D( cerr << "Ligne = " << ligne << " Col = " << col << " j = " << j
                     << endl; )

          l_liste_sommes[i]->liste[j] = new s_Liste_cases;
          l_liste_sommes[i]->liste[j]->nb_csblanche = 0;
          l_liste_sommes[i]->liste[j]->pareil = 0;
          l_liste_sommes[i]->liste[j]->tmp_val = l_liste_sommes[i]->val[j];
          l_liste_sommes[i]->liste[j]->pos_val = new SET<1>;
          l_liste_sommes[i]->liste[j]->val_trouvee = new SET<1>;

          switch( j )
          {
             case GAUCHE:
                // Il ne peut y avoir une fleche gauche si col == 0
                if( !col ) goto CORROMPUE;
                else
                {
                  while( col && l_grille[ligne][col - 1].type == 0 )
                  {
                     PTRSOMME(ligne,col-1,BLANCHE(ligne,col-1).nb_somme++)
                     = l_liste_sommes[i]->liste[j];
                     l_liste_sommes[i]->liste[j]->csblanche[l_liste_sommes[i]->liste[j]->nb_csblanche++]
                     = &BLANCHE(ligne,--col);
                  }
                }
                break;
             case DROITE:
                // Il ne peut y avoir fleche droite si col == NB_COL-1.
                if( col >= NB_COL-1 ) goto CORROMPUE;
                else
                {
                  while( (col < NB_COL-1) && l_grille[ligne][col+1].type == 0 )
                  {
                     PTRSOMME(ligne,col+1,BLANCHE(ligne,col+1).nb_somme++)
                     = l_liste_sommes[i]->liste[j];
                     l_liste_sommes[i]->liste[j]->csblanche[l_liste_sommes[i]->liste[j]->nb_csblanche++]
                     = &BLANCHE(ligne,++col);
                  }
                }
                break;
             case HAUT:
                // Il ne peut y avoir une fleche vers le haut si ligne == 0.
                if( !ligne ) goto CORROMPUE;
                else
                {
                  while( ligne && l_grille[ligne-1][col].type == 0 )
                  {
                     PTRSOMME(ligne-1,col,BLANCHE(ligne-1,col).nb_somme++)
                     = l_liste_sommes[i]->liste[j];
                     l_liste_sommes[i]->liste[j]->csblanche[l_liste_sommes[i]->liste[j]->nb_csblanche++]
                     = &BLANCHE(--ligne,col);
                  }
                }
                break;
             case BAS:
                // Il ne peut y avoir une fleche vers le bas si ligne == NB_ROW-1.
                if( ligne < NB_ROW-1 )
                {
                  while( (ligne < NB_ROW-1 ) && l_grille[ligne+1][col].type == 0 )
                  {
                     PTRSOMME(ligne+1,col,BLANCHE(ligne+1,col).nb_somme++)
                     = l_liste_sommes[i]->liste[j];
                     l_liste_sommes[i]->liste[j]->csblanche[l_liste_sommes[i]->liste[j]->nb_csblanche++]
                     = &BLANCHE(++ligne,col);
                  }
                  break;
                }

                CORROMPUE:
                cerr << DEBUGTAG << " La structure somme #" << i
                      << " est corrompue." << endl;
                throw CaEx( CA_CORRUPT );
          }  // END SWITCH
          // Initialise nb_csvide a la valeur de nb_csblanche.
          l_liste_sommes[i]->liste[j]->nb_csvide =
             l_liste_sommes[i]->liste[j]->nb_csblanche;
        }    // END IF( val[j] )
     }      // END FOR( each side )
  }        // END FOR( each sum )
}

/******************************************************************************
 *
 * Nom       : f_init_pareil
 *
 ****************************************************************************/
static void f_init_pareil( void )
{
  unsigned i, k;
  int j, z;

  D( cerr << "Entre dans f_init_pareil()" << endl; )
  // Pour chaque entree de la liste des sommes
  for( i = 0; i < nb_somme; i++ )
  {
     // Pour les 4 sommes de l'entree
     for( j = 0; j < 4; j++ )
     {
        // Si la somme est initialisee
        if( l_liste_sommes[i]->val[j] )
        {
          // Si la somme n'a pas deja ete comptabilise comme etant pareil
          if( !l_liste_sommes[i]->liste[j]->pareil )
          {
             // Alors elle est comparee a toutes les autres sommes.
             for( k = i; k < nb_somme; k++ )
             {
                /* En partant de la somme suivante
                 * si il sagit de l'entree courante ou
                 * de la premiere somme de l'entree
                 * pour toutes les autres entrees.
                 */
                for( z = (k == i) ? j+1:0; z < 4; z++ )
                {
                  if( l_liste_sommes[i]->val[j] == l_liste_sommes[k]->val[z] )
                  {
                     if( l_liste_sommes[i]->liste[j]->nb_csblanche ==
                          l_liste_sommes[k]->liste[z]->nb_csblanche )
                     {
                        f_set_pareil( l_liste_sommes[i]->liste[j],
                                      l_liste_sommes[k]->liste[z] );
                     }
                  }
                }  // END FOR( toutes les sommes z )
             }
          }      // END IF ( val[j]              )
          f_set_discrimset( l_liste_sommes[i]->liste[j],
                            l_liste_sommes[i]->val[j] );
        }
     }        // END FOR( toutes les sommes  j )
  }          // END FOR( toutes les entrees i )
}

/******************************************************************************
 *
 * Nom       : f_set_pareil
 *
 ****************************************************************************/
static void f_set_pareil( s_Liste_cases *const somme1,
                          s_Liste_cases *const somme2
                        )
{
  unsigned i;

  D( cerr << "Entre dans f_set_pareil" << endl; )

  // Si somme1 a deja une liste de sommes pareilles
  if( somme1->pareil )
  {
     // Copie la liste de la somme1 dans la liste de la somme2
     somme2->pareil = 1;
     somme1->somme_pareil.resize(somme1->somme_pareil.length()+1);
     somme2->somme_pareil.resize(somme1->somme_pareil.length());

     for( i = 0;
          i < somme1->somme_pareil.length() - 1;
          i++ )
     {
        somme2->somme_pareil[i] =
        PTRSOMPAREIL(somme1, i);
     }
  }
  // Sinon initialise les listes de la somme1 et de la somme2.
  else
  {
     somme1->pareil =
     somme2->pareil = 1;
     somme1->somme_pareil.resize(1);
     somme2->somme_pareil.resize(1);
  }
  // Ajoute la somme2 dans la liste des sommes listees dans la liste
  // de la somme1.
  for( i = 0;
       i < somme1->somme_pareil.length() - 1;
       i++ )
  {
     s_Liste_cases *const nextSum = PTRSOMPAREIL(somme1,i);
     nextSum->somme_pareil.resize(nextSum->somme_pareil.length()+1);
     nextSum->somme_pareil[nextSum->somme_pareil.length()-1] = somme2;
  }
  // Ajoute la somme1 dans la liste de la somme2.
  somme2->somme_pareil[somme2->somme_pareil.length()-1]
  = somme1;
  // Ajoute la somme2 dans la liste de la somme1.
  somme1->somme_pareil[somme1->somme_pareil.length()-1]
  = somme2;
}

/******************************************************************************
 *
 * Name       : f_set_discrimset
 *
 * Note       : This function share commun code with f_set_recalcule. There is
 *              an opportunity to refactorize and simplify this code.
 *
 ****************************************************************************/
static void f_set_discrimset( s_Liste_cases *const somme,
                              unsigned val )
{
  unsigned i, j;

  SET<1> tmpset;

  D( cerr << "Entre dans f_set_discrimset()" << endl; )
  f_set_set( somme, val, somme->nb_csblanche, 1 );
  D( cerr << "nb_discrimset =" << somme->discrimset.length() << endl; )

  SET<1> *tmp_discrimset = new SET<1>[somme->discrimset.length()];

  for( i = 0; i < somme->discrimset.length(); i++ )
  {
     tmpset.clear();
     for( j = 0; j < somme->discrimset.length(); j++ )
     {
        if( j != i )
          tmpset |= *static_cast<SET<1> *>(somme->discrimset[j]);
     }
     *somme->pos_val  |= *static_cast<SET<1> *>(somme->discrimset[i]);
     tmpset           &= *static_cast<SET<1> *>(somme->discrimset[i]);
     tmp_discrimset[i] = *static_cast<SET<1> *>(somme->discrimset[i]) - tmpset;
  }
  // Place les vrais ensembles de discriminants
  D( cerr << "val =" << val << endl << *somme->pos_val; )
  for( i = 0; i < somme->discrimset.length(); i++ )
  {
     *static_cast<SET<1> *>(somme->discrimset[i]) = tmp_discrimset[i];
  }
  delete[] tmp_discrimset;
}

/******************************************************************************
 *
 * Name       : f_set_set
 *
 * Note : Recursive functions that compute all the possible number combinations
 *        between (1-9) to reach val with nb_cases numbers in the combination.
 *
 ****************************************************************************/
static void f_set_set( s_Liste_cases *const somme,
                              unsigned val,
                              unsigned nb_cases,
                              unsigned first_pos )
{
  unsigned i, current_set;

  D( cerr << "Entre dans f_set_set()" << endl; )

  // Initialise la liste discrimset si elle ne l'est pas.
  if( !somme->discrimset.length() )
  {
     somme->discrimset.resize(1);
     somme->discrimset[0] = new SET<1>;
  }

  current_set = somme->discrimset.length() - 1;

  D( cerr << "val =" << val << " nb_cases=" << nb_cases << " first_pos ="
             << first_pos << endl; )
  for( i = first_pos; i <= 9; i ++ )
  {
     // Si il ne reste que une case.
     if( nb_cases == 1 )
     {
        if( val > 9 )
          throw CaEx( CA_BOUNDS );

        static_cast<SET<1> *>(somme->discrimset[current_set])->ADD(val);
        break;
     }
     /*
      * La valeur i fait partie de la combinaison SI la somme des (nb_cases-1)
      * suivant i est <= que val-i ET que la somme des (nb_cases-1) plus grandes
      * valeurs possibles >= que val-i.
      */
     else if((((nb_cases-1)*(i + nb_cases-1)) - coef[nb_cases-2] <= val-i) &&
                 ((nb_cases-1)*9 - coef[nb_cases-2] >= val-i))
     {
        /*
         * Si la valeur suivant i est valide ET il reste plus que 2 cases alors
         * il existe au moins une autre combinaison.
         */
        if((((nb_cases-1)*(i + nb_cases)) - coef[nb_cases-2] < val-i) &&
             ((nb_cases-1)*9 - coef[nb_cases-2] >= val-(i+1)))
        {
          somme->discrimset.resize(somme->discrimset.length()+1);
          somme->discrimset[somme->discrimset.length()-1] =
             new SET<1>(*static_cast<SET<1> *>(somme->discrimset[current_set]));
          f_set_set(somme, val, nb_cases, i+1);
        }
        static_cast<SET<1> *>(somme->discrimset[current_set])->ADD(i);
        nb_cases--;
        val -= i;
     }
  }
}

/******************************************************************************
 *
 * Nom       : f_calcul
 *
 ****************************************************************************/
static void f_calcul( void )
{
  int     ligne, col;
  unsigned i;
  Boolean status = BOOL_TRUE;

  D( cerr << "Entre dans f_calcul()" << endl; )
  while( status == BOOL_TRUE )
  {
     status = BOOL_FALSE;

     // Calcule l'ensemble des possibilite de chacune des cases.
     for( ligne = 0; ligne < NB_ROW; ligne++ )
     {
        for( col = 0; col < NB_COL; col++ )
        {
          // Si la case est blanche et que la valeur de la case
          // n'a pas encore ete trouve.
          if( l_grille[ligne][col].type == 0 )
          {
             if( !BLANCHE(ligne,col).val )
             {
                for( i = 0; i < BLANCHE(ligne,col).nb_somme; i++ )
                {
                  // L'ensemble des valeurs possibles pour une case blanche est
                  // l'intersection des ensembles de valeurs possibles de la somme
                  // horizontale et verticale.
                  *BLANCHE(ligne,col).pos_val &=
                  *PTRSOMME(ligne,col,i)->pos_val;
                }
                D( cerr << '[' << ligne << "][" << col << "] "
                        << *BLANCHE(ligne,col).pos_val; )
                D( SET<1>::SetOut->DisplayMsg( "", DIAG_WARNING ); )
                if( BLANCHE(ligne,col).pos_val->empty() )
                {
                  D( for( i = 0; i < BLANCHE(ligne,col).nb_somme; i++)
                         cerr << *PTRSOMME(ligne,col,i)->pos_val; )
                  throw CaEx( CA_CORRUPT );
                }
                // Si la valeur de la case est trouve.
                if( BLANCHE(ligne,col).pos_val->size() == 1 )
                {
                  // L'ensemble des valeurs possibles pour les sommes
                  // doit etre recalcule.
                  f_recalcule( ligne, col );
                }
                f_elimine( ligne, col );
                status = BOOL_TRUE;
             }  // END IF   ( val == 0 )
          }
        }      // END FOR  ( l_grille )
     }
  }          // END WHILE( status   )
}

#ifdef DEBUG

static void dumpSets(const voidPTRGVector &setList)
{
    for( unsigned int i = 0; i < setList.length(); i++ )
    {
        cout << "Set #" << i << endl;
        cout << *static_cast<SET<1> *>(setList[i]);
    }
}

static void checkDiscrimSetState(const s_Liste_cases &newDiscrim, s_Liste_cases *somme)
{
    if( somme->intdisc.length() && (newDiscrim.discrimset.length() > somme->intdisc.length()) )
    {
        cout << "New set:\n";
        dumpSets(newDiscrim.discrimset);
        cout << "Old set:\n";
        dumpSets(somme->intdisc);
        throw CaEx( CA_CORRUPT );
    }
}

#endif

/******************************************************************************
 *
 * Nom       : f_recalcule
 *
 ****************************************************************************/
static void f_recalcule( int ligne, int col )
{
  unsigned i, j, k;

  s_Liste_cases tmp;
  SET<1>        tmpset;

  while( (BLANCHE(ligne,col).val =
             BLANCHE(ligne,col).pos_val->next_member())
             == -1 );

  for( i = 0; i < BLANCHE(ligne,col).nb_somme; i++ )
  {
     PTRSOMME(ligne,col,i)->val_trouvee->ADD(BLANCHE(ligne,col).val);
     tmpset.clear();
     tmp.discrimset.resize(0);

     // Soustrait la valeur trouve a la valeur temporaire des sommes.
     PTRSOMME(ligne,col,i)->tmp_val -=
     BLANCHE(ligne,col).val;

     f_set_set( &tmp,
                PTRSOMME(ligne,col,i)->tmp_val,
                --PTRSOMME(ligne,col,i)->nb_csvide,
                1 );

     // Enleve les combinaisons qui contiennent des valeurs
     // deja trouvees.
     for( j = 0; j < tmp.discrimset.length(); j++ )
     {
        if( !(*static_cast<SET<1> *>(tmp.discrimset[j]) &
              *PTRSOMME(ligne,col,i)->val_trouvee).empty() )
        {
          delete static_cast<SET<1> *>(tmp.discrimset[j]);

          // Shift SET pointers
          for( k = j+1; k < tmp.discrimset.length(); k++ )
          {
             tmp.discrimset[k-1] = tmp.discrimset[k];
          }

          tmp.discrimset.resize(tmp.discrimset.length()-1);
          j--;
        }
     }
     // If there are more sets than at the previous iteration
     // it is a bug.
     D( checkDiscrimSetState(tmp, PTRSOMME(ligne,col,i)); )
     if( PTRSOMME(ligne,col,i)->nb_csvide > 2 )
     {
        if( !PTRSOMME(ligne,col,i)->intdisc.length() )
        {
          PTRSOMME(ligne,col,i)->intdisc.resize(tmp.discrimset.length());

          for( j = 0; j < tmp.discrimset.length(); j++ )
          {
             PTRSOMME(ligne,col,i)->intdisc[j] = new SET<1>;
          }
        }
        else
        {
          /*
           * There might be less sets than at the previous iteration
           */
          for( j = tmp.discrimset.length();
               j < PTRSOMME(ligne,col,i)->intdisc.length(); j++ )
          {
             delete static_cast<SET<1> *>(PTRSOMME(ligne,col,i)->intdisc[j]);
          }
          PTRSOMME(ligne,col,i)->intdisc.resize(tmp.discrimset.length());
        }
        /*
         * Note : This function share commun code with f_set_discrimset. There is
         *        an opportunity to refactorize and simplify this code.
         */
        for( j = 0; j < tmp.discrimset.length(); j++ )
        {
          tmpset.clear();

          for( k = 0; k < tmp.discrimset.length(); k++ )
          {
             if( k != j )
             {
                tmpset |= *static_cast<SET<1> *>(tmp.discrimset[k]);
             }
          }
          tmpset &= *static_cast<SET<1> *>(tmp.discrimset[j]);
          // Place les vrais ensembles de discriminants
          *static_cast<SET<1> *>(PTRSOMME(ligne,col,i)->intdisc[j]) =
          *static_cast<SET<1> *>(tmp.discrimset[j]) - tmpset;
        }
     }

     for( j = 0; j < tmp.discrimset.length(); j++ )
     {
        tmpset |= *static_cast<SET<1> *>(tmp.discrimset[j]);
        delete static_cast<SET<1> *>(tmp.discrimset[j]);
     }

     *PTRSOMME(ligne,col,i)->pos_val &= tmpset;
  }
}

/******************************************************************************
 *
 * Nom       : f_elimine
 *
 ****************************************************************************/
static void f_elimine( int ligne, int col )
{
  unsigned i, j, k;
  unsigned num, num2;
  unsigned upper_limit;

  unsigned elem_used;
  int low, high;
  int next, tested_val;
  SET<1> tmpset1;
  SET<1> tmpset2;

  for( i = 0; i < BLANCHE(ligne,col).nb_somme; i++ )
  {
     if( PTRSOMME(ligne,col,i)->nb_csblanche > 3 )
     {
        for( j = 0;
             j < PTRSOMME(ligne,col,i)->intdisc.length();
             j++ )
        {
          if( static_cast<SET<1> *>(PTRSOMME(ligne,col,i)->intdisc[j])->subset(
                            *BLANCHE(ligne,col).pos_val ) )
          {
             for( k = 0;
                  k < PTRSOMME(ligne,col,i)->intdisc.length(); k++ )
             {
                if( k != j )
                {
                  *PTRSOMME(ligne,col,i)->pos_val -=
                  *static_cast<SET<1> *>(PTRSOMME(ligne,col,i)->intdisc[k]);
                }
             }
          }
        }
     }
     for( j = 0;
          j < PTRSOMME(ligne,col,i)->discrimset.length();
          j++ )
     {
        // Si l'ensemble des valeurs possibles de la case blanche est
        // un sous-ensemble d'un ensemble discriminant d'une somme alors
        if( static_cast<SET<1> *>(PTRSOMME(ligne,col,i)->discrimset[j])->subset(
             *BLANCHE(ligne,col).pos_val ) )
        {
          D( cerr << "Un subset a ete trouve" << endl
                  << *static_cast<SET<1> *>(PTRSOMME(ligne,col,i)->discrimset[j]); )

          // Cet ensemble doit etre soustrait a l'ensemble des valeurs
          // possibles des autres sommes identiques.
          if( PTRSOMME(ligne,col,i)->pareil )
          {
             for( k = 0;
                  k < PTRSOMME(ligne,col,i)->discrimset.length();
                  k++ )
             {
                if( k != j )
                {
                  *PTRSOMME(ligne,col,i)->pos_val -=
                  *static_cast<SET<1> *>(PTRSOMME(ligne,col,i)->discrimset[k]);
                }
             }
          }
        }  // END IF ( subset        )
     }    // END FOR( nb_discrimset )

     if( !BLANCHE(ligne,col).val )
     {
        tmpset1.clear();

        // Construit l'ensemble des valeurs possibles de toutes
        // les cases d'une somme sauf de la case qui est traitee.
        for( j = 0; j < PTRSOMME(ligne,col,i)->nb_csblanche; j++ )
        {
          if( (!PTRSOMME(ligne,col,i)->csblanche[j]->val) &&
                (PTRSOMME(ligne,col,i)->csblanche[j] != &BLANCHE(ligne,col)) )
          {
             tmpset1 |= *PTRSOMME(ligne,col,i)->csblanche[j]->pos_val;
          }
        }

        num = BLANCHE(ligne,col).pos_val->size();

        // Examine la validite de chaque valeur possible d'une case en
        // verifiant qu'il est possiblwe de parvenir a la somme avec chaque valeur.
        for( j = 0; j < num; j++ )
        {
          tmpset2 = tmpset1;
          low = high = 0;

          while( (tested_val = BLANCHE(ligne,col).pos_val->next_member())
                    == -1 );
          tmpset2.REMOVE(tested_val);

          if( PTRSOMME(ligne,col,i)->nb_csvide == 2 )
          {
             if( !tmpset2.TEST(PTRSOMME(ligne,col,i)->tmp_val-tested_val) )
             {
                D( cerr << "tested_val: " << tested_val << endl; )
                D( cerr << tmpset2; )
                D( SET<1>::SetOut->DisplayMsg( "", DIAG_WARNING ); )
                BLANCHE(ligne,col).pos_val->REMOVE(tested_val);
             }
          }
          else
          {
             num2 = tmpset2.size();
             upper_limit = num2 - (PTRSOMME(ligne,col,i)->nb_csvide - 1);
             elem_used = 0;

             for( k = 0; k < num2; k++ )
             {
                while( (next = tmpset2.next_member()) == -1 );

                if( k < PTRSOMME(ligne,col,i)->nb_csvide - 1 )
                {
                  low += next;
                  elem_used++;
                }
                if( k >= upper_limit )
                {
                  high += next;
                  elem_used++;
                }
             }
             if(((low > PTRSOMME(ligne,col,i)->tmp_val - tested_val) &&
                  (high < PTRSOMME(ligne,col,i)->tmp_val - tested_val)) ||
                 ((elem_used > num2) &&
                  ((low > PTRSOMME(ligne,col,i)->tmp_val - tested_val) ||
                  (high < PTRSOMME(ligne,col,i)->tmp_val - tested_val))) )
             {
                D( cerr << "tested_val: " << tested_val << " low: " << low
                        << " high: " << high << endl; )
                D( cerr << tmpset2; )
                D( SET<1>::SetOut->DisplayMsg( "", DIAG_WARNING ); )
                BLANCHE(ligne,col).pos_val->REMOVE(tested_val);
             }
          }
        }
        if( BLANCHE(ligne,col).pos_val->size() == 1 )
        {
          f_recalcule( ligne, col );
        }
     }
  }
}

/******************************************************************************
 *
 * Nom       : f_terminate
 *
 ****************************************************************************/
static void f_terminate( void )
{
  int col, ligne;
  ofstream outfile( OFILE, ios::out );

  D( cerr << "Entre dans f_terminate()" << endl; )
  if( !outfile )
  {
     cerr << DEBUGTAG << endl;
     throw CaEx( CA_FILE );
  }

  for( ligne = 0; ligne < NB_ROW; ligne++ )
  {
     for( col = 0; col < NB_COL; col++ )
     {
        outfile << l_grille[ligne][col].type << " ";
        switch( l_grille[ligne][col].type )
        {
          case 0:
             outfile << BLANCHE(ligne,col).val << " 0 0 0 0"
                     << endl;
             break;
          case 2:
             outfile << "0 0 0 0 0" << endl;
             break;
          case 1: // case somme
             outfile << "0 "
                     << l_grille[ligne][col].u.somme.val[GAUCHE] << ' '
                     << l_grille[ligne][col].u.somme.val[DROITE] << ' '
                     << l_grille[ligne][col].u.somme.val[HAUT]   << ' '
                     << l_grille[ligne][col].u.somme.val[BAS]    << endl;
             break;
        }
     }
  }
  // Should perform the structure clean up...
}