Question d'origine :
Bonjour,
Gros débat aujourd'hui au boulot : pour résoudre un Sudoku diabolique, y a-t-il systématiquement une solution logique, ou bien, parfois est-on obligé de choisir au hasard de partir dans une direction?
Merci pour votre réponse
Réponse du Guichet
bml_sci
- Département : Sciences et Techniques
Le 17/02/2006 à 13h58
Le Sudoku (prononcer [sudoku]), du japonais 数, sû, chiffre, et de 独, doku, unique, est un jeu en forme de grille défini en 1979 et inspiré du carré latin ainsi que du problème des 36 officiers de Leonhard Euler. Le but du jeu est de remplir cette grille avec des chiffres allant de 1 à 9 en respectant certaines contraintes, quelques chiffres étant déjà disposés dans la grille.
Le problème de placer des chiffres sur une grille de n2×n2 comprenant n×n régions est NP-complet. Cela signifie que, raisonnablement, dans l'état actuel des connaissances, on ne sait pas trouver d'algorithme efficace (polynomial en la taille de la grille et déterministe) pour résoudre tous les sudokus de taille non bornée (lire théorie de la complexité pour plus de détails sur ce qu'implique la NP-complétude). Sur les grilles d'une taille finie donnée, la résolution peut se faire via un automate fini qui connaît l'ensemble de l'arbre du jeu.
La résolution d'un Sudoku peut être formalisée par le problème de la coloration de graphe. Le but, dans la version classique du jeu, est d'appliquer 9 couleurs sur un graphe donné, à partir d'un coloriage partiel (la configuration initiale de la grille). Ce graphe possède 81 sommets, un par cellule. Chacune peut être étiquetée avec un couple ordonné (x, y), où x et y sont des entiers compris entre 1 et 9. Deux sommets distincts étiquetés par (x, y) et (x’, y’) sont reliés par une arête si et seulement si :
x = x’ ou,
y = y’ ou,
⌈x/3⌉ = ⌈x’/3⌉ et ⌈y/3⌉ = ⌈y’/3⌉
La grille se complète en affectant un entier entre 1 et 9 pour chaque sommet, de façon que tous les sommets liés par une arête ne partagent pas le même entier.
Une grille solution est aussi un carré latin. Il y a notablement moins de grilles solutions que de carrés latins, car le Sudoku impose des contraintes supplémentaires (Voir ci dessus point 4 : nombre de grilles complètes possibles).
Le nombre maximum de dévoilés sans qu'une solution unique n'apparaisse immédiatement, peu importe la variante, est la taille de la grille moins 4 : si deux paires de candidats ne sont pas inscrits et que les cellules vides occupent les coins d'un rectangle, et que exactement deux cellules sont dans une région, alors il existe deux façons d'inscrire les candidats. L'opposé de ce problème, à savoir le nombre minimum de dévoilés pour garantir une solution unique, est un problème non résolu, bien que des enthousiastes japonais aient découvert une grille 9×9 sans symétrie qui contient seulement 17 dévoilés (pour en savoir plus, voir (en) [13] et (en) [14]), alors que 18 est le nombre minimum de dévoilés pour les grilles 9×9 symétriques.
A lire la suite de cet article très complet sur Wikipedia.
Vous trouverez également des précieuses informations sur le site de Gérard Villemin qui précise :
Un vrai Sodoku offre toujours une suite logique de déductions pour arriver à la résolution complète
A vous de jouer :
Pièces jointes
DANS NOS COLLECTIONS :
Ça pourrait vous intéresser :
Commentaires 0
Connectez-vous pour pouvoir commenter.
Se connecter