Mathématiques du Sudoku

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Grille de Sudoku classique
Variante du Sudoku basée sur des comparaisons entre les cases
Sudoku classique avec une contrainte supplémentaire sur les diagonales

Le jeu du Sudoku consiste à compléter une grille carrée divisée en N régions de N cases, en partie remplie avec des chiffres, de façon à ce que dans chaque ligne, chaque colonne et chaque région les chiffres de 1 à N apparaissent une et une seule fois.

Une analyse mathématique du Sudoku permet de découvrir les différentes propriétés et problèmes qui se cachent derrière ce jeu et ses variantes.

Introduction[modifier | modifier le code]

L'analyse mathématique du Sudoku se divise en deux grandes parties : l'analyse des propriétés des grilles complètes et l'analyse de la résolution d'une grille.

L'analyse des grilles s'est en grande partie focalisée sur l'énumération des solutions possibles pour différentes variantes du jeu. L'étude de la résolution se concentre sur les valeurs initiales de la grille et sur les étapes qui mènent à la grille complète. Ces techniques font appel à plusieurs disciplines : analyse combinatoire, algorithmique, théorie des groupes ainsi que la programmation puisque l'ordinateur permet de rapidement résoudre les grilles.

Il y a un grand nombre de variantes du Sudoku, en général caractérisées par la taille de la grille (le paramètre N) et la forme des régions. Les Sudoku classiques ont un N égal à 9 avec des régions de 3x3 cases. Un Sudoku rectangulaire possède des régions rectangulaires d'une taille L×CL est le nombre de lignes et C le nombre de colonnes. Un tel Sudoku, avec une taille de L×1 (ou 1×C), devient un carré latin puisque la région est une ligne ou une colonne unique.

Des variantes plus complexes existent comme celles avec des régions découpées de manière irrégulière (Nanpure), avec des contraintes supplémentaires (Samunamupure ou Killer Sudoku, respect de l'unicité sur les diagonales avec le Kokonotsu, contraintes sur l'ordre des éléments avec le Greater-Than) ou des assemblages de plusieurs grilles (Samurai, Sudoku en 3D). Dans certaines variantes, les chiffres sont remplacés par des lettres. Cette substitution des caractères utilisés ne change toutefois rien aux propriétés intrinsèques du puzzle si les règles restent les mêmes.

L'analyse mathématique du Sudoku a suivi la popularité du jeu. Les analyses concernant la complexité algorithme et le caractère NP-complet du jeu furent documentés vers la fin de l'année 2002[1], les résultats d'énumération ont fait leur apparition vers le milieu de l'année 2005[2]. Les contributions des nombreux chercheurs et amateurs ont permis de mettre à jour les propriétés du jeu. L'apparition des variantes du Sudoku étend d'autant plus les éléments mathématiques à considérer et explorer.

Contrastant avec les deux approches mathématiques principales citées au début, une approche basée sur la logique mathématique et s'attaquant au problème de la résolution des puzzles a été proposée récemment dans le livre de Denis Berthier, « The Hidden Logic of Sudoku »[3] (La logique cachée du Sudoku). Cela a permis de découvrir et de formaliser toutes les symétries généralisées du jeu et de découvrir de nouvelles règles de résolution basées dessus, comme les chaînes xy cachées.

Contexte mathématique[modifier | modifier le code]

Le problème de placer des chiffres sur une grille de n2×n2 comprenant n×n régions est prouvé NP-complet[4].

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,
  • \left\lceil {\dfrac{x}{3}} \right\rceil = \left\lceil \dfrac{x'}{3} \right\rceil et \left\lceil \dfrac{y}{3} \right\rceil = \left\lceil \dfrac{y'}{3} \right\rceil (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 »[3], 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).

Contrairement au nombre de grilles solutions, le nombre exact de puzzles minimaux n'est pas connu. (Un puzzle est minimal si aucun dévoilé ne peut être supprimé sans compromettre l'unicité de la solution.) Cependant, des techniques statistiques combinées avec la définition d'un nouveau type de générateur (générateur à biais contrôlé) permettent de montrer qu'il y a approximativement (avec une erreur relative de 0.065%):

  • 3.10 × 1037,
  • 2.55 × 1025 puzzles minimaux non équivalents.

(voir le livre Pattern-Based Constraint Satisfaction and Logic Puzzles[5] ou l'article Unbiased Statistics of a CSP - A Controlled-Bias Generator'[6]) .

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

