Question d'origine :
Existe t'il une méthode mathématique rigoureuse permettant de résoudre tous les sudokus ?
Réponse du Guichet
gds_alc
- Département : Equipe du Guichet du Savoir
Le 19/04/2014 à 15h35
Bonjour,
Comme nous l’expliquions dans notre réponse apportée sur le sudoku, celui-ci 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.
Tels que les sudokus sont conçus,la solution est unique et ne peut résulter que d'une déduction logique , la question est plutôt de savoir quel serait le nombre minimal de cases préalablement remplies pour rendre la résolution unique :Le meilleur résultat, obtenu par des Japonais, est de 17 cases sans contrainte de symétrie :
Le problème de placer des chiffres sur une grille de n2×n2 comprenant n×n régions est NP-complet. Celasignifie 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).
Dernièrement, des mathématiciens se sont intéressés au Sudoku et ont montré que les combinaisons étaient très nombreuses. Sur ce point, nous vous laissons découvrir l'article publié sur l'un des blogs du Monde, Passeur des sciences.
Il existe en revanche des ouvrages proposant à la fois des jeux et des conseils pratiques qui devraient vous aider à vous améliorer et à acquérir une certaine logique. Voici quelques titres que nous avons pu trouver sur internet. La Bibliothèque municipale ne les possède malheureusement pas :
200 sudoku, 2005 : présentation des règles de base du jeu. Avec une série de conseils pratiques et astuces pour devenir un as du sudoku, des grilles classées selon 5 niveaux de difficulté, des combinaisons les plus simples aux situations les plus complexes.
Sudoku factory, volume 2. ceinture noire : 110 grilles et toutes les techniques, 2005 : astuces stratégiques et conseils techniques.
Comme nous l’expliquions dans notre réponse apportée sur le sudoku, celui-ci 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.
Tels que les sudokus sont conçus,
Le problème de placer des chiffres sur une grille de n2×n2 comprenant n×n régions est NP-complet. Cela
Dernièrement, des mathématiciens se sont intéressés au Sudoku et ont montré que les combinaisons étaient très nombreuses. Sur ce point, nous vous laissons découvrir l'article publié sur l'un des blogs du Monde, Passeur des sciences.
Il existe en revanche des ouvrages proposant à la fois des jeux et des conseils pratiques qui devraient vous aider à vous améliorer et à acquérir une certaine logique. Voici quelques titres que nous avons pu trouver sur internet. La Bibliothèque municipale ne les possède malheureusement pas :
200 sudoku, 2005 : présentation des règles de base du jeu. Avec une série de conseils pratiques et astuces pour devenir un as du sudoku, des grilles classées selon 5 niveaux de difficulté, des combinaisons les plus simples aux situations les plus complexes.
Sudoku factory, volume 2. ceinture noire : 110 grilles et toutes les techniques, 2005 : astuces stratégiques et conseils techniques.
DANS NOS COLLECTIONS :
Commentaires 0
Connectez-vous pour pouvoir commenter.
Se connecter