/*
Resolution de SU-DO-KU
par cycles de 2 phases (elimination et necessite)
Eric H, 2005
*/

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


#define gets(X)         {fgets(X, sizeof(X), stdin); X[strlen(X)-1]=0;}

/* nb maximal de grilles predefinies par niveau */
#define MAX_GRILLE_NIVEAU 10

/* nb maximal d'hypotheses simultanees */
#define MAX_HYPOT 50


typedef enum {FALSE, TRUE} bool;

#ifndef randomize()
#define randomize()     srand((unsigned)time(NULL))
#define random(N)       (rand()%(N))
#endif

typedef struct
  {
  bool possible[9];             /* la valeur i+1 est-elle possible */
  unsigned char val;            /* valeur fixee (de 1 a 9) */
  struct
    {
    unsigned init : 1;          /* valeur donnee initialement */
    unsigned necess : 1;        /* resolue par necessite ou elimination */
    unsigned prem_hyp : 1;      /* hypothese de depart ou deduit apres */
    } f;
  unsigned short hypot;         /* niveau d'hypothese (0=aucune) */
  } CASE;                       /* case de grille de Sudoku */

typedef enum {INCONNU, EASY, MEDIUM, HARD, EVIL} typ_niveau;

#define PLUR(N)         &"s"[(N)<=1]


bool resout_grille(void);
bool elimination(bool *impossible);
bool necessite(void);
bool make_hypothese(bool annuler_precedent);
unsigned short min_nb_valeurs_possibles(void);
void nb_cases_multiposs(short nb_poss_max, short *nb_vides,
                short *n_candidates);
bool decroit_hypothese(void);
bool verifie_grille(void);
void affiche_grille(void);
void affiche_grille_log(void);
void affiche_grille_html(void);
void _affiche_grille(FILE *out, bool with_colors);
void init_grille_auto(short num_grille);
short nb_connues_moy(typ_niveau niveau);
typ_niveau niveau_theorique(short nb_connues, short nb_hyp);
char *sniveau(typ_niveau niveau);
void saisit_grille_manu(void);
void saisit_grille_fichier(char *fic);
bool saisit_ligne(char *lig, CASE *t);
bool resolu(void);
void reset_grille(void);
void calcule_possibilites_cases(void);
void calcule_possibilites_case(short i, short j);
unsigned short nb_possib(short i, short j);
char *get_possibles(short i, short j);
unsigned short nb_fixe(void);
void pause(void);
void stat_grille(unsigned short niveau_hypot);

void cree_grille(typ_niveau niveau);
void cree_grille_hasard(short n_serie);
void fixe_hypot_hasard(void);
void epure_grille(void);
bool _epure_grille(short *n_supp);
void clean_grille(void);
void hasard(short *i, short *j);
void ajoute_valeurs_grille(typ_niveau niveau);

/* ----------------------------------------------------------------------- */

CASE tab[9][9];         /* LA grille de Sudoku */

/* nb de tours au-dela duquel on abandonne la recherche */
unsigned long n_tour_max=1000;

typ_niveau niveau;              /* niveau de difficulte de la grille */
unsigned short niveau_hypot;    /* niveau d'hypothese (0=aucune) */
unsigned short niveau_hypot_max=MAX_HYPOT;  /* niveau maximum d'hypothese */
unsigned long n_gomme;         /* nb d'echecs dans les hypotheses */
unsigned long n_passe;         /* nb de tours lors de la resolution */
bool verbose=FALSE;
bool verbose2=FALSE;    /* mode debug */
bool muet=FALSE;
bool with_pause=FALSE;
bool with_colors=TRUE;
/* insiste dans la phase 2 autant que dans la phase 1 */
bool insist2=FALSE;
/* visite aussi les hypotheses suivantes, en cas de niveau_hypot_max */
bool persist_suivants;


int main(int argc, char **argv)
  {
  short num_grille = 0;
  char *fic=0;
  bool mode_creation=FALSE;
  bool cherche_solution = TRUE;

  with_colors = TRUE;
  muet = FALSE;
  niveau = 0;
  randomize();

  /* examen parametres */
  while (argc > 1)
    {
    if (strcmp(argv[1], "-v") == 0)
      {
      argc--;
      argv++;
      verbose=TRUE;
      }
    else if (strcmp(argv[1], "-n") == 0)
      {
      argc--;
      argv++;
      with_colors=FALSE;
      }
    else if (strcmp(argv[1], "-s") == 0)
      {
      argc--;
      argv++;
      cherche_solution=FALSE;
      }
    else if (strcmp(argv[1], "-i") == 0)
      {
      argc--;
      argv++;
      insist2=TRUE;
      }
    else if (strcmp(argv[1], "-m") == 0)
      {
      argc--;
      argv++;
      muet=TRUE;
      }
    else if (strcmp(argv[1], "-p") == 0)
      {
      argc--;
      argv++;
      with_pause=verbose=TRUE;
      }
    else if (strcmp(argv[1], "-c") == 0)
      {
      argc--;
      argv++;
      mode_creation=TRUE;
      }
    else if (argc > 2 && strcmp(argv[1], "-f") == 0)
      {
      fic = argv[2];
      argc-=2;
      argv+=2;
      }
    else if (argc > 2 && strcmp(argv[1], "-h") == 0)
      {
      if (*argv[2]<'0' || *argv[2]>'9')
        goto help;
      niveau_hypot_max = atoi(argv[2]);
      argc-=2;
      argv+=2;
      }
    else if (argc > 2 && strcmp(argv[1], "-t") == 0)
      {
      int n;
      n = atoi(argv[2]);
      if (n == 0 && *argv[2] != '0')
	goto help;
      if (n <= 0)
	n_tour_max = (unsigned long)-1L;
      else
	n_tour_max = n;
      argc-=2;
      argv+=2;
      }
    else
      break;
    }
  if (fic && argc > 1
        || argc > 3
        || argc > 1 && *argv[1]=='-'
        || mode_creation && (fic || niveau_hypot_max != MAX_HYPOT))
    {
help:
    printf("Resolution ou creation de grilles de SU-DO-KU\n\n"
"Syntaxes:\n"
"  sudoku [-v|p|m] [-i] [-n] [-h n] [-t n] [-f fichier | [niveau] [num_grille]]\n"
"  sudoku -s [-f fichier | [niveau] [num_grille]]\n"
"  sudoku -c [niveau | nb_cases_connues]\n"
"Grille a resoudre dans un fichier texte, ou grilles internes (niveau: 1 a 5)\n"
"Options:\n"
" -v : montre chaque etape de resolution.\n"
" -p : fait une pause clavier a chaque etape de resolution.\n"
" -m : completement muet\n"
" -n : sans les couleurs (utile pour redirections)\n"
" -f : lit la grille depuis un fichier texte.\n"
" -i : insiste dans Phase 2 de resolution autant que dans Phase 1\n"
" -h n : s'efforce de ne pas poser plus de n hypotheses simultanees\n"
" -t n : modifie le nombre de tours maximum pour trouver (def: %lu); 0=infini\n"
" -s : ne cherche pas la solution (utile pour imprimer)\n"
" -c : cree une grille automatiquement\n"
"Voir:\n"
"  sudoku.doc pour une documentation (format RTF)\n"
"  http://www.websudoku.com pour des millions de grilles.\n", n_tour_max);
    return 1;
    }
  if (mode_creation)
    {
    niveau = 0;
    if (argc > 1)
      {
      if (*argv[1]<'1' || *argv[1]>'8')
        goto help;
      niveau = atoi(argv[1]);
      }
    cree_grille(niveau);
    affiche_grille();
    stat_grille(0);
    affiche_grille_log();
    affiche_grille_html();
    return 0;
    }
  if (fic)
    ;
  else if (argc > 1)
    {
    if (*argv[1]<='0' || *argv[1]>'9')
      goto help;
    niveau = atoi(argv[1]);
    }
  else
    {
    char s[10];
    printf("Saisie manuelle=0, ou bien automatique:\nfacile=1, "
        "moyen=2, dur=3, vilain=4, inconnu=5 : ");
    fflush(stdout);
    gets(s);
    niveau = atoi(s);
    }
  if (niveau < 0 || niveau > 5)
    goto help;
  if (niveau && argc > 2)
    num_grille = atoi(argv[2]);
  else if (niveau)
    {
    char s[10];
    printf("Numero de grille (1 a ...) : ");
    fflush(stdout);
    gets(s);
    num_grille = atoi(s);
    }
  if (niveau && num_grille <= 0)
    goto help;
  reset_grille();       /* utile seulement si boucle */
  if (fic)
    saisit_grille_fichier(fic);
  else if (niveau == INCONNU)
    saisit_grille_manu();
  else
    {
    if (niveau == 5)
      niveau = INCONNU;
    init_grille_auto(num_grille);
    }
  if (! verifie_grille())
    return 1;
  if (cherche_solution)
    resout_grille();
  affiche_grille();
  affiche_grille_html();
  return 0;
  }