Nombre de grilles complètes possibles[modifier | modifier le code]

Le nombre de grilles complètes possibles est inférieur à 9!^9 qui correspond 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é[10] que ce nombre de grilles était de :

6 670 903 752 021 072 936 960≈6,67.1021 [11],[12].

Ce nombre est égal à :

9!×722×27×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 [13].

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 minimum de cases remplies au préalable pour rendre la résolution unique est de 17; il a été prouvé par le calcul en janvier 2012 par une équipe irlandaise [14]. Une liste de l'ensemble des sudoku à solution unique ayant 17 cases remplies a été établie par des japonais [8] ,[15]. 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 :

  1. permutations des 9 nombres
  2. échange des lignes avec les colonnes (transposition)
  3. permutation des lignes dans un seul bloc
  4. permutation des colonnes dans un seul bloc
  5. permutation des blocs sur une ligne de blocs
  6. permutation des blocs sur une colonne de blocs

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

Terminologie[modifier | modifier le code]

Un puzzle est une grille incomplète où figurent des valeurs initiales. Les régions sont également appelées des blocs ou des zones. Le terme de carré est évité pour lever toute confusion.

Une bande est une suite de blocs adjacents sur l'axe horizontal. Une pile est une suite de blocs adjacents sur l'axe vertical. Dans un Sudoku de 9x9 cases, il y a ainsi 3 bandes et 3 piles.

Un Sudoku correctement conçu a une et une seulement solution : la grille finale est unique, mais la résolution à partir de la grille partielle peut toutefois prendre des chemins différents.

Formalisation des différentes variantes[modifier | modifier le code]

Une région peut être décrite par ses dimensions : LxCL est le nombre de lignes et C le nombre de colonnes dans la région. Dans la version classique du Sudoku, L = C = 3. Cela implique qu'il existe L régions par bande et C régions par pile. Il est plus pratique de mentionner la taille de la région plutôt que le nombre d'éléments car une région de 2x6 a le même nombre de cases que celle de 3x4.

La découpe suivante peut être adoptée pour classifier grossièrement les variantes :

  • régions rectangulaires
    • régions carrées
  • régions irrégulières (polyomino)

Des contraintes supplémentaires permettent de mieux cibler le type de jeu.

Un Sudoku carré de NxN régions possède plusieurs propriétés respectées pour tous ses sous-éléments, en plus de la règle classique de l'absence de doublons. En effet, chaque ligne et chaque colonne a une intersection avec N régions et partage N cases avec chacune d'entre elles. Le nombre de bandes et de piles est aussi égal à N. Le Sudoku rectangulaire n'a pas ces propriétés.

Le Sudoku avec des régions de 3x3 cache une autre propriété qui lui est propre : N est le nombre de sous-unités considérées dans le jeu, à savoir trois : la ligne, la colonne et la région.

Définitions[modifier | modifier le code]

Notation avec les régions, les triplets h56 et v56
1 2 3
2 R1
3  
4 5 6
R2
 
7 8 9
R3
 
4
5 R4
6
v
R5 5
h 5 6
 
R6
 
7
8 R7
9
 
R8
 
 
R9
 

Soit :

  • s une solution d'un Sudoku avec des dimensions spécifiques et qui satisfait les règles du Sudoku original (pas de doublons dans les lignes, colonnes et régions)
  • S = {s}, l'ensemble de toutes les solutions possibles
  • |S|, la cardinalité (taille) de l'ensemble S (ie. le nombre de solutions)

Le nombre de solutions dépend de la taille de la grille, des règles appliquées et de la définition précise d'une solution distincte. Pour un Sudoku avec des régions de 3x3, les conventions pour l'affichage du contenu de la grille sont les suivantes : les bandes sont labelisées du haut vers le bas, les piles de la gauche vers la droite. Les régions sont donc numérotés de la gauche vers la droite et du haut vers le bas. Cette convention s'applique aussi pour les grilles rectangulaires.

