Le sudoku

struct case_t{
  // 0 si la case est vide, une valeur entre 1 et n sinon
  unsigned valeur;

  // un tableau de n cases ; masque[i] == 1 si et seulement
  // si la valeur (i+1) est acceptable ; 0 sinon
  int *masque;  
};

typedef struct case_t ** grille_t;

struct grille_t{
  unsigned n:
  struct case_t **cases;
};

struct case_t creer_case(unsigned n){
  struct case_t c;
  unsigned i;
  c.valeur = 0;
  c.masque = (int *)malloc(n*sizeof(int));
  for(i=0;i<n;++i) masque[i] = 1;
  return c;
}

void detruire_case(case_t *c){
  free(c.masque);
}

grille_t creer_grille(unsigned n){
  unsigned i,j;
  // une matrice est un tableau de tableau
  grille = (case_t **)malloc(sizeof(case_t *)*n);
  for(i=0;i<n;++i){
    // on alloue la ième ligne de la matrice
    grille[i] = (case_t *)malloc(sizeof(case_t)*n);
    for(j=0;j<n;++j) grille[i][j] = creer_case(n);
  }
}

void detruire_grille(grille_t g){
  unsigned i,j;
  for(i=0;i<n;++i){
    for(j=0;j<n;++j) detruire_case(&grille[i][j]);
    free(grille[i]);
  }
  free(grille);
}

#include <stdlib.h>

void randint(unsigned n){
  return rand()/(int)(((unsigned)RAND_MAX + 1) / n) + 1;
}

#include <cassert.h>
#include <math.h> // compiler le programme avec l'option -lm

// Mettre dans grille[i][j] de dimension n*n la valeur x ; corriger le masque ; retourner 1 si tout va bien 0 sinon
int set_value(grille_t g,unsigned n,unsigned i,unsigned j,unsigned x){
  unsigned k,l,n_sqrt;
  assert(i < n);
  assert(j < n);
  assert(sqrt(n) == (unsigned) sqrt(n));
  n_sqrt = (unsigned) sqrt(n);

  // vérifier si la case n'est pas déjà remplie et si elle accepte la valeur x
  if(!g[i][j].masque[x] || g[i][j].value != 0) return 0;

  // remplir la case
  g[i][j].value =x

  // corriger les masques
  for(k=0;k<n,++k){
    g[i][k].masque[x] = 0; // on ne peut plus affecter x au cases de la ligne i
    g[k][j].masque[x] = 0; // on ne peut plus affecter x au cases de la colonne j
  }

  // la ligne case en haut à gauche du carré
  // contenant la case (i,j);
  i0 = i-(i%sqrt_n);

  // la colonne case en haut à gauche
  // du carré contenant la case (i,j);
  j0 = j-(j%sqrt_n);

  // Exemple : dans un sudoku 9x9 la case (5,3) est représentée par X
  // est dans le carré suivant :
  //
  // 0 . . . | . . . | . . .
  // 1 . . . | . . . | . . .
  // 2 . . . | . . . | . . .
  //   ----------------------
  // 3 . . . | S . . | . . .
  // 4 . . . | . . . | . . .
  // 5 . . . | X . . | . . .
  //   ----------------------
  // 6 . . . | . . . | . . .
  // 7 . . . | . . . | . . .
  // 8 . . . | . . . | . . .
  //   0 1 2   3 4 5   6 7 8

  // ce carré a pour case supérieure gauche la case S,
  // qui est à la position (3,3)
  //
  // en effet (% = opérateur modulo)
  // i0 = 5 - (5%3) = 5 - 2 = 3
  // j0 = 3 - (3%3) = 3 - 0 = 3

  // cette boucle balaye le carré contenant (i,j)
  for(k=0;k<n_sqrt;++k){
    for(l=0;l<n_sqrt;++l){
      // les cases appartenant au même carré
      // que (i,j) n'admettent plus la valeur x
      g[i0+k][j0+l].masque[x] = 0; 
    }
  }
  // la case (i,j) n'admet plus aucune valeur
  for(k=0;k<n;++k) g[i][j].masque[x] = 0;
  return 1;
}

x M M | M M M | M M M
M M M | . . . | . . . 
M M M | . . . | . . . 
----------------------
M . . | . . . | . . .
M . . | . . . | . . .
M . . | . . . | . . .
----------------------
M . . | . . . | . . .
M . . | . . . | . . .
M . . | . . . | . . .