Mathématiques du Sudoku

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 nombres, de façon à ce que dans chaque ligne, chaque colonne et chaque région les nombres 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.

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 Sudoku classiques ont un N égal à 9 avec des régions de 3x3 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é algorithme 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 2005 . 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.

Le problème de placer des chiffres sur une grille de n×n comprenant n×n régions est prouvé NP-complet

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,
• $\lceil \frac{x-1}{3}\rceil =\lceil \frac{x^{\prime }-1}{3}\rceil$ et $\lceil \frac{y-1}{3}\rceil =\lceil \frac{y^{\prime }-1}{3}\rceil$ (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 dessus point 4 : nombre de grilles complètes possibles)

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 que 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 garantir 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 (en). Un résultat publié en 2007, dévoile que pour qu'un sudoku ait une solution unique, il est nécessaire que 8 des 9 chiffres soit dévoilés. [2] et (en) [3]), alors que 18 est le nombre minimum de dévoilés pour les grilles 9×9 symétriques.

Le nombre de grilles complètes possibles est inférieur à 9! qui correspond au nombre de façons de construire les régions sans tenir compte des contraintes sur les lignes et les colonnes.

En 2005, Bertram Felgenhauer et Frazer Jarvis ont prouvé que ce nombre de grilles était de :

6 670 903 752 021 072 936 960≈6,67.10 (pour plus de détails, voir (en) [4] et suite A107739 de l’OEIS).

Ce nombre est égal à :

9!×72×2×27 704 267 971

Le dernier facteur est un nombre premier. Ce résultat a été prouvé 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. Jarvis et Russell ont par la suite montré qu'en tenant compte des symétries, il y avait 5 472 730 538 solutions [5] (pour plus de détails, voir (en) [6] et suite A109741 de l’OEIS).

