Sudoku
Un article de Wikipedia.
Sommaire |
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.
La base de données se nomme 'SudokuCPDB' et contient à sa création les trois grilles citées ci-dessous en exemples.
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.
- Jusqu'à présent, ce programme a résolu toutes les grilles mais, si la grille est trop difficile (ou plutôt avec des solutions multiples), voire entièrement vide, le Palm plante.
Ressources
- Sudoku Media:Sudoku_pas.PDB
- Source Sudoku.pas
Solution des grilles
|
|
|
Catégories: Logiciel | Pascal | Palm
