Mathématiques du sudoku

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.

Le nombre de grilles complètes possibles est de 9! × 72² × 2⁷ × 27 704 267 971 (soit 6 670 903 752 021 072 936 960 grilles ≈ 6,67 × 10²¹[11] - [12] - [13]).

Le dernier facteur est un nombre premier. Ce résultat a été prouvé en 2005 par Bertram Felgenhauer et Frazer Jarvis[14] 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

1. permutations des 9 nombres
2. échange des lignes avec les colonnes (transposition)
3. permutation des lignes dans une bande (en ligne)
4. permutation des colonnes dans une pile (en colonne)
5. permutation des bandes en ligne
6. 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 5 472 730 538 grilles non équivalentes[15] - [13].

À 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 janvier 2012 par une équipe irlandaise[16] - [13]. Une liste de l'ensemble des sudokus à solution unique ayant 17 cases remplies a été établie par des japonais[9] - [17].

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 (c.-à-d. 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.

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).

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 = 3 359 232.

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.

Pour des grandes valeurs de L et C, la méthode de Kevin Kilfoil[18] (généralisée par la suite[19]) 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 les 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 :

${\displaystyle {\mbox{Nombre de grilles}}\simeq {\dfrac {b_{L,C}^{C}\times b_{C,L}^{L}}{(LC)!^{LC}}}}$

où b_{L, C} est le nombre de manières de compléter un sudoku avec L régions (d'une taille de L × C) horizontalement adjacentes. L'algorithme de Pettersen[20], implémenté par Silver[21] 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.

Dimensions	Nombre de bandes	Auteur(s)	Vérification formelle
2 × C	(2C)! (C!)2	(évident)	Oui
3 × C	${\displaystyle (3C)!(C!)^{6}\sum _{k=0\ldots C}{C \choose k}^{3}}$	Pettersen	Oui
4 × C	(Voir ci-dessous pour le résultat mathématique.)	Pettersen	Oui
4 × 4	16! × 4!12 × 1 273 431 960 = c. 9.7304 × 1038	Silver	Oui
4 × 5	20! × 5!12 × 879 491 145 024 = c. 1.9078 × 1055	Russell	Oui
4 × 6	24! × 6!12 × 677 542 845 061 056 = c. 8.1589 × 1072	Russell	Oui
4 × 7	28! × 7!12 × 563 690 747 238 465 024 = c. 4.6169 × 1091	Russell	Oui
(Des calculs jusqu'à 4 × 100 ont été effectués par Silver, mais ne sont pas indiqués ici.)
5 × 3	15! × 3!20 × 324 408 987 992 064 = c. 1.5510 × 1042	Silver	Oui#
5 × 4	20! × 4!20 × 518 910 423 730 214 314 176 = c. 5.0751 × 1066	Silver	Oui#
5 × 5	25! × 5!20 × 1 165 037 550 432 885 119 709 241 344 = c. 6.9280 × 1093	Pettersen/Silver	Non
5 × 6	30! × 6!20 × 3 261 734 691 836 217 181 002 772 823 310 336 = c. 1.2127 × 10123	Pettersen/Silver	Non
5 × 7	35! × 7!20 × 10 664 509 989 209 199 533 282 539 525 535 793 414 144 = c. 1.2325 × 10154	Pettersen/Silver	Non
5 × 8	40! × 8!20 × 39 119 289 737 902 332 276 642 894 251 428 026 550 280 700 096 = c. 4.1157 × 10186	Pettersen/Silver	Non

^{# : même auteur mais avec une autre méthode}

L'expression pour le cas 4 × C est : ${\displaystyle (4C)!(C!)^{12}\sum _{a,b,c}{\left({\dfrac {C!^{2}}{a!b!c!}}\times \sum _{\begin{matrix}k_{12},k_{13},k_{14},\\k_{23},k_{24},k_{34}\end{matrix}}{{a \choose k_{12}}{b \choose k_{13}}{c \choose k_{14}}{c \choose k_{23}}{b \choose k_{24}}{a \choose k_{34}}}\right)^{2}}}$

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

Plusieurs types de contraintes existent sur des sudokus avec des régions de 3 × 3. 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 sudokus sont spéciaux dans le sens où certaines opérations ont le même effet que le renommage des chiffres :

Le sudoku classique avec une grille de 9 × 9, 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[22], lesquelles sont uniques. Parmi ces 39 422 grilles, aucune d'entre elles n'est isomorphe à 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 vraisemblance, permet de déduire que le nombre de ces grilles minimales s'élève à environ 34 550. 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 permettrait 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 fourni des grilles qui étaient déjà dans la liste de Royle[23] - [24], ce qui renforce l'idée de la quasi-complétude de l'ensemble fourni par Royle.

Un 3doku

Des contraintes supplémentaires (avec des sudokus 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[25], des grilles avec 12 valeurs ont été démontrées par Glenn Fowler. Rien n'indique que cette borne minimale ne peut être réduite.
• Hypercube[26], des grilles avec 8 valeurs ont été proposées par Guenter Stertenbrink.
• Magic Sudoku[27], 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[28], Gordon Royle a donné un exemple avec 17 valeurs, borne supposée minimale.
• NRC Sudoku[29], Andries Brouwer a découvert un exemple avec 11 valeurs. On ne sait pas s'il est possible de faire mieux.

Une région peut être décrite par ses dimensions : L × C 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 2 × 6 a le même nombre de cases que celle de 3 × 4.

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 N × N 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 3 × 3 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.

Les Du-sum-oh[30] 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[31]. Il a donné plusieurs exemples.

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 commencer la grille n'est pas connue, ni conjecturée.

Une variante proposée par Miyuki Misawa[32] 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'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! = 362 880 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.