Un gabarit pour Sudoku

J'ai voulu systématiser les règles du Sudoku pour mieux en comprendre l'application lors de la résolution de grilles partielles. J'en suis arrivé à construire un gabarit (feuille de calcul pour Excel) qui les rendent opérationnelles dans un contexte limité de support. Je n'ai jamais eu l'intention de créer un programme qui résoudrait les grilles de lui-même; ce gabarit enregistre seulement les décisions prises et signale de plus les choix potentiels pouvant rester à faire.

Le gabarit et ses différentes composantes sont décrits dans une page séparée et les procédures d'utilisation de ce gabarit dans une autre, mais au préalable il vaut mieux établir certaines prémisses pour mieux comprendre cet outil.

 

Le fichier XLS est téléchargeable librement sous la forme du fichier sudoku_gabarit.zip

 

Les règles et leur mise en œuvre

Tout d'abord un rappel des règles s'impose. Le Sudoku utilise les nombres entiers de 1 à 9 et une grille carrée de 9 par 9 cellules. À partir d'une grille partielle imposée, il s'agit de compléter la grille de telle façon que chacun de ces nombres soit présent une fois et une seule fois dans chaque rangée, dans chaque colonne et dans chacun des 9 groupes de 3 par 3 cellules, sous-ensembles de la grille principale.

 

Un exemple de "problème" et la

  "performance" pour l'entier 1

Le gabarit est basé sur le concept de "tableaux de performance d'un entier", qui est une grille carrée de 9 par 9, contenant originellement des 1; il y a un tel tableau pour chaque entier de 1 à 9; Dans ce cas, 1 signifie que la position est ouverte pour recevoir cet entier, 0 que l'entier ne peut y être assigné.  Le passage de 1 à 0 se fait dans plusieurs circonstances dont la plus évidente est que cette position est "prise" par un autre entier (ainsi les cellules contenant les nombres tels qu'imposés dans le problème). Les autres circonstances résultent de l'application des règles: si l'entier en question est présent dans une cellule, toutes les cellules de la rangée, toutes celles de la colonne et toutes celles des "groupes carrés", où il se trouve sont mises à 0.

La double illustration précédente montre comment un problème est traduit en tableau de performance pour l'entier 1. Cinq des 9 groupes carrés de 3 par 3 n'ont que des 0 puisque 1 est présent 5 fois dans le problème et chaque fois dans un groupe différent (une des règles); de plus avec l'élimination des rangées et des colonnes plus celle des cellules contenant d'autres nombres, il ne reste que 7 cellules dans laquelle on pourrait placer un 1 (nous n'en avons besoin que de 4 puisque le problème en a placé 5 sur la grille).

Les totaux de rangées et ceux des colonnes ont été rajoutés. Dans cet exemple le total de la rangée 9 et celui de la colonne 6 sont de 1; cela signifie que comme il faut un 1 dans cette rangée et dans cette colonne il devra être OBLIGATOIREMENT situé dans la cellule (9,6). On aurait atteint le même résultat en observant que parmi les 9 totaux de groupe 5 sont nuls (ceux des données du problème) 3 ont une valeur de 2 et un seul celle de 1. Un 1 devra donc être placé dans ce groupe (centre bas) dans la seule position acceptable (9,6). S'il y a concordance dans cet exemple entre les différentes approches (totaux de rangée, de colonne et de groupe) il est rare d'avoir ainsi de telles redondances..

L'interprétation à donner à la mise en œuvre des règles nous a fait glisser du simple enregistrement de leurs conséquences à la recherche de solution. Un autre petit pas nous y mettra complètement. Un tableau de performance globale est construit comme la somme des 9 tableaux de  performance des entiers. Les nombres présents varient de 0 (la cellule est déjà définie et aucun entier ne peut y être encore assigné) à 9 (n'importe lequel des entiers de 1 à 9 peut y être assigné, situation théorique probablement impossible à trouver). Dans un tel tableau, 1 veut dire qu'il n'y a qu'un seul entier qui pourrait être assigné dans cette position (il faut identifier cet entier en consultant les tableaux d'entiers pour trouver celui qui a un 1 dans cette position) et il devrait OBLIGATOIREMENT y être assigné.

Les procédures d'utilisation du gabarit sont basées sur ces simples constatations.