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.