/* resout la grille de Su-do_ku */
bool resout_grille(void)
  {
  unsigned long n_tour;
  bool change, change2, impossible, ok;

  niveau_hypot = 0;
  n_gomme = n_passe = n_tour = 0;
  persist_suivants = FALSE;
  if (verbose)
    {
    affiche_grille();
    pause();
    }
  do {
    n_tour++;
    if (verbose)
      printf("---- tour %lu -----\n", n_tour);
    change = elimination(&impossible);
    if (verbose && !change)
      puts("Aucune.");
    if (resolu())
      break;
    if (verbose)
      {
      affiche_grille();
      pause();
      }
    if (! impossible)
      {
      change |= (change2 = necessite());
      if (verbose && !change2)
        puts("Aucune.");
      if (resolu())
        break;
      if (verbose)
        {
        affiche_grille();
        pause();
        }
      }
    if (impossible || ! change)
      {
      if (!impossible && niveau_hypot == niveau_hypot_max)
        {
        /* on force a rester au meme niveau et essayer d'autres hypotheses */
        if (verbose || !muet && !persist_suivants)
          printf("Se refuse a poser hypothese %d. Reste au niveau %d.\n",
                niveau_hypot+1, niveau_hypot);
        impossible = persist_suivants = TRUE;
        }
      if (! make_hypothese(impossible))
        break;
      }
    } while (n_tour < n_tour_max);
  ok = resolu();
  if (! muet)
    {
    stat_grille(niveau_hypot);
    printf("%sesolu en %lu tour%s (%lu passe%s)\n",
        ok ? "R" : "Non r",
        n_tour, PLUR(n_tour),
	n_passe, PLUR(n_passe));
    }
  if (! muet && niveau_hypot)
    printf("Hypothese%s: %d, total %lu  (%lu fois la gomme)\n",
	PLUR(niveau_hypot), niveau_hypot,
	n_gomme + niveau_hypot, n_gomme);
  assert(verifie_grille());  /* temporaire (garde-fou programmeur) */
  return ok;
  }


/* calcule les valeurs de la grille par deduction (case par case) */
bool elimination(bool *impossible)
  {
  /*
  Phase 1:
  Par elimination, on determine les valeurs possibles d'une case en ecartant
  les valeurs rencontrees sur sa ligne, colonne, et region.
  Si une case n'a plus qu'une seule valeur possible, on la fixe.
  On parcourt toutes les cases vides.
  */
  short i,j,k;
  bool change, change0=FALSE;
  unsigned char val_finale;

  *impossible = FALSE;
  if (verbose)
    puts("Cases a unique possibilite...");
  do {
    change=FALSE;  /* aucune modification de la grille au cours de ce tour ? */
    n_passe++;
    /* pour chaque case vide, regarde le nb de possibilites */
    for (i=0; i<9; i++)
      for (j=0; j<9; j++)
        {
        if (tab[i][j].val)
          continue;
        /* evalue les possibilites de cette case vide */
        calcule_possibilites_case(i,j);
        /* bilan case: si 1 valeur possible, on la fixe; si 0, impossible */
        val_finale = 0;
        for (k=0; k<9; k++)     /* pour chaque valeur possible -1 */
          if (tab[i][j].possible[k])
            if (val_finale)
              break;
            else
              val_finale = k+1;
        if (! val_finale)
          {
          if (! muet)
            printf("Aucune valeur possible pour la case (%d,%d)\n", i+1,j+1);
          *impossible = TRUE;
          return change0;
          }
        if (k==9)  /* 1 seule valeur possible */
          {
          if (verbose)
            printf("Case (%d,%d): %d\n", i+1,j+1, val_finale);
          tab[i][j].val = val_finale;
          tab[i][j].hypot = niveau_hypot;
          change = change0 = TRUE;
          }
        }
    } while (change);
  return change0;
  }


