Symétries des grilles

Gordon Royle considère que deux grilles complètes doivent être considérées comme équivalentes si elles peuvent être transformées l’une en l’autre (ou l’inverse) grâce à une combinaison quelconque des opérations suivantes :

1. échange des lignes avec les colonnes (transposition - deux solutions)
2. permutations des 9 nombres (9! solutions)
3. permutation des trois lignes au sein d'un même bloc (3!³ solutions) ou des trois colonnes (3!³ solutions)
4. permutation des trois blocs sur une ligne de blocs (3! solutions) ou sur une colonne de blocs (3! solutions)

Une grille complète permet ainsi de créer un total de 2×9!×(3!)^8 = 1 218 998 108 160 grilles essentiellement équivalentes. On remarque l’analogie avec les opérations matricielles en algèbre linéaire.

Nombre de grilles complètes

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 à

${\displaystyle {\frac {81!}{9!^{9}}}\approx 5,31306887\times 10^{70}}$

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 nombre de carrés latins de côté 9.

Enfin, le nombre de grilles complètes possibles est inférieur à ${\displaystyle 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é^[27] que ce nombre de grilles était de^{[27],[28],[29]} :

${\displaystyle \mathbb {N} =6\;670\;903\;752\;021\;072\;936\;960\approx 6,67\times 10^{21}}$

Ce nombre ${\displaystyle \mathbb {N} }$ est égal à :

9!×72²×2⁷×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^[30],[29]. Un catalogue complet de ces grilles a été constitué.

Nombre de grilles incomplètes

Quant au problème suivant, il semble non résolu : si on s’intéresse au nombre de problèmes proposables, ce nombre est inconnu ; en revanche, on sait qu’il est nettement plus important que le nombre ${\displaystyle \mathbb {N} }$ indiqué ci-dessus car il existe de très nombreuses façons de présenter des grilles initiales dont la solution (unique) conduit à la même grille terminée (complète). En effet, partant d'une grille complète, on peut construire un problème proposable par la méthode suivante :

1. au départ, aucune case de la grille complète n'est « nécessaire » ;
2. choisir une case non « nécessaire » quelconque. Si la suppression de la case choisie conduit à une grille à plusieurs solutions, la marquer comme « nécessaire », sinon la supprimer ;
3. si toutes les cases remplies sont « nécessaires », la grille incomplète est un problème proposable ; sinon réitérer l'étape précédente.

On voit facilement que dans les premières étapes, aucune case n'est réellement nécessaire, ce qui permet d'imposer un problème différent d'un problème « proposable » donné, simplement en vidant une des cases qui était fournie dans ce problème.

Il est facile de montrer, sur certains exemples de grilles complètes, à quel point on peut, pour une même grille complète, présenter des grilles initiales de difficultés tout à fait contrastées, depuis les grilles pour débutants jusqu’aux grilles dites diaboliques ; il est en tout cas très facile, connaissant une grille initiale diabolique, de fabriquer une grille pour débutant dont la solution unique complète soit identique à celle de la grille diabolique choisie !

Cependant, il existe désormais une estimation (basée sur une approche statistique) du nombre total de problèmes minimaux (voir la section « classification des problèmes »).

Nombre minimal de révélés

Exemple de sudoku ne comportant que 17 révélés (avec sa solution présentée sous forme d’animation).

Un révélé étant une case dont le contenu est visible sur une grille de sudoku, se pose le problème de leur nombre minimal.

Le nombre maximal de « révélés » dans une grille qui ne fournisse pas une solution unique est une grille complète moins quatre : si dans une grille complète deux occurrences de deux nombres sont supprimées, et que ces occurrences sont aux angles d'un rectangle, et que deux de ces cellules sont dans un même groupe, alors il y a deux solutions pour compléter la grille. Ceci étant une caractéristique générale des carrés latins, la plupart des grilles de sudoku ont le même maximum.

Le problème de savoir combien de cases initiales remplies sont nécessaires pour conduire à une solution unique est, à ce jour, sans réponse sûre. Le meilleur résultat, obtenu par des Japonais, est de 17 cases sans contrainte de symétrie^[31],[32]. Aujourd’hui on sait qu’il existe un très grand nombre de problèmes comportant 17 révélés (voir un exemple ci-contre avec sa solution).

Rien ne dit que ce ne soit pas possible avec moins de nombres. D'après un article de Gary McGuire publié dans le site de prépublication ArXiv il n'est pas possible d’en définir un ne comportant que 16 révélés et ayant une solution unique^{[33],[34],[29]}.

Autre problème non résolu : à cette date, aucun résultat n’existe sur le nombre de grilles complètes dans un super sudoku (grille 16 × 16).

Principe

À un niveau élémentaire, il faut balayer la grille pour chaque chiffre de un à neuf, et pour chaque bloc :

• Regarder si le chiffre y figure ou pas ;
• Si le chiffre y figure, regarder quelles sont les cases qu'il interdit sur les autres blocs en ligne ou en colonne ;
• Si le chiffre n'y figure pas, regarder quelles sont les cases où il ne peut pas figurer, compte tenu de la position des autres instances du même chiffre dans les autres blocs en ligne ou en colonne.

Lorsqu'il n'y a qu'une seule possibilité pour une ligne, une colonne, ou un bloc, c'est nécessairement là que le chiffre doit s'inscrire. Avec un peu d'expérience, il est possible de visualiser les cases « allumées » sur l'ensemble de la grille, où ce chiffre peut figurer, ce qui permet de détecter des configurations plus avancées.

Quand un problème peut être résolu en n’utilisant que les règles élémentaires de cette section, des joueurs expérimentés peuvent se dispenser de l’écriture explicite des candidats. Ces problèmes correspondent à des niveaux « facile » ou « élémentaire ».

Singleton

Le « singleton » correspond au cas trivial où il n'y a plus qu'une seule cellule vide dans une « région » (ligne, colonne ou bloc). Dans ce cas, la valeur de la cellule est évidemment le seul nombre manquant dans la région : c'est à la fois le seul endroit où le nombre manquant puisse être mis (singleton caché), et c'est la seule valeur que peut recevoir la cellule vide (singleton nu).

Cette configuration se rencontre surtout en fin de problème, quand presque toutes les cellules ont été remplies.

Plus généralement, le « singleton » correspond au cas où il n'y a (localement) qu'une seule solution : une case ne peut recevoir qu'une seule valeur (singleton nu), ou bien une valeur ne peut être affectée qu'à une seule case (singleton caché), tout autre choix conduisant à une incohérence immédiate. Il s'oppose aux « paires », « triplets » et « quadruplets », où la discussion porte sur plusieurs valeurs simultanément.

Élimination directe - Singleton caché

Identification d'un singleton caché : il n'y a qu'une seule case possible pour un « 4 » dans le bloc supérieur droit.

La recherche d'un « singleton caché » revient à se poser la question « Dans cette région (ligne, colonne ou bloc), quelles sont les cases qui peuvent accueillir un 1 (2 ou 3 ou… 9) ? » : si la position est unique dans la région considérée, alors le candidat devient valeur en cette position.

La recherche de singleton caché est d'autant plus facile que la valeur est fréquente dans la grille : les contraintes de positionnement augmentent, alors que le nombre de positions possibles diminue.

Le marquage des cellules n'apporte qu'une faible plus-value pour la recherche des singletons cachés : il faut de toute manière balayer toute la région pour vérifier que la valeur recherchée n'y figure qu'une seule fois comme candidat. C'est pour cette raison que ces singletons sont qualifiés de « cachés ».

Inversement, le « singleton caché » est souvent facilement révélé par un balayage systématique des chiffres et des blocs, parce que sa position ne dépend que de la position du chiffre considéré dans les blocs voisins, et de ce que les cases sont libres ou occupées dans le bloc considéré. Dans l'exemple ci-contre, quand on en est à estimer les possibilités du « 4 » pour le bloc supérieur droit, la seule information nécessaire pour les cases du « 7 » et du « 8 » est qu'elles sont occupées par des chiffres différents de 4 ; la conclusion est la même quel que le soit le chiffre contenu dans ces cases.

Élimination indirecte

Le « 1 » dans le bloc centre droit ne peut qu'être sur la colonne g. Le « 1 » du bloc inférieur droit est donc nécessairement en Gj.

L'élimination indirecte est un prolongement de l'élimination directe.

Lorsqu'on balaye la grille pour localiser les cases admissibles pour un certain candidat, on peut se trouver dans la situation où dans un bloc, les cases admissibles sont toutes localisées sur une même ligne (ou une même colonne). Dans ce cas, quelle que soit la position finale du candidat dans le bloc, cet alignement interdit pour le candidat les autres cases libres de cette même ligne (ou colonne) situées dans les autres blocs. Autrement dit : si dans un bloc, les candidats sont sur une même ligne, le candidat est exclu des autres cases libres de la ligne.

De même, quand dans deux blocs en ligne, les candidats sont limités à deux lignes, les candidats du troisième bloc ne peuvent se trouver que sur la troisième ligne (et réciproquement pour les colonnes).

Cette interdiction peut conduire à identifier un singleton caché, comme dans le premier exemple ci-contre. Elle peut également, de manière plus subtile, conduire à conclure que dans un autre bloc de cette ligne (ou colonne), les candidats ne peuvent se situer que sur un même ligne ou colonne, conduisant de proche en proche à une élimination indirecte en chaîne. Cette première application de l'élimination indirecte peut par conséquent se faire sans marquage, mais demande plus de réflexion.

Exemple d'éliminations indirectes en cascade.

Dans l'exemple ci-contre, après que les paires identifiables ont été marquées, l'examen du candidat "1" permet par exemple d'identifier deux singletons, en enchaînant quatre éliminations indirectes. Il n'y a qu'un seul "1" dans la cellule "Aa", ce qui interdit la présence d'un autre "1" en ligne "A" et en colonne "a" (en jaune).

• On commence par raisonner sur les blocs de la verticale centrale pour faire deux éliminations indirectes :
  • Dans le bloc supérieur central, il ne peut donc y avoir de "1" que sur la colonne "d" (en vert), excluant ce même candidat sur le reste de la colonne.
  • Par conséquent, dans le bloc inférieur central, le "1" ne peut se trouver que sur la colonne "e", excluant ce même candidat sur le reste de la colonne.
  • Et donc, dans le bloc central, le candidat "1" ne peut se trouver que sur la colonne "f" (en bleu).
• On raisonne à présent sur les blocs de l'horizontale centrale pour une élimination indirecte sur deux lignes :
  • Dans le bloc central, "1" ne peut que se trouver sur les lignes "E&F" (en bleu).
  • Mais dans le bloc de centre gauche, le "1" est restreint à ces mêmes lignes "E&F" (en vert).
  • Par conséquent, dans le bloc de centre droit, le "1" se trouve nécessairement sur la ligne "D" (en bleu).
• De là, on examine les blocs de droite pour une seconde élimination sur deux lignes :
  • Dans le bloc de centre droit, le "1" est à présent restreint aux colonnes "h&j" (en bleu).
  • Mais dans le bloc supérieur droit, le "1" est également restreint à ces mêmes colonnes (en vert).
  • Donc, dans le bloc inférieur droit, le "1" ne peut pas se trouver dans les colonnes "h&j" (en jaune).
• On voit à présent que sur la ligne "J", les deux cellules qui avaient été marquées des paires "12" et "13" ne peuvent donc pas recevoir un "1" ; leur valeur est donc nécessairement "2" et "3".

Principe

La deuxième méthode de balayage consiste à se demander, sur un groupe donné (ligne, colonne ou bloc) : (1) quels sont les manquants, et (2) où peuvent-ils se trouver. L'objet est d'identifier des « singletons cachés », et à défaut, des paires à marquer.

Cette méthode est particulièrement triviale dans le cas où il ne manque qu'un seul chiffre dans l'entité, dans ce cas la case est un « singleton », à la fois un « singleton nu » et un « singleton caché », et sa solution est immédiate.

Elle est d'autant plus fructueuse qu'il y a plus de cases remplies sur l'entité considérée. Elle peut donc être faite d'office dès qu'une entité n'a plus que deux cases vides (inscription directe des paires), puis, par ordre de préférence, quand une entité n'a plus que trois, quatre, voire cinq cases vides. Un balayage à « six cases vides » ne donnera des fruits qu'exceptionnellement (mais peut en donner).

Singleton nu

Exemple de grille avec un « singleton nu » : la colonne d doit être complétée par « 14589 », et sur la ligne C seule la valeur « 9 » est possible.

Si une cellule n'accepte qu'un unique candidat, alors c’est la valeur de cette cellule. C'est ce que l'on appelle un « singleton nu ». Le cas a d'autant plus de chance de se produire que la cellule examinée se trouve à l'intersection de régions assez remplies, ce qui augmente les contraintes et restreint le nombre de valeurs possibles sur la cellule examinée.

Cette appellation de « singleton nu » vient de ce que dans les logiciels d'aide à la résolution des sudoku, quand la liste des candidats est affichée sur chaque cellule, ces cases sont immédiatement visibles (nues) parce que ce sont les seules qui n'ont qu'un seul candidat (singleton)^[35]. Pour l'anecdote, cette désignation de « singleton nu » (naked single, en anglais, soit littéralement « célibataire dénudé ») peut conduire certains filtres de contrôle parental à limiter l'accès aux pages de discussion du sudoku^[36]…

Marquage des doublets

Dans ce type de balayage, il est utile de marquer directement les paires, c'est-à-dire les cases de la grille où il ne reste plus que deux candidats. Ces cases peuvent être remplies par le couple de chiffres, inscrits en petit ou au crayon ; et la seule évolution possible pour de telles cases est de basculer sur l'une ou l'autre de ces valeurs. L'avantage de ce marquage est double :

• Dans le balayage « élémentaire » précédent, il permet dans certains cas (quand une même paire est sur la même ligne, colonne, ou bloc) de faire comme si ces deux chiffres étaient effectivement présents sur la grille pour bloquer les possibilités associées aux autres cases.
• En fin de problème, ces cases permettent de terminer très rapidement une grille, puisque dès qu'une des valeurs de la paire est trouvée sur une autre case liée (en ligne, en colonne, ou dans le bloc), on peut immédiatement inscrire l'autre valeur comme valeur effective, sans avoir à refaire tout le raisonnement qui avait conduit initialement à limiter les possibilités à deux valeurs.

Paires couplées

La paire « 78 » apparaît deux fois sur la colonne « e », interdisant ces deux valeurs dans les autres cases de la colonne.

Lorsque les paires sont marquées, on peut rencontrer une même paire de candidats dans deux cases d'un même groupe (ligne, colonne ou bloc). Dans ce cas, les deux cases occupées par la paire sont couplées et fonctionnent comme s'ils étaient occupés par les candidats correspondants, interdisant ces deux candidats à toutes les autres cases libres de ce même groupe (ligne, colonne ou bloc).

Quelques cas particuliers sont facilement identifiables :

• Lorsqu'il ne reste plus que deux cases libres sur une ligne ou une colonne, ces deux cases forment par construction une paire nue ; et si elles sont situées dans un même bloc, elles interdisent ces valeurs au reste du bloc.
• Lorsqu'une paire couplée apparaît dans un groupe ayant trois cases libres, la troisième case n'a qu'une valeur possible : c'est un singleton nu.
• Lorsqu'une paire couplée apparaît dans un groupe ayant quatre cases libres, les deux cases restantes forment nécessairement une paire sur laquelle les deux autres valeurs restantes sont possibles : c'est une paire cachée.

La prise en compte de ces paires couplées peut conduire à noter de nouvelles paires. Dans l'exemple ci-contre, la recherche des candidats possibles a conduit notamment à identifier deux paires « 78 » sur la colonne « e ». Sur les six cases vides de la colonne, il n'y en a donc que quatre qui sont réellement libres, puisque deux peuvent être considérées comme quasi remplies.

• En recherchant où les quatre autres valeurs « 1459 » peuvent être localisées sur cette même colonne, on identifie une nouvelle paire « 14 » en ligne A, et deux paires « 59 » en lignes D et J.
• La case restante en ligne F est donc également une paire « 14 ».

Élimination indirecte

Lorsqu'on balaye la grille pour localiser les cases admissibles pour un certain candidat, on peut se trouver dans la situation où le candidat en cours d'examen figure dans une paire couplée sur une même ligne ou colonne. Dans ce cas, le candidat est exclu du reste de cette ligne (ou colonne), limitant les possibilités dans les autres blocs touchés par cette ligne (ou colonne).

Paires cachées

Trois paires cachées marquées en jaune.

Les « paires cachées » demandent généralement une recherche systématique pour être détectées. Pour les détecter, il faut effectuer un balayage systématique par bloc (ligne, colonne, ou carré). Sur chaque bloc, il faut se poser la question « où sont les 1 » [...] « où sont les 9 ». Si un des chiffres ne peut être que dans deux emplacements possibles, il est possible qu'il fasse partie d'une paire cachée ; et si un autre chiffre ne peut être que dans ces deux mêmes emplacements, ces deux chiffres forment ensemble une « paire cachée ». Dans ce cas, parce que ces deux chiffres ne peuvent qu'être à ces deux emplacements, il n'est pas possible qu'un autre chiffre se trouve sur ces mêmes emplacements, ce qui élimine les possibilités correspondantes pour les autres chiffres.

La recherche des paires cachées est beaucoup plus fastidieuse, parce qu'elle porte théoriquement sur les 3x9=27 blocs, pour lesquels il faut vérifier si l'une des 9x8/2=36 paires possibles ne peut occuper que deux parmi 9 cases possibles. Il est possible d'accélérer un peu cette recherche, en remarquant d'une part que si la recherche est systématique, une fois la paire "a-b" testée il est inutile de tester la paire "b-a", et surtout, d’autre part, que si une case est déjà occupée par un doublet, une éventuelle paire cachée ne peut porter que sur ces deux mêmes éléments.

Par exemple, sur la figure ci-jointe, trois paires cachées ont été identifiées, qui permettent de remplir une case chacune :

• Les cases B-bc (jaune) sont les seules du carré supérieur gauche où peuvent être présentes les valeurs 6 et 7 ; de ce fait, le 5 n'est possible dans ce carré qu'en Ab (vert).
• Sur la ligne C, les cases C-df (jaune) sont les seules de la ligne pouvant recevoir les valeurs 4 et 8 ; de ce fait, le 3 n'est possible dans cette ligne qu'en Ca (vert).
• Sur la ligne I, les cases I-ef (jaune) sont les seules de la ligne à pouvoir recevoir les valeurs 3 et 8 ; de ce fait, le 5 n'est possible qu'en Ih (vert).

Triplets nus

Lorsqu'on recherche les manquants sur un groupe où les paires sont marquées, on peut se trouver dans la situation où le groupe affiche deux paires « ab » et « bc » ayant un élément « b » en commun. Il convient alors d'examiner si une autre case de ce groupe n'admet comme valeurs possibles que ces trois mêmes valeurs « abc ». Si c'est le cas, ces trois valeurs se répartissent nécessairement sur ces trois cases, et sont par conséquent exclues des autres cases libres du groupe :

• Si le groupe n'a que quatre cases libres, la quatrième est nécessairement un singleton.
• Si le groupe a cinq cases libres, les deux autres forment nécessairement une paire couplée.
• D'une manière générale, il devient possible de rechercher singletons et paires sur les autres cases libres du groupe, en excluant ces trois valeurs « abc ».

Gestion des nombres candidats

Un exemple de la notation pointée.

Ces recherches sont plus laborieuses que les précédentes, et pour les conduire systématiquement, il est plus facile de marquer les cellules. La notion de candidat n’est pas inhérente au problème du Sudoku, mais doit être introduite par le joueur pour mettre en œuvre la plupart des méthodes de résolution.

Lorsqu’un chiffre n’est pas a priori impossible dans une cellule, on dit qu’il est un candidat. Alors que les dévoilés sont les données initiales du problème, l’ensemble des candidats évolue au cours du processus de résolution. Il ne peut que diminuer ; et cela se produit lorsqu’on a démontré (par les diverses méthodes décrites plus bas) qu’un candidat est en fait impossible. Les fondements logiques formels de cette notion (qui n’est pas aussi évidente qu’il paraît) ont été définis et étudiés en détail dans La Logique cachée du Sudoku, un livre en anglais (The Hidden Logic of Sudoku^[24]) ; ils font appel à la logique épistémique. L’article From Constraints to Resolution Rules, Part I: Conceptual Framework^[37], librement disponible sur les pages web de son auteur, expose aussi cette logique dans le cadre général des problèmes de satisfaction de contraintes.

Il y a deux notations utilisées pour les candidats : indicée et pointée.

• Pour la notation indicée, les candidats sont inscrits dans une cellule, chaque chiffre occupant ou non une place précise. Quand un candidat est impossible, il est rayé de la liste. L’inconvénient de cette méthode est que les journaux publient des grilles de petite taille, ce qui rend difficile l’inscription de plusieurs chiffres dans une même cellule. Plusieurs joueurs reproduisent à plus grande échelle de telles grilles ou ont recours à un crayon à pointe fine.
• Pour la notation pointée, les joueurs inscrivent des points dans les cellules vides. Il y a deux logiques possibles, opposées et mutuellement exclusives :
  • Quand un candidat s'avère impossible, le point correspondant est noirci. Par exemple, pour indiquer que « 1 » ne peut pas être candidat, un point est marqué en haut à gauche dans la cellule. Cette notation permet de jouer directement avec une grille imprimée dans un journal, et présente l'avantage de ne pas avoir à effacer ses marques. Cependant, elle demande du soin : il est possible de mal placer un point dans un moment d’inattention et une petite marque faite par erreur peut mener à de la confusion. Certains joueurs préfèrent utiliser un stylo pour limiter les fautes.
  • Quand un candidat s'avère possible, le point correspondant est noirci. La position relative du point indique le chiffre manquant. Par exemple, pour représenter le chiffre 1, le joueur positionnera son point en haut à gauche de la cellule (cf schéma ci-dessus). S'il s'avère plus tard dans le raisonnement que cette hypothèse peut être éliminée, il suffira alors de barrer ce point d'une petite croix.

Lorsqu'on peut déduire qu'un nombre est nécessairement la valeur d’une cellule :

• on peut supprimer tous les autres candidats de cette cellule,
• et on peut supprimer ce nombre comme candidat de toutes les autres cellules de la même ligne, de la même colonne et du même bloc.

Élimination indirecte - interactions ligne-bloc et colonne-bloc

Lorsqu'on utilise un marquage des candidats possibles, la méthode d'élimination indirecte (mentionnée ci-dessus dans les méthodes « faciles ») se décline alors en deux cas permettant d'exclure certains candidats :

• Comme précédemment, si dans un bloc, les candidats se concentrent sur une même ligne (ou colonne), le candidat est exclu sur le reste de la ligne (ou colonne). Ce premier cas se rencontrait déjà dans les méthodes simples, parce qu'il permet parfois d'identifier un singleton caché.
• De plus à présent, si dans une ligne (ou colonne) les candidats se concentrent sur un même bloc, le candidat est exclu du reste du bloc. Ce deuxième cas ne peut jamais conduire à identifier un singleton caché.

L'élimination indirecte peut se faire formellement sur des cellules marquées, mais sa détection n'est pas tellement facilitée par le marquage.

Groupes nus et cachés

Les groupes nus et cachés correspondent à des situations assez symétriques : dans une même région (ligne, colonne ou bloc), on recherche un groupe de n (couramment de deux à quatre) nombres dont la présence est possible dans un nombre égal de cases vides et présentant une configuration remarquable, soit que la présence de ces nombres soit impossible dans les autres cases de la même région, soit qu'aucun autre nombre ne puisse apparaître dans les cases du groupe :

• si seuls les nombres du groupe peuvent apparaître dans les cases (mais la présence de ces nombres est éventuellement possible dans d'autres cases de la même région) : il s'agit alors d'un « groupe nu » ;
• si les nombres du groupe ne peuvent pas apparaître dans d'autres cases de la même région (mais d'autres nombres peuvent éventuellement apparaître dans les cases du groupe) : il s'agit alors d'un « groupe caché ».

On voit que ces définitions sont symétriques : si un groupe de n cases vides dans une région forme un groupe nu avec n candidats, les autres cases vides formeront un groupe caché (avec un nombre éventuellement différent de membres) avec le reste des candidats ; et inversement.

La recherche des singletons cachés a déjà été faite avec le balayage élémentaire, et les singletons nus ont déjà été identifiés avec la recherche des manquants et le marquage des paires. De même, les paires nues couplées peuvent être identifiées par un simple marquage des paires. Ces groupes nus et cachés non triviaux ne peuvent apporter du nouveau que dans les régions ayant de nombreuses cases libres : au minimum, si dans une même région il y a à la fois un groupe nu (de deux cases ou plus) et un groupe caché (de deux cases ou plus), la région a nécessairement au moins quatre cases libres ou plus. Si une région a moins de quatre cases libres, elle ne peut plus être réduite ; si un sous-groupe a moins de quatre membres, il ne peut pas lui-même être réduit ; et une fois qu'une telle région a été réduite, il n'est plus nécessaire de l'examiner par la suite.

La méthode ne trouve sa pleine application qu'à partir de cinq cases libres et la recherche de triplets nus : une région de cinq cases libres peut comporter un triplet nu (et une paire cachée), une région de six cases peut comporter un triplet ou un quadruplet nu (et, respectivement, un triplet ou une paire cachée), et ainsi de suite.

Quel que soit le groupe identifié, on peut alors éliminer les candidats:

• si le groupe identifié est nu, on peut le « cacher », en supprimant ses candidats des autres cases de la région ;
• s'il est caché, on peut le « dénuder », en supprimant du groupes les candidats qui n'en font pas partie.

Après cette réduction, la situation est celle d'une exclusion mutuelle : les nombres du groupe n'apparaissent pas ailleurs, et il n'y a que les nombres du groupe dans les cases.

Groupes nus

Un groupe nu en colonne e : Le groupe des 2 cases Ce et Ge de la colonne e forme une paire nue dont les candidats sont 78 ; on peut donc éliminer les candidats 7 et le 8 des autres cases de la colonne e (le 8 de la case Fe et les 7 et 8 des cases Ae, De et Je).

Le traitement des « paires liées » a été décrit avec le marquage des paires, et la possibilité d'identifier parfois quelques « triplets nus » y avait été signalée. Les « groupes nus » sont le cas plus général de ce traitement. Le raisonnement est le même que le groupe soit de deux, de trois, ou de quatre cases (et sera donné ici pour trois cases) ; mais il demande en pratique de marquer les candidats.

La règle est la suivante. Si dans une même région (ligne, colonne ou bloc), on observe un groupe de trois cases pour lesquelles :
i) il y a au plus trois candidats, et
ii) tous ces candidats sont pris parmi les trois mêmes valeurs ;
alors nécessairement, ces trois valeurs devront être prises sur ces trois cases, et ne peuvent pas aller ailleurs dans cette région. La démonstration se fait par l'absurde : si l'une de ces trois valeurs candidates était affectée à une case autre de cette région, alors il ne resterait plus que deux valeurs possibles pour remplir ces trois cases, conduisant à une impossibilité. De ce fait, quand cette configuration de groupe est identifiée, les valeurs du groupe ne peuvent pas être prises par les cases qui n'appartiennent pas au groupe : dans le reste de la région, les candidats correspondants à ces valeurs peuvent être supprimés.

