Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Théorie des ensembles appliquée au sudoku 1 M-P Falissard Théorie des ensembles

Théorie des ensembles appliquée au sudoku 1 M-P Falissard Théorie des ensembles appliquée au sudoku et algorithmique associée Marie-Pierre Falissard, professeure de mathématiques à Pully-Lausanne (collège Champittet) 1. Description ensembliste du sudoku Une grille de sudoku peut se caractériser par 3 types d'ensembles, qui sont des données de base propres à chaque variante du jeu de sudoku : a. Un ensemble de symboles S, par exemple le plus courant est S = {1, 2, … 9}. Ces symboles seront utilisés pour remplir la grille. On trouve parfois des ensembles plus petits (à 4 symboles) ou plus grands (à 12 ou 16 symboles). On y adjoindra par commodité un symbole particulier : 0, qui correspondra à une case vide. On notera alors : S’ = S ∪ {0}. b. Un ensemble ordonné C de cases ci. On peut désigner chaque case par un numéro, qui ira ainsi de 1 à 81 pour le sudoku usuel : C = {1, 2, … 81}. On utilise aussi une notation positionnelle, par exemple LiCj désigne la case intersection de la ligne i et de la colonne j ; on aurait alors C = {L1C1, L1C2, …, L9C8, L9C9} pour le sudoku classique à 81 cases, décrit ligne à ligne, de gauche à droite et de haut en bas. c. Un certain nombre d’ensembles Ej donnés, qui sont des sous-ensembles particuliers de C ("régions"). Chacun de ces ensembles, a priori quelconque, est caractérisé par la propriété suivante : card(Ej) = card(S), car chacun est destiné à contenir la totalité des symboles de S : il faut donc qu'il y ait autant de cases dans cet ensemble que de symboles possibles. Par exemple, pour des sudokus 9 x 9 : L1= {L1C1, L1C2, …, L1C9 } (première ligne) C3= {L1C3, L1C3, …, L9C3 } (troisième colonne) B1= {L1C1, L1C2, L1C3, L2C1 …, L3C3 } (premier bloc) D1= {L1C1, L2C2, …, L9C9 } (diagonale descendante) Le but du jeu consiste à « remplir les cases » en se conformant aux règles du sudoku, c’est-à-dire à définir complètement une application f de C vers S’ qui soit une surjection de C vers S vérifiant les propriétés suivantes : propriété commentaire f(C) ≠ {0} Avant la résolution, certaines cases sont déjà remplies : pour certains c de C, f(c) ≠ 0, pour tous les autres, f(c) = 0 (case vide). ∀ j, f(Ej) = S Après la résolution, il y a non-répétition des symboles dans chaque région (ligne, colonne, bloc, diagonale). La fonction f est donc une bijection de chaque Ej vers S. 2. Algorithme de résolution de grille par force brute L'algorithme cherche à compléter une grille préalablement initialisée en remplissant chaque case vide l'une après l'autre. Les valeurs initiales sont évidemment supposées constituer une grille valide (pour s'en assurer, on peut faire précéder la routine de résolution d'une étape de vérification qui invoquerait pour chaque case non vide la routine Validation indiquée ci-dessous). La routine de résolution principale peut être de la forme suivante : Théorie des ensembles appliquée au sudoku 2 M-P Falissard Résolution En entrée : S ensemble de symboles, C ensemble de cases, (Ej) régions de C vérifiant card(Ej) = card(S). instruction commentaire 1 Pour toute case ci de C Passer en revue successivement chaque case ci de la grille 2 Si f(ci ) = 0, alors f(ci) ←Remplissage(ci) Si la case est vide, chercher à la remplir 3 Si f(ci ) = 0, alors afficher "Impossible" Si l'on ne peut remplir une case, la grille est impossible Pour remplir chaque case, la routine Remplissage ci-dessous est invoquée. Cette routine a la particularité d'être récursive (elle s'invoque elle-même en ligne 5). Cette récursivité permet de remplir progressivement la grille jusqu'à ce qu'une impossibilité oblige à faire marche arrière (instruction "f(ci) ← 0" en ligne 5) d'un ou plusieurs niveaux pour tester d'autres valeurs possibles ("backtracking"). La ligne 1 (remplissage terminé) donne une condition d'arrêt pour éviter une boucle sans fin. Quand la dernière case vide est remplie, la grille est constituée. Si l'une des cases ne peut être remplie après avoir essayé toutes les valeurs permises et qu'il est impossible de revenir en arrière, la grille est déclarée impossible. Remplissage En entrée : case ci (case vide de C à remplir) En sortie : s (valeur proposée f(ci) pour remplir la case ci) ; 0 si la case ne peut être remplie instruction commentaire 1 Si i > card(C) alors retour (on renvoie une valeur quelconque non nulle) Si l'on a atteint la dernière case de la grille, la recherche est terminée. 2 Pour tout élément s de S s désigne un symbole candidat pour être affecté à la case ci. 3 Si Validation(ci , s) = OK, alors : Si la valeur s placée dans la case ci respecte les règles du sudoku, 4 f(ci) ← s elle est candidate pour être affectée à cette case, 5 si Remplissage(casevidesuivante(ci))=0 alors f(ci) ← 0 sauf s'il est impossible de remplir alors la case vide suivante. 6 Si f(ci) = 0, tester le symbole s suivant, sinon retour de f(ci) Si la valeur s ne convient pas, essayer une valeur suivante, sinon garder cette valeur pour la case. 7 Si tous les s de S ont été testés et f(ci) = 0, on renvoie 0 Impossible d’affecter une valeur à la case ci (toutes les valeurs possibles de S ont été essayées) . La ligne 2 n'indique pas de quelle façon la valeur s est choisie dans S : en première approche, on peut procéder séquentiellement, dans l'ordre des symboles (par exemple 1, 2, ...9). La routine Validation est destinée à vérifier que la valeur candidate ne contrevient pas aux règles du sudoku : Validation En entrée : case c (case vide de C à remplir), valeur s En sortie : OK si la valeur s convient pour la case c ; KO sinon instruction commentaire 1 Pour tout ensemble Ej Passer en revue chaque ensemble (ligne, colonne, bloc, diagonale...) 2 Si c ∈ Ej et s ∈ f(Ej – {c}), alors retourner KO Si une autre case de l’ensemble Ej a la même valeur s, cette valeur ne convient pas pour c 3 retourner OK Aucune case de l’ensemble Ej n'a la valeur s Théorie des ensembles appliquée au sudoku 3 M-P Falissard La routine casevidesuivante donne la case vide qui suit immédiatement une case donnée : casevidesuivante En entrée : case ci (case en cours) En sortie : cj : la case vide qui suit la case ci (dans l'ordre adopté pour C), sinon une valeur quelconque supérieure à card(C) En pratique, les données de base (S, C et les Ej), caractéristiques du sudoku, ne sont pas définies dans le programme, mais sont "externalisées" dans un module séparé, qui décrit la variante de sudoku à laquelle on a affaire. Cela permet d'utiliser le même algorithme pour différentes variantes du sudoku (sudoku à symboles différents, à grille plus grande ou "multi-grilles", à régions différentes dans la grille). Ci-dessous, générés par l'algorithme, un sudoku à deux diagonales et un sudoku à 13 blocs (4 blocs en grisé auxquels s'ajoutent les 9 blocs du sudoku courant) ; ces deux grilles inédites1 sont considérées l'une comme facile, car résoluble par des stratégies élémentaires, l'autre comme de niveau moyen, car résoluble par des stratégies de difficulté moyenne (détection de "paires nues"2), moins abordables cependant pour le débutant. 3. Unicité de la solution L'algorithme de résolution ne s'assure pas de l'unicité de la solution, il s'assure seulement de son existence. Pour vérifier l'unicité, on va chercher une deuxième solution et vérifier si elle coïncide avec la première. On effectue cela en réexécutant l'algorithme de résolution en modifiant la ligne 2 de la routine de remplissage pour "choisir différemment" la valeur à tester. Une possibilité, pour trouver une éventuelle "deuxième solution" aussi différente de la première que possible, consiste à tester pour une case donnée le symbole qui suit immédiatement la valeur trouvée pour cette case lors du calcul de la première solution (si "2" était la première solution pour cette case, on va tester, dans l'ordre : 3, 4, ..., 9, 1 et 2 au second passage). 4. Algorithme de génération de grille La génération d'une grille consiste à remplir une grille vide sans autre règle que le respect des contraintes du sudoku. La génération d'une grille peut être considérée comme un cas particulier de résolution : c'est en fait la résolution d'une grille initialement vide (f(C) = {0}). 1 Solutions détaillées sur http://tinyurl.com/2sudokus 2 Par exemple, on constatera, au cours de la résolution du sudoku de droite, que f({L6C4, L6C6}) = {2,3}, ce qui détermine une "paire nue" {2,3}. On en déduira alors que f(L6C2) = 9, seule valeur possible pour la case L6C2. 1 2 3 4 5 6 7 8 9 1 9 4 2 7 8 3 4 6 5 4 2 6 5 8 9 6 8 4 7 5 2 3 8 1 5 9 3 7 1 2 3 4 5 6 uploads/Geographie/ theorie-des-ensembles-appliquee-au-sudoku-et-algorithmique-associee.pdf