/* calcule les valeurs de la grille par deduction (valeur possible) */
bool necessite(void)
  {
  /*
  Phase 2:
  Une case vide peut avoir plusieurs valeurs possibles.
  Si une de ces valeurs est unique par rapport aux possibilites des autres
  cases vides de la ligne, colonne ou region, on fixe la case a cette valeur.
  On parcourt chaque ligne, colonne, region.
  */
  struct
    {
    unsigned char ij[2];        /* coordonnees de la 1ere case candidate */
    short n_case;               /* nb de cases */
    } poss[9];  /* par valeur possible (-1), reperage des cases */
  short i,j,k,ic,jc,ic0,jc0,m;
  bool change, change0=FALSE;

  if (verbose)
    puts("Seule opportunite pour telle valeur...");
  do {
    change=FALSE;  /* aucune modification de la grille au cours de ce tour ? */
    n_passe++;
    /* chaque ligne */
    for (i=0; i<9; i++)
      {
      memset(poss, 0, sizeof(poss));
      for (j=0; j<9; j++)
        {
        if (tab[i][j].val)
          continue;
        for (k=0; k<9; k++)       /* cherche valeurs possibles de la case */
          {
          if (! tab[i][j].possible[k])
            continue;
          poss[k].ij[0] = i;
          poss[k].ij[1] = j;
          poss[k].n_case++;
          }
        }
      /* analyse de poss[] */
      for (k=0; k<9; k++)
        if (poss[k].n_case == 1)
          {
          short i0,j0;
          i0 = poss[k].ij[0];
          j0 = poss[k].ij[1];
          if (verbose)
            printf("Case (%d,%d): %d (unique sur ligne %d)\n",
                  i0+1, j0+1, k+1, i+1);
          tab[i0][j0].val = k+1;
          tab[i0][j0].hypot = niveau_hypot;
          change0 = TRUE;
          if (insist2)
            change=TRUE;
          if (nb_possib(i0,j0) > 1)  /* pour distinguer d'une seule possible */
            tab[i0][j0].f.necess = TRUE;
          /* soustraire k+1 des valeurs possibles pour vides de la colonne et region */
          assert(i == i0);
          for (m=0; m<9; m++)
            {
            if (tab[m][j0].val)
              continue;
            tab[m][j0].possible[k] = FALSE;
            }
          ic0=i0/3;
          jc0=j0/3;
          for (ic=3*ic0; ic<3*ic0+3; ic++)
            for (jc=3*jc0; jc<3*jc0+3; jc++)
              {
              if (tab[ic][jc].val)
                continue;
              tab[ic][jc].possible[k] = FALSE;
              }
          }
      }
    /* chaque colonne */
    for (j=0; j<9; j++)
      {
      memset(poss, 0, sizeof(poss));
      for (i=0; i<9; i++)
        {
        if (tab[i][j].val)
          continue;
        for (k=0; k<9; k++)       /* cherche valeurs possibles de la case */
          {
          if (! tab[i][j].possible[k])
            continue;
          poss[k].ij[0] = i;
          poss[k].ij[1] = j;
          poss[k].n_case++;
          }
        }
      /* analyse de poss[] */
      for (k=0; k<9; k++)
        if (poss[k].n_case == 1)
          {
          short i0,j0;
          i0 = poss[k].ij[0];
          j0 = poss[k].ij[1];
          if (verbose)
            printf("Case (%d,%d): %d (unique sur colonne %d)\n",
                  i0+1, j0+1, k+1, j+1);
          tab[i0][j0].val = k+1;
          tab[i0][j0].hypot = niveau_hypot;
          change0 = TRUE;
          if (insist2)
            change=TRUE;
          if (nb_possib(i0,j0) > 1)   /* pour distinguer d'une seule possible */
            tab[i0][j0].f.necess = TRUE;
          /* soustraire k+1 des valeurs possibles pour vides de la ligne et region */
          assert(j == j0);
          for (m=0; m<9; m++)
            {
            if (tab[i0][m].val)
              continue;
            tab[i0][m].possible[k] = FALSE;
            }
          ic0=i0/3;
          jc0=j0/3;
          for (ic=3*ic0; ic<3*ic0+3; ic++)
            for (jc=3*jc0; jc<3*jc0+3; jc++)
              {
              if (tab[ic][jc].val)
                continue;
              tab[ic][jc].possible[k] = FALSE;
              }
          }
      }
    /* chaque region */
    for (ic=0; ic<3; ic++)
      for (jc=0; jc<3; jc++)
        {
        memset(poss, 0, sizeof(poss));
        for (i=3*ic; i<3*ic+3; i++)
          for (j=3*jc; j<3*jc+3; j++)
            {
            if (tab[i][j].val)
              continue;
            for (k=0; k<9; k++)   /* cherche valeurs possibles de la case */
              {
              if (! tab[i][j].possible[k])
                continue;
              poss[k].ij[0] = i;
              poss[k].ij[1] = j;
              poss[k].n_case++;
              }
            }
          /* analyse de poss[] */
          for (k=0; k<9; k++)
            if (poss[k].n_case == 1)
              {
              short i0,j0;
              i0 = poss[k].ij[0];
              j0 = poss[k].ij[1];
              if (verbose)
                printf("Case (%d,%d): %d (unique sur region %d,%d)\n",
                      i0+1, j0+1, k+1, ic+1,jc+1);
              tab[i0][j0].val = k+1;
              tab[i0][j0].hypot = niveau_hypot;
              change0 = TRUE;
              if (insist2)
                change=TRUE;
              if (nb_possib(i0,j0) > 1)
                /* on distingue d'une seule possible */
                tab[i0][j0].f.necess = TRUE;
              /* soustraire k+1 des valeurs possibles pour vides de la ligne et colonne */
              for (m=0; m<9; m++)
                {
                if (tab[m][j0].val)
                  continue;
                tab[m][j0].possible[k] = FALSE;
                }
              for (m=0; m<9; m++)
                {
                if (tab[i0][m].val)
                  continue;
                tab[i0][m].possible[k] = FALSE;
                }
              }
          }
    } while (change);   /* si on insiste, on reprend */
  return change0;
  }


/* saisit la grille depuis un fichier texte */
void saisit_grille_fichier(char *fic)
  {
  FILE *fp;
  char lig[80];
  short i;
  if (! (fp=fopen(fic, "r")))
    {
    perror(fic);
    exit(1);
    }
  i=0;
  while (fgets(lig, sizeof(lig), fp))
    {
    if (! saisit_ligne(lig, tab[i]))
      continue;
    i++;
    if (i == 9)
      break;
    }
  fclose(fp);
  }


/* entre les chiffres de la grille au clavier */
void saisit_grille_manu(void)
  {
  unsigned char s[80];
  short i;

  puts("Saisie de la grille ligne par ligne (espace=case vide).\n"
  "Exemple: \"  18 95 3\"\n");
  for (i=0; i<9; i++)
    {
    printf("Ligne %d: ", i+1);
    fflush(stdout);
    gets(s);
    saisit_ligne(s, tab[i]);
    }
  }


/* saisit les 9 cases d'une ligne depuis une chaine de caracteres */
bool saisit_ligne(char *lig, CASE *t)
  {
  /*
  La ligne peut etre de la forme:
  "  345"
  ou bien:
  | 1 2 3      |
  */
  register char *p;
  register short j;
  bool found=FALSE;
  bool espace=FALSE;

  if (*lig=='#' || strstr(lig, "---"))
    return FALSE;
  espace = (*lig == '|');
  /* cherche 1er chiffre */
  for (p=lig; *p; p++)
    if (*p>='1' && *p<='9')
      {
      found=TRUE;
      break;
      }
  if (! found)
    return TRUE;        /* ligne vide (9 blancs) */
  /* vers l'arriere tant que blanc (cherche debut) */
  for (;;)
    {
    if (p==lig)
      break;
    p--;
    if (*p != ' ')
      {
      p++;
      break;
      }
    }
  /* memorise la ligne */
  for (j=0; (*p==' ' || *p>='1' && *p<='9') && j<9; p++, j++)
    {
    if (espace)
      {
      if (*p != ' ')
        return FALSE;
      p++;
      if (! (*p==' ' || *p>='1' && *p<='9'))
        return FALSE;
      }
    if (*p != ' ')
      {
      t[j].val = *p - '0';
      t[j].f.init = TRUE;
      }
    }
  return TRUE;
  }


