Les mathématiques sont un jeu que l’on exerce selon des règles simples en manipulant des symboles ou des concepts qui n’ont en soi, aucune importance particulière. David Hilbert (1862-1943)
Le paradoxe du Sudoku est que la simplicité de ses contraintes engendre tout de même un casse-tête d’une étonnante complexité. Selon la structure de la solution du Sudoku et des cases qui sont vides au début, on peut se retrouver soit avec un casse-tête taquinant le débutant, soit avec un casse-tête exaspérant l’expert. Bien qu’il soit souvent possible dans d’autres jeux, comme les échecs et les mots-croisés, de gagner une vue d’ensemble en mémorisant une fraction des combinaisons, en revanche, au Sudoku, l’analyse directe de toutes les combinaisons dépasse rapidement les facultés des plus doués. Toutefois, il existe un grand nombre de techniques élémentaires qui permettent de rapidement réduire le nombre de combinaisons admissibles. C’est grâce à ces astuces, et beaucoup de pratique, qu’en 2012 Jan Mrozowski a complété 10 Sudokus en 54 minutes et 4 secondes, le couronnant ainsi Champion du Monde du Sudoku.
À partir des règles du Sudoku, nous déduirons une famille de techniques qui nous permettront d’exclure certains candidats des cases vides. Ces règles d’exclusion sont parmi celles utilisées par les experts, mais nous ne nous attarderons qu’à un échantillon représentatif de ces techniques et à leur formulation mathématique. Toutefois, celles que nous présenteront devraient permettre au lecteur assidu de facilement compléter la majorité des Sudokus de nos hebdomadaires régionaux.
Les règles du Sudoku
Le jeu du Sudoku commence avec une figure formée de 81 cases organisées en 9 rangées et 9 colonnes. De plus, les cases sont aussi organisées en 9 blocs de 9 cases, circonscrit par les lignes plus foncées dans la figure. Il est coutume d’appeler Sudoku la figure d’un jeu de Sudoku et de dire que les blocs, les rangées, et les colonnes forment les rangées virtuelles du Sudoku. Une fois résolu, chaque case du Sudoku contient exactement un chiffre entre 1 et 9, mais les cases du Sudoku sont au départ majoritairement vides. L’objectif du Sudoku est de déduire les chiffres des cases vides de la contrainte fondamentale:
Chaque rangée virtuelle doit contenir les chiffres 1 à 9 une et une seule fois.
Malheureusement, cette prescription ne nous indique nullement comment procéder. Nous verrons comment réinterpréter cette contrainte en techniques déductives pour découvrir le contenu des cases vides.
Avant de continuer, mentionnons quelques conventions que les amateurs partagent. Les lettres de a à i sont utilisées pour énumérer les rangées du haut vers le bas. Les colonnes sont identifiées de la gauche vers la droite par un chiffre entre 1 et 9. Pour les blocs, les joueurs utilisent les trois lettres des rangées et les trois chiffres des colonnes qui se rencontrent au bloc en question.
Exclusions naïves
Tous les joueurs de Sudoku, du néophyte au champion, débutent la résolution en appliquant une technique d’exclusion simple mais efficace qui consiste à exclure certains possibilités. Cette technique ne tient pas compte de toutes les contraintes mais est tout de même un excellent point de départ pour l’application d’exclusions plus complexes.
Soit une case vide d’un Sudoku et les trois listes de chiffres connus appartenant respectivement à la rangée, la colonne, et le bloc qui se partagent la case vide. Appelons ces listes
R = {les chiffres connus de la rangée},
C = {les chiffres connus de la colonne},
B = {les chiffres connus du bloc}.
À partir uniquement de cette information, la contrainte fondamentale nous permet seulement de conclure que l’ensemble \(L\) des chiffres qui sont candidats de la case vide, ou plus brièvement l’ensemble des candidats \(L\) de la case vide, est précisément l’ensemble des chiffres autres que ceux déjà connus, donc \(L = \overline{R ∪C ∪B}.\) L’objectif de l’exclusion naïve est d’exclure de {1, 2, …, 9} les chiffres qui apparaissent déjà dans \(R, C\) ou \(B\) et d’écrire la courte liste \(L\) dans la case vide. Selon \(L = \overline{R ∪C ∪B},\) le calcul de \(L\) doit commencer avec le calcul de l’union \(R∪C∪B\) avant de passer à l’identification des chiffres de 1 et 9 qui n’appartiennent pas à \(R ∪ C ∪ B.\) Ceci exigerait que l’on écrive l’ensemble \(R ∪ C ∪ B\) ailleurs sur un papier brouillon avant d’écrire la liste \(L\) dans la case vide, une procédure très peu commode.
La loi de De Morgan offre une alternative calculatoire que vous aurez peut-être déjà devinée. Appliquant cette loi à notre expression précédente pour la liste \(L\) des candidats, on déduit que
\[L = \overline{R ∪C ∪B} = \overline{R} ∩\overline{C} ∩\overline{B}.\]
Notions de la théorie des ensembles
Soit un ensemble $A,$ et deux sous-ensembles $B$ et $C$ de $A.$ On écrit $B \subset A$ et $C \subset A.$ Il existe plusieurs opérations élémentaires que l’on peut effectuer sur ces ensembles.
Le complément de $B$ dans $A,$ noté $\overline{B},$ est le sous-ensemble des éléments de $A$ qui ne sont pas dans $B.$
L’union de $B$ et de $C,$ noté $B ∪ C,$ est l’ensemble des éléments qui appartiennent soit à $B$, soit à $C.$
L’intersection de $B$ et $C,$ noté $B ∩ C,$ est l’ensemble des éléments qui appartiennent à la fois à $B$ et à $C.$
Ces opérations sont liées entre elles par les lois de De Morgan, qui sont en fait complètement évidentes
\[\overline{B∪C} =\overline{B}∩ \overline{C} \: \text{et} \: \overline{B∩C} =\overline{B}∪ \overline{C}.\]
La convention est de designer l’ensemble vide par le symbole $\varnothing.$
Cette nouvelle expression pour \(L\) indique qu’il est possible de calculer \(L\) en vérifiant systématiquement, pour les chiffres de 1 à 9, qu’ils n’appartiennent ni à \(R,\) ni à \(C,\) et ni à \(B.\) Pour chaque chiffre de 1 à 9, une telle vérification peut se faire visuellement en survolant les trois rangées virtuelles, et si le chiffre appartient à \(L,\) on peut immédiatement l’écrire en petit caractères dans la case vide avant de passer au prochain chiffre de la liste. On résume donc cette technique d’exclusion naïve de la manière suivante.
Pour chaque case vide, et pour chaque chiffre entre 1 et 9, écrivez ce chiffre dans la case vide s’il n’apparaît dans aucune des trois rangées virtuelles auquel appartient la case vide.
Le résultat de cette procédure est un Sudoku semblable à celui de la figure 1. C’est une opération répétitive mais simple et que l’on gagne à pratiquer. Pour la durée du reste de cet article, nous prendrons pour acquis que tout joueur de Sudoku débute la résolution de son Sudoku avec cette technique.
Figure 1 : Un Sudoku avec la liste des candidats obtenus à partir de l’exclusion naïve.
Exclusions nues et cachées
Quand vous êtes chanceux, l’exclusion naïve produit dans chaque case vide une liste ne contenant qu’un seul candidat, ce qui s’appelle un simplet nu. Toutefois, il existe très souvent une autre situation permettant d’identifier immédiatement le chiffre caché d’une case. Si un candidat d’une case ne se retrouve dans aucune autre case d’une des rangées virtuelles contenant la case, alors ce chiffre est la seule possibilité pour cette case, une situation nommée un simplet caché.
Figure 2 : Le 2 est un simplet nu en a5 et le 5 est un simplet caché en a7.
La notion de simplet caché s’explique bien à l’aide d’un exemple. Dans la rangée de la figure 2, les candidats des cases vides sont
C1={2,9}, C3={2,8,9}, C4={1,2,8},
C5={2}, C7 ={1,2,5,8,9}.
Si l’on regarde la septième case, on remarque que le chiffre 5 n’est candidat dans aucune autre case. Mathématiquement, ceci se résume en écrivant que 5 n’appartient pas à l’ensemble \(C_1 ∪ C_3 ∪ C_4 ∪ C_5\) mais qu’il appartient quand même à \(C_7,\)
\[\{5\}=\overline{(C_1∪C_3 ∪C_4 ∪C_5)}∩C_7.\]
Selon ce raisonnement, tous les simplets cachés du Sudoku peuvent être identifiés en visitant chaque case vide et, pour chaque candidat de la case, en vérifiant que le candidat ne se retrouve pas ailleurs dans chaque rangée virtuelle de la case.
Voici une deuxième manière beaucoup plus rapide d’identifier tous les simplets cachés, que nous justifierons plus loin,
Pour chaque rangée virtuelle et pour chaque chiffre entre 1 et 9, identifiez s’il est candidat d’une seule case. Si c’est le cas, il doit être le chiffre caché de la case.
En examinant l’application de cette méthode à l’exemple précédent, on peut comprendre son équivalence avec celle suggérée par l’expression initiale. Pour la rangée de la figure 2, supposons que l’on cherche à savoir si 5 est un simplet caché quelque part dans la rangée. En un coup d’oeil, on note les cases où 5 est candidat,
\[ \{5\} \cap C_1= \varnothing \Leftrightarrow 5 \in \overline{C_1} \\ \{5\} \cap C_3=\varnothing \Leftrightarrow 5 \in \overline{C_3} \\ \{5\} \cap C_4=\varnothing \Leftrightarrow 5 \in \overline{C_4} \\ \{5\} \cap C_5=\varnothing \Leftrightarrow 5 \in \overline{C_5} \\ \{5\} \cap C_7=\{5\} \Leftrightarrow 5 \in C_7 \]
On déduit alors que le chiffre 5 appartient aux intersections
\[\overline{C_1} \cap C_7, \overline{C_3} \cap C_7, \overline{C_4} \cap C_7, \overline{C_5} \cap C_7.\]
À l’aide de la loi de De Morgan, on conclut que 5 est un simplet caché de la septième case, car
En conclusion, les deux approches diffèrent dans l’ordre dans lequel la recherche se fait et dans les questions qu’on doit se poser, mais le résultat est le même.
Figure 3 : Les chiffres {1, 4, 8} forment un triplet caché en a1, a5, a6.
Les notions de simplet nu et de simplet caché ont des notions cousines de paires, triplets et plus généralement de k-tuplet, nus ou cachés.
Un k-tuplet nu d’une rangée virtuelle est un ensemble T de k chiffres pour lequel il existe k cases vides dont les candidats satisfont
\[C_1 \subset T, C_2 \subset T, \cdots, C_k \subset T.\]
Étant donné que les chiffres du k-tuplet nu sont les seuls occupants possibles de k cases, ils ne peuvent pas apparaître dans les autres cases et on peut exclure les membres de T de candidats de toutes les autres cases.
Un k-tuplet caché d’une rangée virtuelle avec \(k + j\) cases vides est un ensemble \(T\) de \(k\) chiffres pour lequel les \(k + j\) listes de candidats \(C_1, . . . ,C_k, C_{k+1}, . . . ,C_{k+j}\) peuvent s’énumérer de manière à ce que
\[T \subset C_1 \cup \cdots \cup C_k. \\ T \cap (_{Ck+1} \cup \cdots \cup C_{k+j})= \varnothing.\]
Étant donné que les k chiffres du k-tuplet caché doivent occuper les k premières cases vides, on peut exclure tous les autres chiffres \(C_{k+1} ∪ · · · ∪ C_{k+j}\) des listes \(C_1,…,C_k.\) Contrairement aux notions de simplet nu ou caché, l’objectif n’est pas de découvrir la position de certains chiffres mais plutôt de dire où ils ne peuvent pas apparaître. De plus chaque exclusion peut avoir un effet boule de neige et vous mener à découvrir de nouveaux k-tuplets nus ou cachés. Voici la méthodologie à suivre si vous désirez identifier ces exclusions.
- Procédez une rangée virtuelle à la fois.
- Éliminez les chiffres des simplets nus et cachés des autres cases des rangées virtuelles se partageant les cases des simplets identifiés.
- Déterminez visuellement s’il existe deux cases vides avec des listes identiques de deux candidats. Éliminez ces doublets nus de toutes les autres listes de candidats.
- Parmi les listes contenant 3 candidats ou plus, cherchez deux chiffres qui n’apparaissent que dans deux cases. Éliminez de vos deux cases les chiffres autres que ceux du doublet caché.
- Continuez successivement avec les k-tuplets nus et cachés, \(k ≥ 3.\)
Exclusions de Jedi
Dans cette configuration du Sudoku, la force est la logique.
Soit quatre cases vides à l’intersection de deux rangées et de deux colonnes. On dit qu’ils forment une aile-X1 s’il existe un chiffre n qui n’est candidat dans les deux rangées qu’à l’intersection des deux colonnes.
Bien que la définition d’une aile-X exclue déjà la présence de n dans les autres cases des deux rangées, comme nous expliquerons plus tard, cette configuration exclut aussi n des autres cases des deux colonnes. On aurait aussi pu définir une aile-X en inversant le rôle des rangées et des colonnes et l’exclusion aurait eu lieu dans les autres cases des deux rangées.
Figure 4 : Une exclusion de Jedi
L’exclusion de Jedi s’explique aisément dans un exemple concret comme celui du Sudoku de la figure 4. À l’intersection des rangées c, h et des colonnes 2, 7, on observe que le chiffre 3 n’est candidat que dans deux cases des rangées c et h. Soit que 3 appartienne à c2, soit qu’il appartienne à c7. Dans le premier cas, le 3 est alors exclu de c7 et de toutes les autres cases de la colonne 2. Dans la rangée h, le 3 ne peut donc plus appartenir à h2 et il doit donc appartenir à h7. La décision de placer le 3 en c2, permet de l’exclure de toutes les cases des colonnes 2 et 7 sauf c2 et h7. Vice versa, si le chiffre 3 était d’abord placé dans la case c7, alors une analyse semblable démontrerait que 3 ne peut appartenir à aucune des cases des colonnes 2 et 7 sauf c7 et h2. En conclusion, la présence d’une aile-X exclut le 3 des listes de candidats aux cases i2, a7 et f7. La valeur d’une exclusion dépend en grande partie de la facilité avec laquelle elle peut être utilisée. Pour une exclusion de ce type, la technique est identique à sa formulation.
Dans chaque rangée, identifiez les chiffres qui ne sont candidats que dans deux cases. Pour chaque chiffre, vérifiez s’il est candidat à l’intersection des deux colonnes avec une autre rangée. Si ce chiffre n’est pas candidat ailleurs dans cette nouvelle rangée, alors vous pouvez l’exclure des autres cases des deux colonnes.
Les joueurs aguerris du Sudoku cherchent aussi pour la présence d’un chiffre n qui soit candidat à l’intersection de k rangées et de k colonnes, mais pas ailleurs sur ces k rangées. Comme auparavant, cette configuration permet d’exclure le chiffre n des candidats dans toutes les cases des k colonnes à l’extérieur des k rangées. En anglais, la configuration avec k = 3 se nomme Swordfish et avec k = 4, elle se nomme Jellyfish. Toutefois, une configuration avec k ≥ 5 est sans intérêt car il est possible de montrer que les autres 9! k ≤ 4 colonnes et rangées formeront une exclusion de Jedi nécessairement plus simple.
La structure de Tuleja
Plutôt que de présenter une dernière tech- nique d’exclusion, cet article se terminera avec la présentation d’un résultat général de Gregory Tuleja, directeur du Williston Northhampton School, concernant la structure de la solution d’un Sudoku.
Théorème de Tuleja
Supposons qu’un joueur ait réussi à remplir toutes les cases vides du casse-tête initial, tout en satisfaisant la contrainte fondamentale, et qu’il ou elle admire joyeusement son œuvre.
Le contenu d’un triplet horizontal de blocs possède l’une des deux propriétés suivantes.
i) Il existe une subdivision de
{1,2,…,9}
en trois ensembles \(C_1, C_2, C_3\) de trois chiffres, telle que chaque triplet de cases horizontales d’un bloc est l’un de ces trois ensembles.
ii) Il existe une subdivision de
{1, 2, . . . , 9}
en quatre ensembles, les trois premiers \(C_1, C_2, C_3\) contiennent chacun deux chiffres et le dernier contient les trois derniers chiffres.
\[L =\overline{C_1∪C_2 ∪C_3}.\]
Chaque triplet de cases horizontales d’un bloc est l’union d’un des ensembles \(C_i\) et d’un des chiffres de \(L.\)
Grâce à la symétrie des Sudokus, il est évident que ce résultat s’applique autant aux triplets horizontaux de blocs qu’aux triplets verticaux de blocs. Dans la figure 5, le premier cas s’applique aux blocs des rangées abc. Plus précisément, dans le bloc abc, on a
\[C_1=\{1,2,3\},C_2=\{4,5,6\},C_3=\{7,8,9\}\]
et le triplet \(C_1\) apparaît en a123, c456 et b789. Le deuxième cas s’applique aux triplet de blocs des rangées def.
Ce très joli résultat peut aussi être utilisé dans la résolution de Sudoku bien qu’il ne se prête pas à une démarche algorithmique comme les techniques précédentes.
Figure 5 : Une illustration du théorème de Tuleja
Pour en s\(\alpha\)voir plus!
DAVIS, T. The Mathematics of Sudoku. 26 pages.
- L’expression aile-X est une traduction de X-Wing, le célèbre vaisseau de Luke Skywalker dans la série Star Wars. ↩
