PRESENTATION
JEUX
GRILLE BETA
DIVERS
PARTENAIRES


























Nombre de grilles complètes possibles

Il est évident que le nombre de grilles complètes est inférieur au nombre de façons de placer neuf chiffres 1, neuf chiffres 2, ..., neuf chiffres 9 dans une grille de 81 cases. Le nombre de grilles est donc très inférieur à

\frac{81!}{9!^9}

En effet, dans ce décompte, on ne tient compte d'aucune des contraintes d'unicité.


Le nombre de grilles complètes possibles est également inférieur au nombres de carrés latins de côté 9.


Enfin, le nombre de grilles complètes possibles est inférieur à 9!9 qui correspondrait au nombre de façons de construire les régions sans tenir compte des contraintes sur les lignes et les colonnes.


En 2005, Bertram Felgenhauer et Frazer Jarvis ont prouvé que ce nombre de grilles était de :


6 670 903 752 021 072 936 960 \approx 6,67.10^{21}


Ce nombre est égal à :


9! \cdot 72^2 \cdot 2^7 \cdot 27 704 267 971


Le dernier facteur est un nombre premier. Ce résultat a été prouvé grâce à une recherche exhaustive. Frazer Jarvis a ensuite considérablement simplifié la preuve grâce à une analyse détaillée. La démonstration a été validée de manière indépendante par Ed Russell. Jarvis et Russell ont par la suite montré qu'en tenant compte des symétries, il y avait 5 472 730 538 solutions.


En revanche, à cette date, aucun résultat n'existe sur le nombre de grilles complètes dans un super sudoku (grille 16 × 16). Si maintenant, on s'intéresse aux nombres de problèmes proposables, ce nombre est nettement plus important car il existe plusieurs façons de révéler les chiffres d'une même grille.


Le problème de savoir combien de cases remplies sont nécessaires au préalable pour rendre la résolution unique est, à ce jour, sans réponse. Le meilleur résultat, obtenu par des Japonais, est de 17 cases sans contrainte de symétrie. Rien ne dit que ce ne soit pas possible avec moins de nombres. Gordon Royle indique que deux résolutions sont considérées comme différentes si elles ne peuvent pas être transformées l'une vers l'autre (ou l'inverse) grâce à une combinaison des opérations suivantes :


On remarque l'analogie avec les opérations matricielles en algèbre linéaire.

 

Mathématiques

Le problème de placer des chiffres sur une grille de n2×n2 comprenant n×n régions est NP-complet . Cela signifie qu'il n'existe pas d'algorithme efficace (polynomial) pour résoudre tous les Sudoku. Sur les grilles de taille finie, 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 :


Le puzzle 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. Néanmoins, le nombre de grilles solution valides de taille 9×9, calculé par Bertram Felgenhauer en 2005, serait de 6 670 903 752 021 072 936 960. Ce nombre est égal à 9! × 722 × 27 × 27 704 267 971, ce dernier nombre étant un premier. Ce résultat est obtenu en partie par la logique et en partie par calculs en:brute force. Frazer Jarvis a notablement simplifié la méthode de calcul et Ed Russell a confirmé le résultat. Russell et Jarvis ont aussi démontré que lorsqu'il y a symétrie, il reste 5 472 730 538 solutions.


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, alors que 18 est le nombre minimum de dévoilés pour les grilles 9×9 symétriques.

Article de Wikipédia, l'encyclopédie libre.

Page d' Accueil | Signaler un bug | Plan du Site | Webmaster | Livre d'or

Copyright© Sudoku-Land.com