Le Sudoku

Pour continuer sur ma lancée, je vais aujourd’hui parler d’un autre jeu souvent assimilé au Japon bien qu’il n’en soit pas originaire au même titre que le jeu de Go. C’est un jeu qui se joue sur une grille. Ses ancêtres sont des carrés magiques d’abord apparus en Chine et en Inde. Le jeu du Sudoku dont le succès grandissant est mondial a été défini en 1979 et est inspiré du carré latin.

Il n’y a que l’étymologie du nom Sudoku (数独) qui vient du Japon. C’est une abbréviation d’une phrase qui résume bien le but du jeu : “Suuji wa dokushin ni kagiru” (数字は独身に限る). Le sens de la phrase est “il ne peut avoir qu’un unique chiffre” (sous entendu par ligne et par colonne). La grille classique de Sudoku se joue avec les chiffres de 1 à 9 sur des grilles 9×9 contenant des sous grilles 3×3. Il ne peut avoir qu’une seule fois un exemplaire du chiffre dans chaque sous grille. Il existe plusieurs variantes dont certains pour les enfants (4×4, 5×5…).

J’ai eu l’occasion de programmer un outil de résolution de grilles de Sudoku lors de ma première année à l’IUT. Le sujet était imposé par le prof dans le cadre d’un TP noté en algorithmique. Le but était de résoudre une grille de Sudoku passé en entrée le plus rapidement possible. Le prof notait la méthode choisie pour résoudre la grille et le temps de résolution (calculé en ms) grâce à l’outil time de Linux. Dans mon groupe, on a choisi la méthode de backtracking (retour sur trace) qui consiste par exemple à mettre 1 dans la première case puis 2 dans la deuxième, et de tester ainsi de suite jusqu’à trouver une contradiction. Le projet était très instructif mais je ne m’étalerai pas plus sur le sujet, je voulais juste présenter ce petit jeu de réflexion, pas nippon ni mauvais d’ailleurs