Un article de Wikipedia.

Version du 21 mars 2008 à 12:13

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.

L'implémentation utilise les variables ensemble pour stocker les chiffres possibles d'une case vide.

Dans la mesure du possible le programme détermine s'il existe plus d'une solution.

Editeur de grille

Il est possible d'ajouter des grilles.

L'éditeur est rudimentaire, il permet de définir un titre pour la grille et de spécifier l'ensemble des chiffres de la grille.

L'éditeur prend en compte au plus les 9 premiers caractères introduits. Il ne tient compte que de la position des chiffres.

L'éditeur ne sauvegarde qu'une grille valide (unicité des chiffres, par ligne, par colonne et par bloc).

Introduire 'xx2x4' revient à introduire '00204000' ('x' a été utilisé ici pour des questions de lisibilité, mais '-' esst plus simple à introduire sous Palm).

La réédition des lignes d'une grille a les propriétés suivantes :

• Un caractère 0 efface le chiffre qui était présent.
  • Exemple: en introduisant 'xx0' sur la ligne précédente donnée en exemple, cela revient à avoir '00004000' sur la ligne.
• Un autre caractère que les chiffres de 0 à 9 laisse le chiffre qui était présent.
  • Exemple : en introduisant 'xx3xx6' sur la ligne précédente donnée en exemple, cela revient à avoir '00304600' sur la ligne.

Modes debug

Il y a quatre modes debug :

• Sans debug : la grille initiale est affichée puis sa solution.
• Affichage des grilles :
  • la grille initiale est affichée
  • la grille après initialisation
  • la grille après avoir appliqué la procédure des grilles simples (rules)
  • la grille après avoir appliqué la procédure des grilles intermédiaires pour les colonnes (raw)
  • la grille après avoir appliqué la procédure des grilles intermédiaires pour les lignes (line)
  • la grille après avoir appliqué la procédure des grilles intermédiaires pour les blocs (grid)
  • si nécessaire, la grille après avoir appliqué la procédure des grilles difficiles pour une case donnée ((k,l)) en prenant parmi les choix possibles ([1359]) un choix qui conduit soit à une absurdité (-1) ou non (+3)
• Affichage des possibilités : affiche après la grille initiale, la grille avec l'ensemble des choix possibles par case
• Deux affichages précédents : cumule les deux affichages précédents

Exemples de grilles

Conclusions

• En mode sans debug, la résolution d'une grille prend moins d'une seconde.
• Juasuq'à présent, ce programme a résolu toutes les grilles mais, si la grille est trop difficile (ou plutôt avec des solutions mutltiples), voire entièrement vide, le Palm plante.

Ressources

• Sudoku Media:Sudoku_pas.PDB
• Source Sudoku.pas

Solution des grilles