D'autres termes sont utiles dans le cas du Sudoku avec des régions de 3x3 :

  • le triplet est une combinaison non-ordonnée de trois valeurs présentes sur une ligne ou une colonne d'une région. Par exemple, le triplet {3, 5, 7} signifie que les valeurs 3, 5, 7 apparaissent dans une ligne ou une colonne de la région, mais sans spécifier leur ordre d'apparition (on pourrait avoir une ligne avec 5, 7, 3 ou encore une colonne avec 3, 7, 5). Les valeurs d'un triplet peuvent être arrangées de 6 manières différentes (3!) grâce à des permutations. Par convention, les éléments d'un triplet sont écrits dans l'ordre croissant mais cela ne signifie pas qu'ils apparaissent dans la grille selon le même ordre ;
    • la notation hRL indique un triplet pour la région R et la ligne Lde la grille. Le préfixe h indique qu'il s'agit d'un triplet horizontal ;
    • de manière similaire, la notation vRC identifie un triplet pour la région R et la colonne C de la grille. Le préfixe v indique qu'il s'agit d'un triplet vertical.

Par exemple, la notation h56 correspond au triplet de la région 5, ligne 6. En anglais, on utilise la notation r pour row et c pour column.

On parle aussi de mini-ligne ou de mini-colonne pour désigner la portion présente dans une région d'une ligne ou d'une colonne de la grille.

Nombre de solutions possibles[modifier | modifier le code]

La réponse à la question « Combien y a-t-il de Sudoku ? » dépend de la définition d'une solution et de l'équivalence entre plusieurs solutions. Pour l'énumération de toutes les solutions possibles (ie. grilles complètes), on retient la définition suivante :

Une grille A est différente d'une grille B, si la valeur de la case en A(i, j) est différente de B(i, j), pour au moins un couple i, j (valeurs limitées par la dimension de la grille).

Si une grille A est obtenue par symétrie de la grille B alors elles sont considérées comme différentes. Les rotations sont également comptées comme de nouvelles solutions.

Énumérations des solutions symétriquement distinctes[modifier | modifier le code]

Deux grilles sont dites symétriquement distinctes si l'une ne peut être dérivée de l'autre (par une ou plusieurs opérations de préservation de la symétrie).

Préservation de la symétrie[modifier | modifier le code]

Les opérations suivantes transforment toujours une grille valide en une autre grille valide :

  • changer le label de chaque symbole (9!)
  • permutations des bandes (3!)
  • permutations des piles (3!)
  • permutations des lignes dans une bande (3!3)
  • permutations des colonnes dans une pile (3!3)
  • réflexion, transposition, rotation de 90° (avec l'une de ces opérations et les permutations, il est possible de déduire les autres opérations, ce qui fait que ces opérations ne contribuent qu'avec un facteur de 2).

Ces opérations définissent une relation de symétrie entre deux grilles équivalentes. En excluant le changement de labels, et en considérant les 81 valeurs présentes dans la grille, ces opérations forment un sous-groupe du groupe symétrique S81 avec un ordre 3!8×2 = 3359232.

Identifier les solutions grâce au lemme de Burnside[modifier | modifier le code]

Pour une solution, l'ensemble des solutions équivalentes qui peut être obtenu en utilisant ces opérations (sauf le renommage des valeurs), forme une orbite du groupe symétrique. Le nombre de solutions symétriquement distinctes est ainsi le nombre d'orbites, une valeur qui peut être calculée grâce au lemme de Burnside. Les points fixes de la méthode de Burnside sont des solutions qui ne diffèrent que par le renommage. Grâce à cette technique, Jarvis Russell a calculé le nombre de solutions symétriquement distinctes : 5 472 730 538.

Bandes du Sudoku[modifier | modifier le code]

Pour des grandes valeurs de L et C, la méthode de Kevin Kilfoil[16] (généralisée par la suite[17]) est utilisée pour estimer le nombre de façons de compléter une grille. Cette méthode part du principe que les contraintes sur les lignes et les colonnes sont, pour une première approximation, des variables aléatoires conditionnellement indépendantes eu égard à la contrainte sur la région. Des calculs algébriques permettent d'aboutir à la formule de Kilfoil-Silver-Pettersen :

\mbox{Nombre de grilles} \simeq \dfrac{b_{L,C}^C \times b_{C,L}^L}{(LC)!^{LC}}

