Même si l’origine du Sudoku remonte aussi loin que le siècle dernier, un sursaut de popularité peut être noté durant l’année 2005. Je m’en souviens particulièrement bien, car c’est à cette époque que je les ai découverts, alors que je me rendais aux sports d’hiver. J’imagine que j’ai dû tomber sur un recueil de grilles dans une station-service, lors de l’un de nos arrêts en voiture vers notre destination. Ce concept nouveau pour moi m’a occupé quelque temps, le temps de résoudre quelques grilles.

La méthode utilisée précédemment pour remplir la grille se voulait excessivement naïve, car il est tout à fait catastrophique de ne tester la validité de la solution qu’une fois tous les mots placés. Le problème étant combinatoire, la nature exponentielle des combinaisons de mots s’affiche comme autant de branches, branchettes et puis brindilles se subdivisant effroyablement rapidement. Aussi vaut-il mieux se rendre compte le plus tôt possible que la voie choisie n’aboutira à aucune solution, de manière à couper la branche morte dès le début et ne pas perdre du précieux temps de calcul au fin fond de son arborescence.

Appliqué sans discernement, le backtracking peut s’avérer redoutable de complexité, tant la voie qui mène à la solution peut être longue, tortueuse, pleine d’ornières, de pièges et de détours dans lesquels se perdre indéfiniment. Maitriser le problème permet néanmoins de tracer un chemin beaucoup plus direct vers la solution, nettoyé de tous ses obstacles et voies de traverses, et permettant finalement un gain de temps qu’aucune autre optimisation ou puissance de calcul herculéenne ne pourra jamais compenser. Grâce à la méthode exposée dans l’article précédent, nous avons à disposition une autoroute filant pratiquement en ligne droite vers la solution. Mais cela veut-il dire pour autant que nous désirons nous trainer le long de ce chemin à bord d’un vieux tacot fumant et tout cabossé ?