/* choisit une grille predefinie selon le niveau */
void init_grille_auto(short num_grille)
  {
  short i,j;

  unsigned char *s[5][MAX_GRILLE_NIVEAU]=
    {
    {
/* inconnu */
    "5 9  1 42"         /* facile */
    "42 5 8 7 "
    "   9    1"
    "65 3 719 "
    "         "
    " 428 5 67"
    "7    9   "
    " 8 1 4 23"
    "26 7  9 8",

    " 6 1 4 5 "         /* moyen */
    "  83 56  "
    "2       1"
    "8  4 7  6"
    "  6   3  "
    "7  9 1  4"
    "5       2"
    "  72 69  "
    " 4 5 8 7 ",

    "5   93 76"         /* impossible */
    "1  54 3  "
    " 29  64  "
    "7 3    4 "
    "29  8  57"
    " 6    2 1"
    "  78  91 "
    "  2 54  8"
    "48 96   2",  /* 3 en derniere case */

    "1        "
    "         "
    "         "
    "         "
    "         "
    "         "
    "         "
    "         "
    "         ",

    "        3" /* 19 tours */
    " 2 53  7 "
    " 6 1 8   "
    "7    54  "
    " 8 2 3 6 "
    "  56     "
    "   3 4 2 "
    " 7  6  3 "
    "8        ",

    },{
/* facile */
    "   3 4 8 "
    "3  82  14"
    "18  5 63 "
    " 5 6   9 "
    " 9  8  6 "
    " 4   9 2 "
    " 67 3  59"
    "91  62  3"
    " 3 5 8   ",

    " 59 3128 "
    "   9 8  3"
    "1  2   7 "
    "   514   "
    "5       8"
    "   782   "
    " 1   3  7"
    "9  1 6   "
    " 3685 91 ",

    " 69   1 2"
    "1    6  8"
    " 5 8   4 "
    " 8 19367 "
    "  6 4 8  "
    " 73268 1 "
    " 4   9 8 "
    "3  5    1"
    "5 1   39 ",

    "76   15  "
    "  4 29 3 "
    "2  5 79 4"
    "4 765  8 "
    "         "
    " 2  936 7"
    "8 59 4  2"
    " 7 28 4  "
    "  23   79",

    "  3 75 9 "
    " 752  43 "
    " 4    67 "
    "  7 1   3"
    " 3  5  4 "
    "6   2 5  "
    " 29    8 "
    " 84  235 "
    " 1 83 9  "
    },{
/* medium */
    "4 3      "
    "  8 6   5"
    "5 9 7 4 8"
    "1 5  9   "
    "8  4 1  3"
    "   8  1 2"
    "9 2 8 7 6"
    "7   4 8  "
    "      2 1",

    " 6 1 4 5 "
    "  83 56  "
    "2       1"
    "8  4 7  6"
    "  6   3  "
    "7  9 1  4"
    "5       2"
    "  72 69  "
    " 4 5 8 7 ",

    "  532   6"
    "  3 4   7"
    "      83 "
    " 21     4"
    "  41923  "
    "7     62 "
    " 48      "
    "1   7 4  "
    "2   631  ",

    "    6   5"
    "2     73 "
    "5   43 12"
    "      5 7"
    "3 2 1 6 8"
    "4 7      "
    "73 15   9"
    " 16     3"
    "8   3    ",

    "  4 27   "
    " 7      2"
    "  3 4  17"
    " 1 78  9 "
    "  69512  "
    " 9  34 5 "
    "25  9 7  "
    "9      4 "
    "   87 9  "
    },{
/* hard */
    "   5  2  "
    "    2  3 "
    "  19   74"
    "    4 1 2"
    "4 7 1 6 9"
    "1 2 5    "
    "26   34  "
    " 4  7    "
    "  8  5   ",

    "  8 57   "
    "  96 3   "
    "7  1    5"
    "  19  4  "
    "8   4   2"
    "  5  16  "
    "6    2  9"
    "   4 98  "
    "   87 1  ",

    "395 6  1 "
    " 7   3   "
    "     76 3"
    "      57 "
    "  2 9 3  "
    " 81      "
    "8 76     "
    "   8   2 "
    " 1  3 489",

    "        3"
    " 2 53  7 "
    " 671 8   "
    "7    54  "
    " 8 2 3 6 "
    "  56    7"
    "   3 492 "
    " 1  52 8 "
    "9        ",

    "    7   9"
    "6841   73"
    "     8 5 "
    " 5    69 "
    "    1    "
    " 27    1 "
    " 7 2     "
    "21   9546"
    "8   4    "
    },{
/* evil */
    "    18 95"
    " 48 2 7  "
    "         "
    "8      17"
    "  6 3 8  "
    "25      3"
    "         "
    "  3 8 67 "
    "56 27    ",

    " 1   32  "
    "   7  3  "
    "9  2    7"
    "  1  69  "
    "3   1   4"
    "  98  7  "
    "8    7  5"
    "  3  5   "
    "  29   6 ",

    "68   7   "
    "    6  47"
    "   4 91  "
    "  67   8 "
    " 4     2 "
    " 9   47  "
    "  35 1   "
    "51  2    "
    "   3   91",        /* soluble sans hyp. si (7,8)=7 */

    "2       7"
    "   14  8 "
    "7 1 8    "
    "    56 18"
    "  4   6  "
    "65 91    "
    "    9 2 6"
    " 7  23  1"
    "5       3",

    "  6 1  7 "
    "   27  1 "
    "2  4   9 "
    " 24      "
    "7 9   2 8"
    "      54 "
    " 3   1  6"
    " 6  37   "
    " 1  5 9  ",         /* soluble sans hyp. si (4,1)=6 */

    "7 8   3  "
    "   2 1   "
    "5        "
    " 4     26"
    "3   8    "
    "   1   9 "
    " 9 6    4"
    "    7 5  "
    "         "		/* 431 tours, peut etre resolu en 5 hypotheses */
    }
    };
  unsigned char n;
  short len;

  if (niveau < INCONNU || niveau > EVIL)
    {
    printf("Niveau errone (%d)\n", niveau);
    exit(1);
    }
  if (num_grille < 1 || num_grille > MAX_GRILLE_NIVEAU)
    {
err_gri:
    printf("Numero trop grand (%d) pour ce niveau\n", num_grille);
    exit(1);
    }
  if (! s[niveau][num_grille-1])
    goto err_gri;
  len = strlen(s[niveau][num_grille-1]);
  if (len == 0)
    goto err_gri;
  if (len != 81)
    {
    printf("Erreur taille, doit etre 9x9 (%d)\n", len);
    exit(1);
    }
  for (i=0; i<9; i++)
    for (j=0; j<9; j++)
      {
      n = s[niveau][num_grille-1][i*9+j];
      if (n != ' ')
        {
        tab[i][j].val = n-'0';
        tab[i][j].f.init = TRUE;
        }
      }
  }


/* affiche la grille sur "stdout" */
void affiche_grille(void)
  {
  _affiche_grille(stdout, with_colors);
  }


