Discussion :

[Lenou]

Bonjour,
Voila le sujet de mon projet.

Le jeu prend la forme d’une grille de taille 9×9 composee de 9 sous-grilles de 3×3, appelees « regions ». Quelques cases contiennent des chiffres, elles sont dites ”devoilees”. Le but est de remplir les cases vides (c’est a dire de les ”devoiler”). La contrainte `a satisfaire est la suivante : chaque case doit contenir un chiffre, de telle sorte que chaque ligne, chaque colonne et chaque
region contiennent chacune un seul chiffre allant de 1 a 9. Un sudoku n’admet qu’une seule solution.
Exemple :
0 8 7 0 0 0 5 2 0
9 1 0 5 0 2 0 4 6
2 0 0 0 0 0 0 0 7
0 9 0 0 2 0 0 1 0
0 0 0 1 0 6 0 0 0
0 4 0 0 9 0 0 8 0
6 0 0 0 0 0 0 0 3
5 7 0 3 0 1 0 6 8
0 3 8 0 0 0 9 5 0
Les cases non devoilees sont `a 0. Les lignes, colonnes et regions sont numerotees de 0 `a 8.


Methode de resolution : implementation de diverses regles
Pour chaque case non devoilee les candidats sont les chiffres 1, 2, 3, 4, 5, 6, 7, 8, 9.

Certaines regles permettent une determination directe du contenu d’une case non devoilee (R2 candidats seuls, R3 candidats uniques) tandis que d’autres permettent seulement de diminuer le nombre de candidats de certaines cases (R1, R4 considerations interregions).

Regle R1
Une seule occurrence de chaque chiffre dans chaque groupe : Un candidat
à une case ne peut etre qu’un chiffre non encore placé dans un groupe (ligne, colonne et region) qui contient cette case.

Regle R2Candidats seuls
S’il n’y a qu’un candidat `a une case, alors c’est cette valeur qu’il
faut placer dans la case.

L’application de ces deux seules regles est suffisante pour resoudre des sudokus faciles mais, en general, elles ne suffisent pas. Il peut intervenir d'autres regles


R3 Candidats uniques
Un candidat n’apparaissant que pour une seule case d’un groupe peut etre place dans la case correspondante.

(CF Sujet en piece jointe pour plus d'info.