Outils pour utilisateurs

Outils du site


pg108:projet_2

Résolution de Sudoku

Le projet consistera à écrire un programme capable de résoudre une grille de sudoku. Dans un premier temps, nousnous contenterons d'écrire les fonctions de gestion. Dans un second temps, nous nous attaquerons à la résolution en elle-même.

Ce projet sera évalué par un rapport, il vous est donc fortement conseillé :

  • de sauvegarder les versions intermédiaires de votre programme lorsque vous avez atteint une étape importante
  • de faire des captures d'écran de vos résultat (c'est toujours utile pour écrire un rapport)

Pour faire vos différents tests, vous trouverez ci-dessous des fichiers contenant des grilles de difficulté variable :

structure de données

Le sudoku consiste en une grille de 9 colonnes et de 9 lignes. Pour chaque case de la grille, soit le contenu est connu, soit il est inconnu. Dans ce dernier cas, il existe plusieurs valeurs possibles, et des valeurs dont on sait qu'elles sont impossibles.

Nous allons coder chaque élément de la grille par un type de donnée spécifique (un struct) que nous appellerons sudoku_tile. Le type sudoku_tile contient :

  • un entier de type char nommé value.
  • un tableau de 9 entiers de types char, nommé possible.

Pour chaque case de la grille, value est compris entre 0 et 9. Si value est compris entre 1 et 9, cela signifie que la valeur de la case est connue et vaut value. Si value vaut 0, cela signifie que la valeur de la case est inconnue. Dans ce cas, le tableau possible définit, pour chaque valeur, si elle est possible ou pas. Par exemple, si possible[3]==0, cela signifie que la valeur 4 n'est pas possible dans cette case, si possible[7]!=0, cela signifie que la valeur 8 est possible dans cette case.

Pour accéder aux données de la case foo, on utilise la syntaxe suivante :

  foo.value = 2
  if (foo.value == 0) ...
  foo.possible[1] = 0
  if (foo.possible[4] != 0) ...

La grille de jeu, sera alors constituée d'une variable globale. Le type de cette variable sera un tableau de 81 sudoku_tile. Nous l'appellerons grid. Elle sera constituée de 9 lignes de 9 cases chacune. Ainsi, la case de la colone i et de la ligne j sera identifiée par grid[i-1 + (j-1)*9] avec i et j compris entre 1 et 9. Pour parcourir toutes les cases de grid, le code sera donc :

  for (int line=1; line <= 9; line++) {
      for (int col=1; col <= 9; col++) {
          grid[ (line-1)*9 + col -1] = ....
          ...
          function( grid[ (line-1)*9 + col -1] );
          ...
      }
  }

premières fonctions

initialisation

Créez une fonction qui initialise grid. Comme la grille est vide, tous les champs value sont à 0, et toutes les valeurs sont possibles.

affichage

