Mathématiques du Sudoku - Définition

Contexte mathématique

Le problème de placer des chiffres sur une grille de n²×n² comprenant n×n régions est prouvé NP-complet

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 des cases du sudoku 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’ (les deux cellules appartiennent à la même ligne) ou,
• y = y’ (les deux cellules appartiennent à la même colonne) ou,
• et (les deux cellules appartiennent à la même région). 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. La relation entre les deux théories est désormais complètement connue, depuis que D. Berthier a démontré, dans "The Hidden Logic of Sudoku", qu'une formule logique du premier ordre qui ne mentionne pas les blocs (ou régions) est valide pour le Sudoku si et seulement si elle est valide pour les carrés latins.

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). Un résultat publié en 2007, dévoile que pour qu'un sudoku ait une solution unique, il est nécessaire que 8 des 9 chiffres soit dévoilés. [2] et (en) [3]), alors que 18 est le nombre minimum de dévoilés pour les grilles 9×9 symétriques.

Nombre minimal de chiffres dans la grille

Les grilles correctement réalisées doivent avoir une et une seule solution. Une grille est dite irréductible ou minimale si elle est valide et si le retrait d'un chiffre supplémentaire entraîne son invalidité (i.e. elle n'admet plus de solution unique). Il est possible de créer des grilles minimales avec un nombre différent de valeurs initiales. Cette section décrit les propriétés relatives à ce problème.

Sudoku classique

Le Sudoku classique avec une grille de 9x9, soit 81 cases, est pour l'instant limité par une borne inférieure de 17 valeurs initiales, ou 18 quand les positions des chiffres initiaux peuvent être tournées de 90°. Il existe une conjecture qui stipule que cette borne de 17 est la meilleure possible, mais il n'existe pas de preuve formelle, seulement une recherche exhaustive avec des grilles aléatoires :

• Gordon Royle a compilé une liste de grilles avec 17 valeurs, lesquelles sont uniques. Parmi ces 39422 grilles, aucune d'entre elles n'est isomorphique à une autre grille ou contient une solution avec 16 valeurs initiales.
• Une construction indépendante de 700 grilles distinctes a permis de découvrir 33 autres grilles qui n'apparaissaient pas dans la liste de Royle. Une estimation d'après le maximum de la vraisemblance, permet de déduire que le nombre de ces grilles minimales s'élève à environ 34550. Si les méthodes sont vraiment aléatoires et indépendantes, alors la probabilité de trouver une construction valide avec 16 valeurs initiales est faible. En effet, une seule de ces hypothétiques grilles permettraient d'obtenir 65 nouvelles grilles avec 17 valeurs initiales, résultats qui ne sont pas apparus dans les recherches précédentes. Mais en l'absence d'une preuve formelle, ce fait ne peut être confirmé ou infirmé.
• D'autres recherches aléatoires ont fournis des grilles qui étaient déjà dans la liste de Royle, ce qui renforce l'idée de la quasi-complétude de l'ensemble fourni par Royle.

Sudoku avec d'autres contraintes

Un 3doku

Des contraintes supplémentaires (avec des Sudoku dont les régions font 3×3) changent le nombre de valeurs minimales nécessaires pour aboutir à une solution unique :

• 3doku : aucun résultat connu à ce jour (2006)
• Groupes disjoints, des grilles avec 12 valeurs ont été démontrées par Glenn Fowler. Rien n'indique que cette borne minimale ne peut être rabaissée.
• Hypercube, des grilles avec 8 valeurs ont été proposées par Guenter Stertenbrink.
• Magic Sudoku, un exemple avec 7 valeurs a été publié par Guenter Stertenbrink. Ici encore, on ne sait pas s'il s'agit véritablement de la borne minimale.
• Sudoku X, Gordon Royle a donné un exemple avec 17 valeurs, borne supposée minimale.
• NRC Sudoku, Andries Brouwer a découvert un exemple avec 11 valeurs. On ne sait pas s'il est possible de faire mieux.

Sudoku avec des régions irrégulières

Les Du-sum-oh remplacent les régions de 3×3 (ou plus généralement L×C) par des régions irrégulières avec une taille fixe. Bob Harris a prouvé qu'il était toujours possible de créer des du-sum-ohs avec N-1 valeurs initiales sur une grille de N par N. Il a donné plusieurs exemples.

Killer Sudoku

Dans le Samunamupure ou Killer Sudoku, les régions ont non seulement des formes irrégulières mais également des tailles différentes. Les règles d'unicité des nombres dans les lignes, régions et colonnes s'appliquent toujours. Les indications initiales sont données sous la forme de sommes de valeurs dans les régions (par exemple, une région de 4 cellules avec une somme de 10 contiendra les chiffres 1, 2, 3, 4 selon un certain ordre). Le nombre minimal de valeurs nécessaires pour débuter la grille n'est pas connue, ni conjecturée.

Une variante proposée par Miyuki Misawa remplace les sommes par des relations : les indications sont des symboles =, <, >, montrant les valeurs relatives pour certaines régions adjacentes. Un exemple avec seulement 8 relations est donné, mais on ne sait pas si ce nombre est la borne inférieure.