S'identifier S'inscrire

assistant-sudoku.com

Niveau de difficulté d'une grille sudoku

La difficulté (niveau) d'une grille de sudoku est définie en général en fonction des techniques à utiliser pour parvenir à la solution. Plus le nombre et les différents types des techniques sont nécessaires plus le niveau de la grille est élévé.
Ainsi une grille de niveau 1 à 3 ne demande aucune technique particulière si ce n'est de connaître les règles du sudoku et d'être observateur. Les cases se remplissent par induction, les unes après les autres. Entre 3 et 6, seules sont nécessaires les techniques de base : alignements et ensembles fermés (doublets, triplets, etc...). C'est au-delà du niveau 6 que les techniques expertes traditionnelles de plus en plus sophistiquées (X-Wing, X-Chain, ALS, coloriage, etc...) sont nécessaires.
C'est à partir de ce niveau 7 d'ailleurs que la technique des pistes se justifie.

Etalonnage des grilles par la technique des pistes (Niveau TDP)

Les grilles dites difficiles par les techniques expertes traditionnelles sont parfois résolues très facilement par la technique des pistes. Aussi paraît-il nécessaire d'étalonner différemment la difficulté des grilles traitées par la technique des pistes. Voici comment :

- Niveau 0 TDP: les grilles qui ne nécessitent que les techniques de base (induction, alignements et ensembles fermés) et donc ne nécessitent pas l'usage de la technique des pistes.

Les niveaux suivants sont établis en fonction du nombre minimal de contradictions (pistes conduisant à des contradictions) nécessaires à prouver, parmi les jeux pistes choisis, quelles pistes conduisent à la solution et son unicité en complément des techniques de base.
Par jeux de pistes il faut comprendre ici, toutes les combinaisons de pistes utilisées : jeu de deux pistes, jeu de 3 pistes, jeu de pistes secondaires (bifurcations), jeux de pistes simultanés, etc...
Pour simplifier la description des niveaux, on note par C le nombre minimal de pistes utilisées conduisant à des contradictions.
Le niveau TDP d'une grille est donc égale à C.

- Niveau 1 TDP : C=1.
C'est le cas d'une grille résolue avec un seul jeu de 2 pistes par croisement des pistes.
- Niveau 2 TDP : C=2.
C'est le cas d'une grille résolue avec deux jeux de 2 pistes successifs donnant chacun une contradiction, ou avec une seule piste d'un jeu de 2 pistes, la contradiction étant montrée sur la seconde piste en utilisant une bifurcation.
- Niveau 3 TDP : C=3.
C'est le cas d'une grille résolue avec un jeu de 2 pistes nécessitant une contradiction pour la première piste et deux contradictions pour la seconde.
- Niveau 4 TDP : C=4.
C'est le cas d'une grille résolue avec deux jeux de 2 pistes successifs nécessitant deux contradictions chacun.
- Niveau 5 TDP : C=5.
Etc ...

A titre d'exemple, la grille de AI Escargot (évaluée à 32) est au plus(*) de niveau 27 selon cette cotation, la grille N°108 proposée sur ce site (évaluée à 37) est au plus de niveau 25 selon cette cotation et la grille N°107 (évaluée à 17) est elle au plus de niveau 3.

On peut représenter le niveau d'une grille de cette manière, où (S pour solution, C pour contradiction) les flèches indiquent les pistes suivies au départ d'une paire de candidats, par exemple :

Comparaison des échelles de difficulté

Cette comparaison entre le niveau conventionnel obtenu sur la base des techniques expertes et du niveau obtenu par la technique des pistes est approximative, mais donne une idée des niveaux de difficultés des grilles usuelles :