Pour pouvoir vérifier les différentes fonctions à venir, Il faut pouvoir afficher une grille. L'affichage le plus simple est de n'afficher que les valeur qui sont certaines.

  • Écrivez la fonction disp_final qui, pour chaque case, n'affiche que le champ value. Par souci de clarté de l'affichage, si la valeur n'est pas connue, il est préférable d'afficher un espace vide (le caractère espace) au lieu de 0 .
  • Écrivez la fonction disp_possible qui affiche 9 grilles (une pour chaque valeur possible, pour chaque grille, nous l'appelerons d). Chaque case sera affichée avec le contenu suivant :
    • Si la valeur de la case est connue, et vaut d, on affiche cette valeur
    • Si la valeur de la acse est connue, mais ne vaut as d, on affiche le caractère '.'
    • Si la valeur de la case est inconnue, et que d est possible, on affiche le caractère '+'
    • Si la valeur de la case est inconnue, et que d est impossible, on affiche un espace

Ces deux fonctions vous permettront, à chaque étape, de vérifier si les données sont cohérentes avec les fonction que vous avez voulu réaliser.

Testez vos fonctions sur grid, que vous aurez légèrement modifié pour ce test.

Modification d'une case

A chaque fois qu'une valeur d'une case foo devient connue, il faut attribuer sa valeur à foo.value mais aussi mettre à jour le tableau foo.possible. Comme il sera nécessaire de faire cette opération à plusieurs endroits du programme, autant faire une fonction qui s'en occupe.

Écrivez la fonction set_tile_value qui reçoit un pointeur vers une case (un sudoku_tile *) et un char entre 1 et 9 que l'on nommera val, et qui modifie la case pour que val soit sa nouvelle valeur connue.

Utilisez les fonctions disp_final et disp_possible sur une grille que vous aurez modifié grâce à set_tile_value pour vérifier que votre fonction fonctionne correctement.

Saisie de la grille de départ

Écrivez la fonction la fonction req_start_grid qui demande à l'utilisateur d'entrer une grille de départ. On se contentera de définir value et possible pour les cases dont la valeur est connue, en laissant toutes les valeurs possibles pour les cases dont la valeur est inconnue.

Le remplissage de la grille de départ se fait en demandant les neuf lignes à l'utilisateur. Pour Chaque ligne, l'utilisateur entre les valeurs des cases successivemnt. Si la valeur est connue, ce sera donc un caractère de '1' à '9'. Si la valeur est inconnue, ce sera le caractère '?'. Tout autre caractère peut être ignoré, à l'exception du saut de ligne ('\n') qui marque la fin de la ligne.

Utilisez les fonctions disp_final et disp_possible pour vérifier que la saisie fonctionne proprement.

Premières étapes sur les lignes

Dans un premier temps, nous ne travaillerons que sur des lignes. C'est à dire sur des tableaux de 9 cases.

retrait des valeurs impossibles

Etant donné qu'une valeur ne peut se trouver qu'une seule fois par ligne. Pour chaque valeur, si on sait qu'elle est présente dans une case, on peut la retirer des valeurs possibles sur toutes les autres cases.

Écrivez la fonction clean_line qui reçoit une ligne de cases comme argument (pas besoin de connaitre sa taille, elle fait forcément 9 cases). Pour chaque valeur v (entre 1 et 9), si une des cases de la ligne a v comme valeur connue, la fonction clean_line indique que v est impossible pour les autres cases.

clean_line renvoie 0 si elle n'a modifié aucune case, 1 si au moins une case a été modifiée.

Utilisez la fonction clean_line sur chaque ligne de grid (avec une grille non nulle) et utilisez disp_possible pour vérifier son bon fonctionnement.

Confirmation des possibilités uniques

Pour chaque case, si une seule valeur est possible, alors nous pouvons considérer qu'il s'agit d'une valeur connue. Écrivez la fonction validate_single_possibility qui, pour chaque case de grid, vérifie si une seule valeur est marquée comme possible. Si c'est le cas, la fonction validate_single_possibility écrit cette valeur dans la case comme connue.

validate_single_possibility renvoie 0 si aucune case n'a été modifiée, 1 si au moins une case a été modifiée.

Créez une grille spécifique pour tester le bon fonctionnement de la fonction validate_single_possibility grâce à disp_possible.

Condition d'existance

Chaque valeur doit apparaître au moins une fois par ligne. Donc, pour chaque valeur, si elle n'apparait comme possible que dans une seule case d'une ligne. Alors on peut affirmer que cette case contient la valeur considérée.

Écrivez la fonction valid_exist_in_line qui reçoit une ligne de cases comme argument. Pour chaque valeur v (entre 1 et 9), si une case de la ligne a une valeur connue et égale à v, la fonction ne fait rien. Sinon, si une seule case contient v comme valeur possible, on peut marquer v comme valeur connue de cette case (même si d'autres valeur sont possibles pour cette case).

valid_exist_in_line renvoie 0 si aucune case n'a été modifiée, 1 si au moins une case a été modifiée.

Créez une grille spécifique pour tester le bon fonctionnement de la fonction valid_exist_in_line grâce à disp_possible et à disp_final.

Pseudo-résolution

Pour résoudre la grille de sudoku, il faudrait alterner les opérations clean_line, et valid_exist_in_line, chacune suivie de validate_single_possibility. Tant que l'une de ces fonction modifie la grille, c'est que la résolution de la grille avance. Une fois qu'aucune de ces étapes ne modifie la grille, c'est que la grille est résolue, ou qu'elle est trop complexe à résoudre pour les opération simples que nous avons implémentées.

Tenter de résoudre une grille maintenant ne serait par contre pas utile, car nos fonctions ne travaillent que sur des lignes, c'est une vision trop partielle du problème. Il faut donc résoudre à la fois les lignes, les colonnes, et les sous-carrés de dimension 3.

généralisation de la résolution

Il serait facile de créer des fonctions clean_col et valid_exist_in_col pour gérer les colonnes. Par contre, la gestion des sous-carrés reste problématique à cause de la complexité de gestion des indices. Nous allons donc passer par une solution plus flexible qui permet d'utiliser la même fonction, indifféremment pour les colonnes, les lignes et les sous-carrés.

évolution des structures de données

Jusqu'ici, nous avons travailé avec des lignes, car la grille de jeu est stockée sous forme de plusieurs lignes mises bout à bout. Il est donc facile de les identifier grâce à un pointeur pour les fournir aux fonction clean_line et valid_exist_in_line. Pour pouvoir manipuler indifféremment lignes, colonnes et sous carrés, nous allons utiliser un tableau qui ne contient pas des cases (sudoku_tile), mais des pointeurs vers des cases (sudoku_tile *). Il sera ainsi possible de regrouper des cases dans un tableau, même si elles ne sont pas juxtaposées dans la mémoire. Nous appellerons un tel tableau un sous-ensemble. Un tel tableau se définit comme suit :

  sudoku_tile *subset[9];

Un tableau étant un pointeur, toute fonction qui aura besoin d'un sous-ensemble comme argument devra recevoir un sudoku_tile * * et toute fonction renvoyant un sous-ensemble devra renvoyer un sudoku_tile * *. Pour simplifier le code, il vous est proposé de définir le type de donnée sudoku_subset comme étant un sous-ensemble.

Le code est donc :

  typedef sudoku_tile ** subset;

ATTENTION : bien que subset soit maintenant un type connu, définir une variable de type subset ne réserve pas de mémoire. Le type de données subset ne peut donc pas être utilisé pour créer un sous-ensemble, mais uniquement pour référencer ou manipuler un sous-ensemble déjà existant.

Affichage d'un sous-ensemble

Créez une fonction disp_subset qui affiche un sous-ensemble. Cette fonction ne contenant que 9 éléments, vous êtes libres de gérer la représentation comme il vous convient. Vous prendrez tout de même soin de l'expliciter dans votre rapport.

Création d'un sous-ensemble

Nous allons maintenant définir un ensemble de fonctions pour créer les sous-ensembles dont nous avons besoin à partir de la grille principale. Pour chacune des trois fonctions suivantes, vous prendrez soin d'en valider le fonctionnement grâce à la fonction disp_subset.

à partir d'une ligne de la grille

Créez la fonction get_line_subset qui reçoit un entier en argument, et qui renvoie un sous-ensemble correspondant à la ligne dont le numéro est l'argument reçu.

à partir d'une colonne de la grille

Créez la fonction get_col_subset qui reçoit un entier en argument, et qui renvoie un sous-ensemble correspondant à la colonne dont le numéro est l'argument reçu.

à partir d'un sous-carré de la grille

Cette fonction est un peut plus complexe. Prenez d'abord le temps de numéroter les sous-carrés pour mieux pouvoir les référencer par la suite. (certaines numérotations vous simplifieront la vie, d'autres … moins). Il pourrait être utile de montionner ce shéma de numérotation dans le rapport…

Créez la fonction get_subsq_subset qui reçoit un entier en argument, et qui renvoie un sous-ensemble correspondant au sous-carré dont le numéro est l'argument reçu (selon votre schéma de numérotation)

Création de tous les sous-ensembles de la grille de jeu

Dans une grille de jeu, il y a 27 sous-ensembles possibles (9 lignes, 9 colonnes, 9 sous-carrés). Faites en sorte que votre programme crée et mémorise ces 27 sous-ensembles dans une variable dont vous expliquerez le type et l'usage.

Adaptation des fonctions de résolution de grille

A partir de la fonction clean_line, créez la fonction clean_subset, qui se comporte de la même façon, mais sur un sous-ensemble qu lieu d'une ligne.

A partir de la fonction valid_exist_in_line, créez la fonction valid_exist_in_subset, qui se comporte de la même façon, mais sur un sous-ensemble qu lieu d'une ligne.

Vous prendrez soin de valider chacune de ces fonctions sur une ou plusieurs grilles simples de debugage.

Vous pouvez maintenant écrire clean_grid qui applique clean_subset à tous les sous-ensembles de la grille, et valid_exist qui applique valid_exist_in_subset à tous les sous-ensembles.

Résolution de grilles simples

A ce stade, il est possible de résoudre des grilles de complexité moyenne. il suffit d'alterner les appels aux fonction précédentes comme suit :

  • clean_grid
  • validate_single_possibility
  • valid_exist
  • validate_single_possibility

Il faut arrêter le programme dès qu'il n'y a plus de modification effectuée en un tour de boucle. Si la grille est complète, c'est qu'elle est résolue, autant l'afficher fièrement :). Sinon, il faut faire appel à des règles de résolution plus complexes (en théorie…)

Résolution de grilles complexes

A ce stade, votre programme devrait être capable de résoudre les grilles de niveau le plus simple (trivial et basic) mais pas de niveau plus complexe (intermediate). Nous allons nous y atteler maintenant.

Principe

On peut déduire de nombreux critères plus subtils à partir des règles de base pour continuer la résolution de la grille si les règles précédentes ne suffisent pas. Plutôt que d'implanterde nombreuses règles qui sont peu utilisées, nous allons plutôt utiliser l'atout principal des ordinateurs : la force brute.

Pour une case donnée, le programme va tester une valeur possible (suppositon). Si, en continuant la résolution, on tombe sur une impossibilité (une case pour laquelle aucune valeur n'est possible), c'est que la supposition est fausse. On peut donc retirer la valeur supposée des valeurs possibles. Si, en continuant la résolution, on obtient une grille complète, c'est que la supposition était bonne (car la solution est unique).

Pour pouvoir revenir en arrière lors d'une fausse supposition, il y a deux solutions :

  • sauvegarder l'état de la grille
  • mémoriser l'historique des valeurs affectées.

La sauvegarde de la grille complète nécessitera beaucoup de mémoire à chaque nouvelle supposition. Nous allons donc utiliser l'autre solution. Il va donc falloir mettre en place une nouvelle structure dont le rôle sera de mémoriser l'historique des affectations.

Mémorisation chronologique des coups

Au maximum, il y aura 81 affectations dans la grille, nous allons donc utiliser un tableau de 81 éléments. Chaque élément du tableau doit préciser quelle case a été modifiée (nous l'identifierons par un pointeur) et comment cette case a été affectée (supposition ou déduction).

les éléments du tableau seront donc une structure nommée affectation contenant deux champs :

  • un pointeur vers un sudoku_tile que l'on nomera tile
  • un char que l'on nomera supposed qui vaut 0 si l'affectation est le résultat d'une déduction et 1 si elle est le résultat d'une supposition.

Créez la variable history qui contient un tableau de 81 affectation. Créez égalemant la variable history_index de type entier qui indique la première case vide de history (il s'agit de la case dans laquelle il faudra écrire la prochaine opération).

Mise à jour de la fonction set_tile_value

Mettez à jour la fonction set_tile_value. Cette fonction reçoit maintenant une valeur supplémentaire qui définit si l'affectation est une déduction ou une supposition. set_tile_value doit maintenant accepter de définir une case à 0 (il n'est pas forcément nécessaire de mettre à jour les valeurs possibles). set_tile_value doit en plus ajouter l'affectation dans le tableau history.

Il faudra également modifier chaque appel à set_tile_value pour préciser que les affectation sont des déductions (supposed == 0)

Testez si vous n'avez pas altéré le fonctionnement de votre programme.

Il est conseillé d'afficher history à la fin de votre programme pour vérifier qu'il fonctionne correctement.

Validité de la grille

Créez la fonction is_grid_valid qui renvoie 1 si la grille est valide, et 0 sinon. La grille est invalide si elle contient une case dont la valeur est inconnue, et pour laquelle aucune valeur n'est possible. Sinon, elle est considérée comme valide.

Modifiez votre programme pour qu'il s'arrête dans un cas supplémentaire : si la grille est invalide.

Suppositions

Créez la fonction guess_value qui ne reçoit aucun argument en particulier. Cette fonction recherche une case pour laquelle la valeur est inconnue et deux valeurs sont possibles.

  • si une telle case existe, la fonction affecte une des valeurs possibles à la case par supposition et renvoie 1
  • s'il n'existe aucune case inconnue à deux valeurs possibles, la fonction renvoie 0.

Modifiez la boucle de votre programme de la façon suivante :

  clean_grid
  validate_single_possibility
  valid_exist
  validate_single_possibility
  si les opération précédentes n'ont permit aucune déduction
    guess_value

Selon les cas, ce programme permet la résolution de grilles plus complexes, ou aboutit à une grille invalide…

Gestion des mauvaises suppositions

Si le programme aboutit à une grille invalide, il faut utiliser history pour revenir en arrière.

Créez la fonction back_play qui parcours la history à contre-sens. Pour chaque affectation de valeur :

  • si c'était une déduction, la valeur est simplement effacée de la grille (remise à zero de la case) et de l'historique (le simple fait de décrémenter history_index peut suffire)
  • si c'était une supposition, c'est qu'elle est fausse ! dans ce cas, il faut:
    • effacer la case correspondante
    • re-initialiser les valeurs possibles de toutes les cases inconnues (Il était inutile de le faire avant car on ignorait quelles cases étaient correctes)
    • appeler clean_grid pour retrouver des valeurs possibles cohérentes sur les cases inconnues (la case qui contenait la supposition ne devrait avoir que deux valeurs possibles)
    • marquer la valeur supposée comme impossible (puisque la supposition était fausse)
    • retirer la supposition de history

La boucle de résolution va reprendre, mais cette fois, on a retiré une valeur possible à une case qui n'en avait plus que deux, la dernière valeur possible sera donc sélectionnée par la reprise de la déduction classique.

Expliquez pourquoi cette technique ne fonctionne QUE si on s'arrête à la première supposition.

Modifiez votre programme pour que, si la grille est invalide, on fasse appel à back_play au lieu de quitter.

A ce stade, même les grilles intermédiaire devrait être résolues.

Il existe encore des grilles récalcitrantes ?

Il reste un cas qui n'est pas géré : que faire s'il n'y a pas de case avec uniquement deux valeurs possibles pour la supposition ?

Il reste possible de choisir une case avec trois valeurs possibles, mais dans ce cas, si la supposition est fausse, on ne sait pas quelle autre valeur choisir, et si on choisit une autre valeur, comment se souvenir des valeurs qui ont déjà été testées et que l'on sait être fausses ?

La solution est alors de toujours commencer par la valeur possible la plus petite lorsque la grille vient d'être reconstruite. Dans ce cas, la valeur que l'on vient de supposer indique quelles sont les valeurs qui ont déjà été testées (et qui sont donc impossibles). Par exemple, si une case a pour valeur possibles 2,5,8.

  • Au début, on teste la valeur 2, car c'est la plus petite
  • Si 2 implique une grille invalide, c'est que c'est une valeur impossible on la marque comme telle. On teste alors 5 car c'est la plus petite qui reste.
  • Si 5 implique une grille invalide, c'est que 2 et 5 sont impossibles, on est alors sûr que la valeur est un 8.

Cette technique ne fonctionne QUE si le choix de la case sur laquelle on fait les suppositions est déterministe. Le plus simple est de chercher la première case contenant deux valeurs possibles, puis la première case ne contenant que trois valeurs possibles, … ainsi, dès qu'une supposition sera faite, on est certain de retomber sur la même case puisque, ayant une valeur possible en mois, elle sera prioritaire sur toutes les autres.

Petites questions diverses pour occuper vos soirées d'hiver

Ces questions peuvent, selon les cas, vous aider à étoffer votre rapport, vous proposer des pistes de réflexion sur l'amélioration du programme, etc.

  • Le type subset est techniquement inutile. Si une fonction a besoin de recevoir un tableau contenant tous les subset de la grille. Quel sera son prototype (sans utiliser le type subset donc) ?
  • Il existe de nombres pistes pour réduire la quantité de mémoire utilisée par ce programme… faites des propositions
  • Pourquoi ne pas utiliser directement la solution basée sur les suppositions successives ? quantifiez … m'enfin, essayez de quantifier :)
  • C'est un programme où il y a des pointeurs partout … et peut-être même des mallocs (qui sait). Mais on ne parle jamais d'appels à free, pourquoi ? quand faut-il le faire ? c'est grave si on ne le fait pas ?
pg108/projet_2.txt · Dernière modification: 2021/12/10 17:16 par bornat