Remerciez-le!

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

Theorie des ensembles appliquee au sudoku et algorithmique associee 1

Théorie des ensembles appliquée au sudoku et algorithmique associée Marie-Pierre Falissard professeure de mathématiques à Pully-Lausanne collège Champittet Description ensembliste du sudoku Une grille de sudoku peut se caractériser par 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 ? Ces symboles seront utilisés pour remplir la grille On trouve parfois des ensembles plus petits à symboles ou plus grands à ou symboles On y adjoindra par commodité un symbole particulier qui correspondra à une case vide On notera alors S ? S ?? b Un ensemble ordonné C de cases ci On peut désigner chaque case par un numéro qui ira ainsi de à pour le sudoku usuel C ? 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 L C L C ? L C L C pour le sudoku classique à 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 x L L C L C ? L C première ligne C L C L C ? L C troisième colonne B L C L C L C L C ? L C premier bloc D L C L C ? L C diagonale descendante Le but du jeu consiste à remplir les cases ? en se conformant aux règles du sudoku c ? est-à-dire à dé ?nir complètement une application f de C vers S ? qui soit une surjection de C vers S véri ?ant les propriétés suivantes propriété f C ?? ?? j f Ej S commentaire Avant la résolution certaines cases sont déjà remplies pour certains c de C f c ?? pour tous les autres f c case vide 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 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éri ?cation 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 M-P Falissard CRésolution En entrée S ensemble de symboles C ensemble de cases Ej régions de