Sudoku

Carré latin d’ordre 9 composé de neuf compartiments d’ordre 3. Chacun des chiffres de 1 à 9 doit apparaître une seule fois dans chacune des lignes et dans chacune des colonnes du carré d’ordre 9. De plus, chacun de ces neuf chiffres doit apparaître une seule fois dans chacun des neuf compartiments. Ce carré latin apparut dans les journaux en 2004 et connut un succès remarquable qui se rapproche de celui du taquin en 1870 et du cube de Rubik en 1980. Dans la grille de 81 cases, un certain nombre de chiffres sont déjà inscrits. Le problème consiste à compléter la grille. Normalement, une grille ne doit comporter qu’une solution. Voici l’exemple d’une grille comportant 30 chiffres inscrits :

On attribue à tort la paternité du sudoku à Leonhard Euler (1701-1783), un mathématicien suisse. Ce dernier est connu pour ses travaux sur les carrés gréco-latins. Le sudoku n'est pas un carré gréco-latin mais un carré latin à compartiments. La première version du sudoku a été publiée dans un magazine américain au début des années 1980, puis importée au Japon en 1986. Wayne Gould, un juge néo-zélandais retraité à Hong Kong, a découvert le sudoku en 1997 et a imaginé un logiciel permettant de créer des grilles. En 2004, il a vendu des grilles à une soixantaine de journaux dans une vingtaine de pays. Sudoku est un terme japonais qui signifie chiffre unique. Voici deux stratégies de base qui permettent de compléter une grille :

1. La stratégie des trois compartiments 
On vérifie dans chaque groupe de trois compartiments horizontalement ou verticalement si un ou des chiffres peuvent être inscrits. Par exemple, dans les trois compartiments supérieurs à l’horizontale, on peut écrire un 2 au premier rang de la troisième ligne du deuxième compartiment. Dans les trois compartiments à droite à la verticale, on peut écrire un 7 en bas de la première colonne du compartiment supérieur.

2. La stratégie de la croisée 
On choisit une case et on vérifie lesquels chiffres y sont possibles. Par exemple, on pointe la case en haut à gauche du compartiment central de gauche. Cette case ne peut contenir que 9.

Il existe de nombreuses variantes de cette récréation, notamment des grilles 4 × 4 avec des compartiments 2 × 2, des grilles 5 × 5 dont les compartiments sont des pentominos, des grilles 6 × 6 avec des compartiments 2 × 3, des grilles 7 × 7 avec six hexominos. Dans certains cas, les chiffres sont remplacés par des lettres, par des jetons de couleurs ou des dessins. Voici la solution de la grille donnée :

Il est relativement simple de produire des grilles de sudoku avec un crayon et du papier. Voici trois façons de le faire :

1^er On trace une grille 9 × 9 qu’on partage en neuf compartiments. On commence par remplir les trois compartiments supérieurs de gauche à droite chacun avec les chiffres de 1 à 9. On remplit chacun des deux autres compartiments de gauche de haut en bas, puis le compartiment au centre de la grille. On remplit le troisième compartiment de la deuxième rangée horizontale, puis celui de la deuxième rangée verticale. Pour remplir le dernier compartiment, celui du coin inférieur droit, on complète seulement les lignes (ou colonnes). On note les chiffres qui sont en double dans les colonnes (ou lignes). Pour apporter les corrections, on vérifie si ces chiffres apparaissent sur une même ligne (ou colonne) dans les deux compartiments du haut (ou à gauche). Si oui, on intervertit ces chiffres. Voici un exemple :

Le 4, le 8 et le 7 apparaissent deux fois en colonnes. Ils doivent être remplacés dans l’ordre par 8, par 7 et par 4. Alors, on intervertit le 4 et le 8 de la deuxième ligne ; puis le 8 et le 7 de la cinquième ligne. Si on ne réussit pas à faire les corrections, on efface les chiffres du compartiment du coin inférieur droit et on le complète dans l’autre sens.

2^e À partir d’une grille chiffrée, on peut produire des sudokus comportant des lettres. On remplace chaque chiffre de 1 à 9 par une lettre de façon arbitraire. Par exemple, on peut écrire A au lieu du 5, B au lieu du 7, C au lieu du 1 et ainsi de suite. Voici une grille composée de lettres :

Pour produire une grille chiffrée, on donne une valeur arbitraire à chaque lettre. Par exemple, on décide que A = 9, B = 1, C = 7, D = 2, E = 8, F = 6, G = 3, H = 5 et J = 4. On obtient cette grille.

3^e À partir d’une grille chiffrée, on peut produire d’autres sudokus en intervertissant des lignes entières ou des colonnes entières toujours dans une même rangée de trois compartiments. Voici un sudoku qui a été produit à partir de la grille précédente :

Le sudoku apparut à la même époque que le kakuro. Il appartient à la classe des récréations combinatoires.

© Charles-É. Jean