Lorsque n est supérieur à 2, il arrive fréquemment qu'au moins une des cases du groupe n'ait pas comme candidats l'ensemble des chiffres de la liste : on parle alors de groupe « incomplet », mais cela n'enlève rien à la validité de la manœuvre d'élimination.

Les groupes nus exploitables par cette méthode comprennent deux, trois ou quatre éléments. On peut remarquer en effet que le cas limite d'un « groupe nu » à un élément correspond au cas des singletons nus. Inversement, si un « groupe nu » a plus que quatre éléments, on constate qu'en pratique, il est associé symétriquement à un « groupe caché » de moins de cinq éléments, qu'il est plus facile de rechercher.

De même que dans le cas des « singletons nus », ces configurations tirent leur nom de ce qu'elles sont immédiatement apparentes (dévoilées, donc « nues ») sur les grilles où les candidats ont été marqués. En effet, ces « groupes nus » peuvent facilement être recherchés formellement sur une grille où les candidats ont été marqués, et où ces triplets ont ainsi été rendus plus visibles : dès qu'une case n'a qu'un faible nombre de candidats, on recherche la possibilité d'un tel groupe, en regardant si d'autres cases de la même région (ligne, colonne ou bloc) ont des contraintes similaires.

Recherche des « groupes nus »

La recherche des « groupes nus » se fait après marquage des candidats, par balayage systématique des cases contenant deux, trois ou quatre candidats. Les étapes en sont typiquement, par ordre de difficulté croissante :