/* ecrit la grille dans un fichier texte */
void affiche_grille_log(void)
  {
  char *fic_log = "sudoku.log";
  FILE *fp;

  if (fp=fopen(fic_log, "w"))
    {
    _affiche_grille(fp, FALSE);
    fclose(fp);
    fprintf(stderr, "Grille sauvee dans %s\n", fic_log);
    }
  }


/* affiche la grille sur "out" */
void _affiche_grille(FILE *out, bool with_colors)
  {
  register short i,j;
  fputs("|------------------|\n", out);
  for (i=0; i<9; i++)
    {
    putc('|', out);
    for (j=0; j<9; j++)
      {
      if (with_colors)
        {
        if (tab[i][j].f.prem_hyp)
          fputs("\033[1m", out);    /* vif */
        if (tab[i][j].hypot)
          fputs("\033[33m", out);       /* jaune */
        else if (tab[i][j].f.necess)
          fputs("\033[35m", out);   /* magenta */
        else if (! tab[i][j].f.init)
          fputs("\033[36m", out);   /* cyan (valeur calculee) */
        /* sinon blanc (valeur initiale) */
        }
      fprintf(out, " %c", tab[i][j].val ? tab[i][j].val+'0' : ' ');
      if (with_colors)
        fputs("\033[0m", out);      /* blanc */
      }
    fputs("|\n", out);
    }
  fputs("|------------------|\n", out);
  }


/* ecrit la grille dans un fichier HTML */
void affiche_grille_html(void)
  {
  short i,j;
  char s[]="&nbsp;";
  char style;
  char *fic_htm="sudoku.htm";
  FILE *out;

  if (! (out=fopen(fic_htm, "w")))
    return;
  fputs(
    "<HTML>\n"
    "<HEAD>\n"
    "<TITLE>Sudoku</TITLE>\n"
    "<STYLE>\n"
    ".a,.b,.c,.d {width:32pt; height:33pt;\n"
    "  vertical-align:middle; text-align:center;\n"
    "  font-size:18pt; font-family:times,serif;}\n"
    ".t {border-collapse:collapse; border: black solid 2px;}\n"
    ".a,.b,.c,.d {border: black solid 1px;}\n"
    ".b,.d {border-left: black solid 2px;}\n"
    ".c,.d {border-top: black solid 2px;}\n"
    "#neces {color: magenta}\n"
    "#calc {color: blue}\n"
    "#hyp1 {color: orange}\n"
    "#hyp {color: brown}\n"
    "#neces,#calc,#hyp1,#hyp {font-style: italic}\n"
    "</STYLE>\n"
    "</HEAD>\n\n"
    "<BODY onLoad=\"print()\">\n\n", out);
  fprintf(out,
    "<TABLE WIDTH=100%% HEIGHT=100%%>\n"
    "<TR><TD ALIGN=center VALIGN=middle WIDTH=*>\n"
    "<H4>Niveau: %s</H4><BR>\n"
    "<TABLE CELLSPACING=0 CLASS=t>\n",
        sniveau(niveau_theorique(nb_fixe(), niveau_hypot)));

  for (i=0; i<9; i++)
    {
    fputs("<TR>\n", out);
    style = (i == 3 || i == 6 ? 'c' : 'a');
    for (j=0; j<9; j++)
      {
      strcpy(s, "&nbsp;");
      if (tab[i][j].val)
        sprintf(s, "%d", tab[i][j].val);
      fprintf(out, "<TD CLASS=%c", style + (j==3 || j==6 ? 1 : 0));
      if (tab[i][j].f.prem_hyp)
        fputs(" ID=hyp1", out);
      else if (tab[i][j].hypot)
        fputs(" ID=hyp", out);
      else if (tab[i][j].f.necess)
        fputs(" ID=neces", out);
      else if (! tab[i][j].f.init)
        fputs(" ID=calc", out);         /* valeur calculee */
      /* sinon blanc (valeur initiale) */
      fprintf(out, ">%s</TD>\n", s);
      }
    fputs("</TR>\n", out);
    }
  fputs(
    "</TABLE>\n"
    "</TD></TR>\n"
    "</TABLE>\n\n"
    "</BODY>\n"
    "</HTML>\n", out);
  fclose(out);
  if (! muet)
    fprintf(stderr, "Grille sauvee dans %s\n", fic_htm);
  }


/* verifie l'unicite des chiffres dans chaque ligne, colonne et region */
bool verifie_grille(void)
  {
  short i,j,ic,jc;
  bool pris[9];
  unsigned short n;
  for (i=0; i<9; i++)
    {
    memset(pris, 0, sizeof(pris));
    for (j=0; j<9; j++)
      if (n=tab[i][j].val)
        if (pris[n-1])
          {
          printf("Le chiffre %d est en double dans la ligne %d\n", n, i+1);
          return FALSE;
          }
        else
          pris[n-1] = TRUE;
    }
  for (j=0; j<9; j++)
    {
    memset(pris, 0, sizeof(pris));
    for (i=0; i<9; i++)
      if (n=tab[i][j].val)
        if (pris[n-1])
          {
          printf("Le chiffre %d est en double dans la colonne %d\n", n, j+1);
          return FALSE;
          }
        else
          pris[n-1] = TRUE;
    }
  for (ic=0; ic<3; ic++)
    for (jc=0; jc<3; jc++)
      {
      memset(pris, 0, sizeof(pris));
      for (i=3*ic; i<3*ic+3; i++)
       for (j=3*jc; j<3*jc+3; j++)
         if (n=tab[i][j].val)
           if (pris[n-1])
             {
             printf("Le chiffre %d est en double dans la region (%d,%d)\n",
                        n, ic+1,jc+1);
             return FALSE;
             }
           else
             pris[n-1] = TRUE;
      }
  return TRUE;
  }