bL, C est le nombre de manières de compléter un Sudoku avec L régions (d'une taille de LxC) horizontalement adjacentes. L'algorithme de Pettersen[18], implémenté par Silver[19] est actuellement la technique la plus rapide connue pour évaluer de manière exacte les valeurs bL, C.

Le compte des bandes pour les problèmes dont « le nombre total de grilles de Sudoku est inconnu » est donné ci-dessous. Comme dans le reste de cet article, les dimensions correspondent à celles des régions.

Dimensions Nombre de bandes Auteur(s) Vérification formelle
C (2C)! (C!)2 (obvious result) Oui
C (3C)! (C!)^6 \sum_{k=0\ldots C} {C \choose k}^3 Pettersen Oui
C (voir ci-dessous pour le résultat mathématique) Pettersen Oui
4×4 16! × 4!12 × 1273431960 = c. 9.7304×1038 Silver Oui
4×5 20! × 5!12 × 879491145024 = c. 1.9078×1055 Russell Oui
4×6 24! × 6!12 × 677542845061056 = c. 8.1589×1072 Russell Oui
4×7 28! × 7!12 × 563690747238465024 = c. 4.6169×1091 Russell Oui
(des calculs jusqu'à 4×100 ont été effectués par Silver, mais ne sont pas indiqués ici)
5×3 15! × 3!20 × 324408987992064 = c. 1.5510×1042 Silver Oui#
5×4 20! × 4!20 × 518910423730214314176 = c. 5.0751×1066 Silver Oui#
5×5 25! × 5!20 × 1165037550432885119709241344 = c. 6.9280×1093 Pettersen/Silver Non
5×6 30! × 6!20 × 3261734691836217181002772823310336 = c. 1.2127×10123 Pettersen/Silver Non
5×7 35! × 7!20 × 10664509989209199533282539525535793414144 = c. 1.2325×10154 Pettersen/Silver Non
5×8 40! × 8!20 × 39119289737902332276642894251428026550280700096 = c. 4.1157×10186 Pettersen/Silver Non
# : même auteur mais avec une autre méthode

L'expression pour le cas 4×C est : (4C)!(C!)^{12}\sum_{a, b, c} {\left( \dfrac{C!^2}{a! b! c!} * \sum_{\begin{matrix}k_{12},k_{13},k_{14},\\k_{23},k_{24},k_{34}\end{matrix}} {{a\choose k_{12}}{b\choose k_{13}}{c \choose k_{14}}{c \choose k_{23}}{b \choose k_{24}}{a \choose k_{34}} } \right)^2 }

avec :

la somme extérieure s'applique sur tous les a,b,c tel que 0⩽a,b,c et a+b+c=2C
la somme intérieure s'applique sur tous les k12,k13,k14,k23,k24,k34 = 0 tel que
k12,k34 = a    et
k13,k24 = b    et
k14,k23 = c    et
k12+k13+k14 = a-k12+k23+k24 = b-k13+c-k23+k34 = c-k14+b-k24+a-k34 = C

Sudoku avec des contraintes additionnelles[modifier | modifier le code]

Plusieurs types de contraintes existent sur des Sudokus avec des régions de 3x3. Les noms n'ayant pas été standardisés, les liens externes pointent vers les définitions :

Type Nombre de grilles Auteur(s) Vérification formelle
3doku 104015259648 Stertenbrink Oui
Disjoint Groups 201105135151764480 Russell Oui
Hypercube 37739520 Stertenbrink Oui
Magic Sudoku 5971968 Stertenbrink Oui
Sudoku X 55613393399531520 Russell Oui
NRC Sudoku 6337174388428800 Brouwer Oui

Tous les Sudokus sont valides (unicité des nombres dans les lignes, colonnes et régions) après l'application des opérations qui préservent les propriétés du groupe du Sudoku. Certains Sudokus sont spéciaux dans le sens où certaines opérations ont le même effet que le renommage des chiffres :

Transformation Nombre de grilles Auteur(s) Vérification formelle
Transposition 10980179804160 Russell Indirectement
Quart de tour 4737761280 Indirectement
Moitié de tour 56425064693760 Indirectement
Permutation des bandes 5384326348800 Indirectement
Permutations des lignes dans les bandes 39007939461120 Indirectement

Nombre minimal de chiffres dans la grille[modifier | modifier le code]

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[modifier | modifier le code]

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[20], 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 permettrait 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 fourni des grilles qui étaient déjà dans la liste de Royle[21],[22], ce qui renforce l'idée de la quasi-complétude de l'ensemble fourni par Royle.

Sudoku avec d'autres contraintes[modifier | modifier le code]

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[23], 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[24], des grilles avec 8 valeurs ont été proposées par Guenter Stertenbrink.
  • Magic Sudoku[25], 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[26], Gordon Royle a donné un exemple avec 17 valeurs, borne supposée minimale.
  • NRC Sudoku[27], 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[modifier | modifier le code]

Les Du-sum-oh [28] 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 [29]. Il a donné plusieurs exemples.

Killer Sudoku[modifier | modifier le code]

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 commencer la grille n'est pas connue, ni conjecturée.

Une variante proposée par Miyuki Misawa[30] 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.

Méthode de Felgenhauer/Jarvis pour l'énumération de la grille de 9×9[modifier | modifier le code]

L'approche décrite ici est historiquement la première stratégie employée pour énumérer les solutions d'une grille de Sudoku classique (régions de 3x3 dans une grille de 9x9). Elle a été proposée par Felgenhauer et Jarvis[2].

Aperçu[modifier | modifier le code]

L'analyse débute par l'étude des permutations de la première bande utilisée dans des solutions valides. Une fois que la classe d'équivalence et les symétries de cette bande, pour des solutions partielles, sont identifiées, on s'intéresse aux deux autres bandes qui sont construites et comptées pour chaque classe d'équivalence. En effectuant la somme de l'ensemble des combinaisons, on obtient le nombre total de solutions, soit 6 670 903 752 021 072 936 960 (environ 6.67×1021).

Afin de réduire l'espace de recherche, on part du principe que le renommage (par exemple changer le « 1 » en « 2 » et vice-versa) des cases produit une solution équivalente. Une grille autorise 9! = 362880 renommages de ce type : un chiffre choisi parmi les 9 chiffres possibles est attribué au premier type de case, un chiffre parmi les 8 restants est attribué au deuxième type de case, un chiffre parmi les 7 restants est attribué au troisième type de case, etc.

Références[modifier | modifier le code]

  1. « (lien) » (sur l'Internet Archive)
  2. a et b http://www.afjarvis.staff.shef.ac.uk/sudoku/sudoku.pdf
  3. a et b (en) Denis Berthier, « The Hidden Logic of Sudoku », Lulu Publishers,‎ 2007-05-16 (lire en ligne)
  4. pour plus de détails, voir (en) [1]
  5. (en) Denis Berthier, « Pattern-Based Constraint Satisfaction and Logic Puzzles », Lulu Publishers, ISBN 978-1-291-20339-4,‎ 20 november 2012
  6. Denis Berthier, Unbiased Statistics of a CSP - A Controlled-Bias Generator, International Joint Conferences on Computer, Information, Systems Sciences and Engineering (CISSE 09), December 4-12, 2009
  7. Solving Sudokus---Coloring by Numbers
  8. a et b http://www2.ic-net.or.jp/~takaken/auto/guest/bbs46.html
  9. (en) http://www.csse.uwa.edu.au/~gordon/sudokumin.php]
  10. http://www.shef.ac.uk/~pm1afj/sudoku/
  11. (en) http://www.shef.ac.uk/~pm1afj/sudoku/
  12. suite A107739 de l'OEIS
  13. http://www.shef.ac.uk/~pm1afj/sudoku/sudgroup.html (pour plus de détails, voir (en) http://www.shef.ac.uk/~pm1afj/sudoku/sudgroup.html et suite A109741 de l'OEIS)
  14. http://arxiv.org/pdf/1201.0749v1.pdf
  15. http://www.csse.uwa.edu.au/~gordon/sudokumin.php
  16. Sudoku Players' Forums :: View topic - Su-Doku's maths
  17. Sudoku Players' Forums :: View topic - Su-Doku's maths
  18. Sudoku Players' Forums :: View topic - RxC Sudoku band counting algorithm
  19. Sudoku Players' Forums :: View topic - RxC Sudoku band counting algorithm
  20. Minimum Sudoku
  21. Gary McGuire's Minimum Sudoku Page, Sudoku Checker
  22. http://www.csse.uwa.edu.au/~gordon/sudokupat.php?cn=3 strangely familiar
  23. Sudoku Players' Forums :: View topic - Minimum number of clues in Sudoku DG
  24. http://magictour.free.fr/sudoku6
  25. Sudoku Players' Forums :: View topic - Number of « magic sudokus » (and random generation)
  26. Sudoku Players' Forums :: View topic - 13-clue Sudoku X
  27. NRC Sudokus
  28. Du-Sum-Oh Puzzles
  29. Du-Sum-Oh Puzzles
  30. Sum Number Place( =,< > )