Le Sudoku

Le sudoku est un puzzle qui consiste à placer des nombres sur une grille composée de 9x9 cellules en respectant certaines contraintes sur leur positionnement.



Bien que je ne suis pas friand de ce jeu, je me suis récemment intéressé au problème posé par sa résolution.

Complexité
En informatique théorique, la résolution algorithmique du problème général du sudoku, c'est à dire le problème de résolution sur une grille , est dans la classe NP-Complet. En termes simples, cela signifie qu'à ce jour on ne connaît pas d'algorithme déterministe efficace qui pourrait résoudre un sudoku de cases.

Comment se convaincre de l'NP-Complétude.
D'une part, le problème est dans NP car la réponse d'une instance d'un problème de sudoku peut être utilisée comme certificat. Ce même certificat pouvant être vérifié par un algorithme déterministe en temps polynomiale.
D'autre part, le problème est NP-dur dans la mesure où l'on peut réduire-avec un algorithme déterministe en temps polynomial-une instance d'un autre problème NP-Complet à une instance du problème du sudoku.

Pour réaliser cela on peut utiliser une formule booléenne pour exprimer l'ensemble des contraintes du puzzle. Déterminer une interprétation qui rende la formule satisfiable impliquerait de trouver une réponse au sudoku. Comme l'on sait que le problème de satisfiabilité de formule booléenne (SAT) est NP-Complet, on a bien que le problème de résolution d'un sudoku est aussi NP-Complet.

Un algorithme de résolution
La résolution d'un sudoku par un programme informatique peut être réalisée rapidement. A mon avis, l'approche la plus simple est d'utiliser la programmation par contraintes. Une méthode procédurale aussi simple serait d'explorer toutes les possibilités du sudoku donné.

J'ai choisi pour réaliser cela l'algorithme de backtracking suivant:


Le principe consiste à récupérer dans un premier temps l'ensemble des nombres que peut prendre une case. Prendre un élément quelconque de cette ensemble et de l'affecter à la case. On passe aux cases suivantes en répétant le procédé jusqu'à ce qu'on l'on rencontre une case où l'ensemble des nombres possibles est vide. Lorsque ce cas se présente, l'algorithme retourne en arrière (backtrack) sur la case précédente et l'affecte à un nouveau nombre pris de l'ensemble des nombres possibles.
Bien entendu cette technique peut demander beaucoup de retours en arrière, mais un ordinateur réalise ces opérations très rapidement.

Pour finir, je propose une implémentation en Python ici.

Sur ce, bon sudoku pour ceux qui aiment jouer, moi j'évite la prise de tête.