/* fixe a priori la valeur d'une case */
bool make_hypothese(bool annuler_precedent)
  {
  /* tableau indexe par niveau_hypot-1 decrivant ou on en est (i,j, val, nb_poss_max) */
  static unsigned char tab_hypot[MAX_HYPOT][4];

  short num_poss;
  register short i,j,k;

#if(0)
  puts("Tableau des hypotheses:");
  for (i=0; i<niveau_hypot; i++)
    printf("- case (%d,%d): %d (%d possib.)\n",
	tab_hypot[i][0]+1, tab_hypot[i][1]+1, tab_hypot[i][2], tab_hypot[i][3]);
#endif
  /*
  Strategie pour le choix d'une case candidate :
  on prendra de preference une case ne pouvant avoir que nb_poss_max valeurs
  possibles (typiquement: 2).
  On n'augmente le niveau d'hypothese que lorsque le pb est indetermine.
  Si on a epuise les valeurs d'une case (et que le pb est impossible),
  on annule l'hypothese precedente.
  */
  if (annuler_precedent)
    {
    /* efface les cases calculees avec l'hypothese et decremente le niveau */
    if (! decroit_hypothese())
      {
      if (! muet)
        puts("Retour arriere impossible...");
      return FALSE;
      }
    /* recalcule les possibilites de chaque case vide */
    calcule_possibilites_cases();
    }
  /*
  Si "annuler_precedent", niveau_hypot retrouvera sa valeur.
  Sinon, on construit une nouvelle hypothese.

  De plus:
  la case candidate sera une de celles qui ont un nombre faible de valeurs
  possibles pour minimiser le nb d'hypotheses infructueuses.
  On se fixe pour limite le plus petit nb de valeurs possibles rencontre.
  */
  else  /* on echafaude une hypothese supplementaire */
    {
    short n_candidates, nb_vides;

    /* on fait place nette pour la nouvelle hypothese */
    memset(tab_hypot[niveau_hypot], 0, sizeof(tab_hypot[0]));
    tab_hypot[niveau_hypot][3] = min_nb_valeurs_possibles();  /* nb_poss_max */
    assert(tab_hypot[niveau_hypot][3] > 1);    /* la case aurait deja ete resolue */

    if (verbose)
      {
      /* affiche statistiques sur le nb de cases vides et candidates */
      nb_cases_multiposs(tab_hypot[niveau_hypot][3], &nb_vides, &n_candidates);
      printf("%d case%s sur %d vide%s ont %d valeurs possibles\n",
                n_candidates, PLUR(n_candidates),
                nb_vides, PLUR(nb_vides),
                tab_hypot[niveau_hypot][3]);
#if(1)
      for (i=0; i<9; i++)
        for (j=0; j<9; j++)
          {
          if (tab[i][j].val || nb_possib(i,j) > tab_hypot[niveau_hypot][3])
            continue;
          printf("  - case (%d,%d): valeurs possibles: \"%s\"\n",
                    i+1,j+1, get_possibles(i,j));
          }
#endif
      }
    /*
    En fait, entre 2 et nb_poss_max (mais, par construction de nb_poss_max,
    il n'y a pas moins de nb_poss_max valeurs possibles.
    */
    }

  /* chercher case suivante candidate pour l'hypothese */
  for (i=0; i<9; i++)
    for (j=0; j<9; j++)
      {
      if (tab[i][j].val)
        continue;
      if (nb_possib(i,j) > tab_hypot[niveau_hypot][3])
        continue;
      if (i<tab_hypot[niveau_hypot][0] ||
          i==tab_hypot[niveau_hypot][0] && j<tab_hypot[niveau_hypot][1])
        continue;
      /* case i,j candidate */
      num_poss = 0;
      for (k=0; k<9; k++)
        if (tab[i][j].possible[k])
          {
          /* case deja choisie precedemment, mais valeur suivante d'hypothese */
          if (i==tab_hypot[niveau_hypot][0]
            && j==tab_hypot[niveau_hypot][1]
            && k+1 <= tab_hypot[niveau_hypot][2])
            {
            num_poss++;
            continue;   /* next k,i,j */
            }
          if (! muet)
            printf("Hypothese %d: Case (%d,%d): %d  "
                        "(%d%s valeur possible de \"%s\")\n",
                    niveau_hypot+1, i+1,j+1, k+1, num_poss+1,
                    num_poss ? "eme" : "ere", get_possibles(i,j));
          pause();
          /* memorise pour la fois d'apres */
          tab_hypot[niveau_hypot][0] = i;
          tab_hypot[niveau_hypot][1] = j;
          tab_hypot[niveau_hypot][2] = tab[i][j].val = k+1;
          tab[i][j].hypot = niveau_hypot+1;
          /* pour distinguer source hypothese de cases calculees apres */
          tab[i][j].f.prem_hyp = TRUE;
          niveau_hypot++;       /* augmente le niveau d'hypothese */
          return TRUE;
          }
      /*
      C'est ici qu'on n'insiste pas:
      si on a atteint la derniere valeur de la case, ce n'est pas la peine
      de poser la case suivante. On vient de prouver que l'hypothese precedente
      est fausse.

      ... sauf dans le cas ou on se limite a un niveau d'hypothese maximum:
      il faut continuer a chercher dans les cases suivantes (meme lors des
      hypotheses anterieures), car on n'est pas sur que le pb soit impossible
      puisqu'on n'etait pas alle jusqu'au bout.
      */
      if (k == 9 && ! persist_suivants)
        i=j=9;  /* break 2x */
      }
  /* si on arrive ici, on a epuise toutes les hypotheses */
  if (verbose)
    puts("Ne peut plus rien supposer...");
  /* on doit annuler l'hypothese precedente */
  return make_hypothese(TRUE);
  }


/* efface toutes les valeurs calculees sur une hypothese et diminue le niveau */
bool decroit_hypothese(void)
  {
  register i,j;
  if (! niveau_hypot)
    return FALSE;
  /* efface les cases calculees avec cette hypothese */
  if (verbose)
    puts("On revient en arriere...");
  for (i=0; i<9; i++)
    for (j=0; j<9; j++)
      if (tab[i][j].val && tab[i][j].hypot == niveau_hypot)
        {
        tab[i][j].val = 0;
        tab[i][j].f.prem_hyp = FALSE;
        }
  n_gomme++;
  niveau_hypot--;       /* decroit hypothese */
  return TRUE;
  }


/* calcule les possibilites de la case i,j */
void calcule_possibilites_case(short i, short j)
  {
  short k,ic,jc,ic0,jc0;

  /* a priori, toutes les valeurs sont possibles */
  for (k=0; k<9; k++)
    tab[i][j].possible[k] = TRUE;
  /* lignes */
  for (k=0; k<9; k++)
  if (tab[i][k].val)
    tab[i][j].possible[tab[i][k].val-1] = FALSE;
  /* colonnes */
  for (k=0; k<9; k++)
    if (tab[k][j].val)
      tab[i][j].possible[tab[k][j].val-1] = FALSE;
  /* regions */
  ic0=(i/3)*3;
  jc0=(j/3)*3;
  for (ic=ic0; ic<ic0+3; ic++)
    for (jc=jc0; jc<jc0+3; jc++)
      if (tab[ic][jc].val)
        tab[i][j].possible[tab[ic][jc].val-1] = FALSE;
  }


/* calcule les possibilites des cases */
void calcule_possibilites_cases(void)
  {
  register short i,j;
  for (i=0; i<9; i++) /* pour chaque case */
    for (j=0; j<9; j++)
      {
      if (tab[i][j].val)
        continue;
      calcule_possibilites_case(i,j);
      }
  }


/* calcule le nb de cases ayant plusieurs possibilites */
void nb_cases_multiposs(short nb_poss_max, short *nb_vides, short *n_candidates)
  {
  register short i,j;
  short n_poss;

  *n_candidates = *nb_vides =0;
  for (i=0; i<9; i++)
    for (j=0; j<9; j++)
      {
      if (tab[i][j].val)
        continue;
      (*nb_vides)++;
      n_poss = nb_possib(i,j);
      assert(n_poss > 1);   /* serait deja resolu plus tot */
      if (n_poss > nb_poss_max)
        continue;
      (*n_candidates)++;
      }
  }


