Les mathématiques du Sudoku
Une grille de Sudoku est un petit objet mathématique, et l'on a démontré bien des choses à son sujet. Voici les principaux résultats, du plus simple au plus profond, chacun avec sa démonstration : complète quand elle tient en quelques lignes, son idée quand il a fallu un long article ou un ordinateur.
Équivalence directe
Le Sudoku est un problème de coloration de graphe
Théorème. Résoudre un Sudoku, c'est colorier avec 9 couleurs un graphe de 81 sommets, en respectant les couleurs qu'imposent les chiffres donnés. Chaque sommet a exactement 20 voisins.
Prenons un sommet par case, et relions deux sommets quand leurs cases partagent une ligne, une colonne ou un bloc. Les neuf chiffres deviennent neuf couleurs, et colorier le graphe, c'est donner une couleur à chaque sommet sans que deux voisins aient la même.
Démonstration
D'une solution à une coloration : donnons à chaque sommet la couleur du chiffre de sa case. Deux cases voisines partagent une ligne, une colonne ou un bloc ; elles contiennent donc des chiffres différents, et leurs sommets reçoivent des couleurs différentes.
D'une coloration à une solution : les neuf cases d'une ligne sont toutes voisines les unes des autres ; il leur faut donc neuf couleurs différentes. Comme il n'y en a que neuf, chacune apparaît exactement une fois dans la ligne. Il en va de même pour chaque colonne et chaque bloc : en relisant les couleurs comme des chiffres, on obtient une solution.
Le compte des voisines
Une case a 8 autres cases sur sa ligne, 8 sur sa colonne et 8 dans son bloc. Mais 2 cases de son bloc sont aussi sur sa ligne, et 2 sur sa colonne : elles ont été comptées deux fois.
8 + 8 + 8 − 2 − 2 = 20
Le graphe a donc 81 × 20 ÷ 2 = 810 arêtes, chacune comptée depuis ses deux extrémités. Et comme une ligne demande neuf couleurs et que neuf suffisent, le graphe en demande exactement neuf : son nombre chromatique vaut 9.
Dans My Sudoku
Vu ainsi, un Singleton nu est un sommet dont les 20 voisins utilisent déjà 8 des 9 couleurs : il ne lui en reste qu'une.
Source : Wikipédia : Mathématiques du sudoku.
Encodage logique
Le Sudoku est un problème de couverture exacte
Théorème. Une solution de Sudoku est un choix de 81 lignes, parmi les 729 d'une matrice de 0 et de 1 à 324 colonnes, qui couvre chaque colonne exactement une fois.
Chaque coup au Sudoku place un chiffre d dans une case (l, c), et chaque placement satisfait quatre contraintes à la fois :
- case : la case (l, c) contient un chiffre ;
- ligne : le chiffre d figure sur la ligne l ;
- colonne : le chiffre d figure dans la colonne c ;
- bloc : le chiffre d figure dans le bloc de (l, c).
Chaque famille compte 81 contraintes : 81 cases, et 9 chiffres pour chacune des 9 lignes, des 9 colonnes et des 9 blocs.
4 × 81 = 324 contraintes · 81 × 9 = 729 placements
Écrivons une matrice avec une ligne par placement et une colonne par contrainte, et un 1 là où le placement satisfait la contrainte. Chaque ligne contient exactement quatre 1. Placer 7 en L2C5, par exemple, couvre quatre colonnes :
- case L2C5
- un 7 sur la ligne 2
- un 7 dans la colonne 5
- un 7 dans le bloc 2
Démonstration
Une couverture exacte choisit des lignes de la matrice de sorte que chaque colonne contienne exactement un 1 parmi elles. Les 81 contraintes de case donnent à chaque case exactement un chiffre ; les contraintes de ligne, de colonne et de bloc placent chaque chiffre exactement une fois dans chaque ligne, chaque colonne et chaque bloc. C'est une solution du Sudoku ; inversement, les 81 placements d'une solution satisfont chaque contrainte une fois. Les chiffres donnés sont des lignes choisies d'avance.
couverture exacte ⟺ solution : 81 lignes sur 729
Dans My Sudoku
Beaucoup de programmes de résolution travaillent sur cette forme, dont l'algorithme X de Donald Knuth et ses « liens dansants » (Dancing Links) : ils explorent toujours d'abord la contrainte qui a le moins de possibilités. La recherche de My Sudoku fait de même avec les contraintes de case : elle essaie d'abord la case qui a le moins de chiffres possibles.
La matrice montre aussi que les deux singletons sont une seule idée : un Singleton nu est une contrainte de case, un Singleton caché une contrainte de ligne, de colonne ou de bloc, à laquelle il ne reste qu'un placement. Dans les deux cas, une colonne avec un seul 1.
Sources : Donald E. Knuth, Dancing Links (2000), Wikipédia : Mathématiques du sudoku.
Dénombrement par ordinateur, avec les symétries
Il existe 6 670 903 752 021 072 936 960 grilles
Théorème. Il y a exactement 6 670 903 752 021 072 936 960 façons de remplir une grille de 9 × 9 en respectant les règles, soit environ 6,67 × 10²¹. Une fois les symétries mises de côté, 5 472 730 538 sont essentiellement différentes.
Bertram Felgenhauer et Frazer Jarvis les ont comptées en 2005 ; Ed Russell et Frazer Jarvis ont compté peu après celles qui sont essentiellement différentes.
Pourquoi pas (9!)⁹
Chaque ligne peut être ordonnée de 9! = 362 880 façons ; on pourrait donc attendre (9!)⁹ grilles, environ 1,1 × 10⁵⁰. Mais ce nombre compte n'importe quelles neuf lignes empilées, chiffres répétés dans les colonnes et les blocs compris : les contraintes ne sont pas indépendantes, et le vrai nombre est bien plus petit.
Une partie vérifiable : un multiple de 9!
Renommons les chiffres d'une grille : chaque 1 devient un 5, chaque 5 un 2, et ainsi de suite, selon l'une des 9! façons de permuter les neuf chiffres. Chaque ligne, chaque colonne et chaque bloc contient toujours chaque chiffre une fois : le résultat est encore une grille. Deux renommages différents d'une grille donnent deux grilles différentes, et renommer une grille renommée redonne une grille de la même famille. Les grilles se rangent donc en familles d'exactement 9! grilles, et leur nombre est un multiple de 9! :
6 670 903 752 021 072 936 960 = 9! × 18 383 222 420 692 992
Comment le compte a été fait
Felgenhauer et Jarvis ont fixé le premier bloc à 1, 2, …, 9 dans l'ordre de lecture, ce qui rend compte du 9!, puis compté les façons de compléter les trois premières lignes : 2 612 736, soit 56 × 6⁶. Beaucoup se ressemblent, l'une se changeant en l'autre quand on échange des colonnes ou qu'on renomme des chiffres, et se complètent d'autant de façons ; en les regroupant, ils ont fait compter par ordinateur, pour chaque groupe, les façons de remplir les six dernières lignes. Le total se décompose ainsi, son dernier facteur étant un nombre premier :
9! × 72² × 2⁷ × 27 704 267 971
Les grilles essentiellement différentes
Retourner une grille selon sa diagonale, échanger deux bandes ou deux piles de blocs, deux lignes d'une même bande ou deux colonnes d'une même pile, ou renommer ses chiffres donne une grille qui est au fond la même. Ces opérations forment un groupe de 9! × 3 359 232 éléments. Diviser le compte par ce nombre donne environ 5 472 448 000 : c'est proche, mais faux. Quelques grilles sont symétriques, inchangées par une opération, si bien que leur famille est plus petite que le groupe et que la division les sous-compte. Le lemme de Burnside, qui compte les grilles que chaque opération laisse inchangées, rétablit le compte :
5 472 730 538 grilles essentiellement différentes
Le même compte à la main, en 4 × 4
| 1 | 2 | 3 | 4 |
| 3 | 4 | 1 | 2 |
| 2 | 1 | 4 | 3 |
| 4 | 3 | 2 | 1 |
Avec quatre chiffres et des blocs de 2 × 2, tout le compte tient en quelques lignes. Remplissons le premier bloc : 4! = 24 façons, et quitte à renommer les chiffres, on peut supposer que c'est 1 2 / 3 4. Le reste de la ligne 1 contient alors 3 et 4, le reste de la ligne 2 contient 1 et 2, dans un ordre ou dans l'autre : 4 façons. De même pour le reste des colonnes 1 et 2 : 4 façons. Sur ces 16 combinaisons, 12 laissent exactement une façon de remplir le dernier bloc, et 4 n'en laissent aucune :
24 × 12 = 288 grilles
Parmi les carrés latins
Une grille est un carré latin d'ordre 9, chaque chiffre une fois par ligne et par colonne, avec en plus la règle des blocs. Il existe 5 524 751 496 156 892 842 531 225 600 carrés latins d'ordre 9 : les blocs n'en gardent qu'environ un sur 828 000.
Sources : Frazer Jarvis, Sudoku enumeration problems, OEIS A002860, Wikipédia : Mathématiques du sudoku.
Démonstration en quelques lignes
Au moins huit valeurs différentes parmi les chiffres donnés
Théorème. Dans un Sudoku à solution unique, les chiffres donnés prennent au moins huit des neuf valeurs possibles.
Huit valeurs différentes, et non huit chiffres donnés.
Démonstration
Supposons que deux chiffres, par exemple 4 et 7, ne figurent pas parmi les chiffres donnés. Prenons une solution et échangeons-y partout les 4 et les 7.
Chaque ligne contenait un 4 et un 7, et les contient toujours : ils ont seulement échangé leurs places. Il en va de même pour chaque colonne et chaque bloc ; la nouvelle grille est donc aussi une solution. Elle diffère de la première partout où il y avait un 4 ou un 7, et elle respecte tous les chiffres donnés, puisqu'aucun n'est un 4 ou un 7. La grille aurait deux solutions. Il peut donc manquer au plus une valeur parmi les chiffres donnés.
À la limite
La grille à 17 chiffres donnés plus bas est pile à la limite : ses chiffres donnés prennent huit valeurs, sans aucun 6.
Sur une grille de N × N, le même raisonnement exige N − 1 symboles différents parmi les chiffres donnés.
Source : Wikipédia : Mathématiques du sudoku.
Démonstration par construction
Quatre cases peuvent suffire à gâcher une grille
Théorème. Si quatre cases aux coins d'un rectangle, sur deux lignes, deux colonnes et deux blocs, contiennent a b / b a dans une solution et qu'aucune n'est un chiffre donné, la grille a une seconde solution.
Démonstration
| a | b |
| b | a |
| b | a |
| a | b |
Échangeons a et b dans les quatre cases. Chacune des deux lignes contient toujours un a et un b, et chacune des deux colonnes aussi. Les quatre cases se répartissent deux par deux dans deux blocs, chaque paire contenant un a et un b : après l'échange, les blocs sont toujours justes. Rien d'autre ne change : la nouvelle grille est aussi une solution, et elle respecte tous les chiffres donnés, puisqu'aucune des quatre cases n'en est un.
Les ensembles inévitables
Un tel ensemble de cases, dont l'une au moins doit être un chiffre donné, s'appelle un ensemble inévitable. Ici, une grille de 77 chiffres donnés, avec seulement quatre cases vides, a deux solutions : le nombre de chiffres donnés dit peu de chose, leur place en dit beaucoup.
Jamais moins de quatre cases
Inversement, deux solutions différentes d'une même grille diffèrent toujours sur au moins quatre cases. Une grille de 78 chiffres donnés ou plus n'a donc jamais deux solutions, et le rectangle est la plus petite ambiguïté possible.
Regardons les cases où les deux solutions diffèrent. Une ligne ne peut pas en contenir une seule : ses huit autres cases contiendraient les mêmes huit chiffres dans les deux solutions, ce qui laisserait le même neuvième chiffre pour la dernière. Une ligne, ou une colonne, qui contient l'une de ces cases en contient donc au moins deux. Prenons-en une, x. Sa ligne en contient une autre, y ; sa colonne une autre, z ; et la ligne de z une autre, w. Cette case w n'est ni x, qui n'est pas sur la ligne de z, ni y, qui est sur la ligne de x. Cela fait quatre cases différentes.
Dans My Sudoku
La technique du Rectangle unique retourne ce résultat : comme une vraie grille n'a qu'une solution, un tel rectangle ne peut jamais apparaître, et l'on peut retirer les candidats qui le formeraient.
Source : Wikipédia : Mathématiques du sudoku.
Preuve exhaustive par ordinateur
Une grille demande au moins 17 chiffres donnés
Théorème. Un Sudoku de 9 × 9 à solution unique a au moins 17 chiffres donnés. Il en existe avec 17 ; aucun avec 16.
Gary McGuire, Bastian Tugemann et Gilles Civario l'ont démontré en 2012, par une recherche informatique exhaustive. On connaît des dizaines de milliers de grilles à 17 chiffres donnés.
Idée de la preuve
La preuve repose sur les ensembles inévitables vus plus haut : des ensembles de cases d'une grille que les chiffres donnés doivent toucher, faute de quoi leurs chiffres pourraient être réarrangés en une seconde solution. Des chiffres donnés qui déterminent une grille doivent rencontrer chacun de ses ensembles inévitables : ils forment un ensemble transversal (hitting set) de cette famille. La recherche s'est déroulée ainsi :
- pour chacune des 5 472 730 538 grilles essentiellement différentes, trouver un grand nombre de ses ensembles inévitables ;
- énumérer tous les ensembles de 16 cases qui les rencontrent tous, la partie difficile, pour laquelle les auteurs ont conçu un nouvel algorithme ;
- vérifier si les chiffres de la grille dans ces 16 cases la déterminent ;
- ce n'est jamais le cas.
C'est une vraie démonstration, mais que seul un ordinateur peut mener : personne ne pourrait la vérifier à la main.
La même preuve en miniature
Sur les grilles de 4 × 4, la même recherche est minuscule. Parmi les 288 grilles, aucune n'est déterminée par 3 de ses cases, alors que certaines le sont par 4 : le minimum y est de 4, ce qu'un ordinateur vérifie en un instant en essayant tous les cas.
Minimal n'est pas minimum
Une grille est minimale quand retirer n'importe lequel de ses chiffres donnés laisse passer une seconde solution, et minimum quand aucune grille n'en a moins : 17. Une grille peut être minimale avec 25 chiffres donnés, dont aucun ne peut partir, alors que d'autres grilles se contentent de moins.
À part celles du niveau Très facile, les grilles de My Sudoku sont minimales : il remplit une grille au hasard, puis retire les chiffres un à un dans un ordre aléatoire, en remettant tout chiffre dont le retrait laisse passer une seconde solution. Ses grilles finissent le plus souvent avec 22 à 27 chiffres donnés.
Sources : Gary McGuire, Bastian Tugemann, Gilles Civario, There is no 16-Clue Sudoku (2012), Wikipédia : Mathématiques du sudoku.
Démonstration par réduction
Le Sudoku est NP-complet
Théorème. Décider si un Sudoku partiellement rempli de n² × n² cases, à blocs de n × n, a une solution est un problème NP-complet.
Takayuki Yato et Takahiro Seta l'ont démontré en 2003, à partir des carrés latins. Un problème est NP-complet quand il a deux propriétés : il est dans NP, c'est-à-dire qu'une solution proposée se vérifie rapidement, et il est NP-difficile, c'est-à-dire que tout problème de NP peut s'y ramener en temps polynomial. La démonstration a donc deux parties.
Partie A : le Sudoku est dans NP
Prenons une grille remplie de côté N = n². Pour la vérifier, on parcourt ses N lignes, ses N colonnes et ses N blocs, et on la compare aux chiffres donnés. Vérifier qu'une ligne contient une fois chaque symbole de 1 à N demande environ N opérations ; les lignes en demandent donc environ N × N, et de même les colonnes et les blocs :
3 × N × O(N) = O(N²)
C'est un nombre d'opérations proportionnel aux N² cases de la grille. Trouver une solution peut être difficile ; en vérifier une est rapide.
Partie B : le Sudoku est NP-difficile
Un carré latin d'ordre N remplit une grille de N × N avec N symboles, chacun une fois par ligne et par colonne : les règles du Sudoku, sans les blocs.
| 1 | 2 | 3 |
| 2 | 3 | 1 |
| 3 | 1 | 2 |
Charles Colbourn a démontré en 1984 que décider si un carré latin partiellement rempli peut être complété est NP-complet. Yato et Seta transforment n'importe quel carré latin partiellement rempli L en un Sudoku partiellement rempli S(L), en temps polynomial : les chiffres donnés de S(L) sont disposés de sorte que ses cases libres ne puissent être remplies que comme L peut être complété. Chaque complétion de L donne exactement une solution de S(L), et réciproquement (une réduction parcimonieuse) :
L est complétable ⟺ S(L) a une solution
Une méthode rapide pour le Sudoku donnerait donc une méthode rapide pour les carrés latins. Comme compléter un carré latin est NP-complet, le Sudoku est NP-difficile ; avec la partie A, il est NP-complet.
Ce que cela ne veut pas dire
Cela ne veut pas dire que les grilles de 9 × 9 sont difficiles : leur taille est fixe, et un ordinateur résout n'importe laquelle en un instant. La NP-complétude concerne toute la famille, quand n grandit : on ne connaît aucune méthode qui résolve chaque grille en un temps polynomial en sa taille, et en trouver une prouverait que P = NP, l'une des grandes questions ouvertes des mathématiques, dotée d'un prix d'un million de dollars par l'institut Clay.
Une seconde solution : ASP-complet
Yato et Seta démontrent davantage : étant donné un Sudoku et l'une de ses solutions, décider s'il en a une autre est tout aussi difficile. Le problème est ASP-complet (de l'anglais Another Solution Problem, « problème d'une autre solution »). C'est la question que se pose tout créateur de grilles, puisqu'une vraie grille a une solution unique.
Le générateur de My Sudoku ne laisse donc rien au hasard : après chaque chiffre qu'il retire, une recherche tente de trouver une seconde solution, en s'arrêtant à la première trouvée, et s'il en trouve une, le chiffre est remis.
Sources : Takayuki Yato, Takahiro Seta, Complexity and Completeness of Finding Another Solution and Its Application to Puzzles, IEICE Transactions on Fundamentals E86-A (2003), Charles J. Colbourn, The complexity of completing partial Latin squares (1984), Wikipédia : Mathématiques du sudoku.
En résumé
| Résultat | Nature de la preuve |
|---|---|
| Le Sudoku est un problème de coloration de graphe | Équivalence directe |
| Le Sudoku est un problème de couverture exacte | Encodage logique |
| Il existe 6 670 903 752 021 072 936 960 grilles | Dénombrement par ordinateur, avec les symétries |
| Au moins huit valeurs différentes parmi les chiffres donnés | Démonstration en quelques lignes |
| Quatre cases peuvent suffire à gâcher une grille | Démonstration par construction |
| Une grille demande au moins 17 chiffres donnés | Preuve exhaustive par ordinateur |
| Le Sudoku est NP-complet | Démonstration par réduction |