⚙️ Comment sont créés les sudokus

Par Miguel Arechaga

Tu t'es déjà demandé d'où sortent les sudokus ? Est-ce que quelqu'un les invente à la main ? Comment sait-on qu'ils ont une solution... et qu'elle est unique ? Le processus est une petite merveille de logique, et le connaître te rend même meilleur joueur.

Étape 1 : on génère une grille complète

Tout sudoku commence à l'envers de ce que tu vois : on construit d'abord une grille entièrement remplie et valide (81 cases qui respectent les règles). Un ordinateur le fait en quelques millisecondes en remplissant des cases au hasard et en revenant en arrière dès qu'il arrive dans une impasse (la technique s'appelle le backtracking). Il existe environ 6.670 trillions de grilles valides, donc aucun risque de manquer de sudokus.

Étape 2 : on efface des cases

Sur cette grille complète, on retire les chiffres un par un. Et c'est là qu'est l'art : après chaque effacement, il faut vérifier quelque chose de crucial...

Étape 3 : la solution doit être unique

Un vrai sudoku a exactement une solution. Si, en effaçant une case, la grille se retrouve avec deux solutions possibles ou plus, cet effacement est annulé et on essaie avec une autre case. C'est pour ça que tu croises parfois sur internet des sudokus « défectueux » où tu arrives à un point où deux chiffres sont interchangeables : personne n'a vérifié l'unicité. Les nôtres, on la vérifie toujours.

Étape 4 : on mesure la difficulté

Et voilà le plus intéressant : la difficulté ne dépend pas du nombre de cases effacées, mais des techniques nécessaires pour la résoudre. Le générateur résout la grille comme le ferait une personne : si le scan et les singles suffisent, c'est facile ; s'il faut des paires nues, c'est moyen ; s'il oblige à utiliser le X-Wing ou les chaînes, c'est difficile ou expert. Deux sudokus avec le même nombre de cases vides peuvent avoir des difficultés opposées.

Le savais-tu ?

• Le minimum d'indices pour qu'un sudoku classique ait une solution unique est 17 (c'est démontré mathématiquement depuis 2012).
• Faire tourner, refléter ou échanger les chiffres d'un sudoku produit des sudokus « nouveaux » qui, au fond, sont le même.
• Les variantes (killer, diagonal, kropki...) utilisent le même processus en ajoutant leurs règles supplémentaires à la vérification.

Maintenant que tu sais ce qu'il y a derrière, chaque case que tu effaces... enfin, que tu résous, a un petit goût en plus. Mets-toi à l'épreuve avec nos plus de 30 variantes de sudoku.

Voici comment un sudoku est généré sur MundoSudoku, les vraies étapes

On t'explique exactement comment procède notre générateur, sans secrets. Il remplit d'abord une grille complète et valide : il parcourt les cases dans l'ordre et essaie des chiffres mélangés au hasard ; quand une case n'a plus d'options, il revient en arrière et change la précédente (le fameux backtracking). En quelques millisecondes, il y a une grille parfaite de 81 chiffres.

Ensuite commence le vidage : des cases sont choisies au hasard et effacées une à une. Après chaque effacement, le générateur compte combien de solutions a la grille. Y en a-t-il toujours exactement une ? Le trou reste. Une deuxième solution apparaît ? Le chiffre retourne dans sa case et on essaie avec une autre. Le processus s'arrête quand l'objectif d'indices du niveau est atteint : 40 pour facile, 32 pour moyen, 27 pour difficile et 23 pour expert.

Le cas particulier du sudoku du jour

Le sudoku du jour a une astuce élégante : au lieu d'utiliser du hasard pur, le générateur se nourrit d'une graine dérivée de la date. Avec la même graine, le processus aléatoire produit toujours le même résultat, donc tous les joueurs du monde reçoivent exactement la même grille sans qu'aucun serveur ait besoin de l'envoyer. La date 21-7-2026 devient le nombre 20260721, ce nombre lance le générateur, et il en sort le sudoku que tu verras, toi, ton voisin et quelqu'un en Argentine.

Pourquoi 17 indices est la limite magique

Pendant des décennies, on a soupçonné qu'aucun sudoku de 16 indices ne pouvait avoir une solution unique, mais personne ne l'avait démontré. En 2012, une équipe de l'University College Dublin a tranché par la force brute la plus élégante possible : ils ont énuméré les grilles essentiellement différentes et vérifié par ordinateur qu'aucun sudoku de 16 indices n'est unique. Il a fallu 7 millions d'heures de CPU. Nos grilles expertes à 23 indices sont donc étonnamment proches de la limite théorique.

Questions fréquentes

Combien de sudokus différents existe-t-il ?

Il existe 6.670.903.752.021.072.936.960 grilles complètes valides (environ 6,67 trillions). En retirant les rotations, les symétries et les renommages de chiffres, il en reste 5.472.730.538 essentiellement différentes. On n'est pas près d'en manquer.

Un sudoku avec plus de trous est-il toujours plus difficile ?

Pas forcément. La vraie difficulté dépend des techniques qu'il exige, pas seulement du nombre de trous. C'est pour ça que deux grilles à 27 indices peuvent donner des sensations très différentes : ce qui compte, c'est où sont les indices, pas seulement combien il y en a.

Les sudokus de MundoSudoku se répètent-ils ?

L'espace des grilles est si énorme que la probabilité de répétition est pratiquement nulle. Seul le sudoku du jour est « répétable » exprès : le même jour produit la même grille pour tout le monde.