• Sur une case à deux candidats, on recherche sur les trois régions associées (ligne, colonne ou bloc) si une autre case contient les deux mêmes candidats.
• À défaut, sur une case à deux candidats, on recherche s'il existe dans la région deux autres cases ayant deux candidats dont un commun, ouvrant la possibilité d'un triplet lié incomplet (voire d'un quadruplet lié incomplet).

Ces deux premiers balayages peuvent être effectués même lorsque seules les paires candidates sont marquées.

Si ce premier balayage a échoué, un « groupe nu » aura nécessairement au moins trois candidats, dont au moins une case complète (sinon le groupe aurait été détecté dans l'étape précédente). Il formera donc formera un triplet ou un quadruplet :

• Sur une case à trois candidats, on recherche de même sur les trois régions associées si deux autres cases (y compris, le cas échéant, celles n'ayant que deux candidats) prennent leurs candidats dans ces trois mêmes valeurs.
• À défaut, on recherche s'il existe des cases de trois candidats dont deux communs, ouvrant la possibilité d'un quadruplet lié incomplet.

Si ce second balayage a échoué, un éventuel « groupe nu » aura nécessairement quatre candidat, dont au moins une case complète. En dernier ressort, on peut rechercher sur toutes les cases à quatre candidats si ces quatre mêmes candidats se retrouvent sur quatre cases différentes de la même région.

Groupes cachés

Un groupe caché 124 en colonne f : Le groupe de 3 cases Af, Gf et Jf de la colonne f forme un trio camouflé (incomplet) dont les candidats sont 124 ; on peut donc éliminer les candidats 8 et 9 des cases Af et Gf, et les candidats 3 et 8 de la case Jf (ce qui fait apparaître dans le pavé Zy un solitaire camouflé 7 à la case Gd).

Une première remarque est que le complémentaire d'un groupe caché est un groupe nu : si sur les n+c cases libres, un sous-ensemble de c cases forment un « groupe caché » de c candidats (c'est-à-dire que ces c candidats n'apparaissent pas dans les n autres cases), le reste des n cases forme de son côté un groupe nu de n candidats (c'est-à-dire que les candidats du groupe c n'y figurent pas).

Pour rechercher un groupe caché, il faut chercher un groupe de c valeurs dont les candidats n'apparaissent que sur c cases d'une même région. Au sein de cet ensemble de cases, certaines ne contiennent pas le groupe au complet et peuvent contenir d'autres candidats étrangers au groupe. Alternativement, on peut chercher ce même groupe de c valeurs, qui soient exclues de n cases libres du groupe.

Le marquage ne permet pas de les identifier rapidement, et une recherche systématique est nécessaire, ce qui est à l'origine de la désignation de « groupe caché » : leur identification est beaucoup plus laborieuse que celle des « groupes nus », et conduit à des sudoku de difficulté plus importante. Il faut noter de plus que la difficulté croît très fortement avec le nombre de cases du groupe.

L'identification des groupes cachés peut souvent se faire indirectement par l'identification de groupes nus de taille supérieure. Dans l'exemple ci-contre, la recherche d'un triplet nu en colonne "f" conduit à remarquer le groupe "367" en Df et Ff.

• Il n'y a pas d'autre case en colonne "f" limitée aux candidats "367", mais le "3678" en Ef suggère d'étendre la recherche à des quadruplets nus.
• Il n'y a pas d'autre case en colonne "f" limitée aux candidats "3678", mais deux nouvelles cases y sont presque, en y ajoutant le candidat "9" : les cases Cf et Hf.

On a ainsi trouvé de proche en proche un groupe nu de cinq candidats "36789". Le complémentaire, correspondant aux cases Af, Gf et Jf, correspond dont à un groupe caché de trois valeurs "124".

La recherche directe d'un groupe caché porte sur des petits groupes de deux à trois candidats (exceptionnellement quatre), donc ne peut pas porter sur des candidats apparaissant plus souvent dans la région considérée. La recherche consiste à déterminer d'abord les candidats susceptibles de former un groupe caché dans la région, puis de vérifier sur les candidats identifiés s'ils forment effectivement un tel groupe. Pour reprendre l'exemple ci-contre :

• La recherche directe d'un triplet caché en colonne "f" conduit à limiter les membres potentiels aux candidats "1" (deux apparitions), "2", "4" et "9" (trois apparitions). Un triplet caché ne peut donc porter que sur les candidats "1249", l'un d'entre eux étant de trop.
• Un candidat apparaissant trois fois apparaîtra dans les trois cases du triplet caché. Le candidat "9" apparaissant deux fois sans le reste du groupe, il n'est pas possible qu'il fasse partie d'un triplet caché sur cette base, puisqu'il faudrait qu'un autre candidat du triplet fasse toutes ses apparitions sur une dernière case unique.
• Les candidats à tester se limitent donc à "124", et une vérification rapide montre qu'ils forment effectivement un triplet caché.

Fish ou Poissons (X-Wing, Swordfish, Jellyfish)

X-wing sur les lignes F et J pour 8 : Les deux lignes F et J ont toutes deux leurs candidats 8 situés à l'une des cases placées à l'intersection avec les colonnes a et j (configuration dite X-wing) ; par rapport à ces quatre sommets on peut donc éliminer les candidats 8 des cases des lignes et colonnes qui ne sont pas sur les sommets (donc en Ha et Dj).

Pour rechercher ces configurations, on regarde si un candidat n'apparaît que dans un nombre précis de lignes et colonnes, pour lesquelles le nombre d'intersections est déterminé.

Le raisonnement qui permet l'élimination de candidats est le suivant dans le cas du X-Wing. Soient quatre cases a, b, c, d (exemple : Fa, Fj, Jj, Ja) contenant toutes un candidat K commun et formant un rectangle. Si sur les deux lignes (ab) et (cd), le candidat ne peut être présent qu'en a ou b, et en c ou d, alors on peut représenter le X-Wing par le rectangle abcd, ou par ses diagonales (ac) et (bd) qui forment un X. Dans cette situation, l'ensemble des possibilités se résument à deux cas. Dans le premier cas, K se trouve en a, donc il ne peut être ni en b, ni en d, ni sur la colonne de a. Comme K ne peut être en d, il se trouve nécessairement aussi en c, et ne peut donc pas apparaître dans la colonne de c. Dans le deuxième cas, K se trouve en b, donc il ne peut être en a, ni en c, ni dans la colonne de b. Donc K se trouve nécessairement aussi en d et ne peut apparaître dans la colonne de d. Dans les deux cas, sans savoir ou sera K, on voit qu'il ne peut apparaître ni dans la colonne de a, ni dans la colonne de b (sauf en a, b, c ou d), ce qui nous permet d'éliminer des candidats. Un raisonnement similaire peut être mené dans le cas symétrique où ce sont les lignes qui ne peuvent accueillir le candidat.

Le cas du Swordfish fait apparaître une figure non pas de 4 sommets comme le X-Wing, mais de six sommets. On peut le voir comme deux rectangles rattachés par un sommet. Ce sommet en commun n'a aucune utilité dans la figure, si bien qu'il ne reste que six sommets. Techniquement, il faut trouver 3 lignes (ou colonnes) où un candidat K n'apparaît qu'en deux cases. Ces cases étant alignées d'une ligne à l'autre deux à deux.

Une fois identifié, le traitement formel de ces groupes « marinés » est :

• X-Wing en ligne : si sur deux lignes, un candidat n’apparaît que sur les deux mêmes colonnes, alors on supprime ce candidat sur les deux colonnes sauf sur les deux lignes. Pour le X-Wing en colonne, on effectue le traitement en ligne.
• Swordfish : si sur trois lignes différentes, un candidat n’apparaît que sur trois colonnes, alors on supprime ce candidat sur les trois colonnes sauf sur les trois lignes.

Nota bene : il n’existe pas de règle homologue pour les blocs.

Symétries généralisées et tableau de résolution étendu

Dans The Hidden Logic of Sudoku^[24], basé sur une formalisation logique systématique du jeu, toutes ses symétries généralisées ont été explicitées, en particulier entre les lignes et les nombres, entre les colonnes et les nombres et entre les blocs et les nombres. Une nouvelle méthode de résolution a été développée, basée sur leur exploitation systématique. Les espaces rn, cn et bn (complémentaires de l’espace usuel rc) ont ainsi été introduits (p. 35 de la première édition). Une grille de résolution étendue a été conçue, qui fait apparaître les liens de conjugaison comme des cases (de l’espace rc, rn, cn ou bn) à deux candidats et peut faciliter l’application de la méthode. De la sorte, les sous-ensembles cachés, ainsi que les X-wings, Swordfish et Jellyfish, apparaissent tous comme de simples Paires, Triplets ou Quadruplets. Dans un cadre général pour traiter des chaînes, ces symétries ont été utilisées pour introduire de nouvelles règles de résolution, comme les chaînes xy cachées et ultérieurement les chaînes nrczt. Cette méthode a été mise en œuvre dans un résolveur, SudoRules, basé sur des techniques d’intelligence artificielle et simulant un joueur humain.

Chaînes xy

Une chaîne xy, est une suite de cases comportant uniquement des doublons, soit 2 candidats exactement. De plus ces cases doivent avoir un lien entre elles : on doit pouvoir passer de l'une à l'autre en restant dans une même région, tout en suivant « le fil » d'un candidat. Par exemple, pour une suite de quatre cases « bien disposées », on pourrait avoir les candidats suivants {1,9} {1,3} {3,6} {2,6}.

Dans les cas intéressants de chaînes, deux approches permettent l'élimination de candidats :

• Chaînes de type {a, b} {b, c} {c, d} {d, a}

Dans ce cas, on montre que pour toute case X, hors de la chaîne, contenant le candidat « a », et située à la fois dans la même région que la première case et dans la même région que la dernière case, alors cette case ne peut contenir le candidat « a ». Si « a » était vrai dans cette case, alors « a » serait faux dans la première case de la chaîne, et la chaîne se réduirait à {b} {c} {d} {a}. Or « a » ne peut être à la fois dans X et dans la dernière case de la chaîne. Donc X ne peut contenir « a ».

• Cas général : chaînes forcées

Partant d'une case A contenant {x, y} et que l'on voit deux « chemins » différents reposant sur des chaînes du type {x, y}{y, z}{z, t}{t, u}… arrivant à une case B contenant {t, u}, alors il se peut qu’indifféremment du choix de x ou de y dans la première case, et donc du chemin que l'on suit pour éliminer des candidats, un candidat soit systématiquement éliminé. Alors on vient de trouver une solution dans une case. Par exemple si le t de la dernière case est éliminé dans le cas où on choisit y en première case et qu'on suit le chemin 1 : {x, y}{y, z}{z, t}{t, u}, mais aussi dans le cas où on choisit x et qu'on suit le chemin 2 : {x, y}{x, v}{v, u}{u, w}{w, y}{y, t}{t, u}, alors u est la solution de la case B.

Ces raisonnements sont communs à tous les types de chaînes.

Généralisations des chaînes xy : chaînes d'ALS et chaînes nrczt

Parmi les généralisations logiques « naturelles » des chaînes xy, on a :

• les chaînes d’ALS (Almost Locked Sets), les plus anciennes et de loin les plus utilisées par les joueurs sur les forums de Sudoku ; un maillon de ces chaînes n’est plus un candidat mais un ALS (Almost Locked Sets), c’est-à-dire un ensemble de k cellules (sur une même ligne, une même colonne ou dans un même bloc) dont les candidats appartiennent à un ensemble de k+1 nombres ;
• les chaînes xyt, xyz et xyzt ainsi que leurs homologues « cachés » dans les espaces rn, cn et bn (définies dans la première édition de The Hidden Logic of Sudoku) ; les chaînes nrczt, ou chaînes supersymétriques, qui généralisent les précédentes en combinant toutes les cellules des espaces rc, rn, cn et bn (définies dans la seconde édition de The Hidden Logic of Sudoku^[24])) ;
• une combinaison des deux, dont on peut trouver de nombreux exemples sur le forum sudoku-factory.

Le principe du rectangle interdit

Considérons quatre cellules formant un rectangle s’étalant sur deux lignes, deux colonnes et seulement deux blocs. Si le contenu de ces quatre cellules est :

ab ab

ab ab

alors pour toute solution du problème ayant les valeurs

a b

b a

pour les cellules de ce rectangle, il existe une autre solution ayant les valeurs

b a

a b

et le problème ne peut donc avoir une solution unique.

La configuration initiale s’appelle rectangle interdit. À partir de là, on peut définir plusieurs règles visant à empêcher que cette situation se produise. Ces règles ne sont valables que sous l’hypothèse d’unicité.

Exemples de règle reposant sur l'exploitation du rectangle interdit

Règle UR1 : dans la configuration (où les quatre cellules forment un rectangle s’étalant sur deux lignes, deux colonnes et seulement deux blocs) :

ab ab

ab abc

éliminer a et b de la dernière cellule.

Règle UR2-H : dans la configuration (où les quatre cellules forment un rectangle s’étalant sur deux lignes, deux colonnes et seulement deux blocs) :

ab abc

ab abc

où les deux cellules de droite sont dans le même bloc, éliminer c de toute autre cellule liée aux deux cellules de droite.

Il existe de nombreuses variantes de ces règles.

Statistiques de la classification nrczt

Les statistiques de la classification nrczt sont accessibles :

• dans trois livres : The Hidden Logic of Sudoku^[24], Constraint Resolution Theories^[38] et Pattern-Based Constraint Satisfaction and Logic Puzzles^[39]
• et dans deux articles du même auteur : From Constraints to Resolution Rules, Part II: chains, braids, confluence and T&E^[41] (sur la base de 10 000 problèmes minimaux aléatoires) et Unbiased Statistics of a CSP - A Controlled-Bias Generator^[40].

Les résultats suivants sont basés sur le nouveau générateur à biais contrôlé (et sur Presque six millions de problèmes minimaux aléatoires); ils sont non biaisés. Ce générateur et la vaste collection associée sont accessibles sur la plateforme GitHub : https://github.com/denis-berthier/Controlled-bias_Sudoku_generator_and_collection

Le résolveur de Sudokus ayant servi à établir cette classification (SudoRules, partie du logiciel plus général de résolution de contraintes CSP-Rules) est accessible sur la plateforme GitHub : https://github.com/denis-berthier/CSP-Rules-V2.1

La répartition en pourcentage par niveaux nrczt se fait ainsi :

• niveau 0 : 29,17
• niveau 1 : 8,44
• niveau 2 : 12,61
• niveau 3 : 22,26
• niveau 4 : 21,39
• niveau 5 : 4,67
• niveau 6 : 1,07
• niveau 7 : 0,29
• niveau 8 : 0,072
• niveau 9 : 0,020
• niveau 10 : 0,005 5
• niveau 11 : 0,001 5

Sachant que la complexité effective d’un problème croît de manière quasi exponentielle avec son SER ou son NRCZT, ces chiffres montrent que :

1. une très grande majorité des problèmes peut se résoudre par des techniques relativement simples (ici, des chaînes courtes) ;
2. il reste malgré tout des problèmes de très grande complexité, ce qui justifie que les joueurs experts recherchent en permanence de nouvelles règles qui permettraient de simplifier les solutions obtenues avec les règles connues à ce jour ;
3. les problèmes exceptionnellement complexes (comme le fameux Easter Monster^[42]) ont très peu de chances d’être trouvés par un générateur aléatoire et certains joueurs essaient en permanence de créer de nouveaux exemples « à la main ».

Résultats collatéraux : la technique des générateurs à biais contrôlé permet aussi d'estimer le nombre de problèmes minimaux (3,10 × 10³⁷) ainsi que le nombre de problèmes minimaux non équivalents (2,55 × 10²⁵).

Type 1

Utilisation des techniques simples dont « la recherche de la bonne case pour un chiffre et une région donnés » par réduction par croix, et « la recherche, du bon chiffre pour une cellule donnée », par décompte, bien que cette dernière soit un peu plus fastidieuse que la première. En principe, pour ce type de grilles, le raisonnement se fait mentalement, sans que l’on soit obligé d’inscrire les candidats éventuels dans une cellule donnée, et le remplissage de la grille se fait progressivement en suivant l’une des innombrables pistes ou enchaînements qui se présentent. C’est ce type de grilles que vous trouvez fréquemment dans les sites, journaux et magazines ou créées par des logiciels, classant à tort certaines d’entre elles, dans la catégorie des « difficiles » ou même « diaboliques » ! La raison en est qu’il existe une classe de grilles de type 1, vraiment difficile à réussir par calcul mental. Et donc, ne sous-estimez pas les grilles de type 1 : il y en a des « faciles », « moyennes » et même « difficiles ».

Type 2

Utilisation des techniques permettant le traitement des cellules-à-candidats-multiples selon une seule dimension ; ligne, colonne ou région, dont « l’élimination à cause des paires nues », « le dégraissage des candidats cachés » et « le dégraissage des paires camouflées ». Certaines grilles de type 2 peuvent être réussies, comme pour le type 1, mentalement. D’autres, d’un niveau supérieur, nécessitent que l’on inscrive, au fur et à mesure, les candidats dans les cellules d’une région, une ligne ou une colonne, sans toutefois le faire pour toutes les cellules vides, et voir si l’on peut simplifier les multiples par l’une des trois techniques précédentes. Les plus difficiles des grilles de ce type 2 ne se prêtent à la résolution qu’une fois que toutes les cellules contiennent leurs candidats probables. Dans ce cas, il faut essayer d’arriver à la situation optimale de la grille : dans chaque catégorie (ligne, colonne et région), les groupes des « multiples numériquement liés » doivent être « indépendants». D’autres techniques simples de traitement selon une seule dimension peuvent être utilisées, dont « l’élimination à cause des triplets nus » et « le dégraissage des triplets camouflés ». Cette dernière est plus pénible à faire ! On pourra également éliminer certains chiffres par une technique simple de traitement, cette fois-ci, à deux dimensions ligne × région ou colonne × région : « la répartition d’un bloc en quatre domaines complémentaires ou alternés ». Donc, si vous optez pour un exercice mental, ce type de grilles vous propose de bien difficiles. Et si vous vous permettez d’inscrire les multiples dans les cellules, vous avez là de très beaux exercices d’entraînement sur la stratégie de traitement des « groupes indépendants de multiples numériquement liés ».

Type 3

Utilisation des techniques permettant la simplification des cellules-à-candidats-multiples, d’abord comme pour le type 2, selon une seule dimension ; ligne, colonne ou région, mais avec une taille plus grande dont « l’élimination à cause des quadruplets et quintuples nus » et «le dégraissage des quadruplets et quintuples cachés ». Procéder par cette dernière technique, qui est d’ailleurs plus fastidieuse à mener, c’est en fait utiliser « l’élimination à cause d’un ou de deux groupes nus » mais de taille inférieure !

Certaines grilles de type 3 nécessitent un traitement selon deux dimensions (lignes × colonnes, lignes × régions et/ou colonnes × régions) en utilisant des procédés beaucoup plus astucieux, mais justifiables dont X-Wing, Swordfish, Jellyfish, Squirmbag ou la TPU, la technique découlant du « principe de l’unicité de la solution ». Donc pour ce type de grilles, il ne faut pas espérer aboutir à la solution rien qu’en raisonnant mentalement, sans avoir dorénavant mis tous les candidats possibles dans toutes les cellules. Trois degrés de difficulté sont possibles, selon la taille des groupes nus ou camouflés, mais aussi selon leur nombre.

Type 4

La stratégie adoptée pour les grilles de ce type, présentant des cas de figures plus complexes, consiste à prendre en considération simultanément les trois dimensions (lignes × colonnes × régions). Il faut donc pouvoir « sauter » d’une région à une autre, à travers les cases, en utilisant des « passerelles » matérialisées soit par une ligne, une colonne ou une région. Bref, il faut se créer des « chemins » entre les différentes cases. Ainsi, on reconnaîtra des procédés similaires à ceux déjà utilisés par traitement à deux dimensions dont le X-Wing par exemple (les sommets ne sont plus ceux d’un rectangle, mais parmi ceux d’un polygone). Précisons que cette stratégie est basée sur la logique bivalente (pour un chiffre N fixé et une case donnée de multiples, p : « N est la valeur » ou non(p) : « N n’est pas la valeur »).

Vu d’un certain angle, il s’agit de superposer deux ou plusieurs grilles sur la même grille-problème initiale, de faire une conjugaison logique des différentes propositions (concrétisées par des chemins) et de déterminer celles des grilles qui aboutissent à une contradiction avec l’une des règles qui régissent le jeu sudoku, pour découvrir la bonne solution. C’est donc comme si l’on procède par formulation par hypothèse, mais d’une manière détournée ! Il faut avouer que cette manière de faire procure plus de plaisir à jouer et à appliquer des procédés que d’émettre des hypothèses pour obtenir des grilles « pauvres » au niveau intellectuel ! Utilisez des crayons de couleur. Ceux qui sont déjà initiés à cette technique reconnaîtront des grilles faciles, moyennes et même difficiles.

Type 5

Certains journaux, magazines, sites et logiciels livrent des grilles dites «diaboliques» voire «infernales». Le plus souvent, ces grilles peuvent être résolues par les techniques mises au point jusqu’à ce jour, et sont beaucoup moins difficiles qu'il n'y parait. En effet, une grille diabolique est celle qui ne peut être résolue par aucun des procédés mis au point jusqu’à ce jour, sauf par la formulation d’une ou de plusieurs hypothèses sur les chiffres à mettre dans une ou plusieurs cases. Bien entendu, l’unicité de la solution pour la grille est requise.

Désormais, c’est le seul moyen pour aboutir à la solution, en attendant l’élaboration de nouveaux procédés « manuels ».

Signalons enfin, qu’au niveau de la construction des grilles-problèmes, il est fréquemment plus facile d’obtenir une grille de type 1, et presque rare de tomber sur une grille de type 4 ou 5. Les logiciels élaborés jusqu’à ce jour partent bien sûr des différents procédés de résolution, pour fabriquer un problème, mais le niveau souhaité baisse généralement d’un ou même de deux degrés. Statistiquement, on relève que la distribution de la fréquence par type tourne autour de 46 %, 32 %, 11 %, 8 % et 3 %, du premier type au cinquième.