Le Sudoku et le backtracking : la technique de dernier recours qui résout toutes les grilles
Tu es face à une grille de Sudoku classée « diabolique », dans un magazine ou un recueil. Tes techniques habituelles (candidats uniques, paires nues, X-Wing) ne donnent plus rien. La grille semble verrouillée. C'est le moment où entre en scène le backtracking, une méthode de résolution aussi puissante que controversée parmi les puristes. Systématique, implacable et garantie de fonctionner, elle est le filet de sécurité ultime du joueur de Sudoku, mais elle a un prix.
Qu'est-ce que le backtracking ?
Le backtracking, ou « retour sur trace » en français, est un algorithme de résolution qui fonctionne par essais successifs. Son principe est d'une simplicité désarmante : on choisit une case vide, on y place un candidat possible, on continue à remplir la grille. Si l'on arrive à une contradiction (un chiffre impossible à placer quelque part), on revient en arrière jusqu'au dernier choix effectué et on essaie le candidat suivant.
L'idée est ancienne. Les mathématiciens du XIXe siècle procédaient déjà ainsi pour résoudre des problèmes combinatoires comme le problème des huit reines aux échecs : placer huit reines sur un échiquier de sorte qu'aucune ne puisse en capturer une autre. Le terme anglais backtrack est attribué au mathématicien américain D. H. Lehmer, dans les années 1950, et la méthode est devenue depuis un pilier de la programmation.
Appliqué au Sudoku, le backtracking garantit de trouver la solution si elle existe. C'est une certitude mathématique. Là où les techniques logiques classiques peuvent échouer face à certaines configurations, le backtracking ne capitule jamais. Il explore méthodiquement l'espace des possibilités jusqu'à trouver la combinaison gagnante, ou prouver qu'il n'y en a pas.
Comment fonctionne le backtracking au Sudoku, pas à pas
Imaginons une grille où la première case vide est en position ligne 1, colonne 3. Les candidats possibles, après analyse des contraintes de ligne, colonne et bloc, sont 2, 5 et 8. Le backtracking commence par placer le 2. On passe à la case vide suivante, on détermine ses candidats en tenant compte du 2 qu'on vient de placer, et on en choisit un. Et ainsi de suite, case après case.
Si l'un des choix était mauvais, on finit par arriver à une case où aucun candidat n'est possible : à eux trois, la ligne, la colonne et le bloc concernés contiennent déjà les neuf chiffres. C'est le signal du retour en arrière. On revient à la dernière case où l'on avait un choix, on efface le candidat qui a mené à l'impasse, et on essaie le suivant. Si tous les candidats d'une case ont été épuisés sans succès, on remonte encore d'un cran.
Ce processus peut sembler fastidieux, et il l'est pour un humain. Mais il a une propriété remarquable : il est complet. Si la grille a une solution, le backtracking la trouvera. Si elle n'en a pas, il le prouvera en ayant exploré toutes les possibilités. C'est cette exhaustivité qui fait sa force et qui explique pourquoi c'est l'algorithme de référence pour les programmes de résolution de Sudoku.
Le backtracking pour les humains : adaptation et intuition
Un ordinateur peut enchaîner un nombre énorme de retours en arrière en une seconde. Un être humain, non. Mais cela ne signifie pas que le backtracking est inutile pour le joueur de chair et d'os. Il existe une version adaptée et simplifiée que les joueurs expérimentés utilisent régulièrement, souvent sans même savoir qu'ils font du backtracking.
La technique consiste à identifier une case critique, c'est-à-dire une case avec seulement deux candidats possibles. On choisit l'un des deux, on le note au crayon (ou en mode hypothèse sur l'écran), et on continue à résoudre la grille en suivant les conséquences logiques de ce choix. Si l'on arrive à une contradiction, on sait que c'est l'autre candidat qui est le bon. C'est du backtracking avec une profondeur d'un seul niveau, parfaitement gérable pour un cerveau humain.
Cette technique est connue sous le nom de « Nishio », du nom du créateur de puzzles japonais Tetsuya Nishio. Le principe est le même : on suppose qu'un candidat est correct, on suit les implications logiques, et si l'on arrive à une impossibilité, on invalide le candidat. C'est moins élégant qu'une déduction purement logique, mais c'est terriblement efficace sur les grilles qui résistent à toutes les autres méthodes.
L'astuce pour rendre le backtracking humain plus efficace est de bien choisir son point de départ. Plutôt que de commencer par la première case vide venue, cible une case avec peu de candidats dans une zone déjà bien remplie. Moins il y a de candidats, moins il y aura de branches à explorer, et plus vite tu trouveras la contradiction ou la confirmation.
Pourquoi les puristes détestent le backtracking
Dans la communauté du Sudoku, le backtracking fait débat. Les puristes considèrent qu'une grille bien conçue doit être résoluble par la logique pure, sans aucun essai-erreur. Pour eux, recourir au backtracking équivaut à résoudre un mot croisé en essayant toutes les lettres de l'alphabet dans chaque case : techniquement efficace, mais intellectuellement insatisfaisant.
Ce point de vue a du mérite. Les grandes techniques du Sudoku (X-Wing, Swordfish, chaînes de couleur, méduse) sont des raisonnements logiques élégants et déterministes. Elles prouvent que tel chiffre va à tel endroit sans le moindre doute. Le backtracking, en comparaison, procède par tâtonnement. Il ne comprend pas pourquoi la solution est correcte : il constate simplement qu'elle ne produit pas de contradiction.
C'est aussi le parti pris de notre site : toutes nos grilles ont une solution unique et se résolvent sans deviner, y compris au niveau Sudoku expert, où il faut trouver au moins un X-Wing, un XY-Wing ou un Swordfish. Si tu te sens obligé de bifurquer sur l'une d'elles, c'est qu'une technique t'a échappé.
Cependant, cette critique a ses limites. Certaines grilles extrêmes, conçues pour mettre en difficulté les solveurs logiques, sont très difficiles à résoudre sans une forme de bifurcation. Les grilles d'Arto Inkala, présentées par leur auteur comme les plus difficiles du monde, demandent des chaînes de déduction si longues qu'elles s'apparentent dans les faits à du backtracking structuré. La frontière entre « déduction logique avancée » et « backtracking intelligent » est plus floue qu'on ne le croit.
Le backtracking dans l'informatique et au-delà
Le backtracking dépasse largement le cadre du Sudoku. C'est l'un des algorithmes fondamentaux de l'informatique, utilisé pour résoudre des problèmes aussi variés que la coloration de graphes, la satisfaction de contraintes, la planification de trajets ou la conception de circuits électroniques. Chaque fois qu'un problème peut être décomposé en une série de choix avec des contraintes, le backtracking est un candidat naturel.
Les solveurs de Sudoku informatiques utilisent une version optimisée du backtracking combinée avec des techniques de propagation de contraintes. Quand un chiffre est placé, le programme élimine immédiatement ce candidat de toutes les cases liées (même ligne, même colonne, même bloc). Cette propagation réduit drastiquement l'espace de recherche et permet de résoudre la plupart des grilles en quelques millisecondes.
Le programme de Peter Norvig, célèbre informaticien passé par la direction de la recherche de Google, résout les grilles de Sudoku en combinant propagation de contraintes et backtracking. Son implémentation en Python, publiée dans un essai devenu un classique, est remarquablement courte et vient à bout des grilles difficiles en une fraction de seconde. C'est un exemple parfait de la puissance du backtracking quand il est combiné avec des heuristiques intelligentes.
Intégrer le backtracking dans ton arsenal de joueur
Le backtracking ne devrait pas être ta première option, mais il a sa place dans ta boîte à outils. La stratégie la plus sûre est de commencer par les techniques logiques classiques : candidats uniques, paires et triplets nus, pointing pairs. Quand ces méthodes s'épuisent, passe aux techniques avancées : X-Wing, Swordfish, XY-Wing (tu peux les travailler une par une avec nos exercices d'entraînement par technique). Et quand même celles-ci ne suffisent plus, le backtracking contrôlé entre en scène.
Pour pratiquer le backtracking de manière productive et non frustrante, impose-toi une règle : ne bifurque jamais sur une case avec plus de deux candidats. Si aucune case binaire n'est disponible, c'est probablement qu'une technique logique t'a échappé. Reviens en arrière, réexamine la grille, et cherche le pattern que tu as manqué. Le backtracking est un dernier recours, pas une méthode par défaut.
Enfin, le backtracking a un intérêt souvent négligé : il montre où regarder. Quand tu bifurques sur un candidat et que tu arrives à une contradiction, analyse pourquoi. Souvent, la contradiction révèle un pattern logique que tu n'avais pas vu : une chaîne de couleur, une paire cachée, une relation que tes techniques habituelles auraient pu détecter. Le backtracking échoué est ainsi un professeur silencieux qui t'indique ce qu'il te reste à travailler.
La prochaine fois qu'une grille diabolique te résiste, ne la regarde pas comme un mur infranchissable. Choisis une case à deux candidats, prends une branche, et suis le chemin. Si c'est une impasse, reviens et prends l'autre. Le backtracking ne gagnera peut-être pas de prix d'élégance, mais il te mènera toujours à la solution. Et pour t'en passer le plus longtemps possible, rien ne vaut une partie de Sudoku en ligne, où la logique suffit toujours.
