Le jeu du Sudoku est un jeu de puzzle populaire sur certains journaux et magazines, il est représenté sur l’image en bas, globalement il se constitue d’une grille de 9×9 cases partiellement remplies par des chiffres de 1 à 9, la grille est aussi subdivisée en 3×3 carré de 3×3 chiffres, le joueur doit remplir le reste des cases vides restantes en respectant la règle qu’il ne doit pas y avoir de répétition d’un chiffre sur une colonne, sur une ligne ou sur le carré 3×3.
Les règles sont simples mais le casse-tête demande beaucoup de temps à l’humain pour le résoudre, et pourtant c’est déconcertant comment un programme d’une poignée de lignes de code arrive à résoudre le problème sur ordinateur en une fraction de seconde, dans la vidéo qui suit l’enseignant s’exulte de la magie de la récursivité, et c’est d’autant plus vrai que la récursivité est une technique de programmation réputée difficile à apprendre mais très efficace une fois maîtrisée. Il n’était par rare dans les examens d’algorithmique que j’ai eu à corriger de tomber sur des problèmes difficiles à résoudre par les méthodes conventionnelles (par boucles et tests) alors qu’ils devenaient très simples en récursivité.