Un article de Wikipedia.

Version du 21 mars 2008 à 11:29

Sudoku

But

Pouvoir résoudre une grille de Sudoku.

Introduction

Un Sudoku est généralement une grille de 9x9 cases contenant les chiffres de 1 à 9 et satisfaisant aux règles suivantes :

• chaque ligne contient tous les chiffres de 1 à 9
• chaque colonne contient tous les chiffres de 1 à 9
• en découpant la grille en 9 blocs disjoints de 3x3 cases , chaque bloc contient tous les chiffres de 1 à 9

Le jeu consiste à combler les cases vides d'une grille d'un Sudoku dont certaines cases sont déjà connues en satisfaisant les règles précitées.

Méthodes de résolution et types de grilles

Trois méthodes de résolution permettent de définir trois types de grilles :

Grilles simples

Une grille simple peut entièrement être résolue en suivant la procédure ci-dessous qui se base sur l'unicité des chiffres de 1 à 9 sur une ligne, une colonne et un bloc en éliminant des possibilités dans les cases vides les chiffres déjà connus.

• initialement :
  • chaque case est étiquetée comme non exploitée
  • chaque case vide contient l'ensemble des chiffres de 1 à 9
  • chaque case dont le chiffre est connu contient le chiffre connu
• pour chaque case non exploitée et contenant qu'un seul chiffre n, marquer la case comme exploitée et éliminer des autres cases non exploitées de la ligne, la colonne et le bloc où se trouve cette case le chiffre n
• continuer jusqu'à épuisement des cases non exploitées contenant qu'un seul chiffre

Grilles intermédiaires

Une grille intermédiaire peut entièrement être résolue en utilisant la procédure des grilles simples associée à celle ci-dessous se basant sur l'unicité des chiffres sur une ligne, une colonne et un bloc du point de vue des cases vides.

• appliquer la procédure des grilles simples; si la grille n'est pas résolue c'est que les cases non exploitées contiennent plus d'un chiffre
• pour chaque ligne, déterminer parmi les cases non exploitées s'il existe un chiffre n qui n'apparaît qu'une seule fois
  • si c'est le cas, rechercher la case en question et noter que la case contient uniquement le chiffre n
  • appliquer la procédure des grilles simples
• effectuer la même procédure pour chaque colonne et chaque bloc

Grilles difficiles

Une grille difficile doit, en plus d'utiliser la procédure d'une grille intermédiaire, utiliser un raisonnement par l'absurde sur les chiffres possibles de cases vide pour être résolue.

• appliquer la procédure des grilles intermédiaires; si la grille n'est pas résolue alors il existe des cases non exploitées qui contiennent plus d'un chiffre possible
• pour une case non exploitée, choisir un chiffre parmi ceux possibles et appliquer la procédure des grilles intermédiaires
  • si la grille est résolue c'est que le choix était judicieux
  • si cela conduit à une grille incompatible avec les règles du Sudoku c'est que le choix était absurde; il faut recommencer avec un autre chiffre parmi les choix possibles
• si cela ne résout toujours pas la grille il faut choisir une autre case et y appliquer cette procédure

Résultats

L'implémentation utilise les API Palm PalmAPI.pas, la librairie PPlib.pas, la librairie générant des menus Menu.pas ainsi que la base de données CPDBSTD4PP.pas.

Exemples de grilles

Conclusions

Ressources

Solution des grilles