Le sudoku [Résolu/Fermé]

Signaler
Messages postés
5
Date d'inscription
mercredi 21 janvier 2009
Statut
Membre
Dernière intervention
8 mars 2009
-
Messages postés
29895
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
16 juin 2021
-
Bonjour,
je concoit un programme en C qui doit resoudre n'importe quel sudoku j'ai besoin des instuction qui me permettrons
de remplir la grille sans qui est repetition d'un chiffre dans une zone ,colonne et ligne

7 réponses

Messages postés
29895
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
16 juin 2021
7 122
Non tu ne peux pas remplir au hasard car il faut que la grille soit cohérente. En fait il faut que tu balayes ta grille et que tu la remplisse au fur et à mesure. Tu peux effectivement utiliser une fonction aléatoire pour cela, mais il faut veiller à garantir la cohérence de la grille en maintenant pour chaque case l'ensemble des valeurs admissibles (domaine).

La méthode que je vais t'indiquer n'est pas optimisée en terme de qualité de code, c'est juste une manière de faire à peu près simple à présenter. Ensuite libre à toi d'optimiser le code. Je ne teste pas le code le but est juste de te donner un squelette.

Pour chaque case il faut maintenir le chiffre affecté ou les chiffres que tu peux y insérer. Pour cela le plus simple c'est d'utiliser une matrice de struct, ou chaque struct encapsule la valeur insérée (0 si pas de valeur) et un masque indiquant quelles valeurs sont encore acceptables. Si tu débutes en C on ne va pas s'embêter avec un masque, tu peux utiliser directement un tableau de booléens ou la ième case indique si le chiffre i est valide (case à 1) ou non (case à 0). Attention je te rappelle que les tableaux sont numérotés à partir de l'index 0 en C.

La structure d'une case ressemble donc à :
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;  
};

Note qu'on aurait pu utiliser un tableau statique (un int masque[9]) mais le code ne serait alors valable que pour des grilles dont les valeurs vont de 1 à 9. Ainsi l'initialisation des cases et la gestion de la mémoire aurait été simplifiée mais le code moins générique. Or un sudoku se généralise très facilement à des grilles n x n. Dans ton cas imagine que n = 9.

Ensuite définissons un tableau n x n de struct case_t afin de construire ton plateau.
typedef struct case_t ** grille_t;

On pourrait aussi utiliser une structure qui stocke la valeur de n ce qui serait mieux comme par exemple :
struct grille_t{
  unsigned n:
  struct case_t **cases;
};
mais ce serait un peu plus lourd à écrire. Ceci dit c'est plus propre.

Il faut à présent l'initialiser. Chaque champ valeur vaut 0 à ce stade, et chaque masque est un tableau rempli de 1. Pour cela le plus simple est sans doute de créer une fonction qui alloue une case correctement initialisée et une fonction qui créer la grille. On va en profiter pour faire les petites soeurs qui désalloueront la mémoire quand on quittera le programme :
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);
}

Afin de mettre un peu de hasard on va utiliser une fonction aléatoire pour tirer des valeurs entre 1 et n
https://www.thinkage.ca/gcos/expl/c/lib/rand.html
#include <stdlib.h>

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

À présent passons à l'algorithme proprement dit. le but du jeu c'est que quand tu affectes une valeur x à une case, tu bascule masque[x] de chaque case appartenant à la même ligne/colonne/carré à 0. Ainsi on saura que ces cases ne peuvent se voir attribuer la valeur x.
#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;
}

Ok donc si je ne me suis pas trop craquée, maintenant cette fonction te garantit que si elle retourne 1 tu as inséré avec succès un nombre x dans la case (i,j), et que sinon tu ne pouvais pas le faire sans remettre en cohérence de la grille. A présent il reste presque le plus facile. On place un nombre aléatoire dans une case x (et autorisé par le masque de la case) dans la première case (ligne i=0 et colonne j=0). L'appel à set_value s'occupe de corriger le domaine des cases notées M dans ce schéma :
x M M | M M M | M M M
M M M | . . . | . . . 
M M M | . . . | . . . 
----------------------
M . . | . . . | . . .
M . . | . . . | . . .
M . . | . . . | . . .
----------------------
M . . | . . . | . . .
M . . | . . . | . . .
M . . | . . . | . . .

Puis on passe à la case de droite (0,1) dont le domaine est désormais {0... 9} \ {x}. Comme le domaine est désormais de taille n-1, il suffit de tirer une valeur k entre 1 et n-1 et de prendre la kème valeur du domaine. Si par exemple ton domaine était réduit à {1,2,3,5,6,7,8,9} parce que dans la première case tu as placé la valeur x = 4, et que ta fonction aléatoire te retourne la valeur 6, alors on choisit la 6ème valeur disponible selon le masque (ici 7). On continue ainsi jusqu'à avoir balayé toutes les cases du plateau.

À la fin du programme, pense à désallouer ta grille.

Bonne chance
1
Merci

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

CCM 65492 internautes nous ont dit merci ce mois-ci

Messages postés
8731
Date d'inscription
vendredi 19 septembre 2003
Statut
Modérateur
Dernière intervention
20 août 2016
1 517
Longue vie à Mamie!
Messages postés
1755
Date d'inscription
vendredi 2 mars 2007
Statut
Membre
Dernière intervention
18 mai 2010
89
Utilise une fonction du hasard :)
de 1 à 9 ;)
Messages postés
1755
Date d'inscription
vendredi 2 mars 2007
Statut
Membre
Dernière intervention
18 mai 2010
89
Merci mamiemando pour cette sublime réponse :)

Oui bien entendu , aléatoirement correctement ;) (houlà mauvais français ça :p)
Messages postés
29895
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
16 juin 2021
7 122
Merci du compliment, j'espère qu'elle conviendra aussi à yan.
Messages postés
1755
Date d'inscription
vendredi 2 mars 2007
Statut
Membre
Dernière intervention
18 mai 2010
89
Je voulais pas lui donner toute la soluce non plus :p
Messages postés
29895
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
16 juin 2021
7 122
Bah là même avec ça il lui reste pas mal de quoi s'amuser. De plus les morceaux de codes que j'ai donné ne sont pas testés et ne sont pas très élégants. Notamment la gestion des masques est un peu moisie avec un tableau d'int, il faudrait plutôt utiliser des champs de bits (oui les informaticiens ont des termes douteux).

De toute façon la question suivante dans son exercice est sans doute de coder un solveur de sudoku :-)
Messages postés
29895
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
16 juin 2021
7 122
Je préfère ne pas relever ^^