sudoku

Imaginez une grille presque remplie. Dans une case vide, vous cherchez lequel des chiffres de 1 à 9 manque encore. Vous regardez la ligne, puis la colonne et enfin le carré de 3 × 3 cases qui contient cette case.

Un chiffre n'est possible que s'il ne se répète dans aucun de ces trois ensembles. Le sudoku avance ainsi par élimination logique : les indices déjà imprimés imposent peu à peu la valeur des cases vides, sans qu'aucune addition soit nécessaire.

Un sudoku standard est une grille de 81 cases disposées en 9 lignes et 9 colonnes. Elle est aussi partagée en neuf régions, ou boîtes, de 3 × 3 cases. Certaines cases contiennent dès le départ des chiffres appelés indices. Il faut compléter les autres avec les chiffres de 1 à 9. Dans chaque ligne, chaque colonne et chaque région, chacun de ces neuf chiffres doit apparaître exactement une fois.

Les chiffres jouent ici le rôle de symboles distincts : la règle porte sur leur présence et leur unicité, non sur leur somme.

Dans une grille presque achevée, la case située au croisement de la ligne 5 et de la colonne 5 est vide. La ligne contient 4, 2, 6, 8, une case vide, 3, 7, 9, 1. La colonne contient 7, 9, 4, 6, une case vide, 2, 3, 1, 8. Dans la région centrale, les trois rangées sont 7, 6, 1 ; 8, une case vide, 3 ; puis 9, 2, 4.

Étape 1. Comparez la ligne 5 avec la liste des chiffres de 1 à 9. Tous sont présents sauf le 5 : la case vide ne peut donc recevoir que 5.

Étape 2. Contrôlez la colonne 5. Elle contient elle aussi tous les chiffres de 1 à 9 sauf le 5 ; la valeur proposée ne crée aucune répétition.

Étape 3. Contrôlez enfin la région centrale. Les huit chiffres déjà inscrits sont 1, 2, 3, 4, 6, 7, 8 et 9. Le seul absent est encore 5.

La case centrale vaut donc 5. Le contrôle est refaisable : après l'inscription, la ligne, la colonne et la région contiennent chacune exactement une fois tous les chiffres de 1 à 9.

Lorsqu'une ligne n'a plus qu'une case vide, comparez ses huit chiffres avec la liste de 1 à 9. Si plusieurs valeurs manquent, l'examen de la colonne et de la région fournit les contraintes supplémentaires.

Pour contrôler une grille terminée, vérifiez séparément chaque ligne, chaque colonne et chacune des neuf régions. Le simple fait que les 81 cases soient remplies ne suffit pas : une répétition dans un seul de ces ensembles enfreint la règle.

Avant d'appliquer cette méthode, repérez le format du puzzle. La définition standard suppose 9 × 9 cases et des régions de 3 × 3 ; une grille organisée autrement demande que sa propre règle soit énoncée.

Sudoku et carré latin. Dans une solution complète de sudoku comme dans un carré latin, chaque chiffre apparaît une fois par ligne et par colonne. Le critère qui les sépare est la région : le sudoku standard impose aussi une occurrence de chaque chiffre dans chacun des neuf carrés de 3 × 3 cases. Une grille entièrement remplie qui respecte seulement les lignes et les colonnes peut donc être un carré latin sans être un sudoku valide.

Moins de 17 indices. Dans une grille standard de 9 × 9, un nombre d'indices inférieur à 17 signale qu'une solution unique est impossible. Il faut alors remettre en cause l'unicité annoncée, et non chercher indéfiniment une déduction manquante.

Exactement 17 indices. Le nombre 17 est un minimum, pas une méthode de résolution. Atteindre ce seuil ne dispense pas d'appliquer les trois contraintes et de vérifier que le remplissage obtenu est unique.

Une grille pleine mais invalide. Si un chiffre se répète dans une ligne, une colonne ou une région, les 81 cases remplies ne constituent pas une solution. Le bon contrôle consiste à retrouver exactement les chiffres de 1 à 9 dans chacun de ces ensembles.

Le sudoku tire son nom de l'abréviation japonaise de « Sūji wa dokushin ni kagiru », que l'on peut rendre par « les chiffres doivent rester seuls ». Le carré gréco-latin, étudié notamment par Euler au XVIII^e siècle, fait intervenir l'orthogonalité de deux carrés latins, une propriété qui ne figure pas dans les règles du sudoku.

La forme actuelle du puzzle a été conçue en 1979 par l'Américain Howard Garns. Sa popularité mondiale a explosé à partir de 2005, notamment grâce à sa diffusion dans la presse quotidienne.

Le glossaire carré latin isole la contrainte commune sur les lignes et les colonnes, avant l'ajout des régions propres au sudoku.

L'article Le Sudoku dès 3 ans ! ouvre une piste de lecture sur une adaptation du puzzle destinée aux très jeunes joueurs.