En revanche, à 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 problème de savoir combien de cases remplies sont nécessaires au préalable pour rendre la résolution unique est, à ce jour, sans réponse. Le meilleur résultat, obtenu par des Japonais, est de 17 cases sans contrainte de symétrie. [7] [8]. Rien ne dit que ce ne soit pas possible avec moins de nombres. Gordon Royle indique que deux résolutions sont considérées comme différentes si elles ne peuvent pas être transformées l'une vers l'autre (ou l'inverse) grâce à une combinaison des opérations suivantes :

1. permutations des 9 nombres
2. échange des lignes avec les colonnes (transposition)
3. permutation des lignes dans un seul bloc
4. permutation des colonnes dans un seul bloc
5. permutation des blocs sur une ligne de blocs
6. permutation des blocs sur une colonne de blocs

On remarque l'analogie avec les opérations matricielles en algèbre linéaire.

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 9x9 cases, il y a ainsi 3 bandes et 3 piles.

Un Sudoku correctement conçu a une et une seulement solution : la grille finale est unique, mais la résolution à partir de la grille partielle peut toutefois prendre des chemins différents.

Formalisation des différentes variantes

Une région peut être décrite par ses dimensions : LxC où L est le nombre de lignes et C le nombre de colonnes dans la région. Dans la version classique du Sudoku, L = C = 3. Cela implique qu'il existe L régions par bande et C régions par pile. Il est plus pratique de mentionner la taille de la région plutôt que le nombre d'éléments car une région de 2x6 a le même nombre de cases que celle de 3x4.

La découpe suivante peut être adoptée pour classifier grossièrement les variantes :

• régions rectangulaires
• régions carrées
• régions irrégulières (polyomino)

Des contraintes supplémentaires permettent de mieux cibler le type de jeu.

Un Sudoku carré de NxN régions possède plusieurs propriétés respectées pour tous ses sous-éléments, en plus de la règle classique de l'absence de doublons. En effet, chaque ligne et chaque colonne a une intersection avec N régions et partage N cases avec chacune d'entre elles. Le nombre de bandes et de piles est aussi égal à N. Le Sudoku rectangulaire n'a pas ces propriétés.

Le Sudoku avec des régions de 3x3 cache une autre propriété qui lui est propre : N est le nombre de sous-unités considérées dans le jeu, à savoir trois : la ligne, la colonne et la région.

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 (ie. 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 3x3, les conventions pour l'affichage du contenu de la grille sont les suivantes : les bandes sont labelisées du haut vers le bas, les piles de la gauche vers la droite. Les régions sont donc numérotés 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 3x3 :

• 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 Lde 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.

La réponse à la question « Combien y a-t-il de Sudoku ? » 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 (ie. 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 tout 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.

É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 :

• changer le label de chaque symbole (9!)
• permutations des bandes (3!)
• permutations des piles (3!)
• permutations des lignes dans une bande (3!)
• permutations des colonnes dans une pile (3!)
• réflexion, transposition, rotation de 90° (avec l'une de ces opérations et les permutations, il est possible de déduire les autres opérations, ce qui fait que ces opérations ne contribuent qu'avec un facteur de 2).

Ces opérations définissent une relation de symétrie entre deux grilles équivalentes. En excluant le changement de labels, et en considérant les 81 valeurs présentes dans la grille, ces opérations forment un sous-groupe du groupe symétrique S₈₁ avec un ordre 3!×2 = 3359232.

Identifier les solutions grâce au lemme de Burnside

Pour une solution, l'ensemble des solutions équivalentes qui peut être obtenu en utilisant ces opérations (sauf le renommage des valeurs), forme une orbite du groupe symétrique. Le nombre de solutions symétriquement distinctes est ainsi le nombre d'orbites, une valeur qui peut être calculée grâce au lemme de Burnside. Les points fixes de la méthode de Burnside sont des solutions qui ne diffèrent que par le renommage. Grâce à cette technique, Jarvis Russell a calculé le nombre de solutions symétriquement distinctes : 5 472 730 538.

Bandes du Sudoku

Pour des valeurs L et C larges, la méthode de Kevin Kilfoil (généralisée par la suite ) est utilisée pour estimer le nombre de façons de compléter une grille. Cette méthode part du principe que les contraintes sur lignes et les colonnes sont, pour une première approximation, des variables aléatoires conditionnellement indépendantes eu égard à la contrainte sur la région. Des calculs algébriques permettent d'aboutir à la formule de Kilfoil-Silver-Pettersen :

où b_{L, C} est le nombre de manières de compléter un Sudoku avec L régions (d'une taille de LxC) horizontalement adjacentes. L'algorithme de Pettersen , implémenté par Silver est actuellement la technique la plus rapide connue pour évaluer de manière exacte les valeurs b_{L, C}.

Le compte des bandes pour les problèmes dont "le nombre total de grilles de Sudoku est inconnu" est donné ci-dessous. Comme dans le reste de cet article, les dimensions correspondent à celles des régions.

L'expression pour le cas 4×C est :

avec :

la somme extérieure s'applique sur tous les a,b,c tel que 0⇐a,b,c et a+b+c=2C

la somme intérieure s'applique sur tous les k₁₂,k₁₃,k₁₄,k₂₃,k₂₄,k₃₄ = 0 tel que

k₁₂,k₃₄ = a    et

k₁₃,k₂₄ = b    et

k₁₄,k₂₃ = c    et

k₁₂+k₁₃+k₁₄ = a-k₁₂+k₂₃+k₂₄ = b-k₁₃+c-k₂₃+k₃₄ = c-k₁₄+b-k₂₄+a-k₃₄ = C

Sudoku avec des contraintes additionnelles

Plusieurs types de contraintes existent sur des Sudokus avec des régions de 3x3. Les noms n'ayant pas été standardisés, les liens externes pointent vers les définitions :

Tous les Sudokus sont valides (unicité des nombres dans les lignes, colonnes et régions) après l'application des opérations qui préservent les propriétés du groupe du Sudoku. Certains Sudoku sont spéciaux dans le sens où certaines opérations ont le même effet que le renommage des chiffres :

Les grilles correctement réalisées doivent avoir une et une seule solution. Une grille est dite irréductible ou minimale si elle est valide et si le retrait d'un chiffre supplémentaire entraîne son invalidité (i.e. elle n'admet plus de solution unique). Il est possible de créer des grilles minimales avec un nombre différent de valeurs initiales. Cette section décrit les propriétés relatives à ce problème.

Sudoku classique

Le Sudoku classique avec une grille de 9x9, soit 81 cases, est pour l'instant limité par une borne inférieure de 17 valeurs initiales, ou 18 quand les positions des chiffres initiaux peuvent être tournées de 90°. Il existe une conjecture qui stipule que cette borne de 17 est la meilleure possible, mais il n'existe pas de preuve formelle, seulement une recherche exhaustive avec des grilles aléatoires :

• Gordon Royle a compilé une liste de grilles avec 17 valeurs , lesquelles sont uniques. Parmi ces 39422 grilles, aucune d'entre elles n'est isomorphique à une autre grille ou contient une solution avec 16 valeurs initiales.
• Une construction indépendante de 700 grilles distinctes a permis de découvrir 33 autres grilles qui n'apparaissaient pas dans la liste de Royle. Une estimation d'après le maximum de la vraisemblance, permet de déduire que le nombre de ces grilles minimales s'élève à environ 34550. Si les méthodes sont vraiment aléatoires et indépendantes, alors la probabilité de trouver une construction valide avec 16 valeurs initiales est faible. En effet, une seule de ces hypothétiques grilles permettraient d'obtenir 65 nouvelles grilles avec 17 valeurs initiales, résultats qui ne sont pas apparus dans les recherches précédentes. Mais en l'absence d'une preuve formelle, ce fait ne peut être confirmé ou infirmé.
• D'autres recherches aléatoires ont fournis des grilles qui étaient déjà dans la liste de Royle , ce qui renforce l'idée de la quasi-complétude de l'ensemble fourni par Royle.

Sudoku avec d'autres contraintes

Des contraintes supplémentaires (avec des Sudoku dont les régions font 3×3) changent le nombre de valeurs minimales nécessaires pour aboutir à une solution unique :

• 3doku : aucun résultat connu à ce jour (2006)
• Groupes disjoints , des grilles avec 12 valeurs ont été démontrées par Glenn Fowler. Rien n'indique que cette borne minimale ne peut être rabaissée.
• Hypercube , des grilles avec 8 valeurs ont été proposées par Guenter Stertenbrink.
• Magic Sudoku , un exemple avec 7 valeurs a été publié par Guenter Stertenbrink. Ici encore, on ne sait pas s'il s'agit véritablement de la borne minimale.
• Sudoku X , Gordon Royle a donné un exemple avec 17 valeurs, borne supposée minimale.
• NRC Sudoku , Andries Brouwer a découvert un exemple avec 11 valeurs. On ne sait pas s'il est possible de faire mieux.

Sudoku avec des régions irrégulières

Les Du-sum-oh remplacent les régions de 3×3 (ou plus généralement L×C) par des régions irrégulières avec une taille fixe. Bob Harris a prouvé qu'il était toujours possible de créer des du-sum-ohs avec N-1 valeurs initiales sur une grille de N par N . Il a donné plusieurs exemples.

Killer Sudoku

Dans le Samunamupure ou Killer Sudoku, les régions ont non seulement des formes irrégulières mais également des tailles différentes. Les règles d'unicité des nombres dans les lignes, régions et colonnes s'appliquent toujours. Les indications initiales sont données sous la forme de sommes de valeurs dans les régions (par exemple, une région de 4 cellules avec une somme de 10 contiendra les chiffres 1, 2, 3, 4 selon un certain ordre). Le nombre minimal de valeurs nécessaires pour débuter la grille n'est pas connue, ni conjecturée.

Une variante proposée par Miyuki Misawa remplace les sommes par des relations : les indications sont des symboles =, <, >, montrant les valeurs relatives pour certaines régions adjacentes. Un exemple avec seulement 8 relations est donné, mais on ne sait pas si ce nombre est la borne inférieure.

L'approche décrite ici est historiquement la première stratégie employée pour énumérer les solutions d'une grille de Sudoku classique (régions de 3x3 dans une grille de 9x9). Elle a été proposée par Felgenhauer et Jarvis .

Aperçu

L'analyse débute par l'étude des permutations de la première bande utilisée dans des solutions valides. Une fois que la classe d'équivalence et les symétries de cette bande, pour des solutions partielles, sont identifiées, on s'intéresse aux deux autres bandes qui sont construites et comptées pour chaque classe d'équivalence. En effectuant la somme de l'ensemble des combinaisons, on obtient le nombre total de solutions, soit 6 670 903 752 021 072 936 960 (environ 6.67×10).

Afin de réduire l'espace de recherche, on part du principe que le renommage (par exemple changer le '1' en '2' et vice-versa) des cases produit une solution équivalente. Une grille autorise 9! = 362880 renommages de ce type : un chiffre choisi parmi les 9 chiffres possibles est attribué au premier type de case, un chiffre parmi les 8 restants est attribué au deuxième type de case, un chiffre parmi les 7 restants est attribué au troisième type de case, etc.