/* renvoie le plus petit nb de valeurs possibles des cases vides */
unsigned short min_nb_valeurs_possibles(void)
  {
  register short i,j;
  unsigned short n_min=9, n;

  for (i=0; i<9; i++)
    for (j=0; j<9; j++)
      {
      if (tab[i][j].val)
        continue;
      n = nb_possib(i,j);
      if (n < n_min)
        n_min = n;
      }
  return n_min;
  }


/* retourne le nombre de valeurs donnees initialement dans la grille */
unsigned short nb_fixe(void)
  {
  register short i,j;
  unsigned short n=0;
  for (i=0; i<9; i++)
    for (j=0; j<9; j++)
      if (tab[i][j].f.init)
        n++;
  return n;
  }


/* retourne les valeurs possibles de la case (i,j) */
char *get_possibles(short i, short j)
  {
  static char poss[10];
  register short k;
  register char *p;
  for (k=0, p=poss; k<9; k++)
    if (tab[i][j].possible[k])
      *p++ = k+'1';
  *p = 0;
  return poss;
  }


/* retourne le nombre de valeurs possibles de la case (i,j) */
unsigned short nb_possib(short i, short j)
  {
  register short k;
  unsigned short n=0;
  for (k=0; k<9; k++)
    if (tab[i][j].possible[k])
      n++;
  return n;
  }


/* remet la grille a 0 avant initialisation */
void reset_grille(void)
  {
  memset(tab, 0, sizeof(tab));
  }


/* la grille est-elle toute resolue ? */
bool resolu(void)
  {
  register short i,j;
  for (i=0; i<9; i++)
    for (j=0; j<9; j++)
      if (! tab[i][j].val)
        return FALSE;
  return TRUE;
  }


/* affiche statistiques sur la grille brute */
void stat_grille(unsigned short niveau_hypot)
  {
  short n_fix;
  typ_niveau niveau_theo;
#if(0)
  register short i,j;
  short bilan[9]={0};

  for (i=0; i<9; i++)
    for (j=0; j<9; j++)
      if (tab[i][j].f.init)
        bilan[tab[i][j].val-1]++;
  for (i=0; i<9; i++)
    printf("valeur %d: %d fois\n", i+1, bilan[i]);
#endif

  n_fix = nb_fixe();
  niveau_theo = niveau_theorique(n_fix, niveau_hypot);
  if (niveau && niveau!=niveau_theo && niveau <= EVIL)
    printf("Niveau choisi: %s\n", sniveau(niveau));
  printf("Niveau%s: %s (%d case%s connue%s",
        niveau==niveau_theo ? "" : " estime",
        sniveau(niveau_theo),
        n_fix, PLUR(n_fix), PLUR(n_fix));
  if (niveau_hypot)
    printf(" + hypot.");
  puts(")");
  }


/* nombre de cases connues en fonction du niveau de difficulte */
short nb_connues_moy(typ_niveau niveau)
  {
  short n[]={81, 35, 30, 0};
  assert(niveau >= EASY && niveau <= HARD);
  return n[niveau];
  }


/* niveau de difficulte theorique de la grille (apres resolution) */
typ_niveau niveau_theorique(short nb_connues, short nb_hyp)
  {
  /*
  Il semble que, sur nos 5 grilles de chaque niveau (nb de cases connues):
  facile: >= 32
  moyen: 29-31
  difficile: 27-28 (et au moins 2 tours)
  diabolique: au moins une hypothese (et <= 27)
  */
  if (nb_hyp)
    return EVIL;
  if (nb_connues >= 32)
    return EASY;
  if (nb_connues >= 29)
    return MEDIUM;
  return HARD;
  }

/* niveau en clair */
char *sniveau(typ_niveau niveau)
  {
  char *s[]={"inconnu", "facile", "moyen", "difficile", "diabolique"};
  if (niveau < 0 || niveau > 4)
    return "?";
  return s[niveau];
  }


/* fait une pause a l'ecran */
void pause(void)
  {
  char s[10];
  if (! with_pause)
    return;
  fprintf(stderr,"Taper Entree...");
  fflush(stderr);
  gets(s);
  }

/* --------------------- creation de grille ----------------------------- */

/* cree une grille de Su-do-ku, soluble sans poser d'hypothese. */
void cree_grille(typ_niveau niveau)
  {
  /*
  1) on cree une grille avec 2x9 chiffres, cases au hasard.
  2) on resout (necessairement on devra poser des hypotheses)
  3) on fixe des valeurs de la solution (au hasard) jusqu'a ce que ce soit
     soluble sans hypothese
  4) on supprime des valeurs tant que c'est toujours soluble
  5) on rajoute des valeurs si on souhaite un niveau plus facile
  */
  int n, n_serie = 2;

  if (! verbose)
    muet = TRUE;
encore:
  n=0;
  do {
    if (verbose)
      printf("Creation %d: grille au hasard (%d series de 9 chiffres)\n",
        n+1, n_serie);
    if (n > 0 && (verbose2 || verbose))
      {
      /* Sans solution... Rare mais ca peut arriver */
#if(0)
      clean_grille();
      affiche_grille();         /* affichons ce phenomene */
#endif
      fprintf(stderr, "Cree grille minimale (%deme fois)\n", n+1);
      }
    cree_grille_hasard(n_serie);
    n++;
    if (verbose)
      puts("Resolution de la grille minimale:");
    } while (! resout_grille());
  while (niveau_hypot)
    {
    fixe_hypot_hasard();
    clean_grille();
    if (! resout_grille())
      {
      /*
      Sans solution... Tres rare, mais ca peut arriver:
      en toute rigueur, il faudrait fixer les hypotheses dans l'ordre et a la
      valeur qu'elles avaient lors de la resolution de la grille minimale.
      Mais ce serait favoriser le debut de la grille.
      */
      if (verbose || verbose2)
        {
#if(0)
        clean_grille();
        affiche_grille();       /* affichons ce phenomene */
#endif
        fprintf(stderr, "Echec creation. Reprend tout...\n");
        }
      goto encore;
      }
    }
  if (verbose)
    puts("Cherche a supprimer des valeurs fixes redondantes");
  epure_grille();
  if (niveau == EVIL)
    /* temporaire: il faudra supprimer 1 valeur manuellement */
    fprintf(stderr, "Erreur: le niveau %s n'est pas programme.\n", sniveau(niveau--));
  if (niveau)
    ajoute_valeurs_grille(niveau);
  }


