Wednesday, August 09, 2006

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.

12 Comments:

Anonymous Jonathan said...

cool ton blog,, mauricien ??

1:21 AM  
Anonymous sudoku said...

.

Cette technique me semble valable pour les grilles faciles...
Pour les grilles difficiles, ça m'a l'air un peut plus juste.

Solutionneur en ligne ici : http://www.123sudoku.net/sudoku/solutionneur/

.

12:11 PM  
Blogger Ala nou alé said...

Cette technique explore de manière exhaustive les possibilités d'une grille. On finira toujours par tomber sur un résultat.

Peut-être pourrais tu être plus clair et même venir avec un exemple de grille difficile pour laquelle la technique à l'air un peu juste.

10:51 PM  
Anonymous Diane said...

Le sudoku jsui accro mais j'ai kan meme des problème avc les grilles difficiles :s

11:33 AM  
Anonymous ala mo vini said...

Ca me fait penser au principe de la boussole qui dis: Lorsque tu as le nord devant toi, tu as le "sudoku" ;)

2:11 AM  
Anonymous @rtur said...

Salut,

Juste pour dire que tu as fait ta réduction de complexité à l'envers. Pour montrer que le sudoku est NP-dur il faudrait montrer que :
Si Sudoku est résolvable en temps polynomial alors on peut résoudre toute instance du problème SAT en temps polynomial.

En d'autres termes, si on montre qu'on peut résoudre SAT à partir de Sudoku, on a gagné : dans ce cas, si on suppose que Sudoku n'est pas NP-dur, on a que SAT ne l'est pas non plus et on aboutit à une contradiction. Donc, on en déduit que Sudoku est NP-dur.

8:14 AM  
Blogger Ala nou alé said...

Salut,
Excellent @rthur, merci de partager le principe de la preuve sur le blog.

9:40 AM  
Anonymous @rtur said...

J'ai un peu cherché, et apparemment la NP-Complétude du sudoku a été démontrée fin 2002 par les japonais Yato et Seta.
Malheureusement la preuve n'a vraiment pas l'air triviale...

1:32 AM  
Anonymous Anonymous said...

salut!!je suis en L2 et g kom projet justement de programmmer le sudoku en python!!!!!é jariv pas du tt a faire le backtrack é c'est à rendre pour mardi!! ce seré très sympa à toi si tu pouvé remettre en ligne ce que t'avais fait en python sa maideré vraiment beaucoup je suis trop desespérée!!!lol
koike tu decides merci kan mm!!

7:16 AM  
Blogger ii2 said...

Salut

Un bon exemple de backtracking en langage c avec commentaires. De plus le site résoud et conseille en ligne sudoku et hexadoku. Ils ont poussé assez loin les résolutions en ligne.
Par contre le code de résolution du site doit être bien plus poussé que celui de l'exemple, il me semble.
A tester. Impressionant.
http://www.top-sudoku.com/sudoku/fr/exemple-backtracking-c.php
A+ et bravo pour ton blog.
Alexis

8:34 PM  
Anonymous sudoku online said...

Merci pour l'explication. C'est vrai que l'algo pour les grilles plus difficiles est plus complexe. Bien plus que le sudoku :)

Carolina
domo sudoku

6:12 AM  
Anonymous Anonymous said...

Amiable brief and this enter helped me alot in my college assignement. Thanks you for your information.

10:04 PM  

Post a Comment

<< Home