thumb|Grille de sudoku classique thumb|Variante du sudoku basée sur des comparaisons entre les cases thumb|Sudoku classique avec une contrainte supplémentaire sur les diagonales Le jeu du sudoku consiste à compléter une grille carrée divisée en N régions de N cases, en partie remplie avec des chiffres, de façon que dans chaque ligne, chaque colonne et chaque région les chiffres de 1 à N apparaissent une et une seule fois.
Une analyse mathématique du sudoku permet de découvrir les différentes propriétés et problèmes qui se cachent derrière ce jeu et ses variantes.
Introduction L'analyse mathématique du sudoku se divise en deux grandes parties : l'analyse des propriétés des grilles complètes et l'analyse de la résolution d'une grille.
L'analyse des grilles s'est en grande partie focalisée sur l'énumération des solutions possibles pour différentes variantes du jeu. L'étude de la résolution se concentre sur les valeurs initiales de la grille et sur les étapes qui mènent à la grille complète. Ces techniques font appel à plusieurs disciplines : analyse combinatoire, algorithmique, théorie des groupes ainsi que la programmation puisque l'ordinateur permet de rapidement résoudre les grilles.
Il y a un grand nombre de variantes du sudoku, en général caractérisées par la taille de la grille (le paramètre N) et la forme des régions. Les sudokus classiques ont un N égal à 9 avec des régions de 3 × 3 cases. Un sudoku rectangulaire possède des régions rectangulaires d'une taille L × C où L est le nombre de lignes et C le nombre de colonnes. Un tel sudoku, avec une taille de L × 1 (ou 1 × C), devient un carré latin puisque la région est une ligne ou une colonne unique.
Des variantes plus complexes existent comme celles avec des régions découpées de manière irrégulière (Nanpure), avec des contraintes supplémentaires (Samunamupure ou Killer Sudoku, respect de l'unicité sur les diagonales avec le Kokonotsu, contraintes sur l'ordre des éléments avec le Greater-Than) ou des assemblages de plusieurs grilles (Samurai, Sudoku en 3D). Dans certaines variantes, les chiffres sont remplacés par des lettres. Cette substitution des caractères utilisés ne change toutefois rien aux propriétés intrinsèques du puzzle si les règles restent les mêmes.
L'analyse mathématique du sudoku a suivi la popularité du jeu. Les analyses concernant la complexité algorithmique et le caractère NP-complet du jeu furent documentés vers la fin de l'année 2002, les résultats d'énumération ont fait leur apparition vers le milieu de l'année 2005http://www.afjarvis.staff.shef.ac.uk/sudoku/sudoku.pdf. Les contributions des nombreux chercheurs et amateurs ont permis de mettre à jour les propriétés du jeu. L'apparition des variantes du sudoku étend d'autant plus les éléments mathématiques à considérer et explorer.
Contrastant avec les deux approches mathématiques principales citées au début, une approche basée sur la logique mathématique et s'attaquant au problème de la résolution des puzzles a été proposée récemment dans le livre de Denis Berthier, « The Hidden Logic of Sudoku » (La logique cachée du sudoku). Cela a permis de découvrir et de formaliser toutes les symétries généralisées du jeu et de découvrir de nouvelles règles de résolution basées dessus, comme les chaînes xy cachées.
Contexte mathématique Le problème de placer des chiffres sur une grille de n × n comprenant n × n régions est prouvé NP-completpour plus de détails, voir .
La résolution d'un sudoku peut être formalisée par le problème de la coloration de graphe. Le but, dans la version classique du jeu, est d'appliquer 9 couleurs sur un graphe donné, à partir d'un coloriage partiel (la configuration initiale de la grille). Ce graphe possède 81 sommets, un par cellule. Chacune des cases du sudoku peut être étiquetée avec un couple ordonné (x, y), où x et y sont des entiers compris entre 1 et 9. Deux sommets distincts étiquetés par (x, y) et (x’, y’) sont reliés par une arête si et seulement si : x = x’ (les deux cellules appartiennent à la même ligne) ou, y = y’ (les deux cellules appartiennent à la même colonne) ou, et (les deux cellules appartiennent à la même région).
La grille se complète en affectant un entier entre 1 et 9 pour chaque sommet, de façon que tous les sommets liés par une arête ne partagent pas le même entier.
Une grille solution est aussi un carré latin. La relation entre les deux théories est désormais complètement connue, depuis que D. Berthier a démontré, dans « The Hidden Logic of Sudoku », qu'une formule logique du premier ordre qui ne mentionne pas les blocs (ou régions) est valide pour le sudoku si et seulement si elle est valide pour les carrés latins.
Il y a notablement moins de grilles solutions que de carrés latins, car le sudoku impose des contraintes supplémentaires (Voir ci-dessous point 4 : nombre de grilles complètes possibles).
Contrairement au nombre de grilles solutions, le nombre exact de puzzles minimaux n'est pas connu. (Un puzzle est minimal si aucun dévoilé ne peut être supprimé sans compromettre l'unicité de la solution.) Cependant, des techniques statistiques combinées avec la définition d'un nouveau type de générateur (générateur à biais contrôlé.) permettent de montrer qu'il y a approximativement (avec une erreur relative de 0.065%) : puzzles minimaux, puzzles minimaux non équivalents. (voir le livre ou l'article Denis Berthier, , , , (CISSE 09), ).
Le nombre maximum de dévoilés sans qu'une solution unique n'apparaisse immédiatement, peu importe la variante, est la taille de la grille moins 4 : si deux paires de candidats ne sont pas inscrits et que les cellules vides occupent les coins d'un rectangle, et qu'exactement deux cellules sont dans une région, alors il existe deux façons d'inscrire les candidats. L'opposé de ce problème, à savoir le nombre minimum de dévoilés pour une solution unique, est un problème non résolu, bien que des enthousiastes japonais aient découvert une grille 9 × 9 sans symétrie qui contient seulement 17 dévoilés (pour en savoir plus, voir ). Un résultatSolving Sudokus---Coloring by Numbers publié en 2007 apprend que pour qu'un sudoku ait une solution unique, il est nécessaire que 8 des 9 chiffres soient dévoiléshttps://archive.wikiwix.com/cache/20080823015717/http://www2.ic-net.or.jp/~takaken/auto/guest/bbs46.html. http://www.csse.uwa.edu.au/~gordon/sudokumin.php], alors que 18 est le nombre minimum de dévoilés pour les grilles 9 × 9 symétriques.
Nombre de grilles complètes possibles Terminologie Un puzzle est une grille incomplète où figurent des valeurs initiales. Les régions sont également appelées des blocs ou des zones. Le terme de carré est évité pour lever toute confusion.
Une bande est une suite de blocs adjacents sur l'axe horizontal. Une pile est une suite de blocs adjacents sur l'axe vertical. Dans un sudoku de 9 × 9 cases, il y a ainsi 3 bandes et 3 piles.
Un sudoku correctement conçu a une et une seule solution : la grille finale est unique, mais la résolution à partir de la grille partielle peut toutefois prendre des chemins différents.
Dénombrement Le nombre de grilles complètes possibles est de 9! × 72 × 2 × (soit grilles ≈ http://www.shef.ac.uk/~pm1afj/sudoku/).
Le dernier facteur est un nombre premier. Ce résultat a été prouvé en 2005 par Bertram Felgenhauer et Frazer Jarvis. grâce à une recherche exhaustive. Frazer Jarvis a ensuite considérablement simplifié la preuve grâce à une analyse détaillée. La démonstration a été validée de manière indépendante par Ed Russell.
Cependant, plusieurs grilles sont équivalentes si on prend en compte un certain nombre de symétries, à savoir permutations des 9 nombres échange des lignes avec les colonnes (transposition) permutation des lignes dans une bande (en ligne) permutation des colonnes dans une pile (en colonne) permutation des bandes en ligne permutation des piles en colonne (On remarque l'analogie avec les opérations matricielles en algèbre linéaire). En tenant compte de ces symétries, Jarvis et Russell ont montré qu'il y avait non équivalenteshttp://www.shef.ac.uk/~pm1afj/sudoku/sudgroup.html (pour plus de détails, voir http://www.shef.ac.uk/~pm1afj/sudoku/sudgroup.html et ).
À l'inverse, à cette date, aucun résultat n'existe sur le nombre de grilles complètes dans un super sudoku (grille 16 × 16).
Si maintenant, on s'intéresse aux nombres de problèmes proposables, ce nombre est nettement plus important car il existe plusieurs façons de révéler les chiffres d'une même grille.
Le minimum de cases remplies au préalable pour rendre la résolution unique est de 17; il a été prouvé par le calcul en par une équipe irlandaisehttps://arxiv.org/pdf/1201.0749v1.pdf. Une liste de l'ensemble des sudokus à solution unique ayant 17 cases remplies a été établie par des chercheurs japonais http://www.csse.uwa.edu.au/~gordon/sudokumin.php.
Nombre de solutions possibles La réponse à la question « Combien y a-t-il de sudokus ? » dépend de la définition d'une solution et de l'équivalence entre plusieurs solutions. Pour l'énumération de toutes les solutions possibles ( grilles complètes), on retient la définition suivante :
Une grille A est différente d'une grille B, si la valeur de la case en A(i, j) est différente de B(i, j), pour au moins un couple i, j (valeurs limitées par la dimension de la grille).
Si une grille A est obtenue par symétrie de la grille B alors elles sont considérées comme différentes. Les rotations sont également comptées comme de nouvelles solutions.
Définitions
Soit : s une solution d'un sudoku avec des dimensions spécifiques et qui satisfait les règles du sudoku original (pas de doublons dans les lignes, colonnes et régions) S = {s}, l'ensemble de toutes les solutions possibles |S|, la cardinalité (taille) de l'ensemble S ( le nombre de solutions)
Le nombre de solutions dépend de la taille de la grille, des règles appliquées et de la définition précise d'une solution distincte. Pour un sudoku avec des régions de 3 × 3, les conventions pour l'affichage du contenu de la grille sont les suivantes : les bandes sont numérotées du haut vers le bas, les piles de la gauche vers la droite. Les régions sont donc numérotées de la gauche vers la droite et du haut vers le bas. Cette convention s'applique aussi pour les grilles rectangulaires.
D'autres termes sont utiles dans le cas du sudoku avec des régions de 3 × 3 : le triplet est une combinaison non-ordonnée de trois valeurs présentes sur une ligne ou une colonne d'une région. Par exemple, le triplet {3, 5, 7} signifie que les valeurs 3, 5, 7 apparaissent dans une ligne ou une colonne de la région, mais sans spécifier leur ordre d'apparition (on pourrait avoir une ligne avec 5, 7, 3 ou encore une colonne avec 3, 7, 5). Les valeurs d'un triplet peuvent être arrangées de 6 manières différentes (3!) grâce à des permutations. Par convention, les éléments d'un triplet sont écrits dans l'ordre croissant mais cela ne signifie pas qu'ils apparaissent dans la grille selon le même ordre ; la notation hRL indique un triplet pour la région R et la ligne L de la grille. Le préfixe h indique qu'il s'agit d'un triplet horizontal ; de manière similaire, la notation vRC identifie un triplet pour la région R et la colonne C de la grille. Le préfixe v indique qu'il s'agit d'un triplet vertical.
Par exemple, la notation h56 correspond au triplet de la région 5, ligne 6. En anglais, on utilise la notation r pour row et c pour column.
On parle aussi de mini-ligne ou de mini-colonne pour désigner la portion présente dans une région d'une ligne ou d'une colonne de la grille.
Énumérations des solutions symétriquement distinctes Deux grilles sont dites symétriquement distinctes si l'une ne peut être dérivée de l'autre (par une ou plusieurs opérations de préservation de la symétrie).
Préservation de la symétrie Les opérations suivantes transforment toujours une grille valide en une autre grille valide :