/* ajoute des valeurs a la grille initiale jusqu'a atteindre le niveau */
void ajoute_valeurs_grille(typ_niveau niveau)
  {
  short nb_connues_souhaite;
  short nb_connues = nb_fixe();
  short i0,j0,i,j,n,ic,jc;
  unsigned long n_tour;         /* pour abandon en cas de boucle sans fin */

  if (niveau > EVIL)
    nb_connues_souhaite = niveau;
  else
    nb_connues_souhaite = nb_connues_moy(niveau);
  resout_grille();
  for (n_tour=0; nb_connues<nb_connues_souhaite && n_tour<n_tour_max; n_tour++)
    {
    /* il faut fixer au hasard une case qui ne soit pas deja fixee */
    hasard(&i0, &j0);
    if (tab[i0][j0].f.init)
      continue;
    tab[i0][j0].f.init = TRUE;
    /* il doit rester > 1 case inconnue dans la ligne, colonne ou region */
    /* colonne */
    n=0;
    for (i=0; i<9; i++)
      if (! tab[i][j0].f.init)
        n++;
    if (n <= 1)
      {
      tab[i0][j0].f.init = FALSE;
      if (verbose || verbose2)          /* tres rare */
        printf("Case (%d,%d) = %d non ajoutee (colonne %d)\n", i0+1, j0+1, 
                tab[i0][j0].val, j0+1);
      continue;
      }
    /* ligne */
    n=0;
    for (j=0; j<9; j++)
      if (! tab[i0][j].f.init)
        n++;
    if (n <= 1)
      {
      tab[i0][j0].f.init = FALSE;
      if (verbose || verbose2)          /* tres rare */
        printf("Case (%d,%d) = %d non ajoutee (ligne %d)\n", i0+1, j0+1, 
                tab[i0][j0].val, i0+1);
      continue;
      }
    /* region */
    n=0;
    ic = 3*(i0/3);
    jc = 3*(j0/3);
    for (i=ic; i<ic+3; i++)
      for (j=jc; j<jc+3; j++)
        if (! tab[i][j].f.init)
          n++;
    if (n <= 1)
      {
      tab[i0][j0].f.init = FALSE;
      if (verbose || verbose2)          /* tres rare */
        printf("Case (%d,%d) = %d non ajoutee (region %d,%d)\n",
                        i0+1, j0+1, tab[i0][j0].val,
                        ic/3+1, jc/3+1);
      continue;
      }
    if (verbose)
      printf("Case (%d,%d) = %d ajoutee\n", i0+1, j0+1, tab[i0][j0].val);
    nb_connues++;
    }
  clean_grille();
  }


/* cree une grille au hasard, ayant n_serie x 9 chiffres */
void cree_grille_hasard(short n_serie)
  {
  int val;
  short i,j,k,n,ic0,ic,jc0,jc;
  bool pris;

  reset_grille();
  for (val=1; val<=9; val++)    /* pour chaque valeur */
    {
    for (n=0; n<n_serie; )      /* n exemplaires */
      {
      hasard(&i, &j);           /* choisit une case au hasard */
      if (tab[i][j].val)
        continue;
      pris = FALSE;
      /* deja pris sur la colonne ? */
      for (k=0; k<9 && !pris; k++)
        if (tab[i][k].val == val)
          pris = TRUE;
      if (pris)
        continue;
      /* deja pris sur la ligne ? */
      for (k=0; k<9 && !pris; k++)
        if (tab[k][j].val == val)
          pris = TRUE;
      if (pris)
        continue;
      /* deja pris dans la region ? */
      ic0 = (i/3) * 3;
      jc0 = (j/3) * 3;
      for (ic=ic0; ic<ic0+3 && !pris; ic++)
        for (jc=jc0; jc<jc0+3 && !pris; jc++)
          if (tab[ic][jc].val == val)
            pris = TRUE;
      if (pris)
        continue;
      tab[i][j].f.init = TRUE;
      tab[i][j].val = val;
      n++;
      }
    }
  }


/* fixe une case au hasard a sa valeur calculee avec hypothese */
void fixe_hypot_hasard(void)
  {
  register short i,j;
  short n_cases_hyp, k;

  /* nb de cases calculees avec hypothese */
  n_cases_hyp = 0;
  for (i=0; i<9; i++)
    for (j=0; j<9; j++)
      if (tab[i][j].hypot)
        n_cases_hyp++;
  /* on fixe au hasard la k.ieme case (a sa valeur) */
  k = random(n_cases_hyp);
  n_cases_hyp = 0;
  for (i=0; i<9; i++)
    for (j=0; j<9; j++)
      if (tab[i][j].hypot)
        {
        if (n_cases_hyp == k)
          {
          tab[i][j].f.init = TRUE;
          if (verbose)
            printf("Fixe case (%d,%d) a sa valeur (%d)...\n",
                        i+1, j+1, tab[i][j].val);
          return;
          }
        n_cases_hyp++;
        }
  assert(0);
  }


/* regarde si on peut supprimer des valeurs et que la grille reste soluble */
void epure_grille(void)
  {
  short n_supp = 0;
  _epure_grille(&n_supp);       /* 1 fois suffit */
  if (! muet)
    fprintf(stderr, "%d valeur%s supprimee%s\n",
                n_supp, PLUR(n_supp), PLUR(n_supp));
  }


/* regarde si on peut supprimer des valeurs et que la grille reste soluble */
bool _epure_grille(short *n_supp)
  {
  short i,j,k, val;
  bool ok;
  typedef struct
    {
    bool pris;
    short i,j;
    } FIXE;
  FIXE fixe[81]={0}, fixe_melange[81];
  short n_fixe=0;
  CASE *c;
  bool change = FALSE;

  clean_grille();
  /*
  Le plus simple serait de supprimer les valeurs dans l'ordre du tableau,
  mais ce serait privilegier le debut du tableau.
  Non, il nous faut faire une liste en desordre des valeurs fixes.
  */
  for (i=0; i<9; i++)
    for (j=0; j<9; j++)
      if (tab[i][j].val)
        {
        fixe[n_fixe].i = i;
        fixe[n_fixe].j = j;
        n_fixe++;
        }
  /* melange de la liste */
  for (i=0; i<n_fixe; )
    {
    k = random(n_fixe);
    if (fixe[k].pris)
      continue;
    fixe_melange[i++] = fixe[k];
    fixe[k].pris = TRUE;
    }

  for (k=0; k<n_fixe; k++)
    {
    c = &tab[fixe_melange[k].i][fixe_melange[k].j];
    val = c->val;
    c->val = 0;
    c->f.init = FALSE;
    if (verbose)
      printf("Resolution avec case (%d,%d) supprimee\n",
                fixe_melange[k].i+1, fixe_melange[k].j+1);
    ok = resout_grille();
    clean_grille();
    if (ok && niveau_hypot==0)
      {
      if (verbose)
        printf("Suppression case (%d,%d) definitive\n",
                fixe_melange[k].i+1, fixe_melange[k].j+1);
      (*n_supp)++;
      change = TRUE;
      }
    else        /* echec, on restaure la valeur */
      {
      c->val = val;
      c->f.init = TRUE;
      }
    }
  niveau_hypot = 0;
  return change;
  }


/* remet la grille aux valeurs initiales */
void clean_grille(void)
  {
  register short i,j;
  short sav[9][9] = {0};

  for (i=0; i<9; i++)
    for (j=0; j<9; j++)
      if (tab[i][j].f.init)
        sav[i][j] = tab[i][j].val;
  reset_grille();
  for (i=0; i<9; i++)
    for (j=0; j<9; j++)
      if (sav[i][j])
        {
        tab[i][j].val = sav[i][j];
        tab[i][j].f.init = TRUE;
        }
  }



/* choisit une case au hasard */
void hasard(short *i, short *j)
  {
  *i = random(9);
  *j = random(9);
  }