[C] TP 1 : Sudoku

Le menu est disponible grâce au bouton droit

Date de première publication : 2014/09/25

Le TP sur les outils doit être fait au préalable.

Présentation

Le principe du SUDOKU est très simple. Sur une grille 9x9, il faut placer les chiffres de 1 à 9 tels que toutes les lignes, toutes les colonnes et toutes les régions ne doivent voir ces chiffres qu’une seule fois. La première figure montre un sudoku résolu. Les nombres en rouge ont été donnés au départ. La deuxième figure nomme chacune des neuf régions. Les figures viennent de Wikipedia.

On vous propose de réaliser le moteur de jeu texte du sudoku. Pour cela, vous devrez compiler et tester régulièrement. Sous gcc, vous devez utiliser les options :

-Wall -Wextra -g

Les éléments devront être déclarés et bien documentés : vous devez mettre ensemble les constantes en début de programme.

Pour définir une matrice réelle de taille NxM, cela se fait très simplement :

float matrice [N][M];

Un tableau à deux dimensions ne peut exister en C, il s’agit en fait d’un tableau à une dimension où les lignes sont stockées les unes après les autres. C’est pour cela, qu’il faut toujours donner la deuxième dimension - le nombre de colonnes - lors de passage de paramètres Cette dimension permet de calculer l'indice des éléments (num_ligne*nb_colonnes+num_colonne).

void premiere_maniere(float m[] [M]);
void autre_maniere   (float m[N][M]);

À vous de coder !

1. Écrire le squelette du programme : la fonction int main() qui affiche "SUDOKU" sur la sortie standard.
2. Définir une constante symbolique N qui représente la taille de la grille carrée du jeu.

Qui lit / évalue cette constante ?

C'est le préprocesseur qui "voit" la constante symbolique. Je vous rappelle qu'il s'agit d'un remplacement de texte qui a lieu avant la compilation proprement dite.

3. Déclarer une matrice carrée de N cases de côté appelée grille dans la fonction main(). Cette grille contient des entiers et représente la grille de sudoku. La valeur 0 signifie que la case n'a pas encore eu de valeur.
4. Déclarer et initialiser une variable entière remplissage, elle représente le nombre d'éléments non nuls dans la grille.
5. Écrire une fonction initialiser() qui prend en paramètre grille et qui initialise tous les éléments de la grille à 0 et qui renvoie un entier 0
6. Écrire une fonction afficher() qui prend en paramètre la grille et qui l’affiche en texte. Vérifier que tout marche jusque là

Le plus difficile à faire pour jouer au Sudoku est de trouver une bonne grille de départ. On peut imaginer différents algorithmes pour ce faire mais cela n'est pas le propos de ce TP. Je vous propose de créer une fonction generer() qui va permettre de disposer d'une grille presque complète pour que les tests fonctionnels soient plus rapides à écrire.

int i, j, k;
int tab[9][9];

for(j=0;j<9; ++j) 
{
  for(i=0; i<9; ++i)
      tab[j][i] = (i + j*3 +j /3) %9 +1 ; 
}
   
for(i=0;i<9; ++i) 
{
  for(j=0; j<9; ++j)
    printf("%d ", tab[i][j]);
  printf("\n");  
}

Il suffit d'enlever quelques valeurs (d'une ligne, d'une colonne ou d'un bloc) pour tester rapidement les fonctions que l'on vous demande d'écrire dans la suite du sujet.

7. Ecrire la fonction generer(), elle prend en paramètre la grille et renvoie le nombre d'éléments non nuls.
8. Écrire une fonction saisir() qui demande à l’utilisateur de saisir au clavier les indices i et j et la valeur v à placer à l’emplacement (i,j). La fonction doit vérifier la validité des indices et de la valeur. Si la case n’est pas occupée, la valeur doit être placée dans la grille. remplissage est alors incrémentée
9. Écrire la fonction verifierLigneColonne() qui prend en paramètre un numéro et un sens (HORIZ ou VERT) qui vérifie que la ligne ou la colonne (suivant les cas) numéro est bien remplie. On pourra utiliser un tableau intermédiaire pour vérifier cela. La fonction retournera 1 si tout s’est bien passé, 0 sinon. Les constantes HORIZ de valeur 0 et VERT de valeur 1 sont à définir.
10. Écrire la fonction verifierRegion() qui prend en paramètre deux indices k et l qui correspondent à la région (k,l) et qui renvoie 1 si la région est correctement remplie, 0 sinon.
11. Écrire la fonction verifierGrille() qui renvoie 1 si la grille est correctement remplie et 0 sinon
12. Écrire le programme principal, en supposant que la seule condition d’arrêt est la réussite du sudoku (ce test ne devra être fait que si nécessaire)

Questions BONUX

13. Un petit problème subsiste : on peut réécrire sur les nombres qui ont été donnés au départ. Est-ce que vous pourriez coder quelque chose qui permettrait de contourner ce problème ? Une idée toute simple est possible avec uniquement ce qui a été vu en semaines bloquées (pas de structures ou de choses du genre)
14. Vous pouvez écrire une fonction pour lire une grille de sudoku à partir d’un fichier texte.

Il ne faut pas cliquer trop vite sur les boîtes proposant des solutions. Cherchez encore !