Avant toute chose allez voir les
régles du jeu et le
plan du site en html
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 à
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 :
Ce nombre est égal à :
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 :
permutations des 9 nombres
échange des lignes avec les colonnes
(transposition)
permutation des lignes dans un seul bloc
permutation des colonnes dans un seul bloc
permutation des blocs sur une ligne de blocs
permutation des blocs sur une colonne de blocs
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 :
x=x' ou,
y=y' ou,
[x/3] = [x'/3] et [y/3] = [y'/3]
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.
A NE PAS RATER
Le
kamaji : les règles, conseils et le
but du jeu
3 ème
sudoku masters 2007 (championnat de France
)
: Les grilles du championnat
du monde de 2007
Télécharger des grilles de Hanjie géantes
Testez votre QI -test de QI gratuit
Grille super big (25x25)
Le sudokoo
expliqué par l'encyclopédie wikipedia
Super big samourai + la solution
Téléchargez
en une seul fois 6400 grilles
Prison break - le jeu en ligne
|
Vidéos
pour enfants | Activités
maternelle | Soutien
scolaire maternelle | Jardinage à l'école
-Référencement Page 1