Sudoku

 

 

 Le SUDOKU étape par étape

 

 

Vocabulaire

Règle :             Une grille de Sudoku, est composée de 81 cases dans un carré de 9 cases de côté. Une rangée de neuf cases disposées horizontalement côte à côte est appelée une ligne, Une rangée de neuf cases disposées verticalement côte à côte est appelée une colonne, de plus, la grille est divisée en neuf carrés de 3 cases par côté ces carrés sont appelés des blocs.

Des symboles sont disposés dans certaines cases de façon à ce que, par déduction logique le joueur termine la résolution de la grille en ayant rempli toutes les cases d’un des neuf symboles sachant qu’il doit y avoir neuf symboles différents par bloc, ligne ou colonne.

Tous types de symboles peuvent être utilisés : imagettes, photos, idéogrammes, lettres, chiffres, au nombre de neuf tous ne sont pas obligatoirement affichés en début de jeu. Dans nos pays occidentaux, les symboles utilisés sont les chiffres de 1 à 9.

Sauf indication contraire, une grille de Sudoku n’a qu’une seule solution.

Notations :     les blocs sont notés de B1 à B9, de gauche à droite et de haut en bas. Les lignes sont notées de L1 à L9 de haut en bas. Les colonnes sont notées C1 à C9 de gauche à droite.

Candidat :      Un des neuf symboles possibles dans une case.

Singleton :     Candidat unique dans une zone, peut être nu (seul candidat de la case) ou caché (parmi plusieurs candidats dans la case, l’un d’eux est unique dans la zone).

Doublet :        Toto de deux candidats dans une case.

Triplet :          Ensemble de trois candidats dans une case.

Quadruplet :  Ensemble de quatre candidats dans une case.

Paire :             Ensemble de deux cases contenant deux doublets identiques dans une même zone.

Paire nue :     les deux candidats sont seuls dans les deux cases. Ils peuvent être supprimés des autres cases de la zone contenant cette paire.

Paire cachée :            Les deux candidats sont dans deux cases d’une zone mais ne sont pas seuls dans les deux cases. Les autres candidats contenus dans les deux cases peuvent être effacés.

Tierce :           Ensemble de trois cases contenant trois triplets identiques dans une même zone. Les trois cases peuvent ne contenir que des doublets ou un doublet et deux triplets ou deux doublets et un triplet. Le principe est que les trois candidats constituant la tierce soient répartis dans trois cases uniquement.

Tierce nue :                Même principe que la paire nue.

Tierce cachée :          Même principe que la paire cachée.

Carré nu, caché :       etc…

Zone d’influence :     ou zone de contrôle : ensemble des cases où ne peut pas s’inscrire comme candidat le symbole considéré. Le bloc, la ligne, la colonne à qui appartient la case contenant le symbole considéré. Le recouvrement des zones d’influences des occurrences d’un candidat donné permet la résolution de problèmes simples.

Lien fort :       Dans une zone, s’il n’existe que deux candidats d’un symbole, alors, un lien fort unit ces deux candidats. Il existe une parité entre ces deux cases : si le candidat de l’une est la solution de cette case il ne peut être solution de l’autre et vice versa.

Lien faible :    Dans une zone, s’il existe plus de deux candidats d’un symbole, alors, un lien faible unit ces candidats. Il ne peut exister de parité.

 

Règles de conduite :

A chaque fois qu’un candidat est éliminé dans une case, il faut recommencer les étapes à partir de la première car il s’agit d’une nouvelle grille.

 

 


 

 

Recouvrement primaire.

 

Trouver les singletons par visualisation des zones d’influence directe d’un symbole :

Il en résulte qu’il y a une seule case vide dans le bloc, la ligne ou la colonne, un seul symbole peut l’occuper, c’est un singleton qui devient automatiquement la solution de cette case.

Il est nécessaire dans un premier temps de trouver un maximum de singletons pour pouvoir inscrire un minimum de candidats dans les autres cases et ainsi avoir une grille la plus claire possible pour les étapes suivantes.

 

 

 

 

 

 

 

 

 

 

 

 

8

 

4

 

 

 

1

 

9

 

 

 

 

5

 

3

 

 

2

 

 

 

 

 

6

 

 

 

 

1

 

 

 

7

 

 

8

 

 

 

 

6

 

 

9

1

 

 

 

5

 

1

 

3

 

2

 

 

 

 

 

8

 

 

 

4

 

 

7

 

 

9

 

 

 

5

 

 

 

 

 

 

2

 

 

 

 

 

La zone d’influence de toutes les occurrences du symbole « 1 » est représentée en jaune. Les cases non occupées non colorées en jaune et uniques par blocs, lignes ou colonnes, sont solutions.

Solution en L5C8.

 

 

 

En pratique :

Toutes les cases contenant les solutions connues sont masquées.

Le 1 en L1C9 contrôle B3, L1 et C9. Imaginer que toutes les cases en B3, L1 et C9 sont masquées comme le montre le schéma ci-dessous :

 

 

 

 

 

 

 

 

 

 

 

 

 

8

 

4

 

 

 

1

 

9

 

 

 

 

5

 

3

 

 

2

 

 

 

 

 

6

 

 

 

 

1

 

 

 

7

 

 

8

 

 

 

 

6

 

 

9

 

 

 

 

5

 

1

 

3

 

2

 

 

 

 

 

8

 

 

 

4

 

 

7

 

 

9

 

 

 

5

 

 

 

 

 

 

2

 

 

 

 

 

 

 

 

 

 

Le 1 en L4C2 contrôle B4, L4 et C2.

 

 

 

 

 

 

 

 

 

 

 

 

 

8

 

4

 

 

 

1

 

9

 

 

 

 

5

 

3

 

 

2

 

 

 

 

 

6

 

 

 

 

1

 

 

 

7

 

 

8

 

 

 

 

6

 

 

9

 

 

 

 

5

 

1

 

3

 

2

 

 

 

 

 

8

 

 

 

4

 

 

7

 

 

9

 

 

 

5

 

 

 

 

 

 

2

 

 

 

 

 

 

Le 1 en L6C4, contrôle B5, L6 et C4.

 

 

 

 

 

 

 

 

 

 

 

 

 

8

 

4

 

 

 

1

 

9

 

 

 

 

5

 

3

 

 

2

 

 

 

 

 

6

 

 

 

 

1

 

 

 

7

 

 

8

 

 

 

 

6

 

 

9

 

 

 

 

5

 

1

 

3

 

2

 

 

 

 

 

8

 

 

 

4

 

 

7

 

 

9

 

 

 

5

 

 

 

 

 

 

2

 

 

 

 

 

 

Toutes les cases masquées sont colorées en jaune, cela signifie que le symbole 1 ne peut y être.

Si une case non masquée se trouve seule dans sa zone d’influence (bloc, ligne ou colonne) alors, le 1 est la solution de cette case.

Ici, le 1 est la solution de la case L5C8.

Les autres cases non masquées, étant plusieurs dans leur zone, ne peuvent être déterminées pour l’instant. Cependant, on pourra y inscrire le 1 comme candidat potentiel le moment venu.

 

 

 

 

 

 

 

 

Recouvrement ou masquage de deuxième ordre.

 

Trouver les singletons par visualisation des zones d’influence indirecte d’un symbole :

Il en résulte qu’il y a une seule case vide dans le bloc, la ligne ou la colonne, c’est un singleton qui devient automatiquement la solution de cette case.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

8

3

 

1

 

 

 

 

2

 

 

 

4

 

 

 

 

1

 

5

 

 

 

 

7

 

 

 

 

 

 

9

 

 

1

 

 

 

4

7

 

 

2

 

 

 

 

 

5

 

6

 

 

 

 

 

 

9

 

 

 

2

 

3

 

 

 

 

7

1

 

 

 

 

5

 

 

6

 

 

 

 

 

8

 

 

Un premier recouvrement

-          permet l’hypothèse du « 1 » en L2C5 ou L2C6. Deuxième recouvrement bloque la ligne 2.

-          permet l’hypothèse du « 1 » en L7C7 ou L9C7. Troisième recouvrement bloque la colonne 7.

Il reste une seule case libre en B3 et L1 et C8 soit L1C8.

En pratique :

 

Après le premier recouvrement, on peut constater que dans certains blocs, des cases non masquées sont dans une ligne et une seule ou sont dans une colonne et une seule. Donc, il est obligatoire que le symbole considéré se trouve dans l’une de ces cases alignées car si elles n’y sont pas, elles ne sont pas dans le bloc ce qui est impossible. Il est donc utile de masquer les cases dans leur prolongement dans les autres blocs.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

8

3

 

 

 

 

 

 

2

 

 

 

4

 

 

 

 

1

 

5

 

 

 

 

7

 

 

 

 

 

 

9

 

 

1

 

 

 

4

7

 

 

2

 

 

 

 

 

5

 

6

 

 

 

 

 

 

9

 

 

 

2

 

3

 

 

 

 

7

1

 

 

 

 

5

 

 

6

 

 

 

 

 

8

 

 

 

Masquage de deuxième ordre :

-          Dans B2, L2C5 et L2C6 seules cases non masquées dans le bloc. On masque les autres cases de la ligne 2.

-          Dans B4, L5C1 et L6C1 seules cases non masquées dans le bloc. On masque les autres cases de la colonne C1.

-          Dans B9, L7C7 et L9C7 seules cases non masquées dans le bloc. On masque les autres cases de la colonne 7.

 

Il en résulte le schéma suivant :

 

 

 

 

 

 

 

 

 

 

 

 

 

 

8

3

 

 

 

 

 

 

2

 

 

 

4

 

 

 

 

1

 

5

 

 

 

 

7

 

 

 

 

 

 

9

 

 

1

 

 

 

4

7

 

 

2

 

 

 

 

 

5

 

6

 

 

 

 

 

 

9

 

 

 

2

 

3

 

 

 

 

7

1

 

 

 

 

5

 

 

6

 

 

 

 

 

8

 

 

 

 

Avec un peu de pratique et de concentration, il est aisé de visualiser les cases masquées sans avoir besoin de crayonner partout.

 

Le masquage de deuxième ordre laisse apparaître une seule case non masquée dans sa zone de contrôle. L1C8 est solution pour le 1 en B3, L1 et C8.

De même, le candidat 1 doit être éliminé des cases L1C7, L2C8, L7C1 et L9C1 (voir le chapitre sur l’écriture des candidats).

 

 

 

 

 

 

Paires cachées.

 

Trouver les paires cachées par visualisation des zones d’influence de deux symboles :

Ici, les deux symboles «  1 » » et « 9 » de C2 et de L4 combinées, libèrent deux cases dans le bloc 4. On peut donc inscrire ces deux symboles en tant que candidats dans ces deux cases.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

8

3

 

 

 

 

 

 

2

 

 

 

4

 

 

 

 

1

 

5

 

 

 

 

7

 

 

 

 

 

 

9

 

 

1

 

19

 

4

7

 

 

2

 

 

 

19

 

5

 

6

 

 

 

 

 

 

9

 

 

 

2

 

3

 

 

 

 

7

1

 

 

 

 

5

 

 

6

 

 

 

 

 

8

 

 

 

 


 

 

Exemples de paires cachées.

 

Dans cette grille, successivement,

Le 3 et le 5 ligne 6 et colonne 8 libèrent 2 cases dans le bloc 6.

Le 2 et le 4 colonne 5 (3 et 5 verrouillées précédemment) libèrent 2 cases dans le bloc 5.

Le 7 ligne 4 et le 4 colonne 8 libèrent 2 cases dans le bloc 6 ligne 6.

 

 

 

 

 

 

 

 

 

 

 

 

 

8

 

4

 

 

 

1

 

9

 

1

 

 

5

 

3

 

 

2

 

 

 

 

 

6

 

 

 

 

1

 

24

 

7

35

 

8

 

 

 

 

6

 

24

9

1

35

 

 

5

 

1

 

3

47

2

47

 

 

 

 

8

57

 

 

4

 

 

7

 

 

9

3

 

 

5

 

 

 

 

 

57

2

 

 

 

 

 

 

 

 

 

 


 

Exemples de triplets.

 

En B5, un triplet automatique apparaît puisqu’il y a trois cases libres pour trois candidats « 589 ».

Triplet 589 dans le bloc 5, élimine le candidat 5 en L7, donc le « 7 » est solution de L7C5, et le « 5 » est solution de L9C4. Conséquemment, en B8, un triplet automatique apparaît puisqu’il y a trois cases libres pour trois candidats « 146 ».

 

 

 

 

 

 

 

 

 

 

 

 

 

8

 

4

 

 

 

1

 

9

 

1

 

6

5

 

3

 

 

2

 

 

 

1

 

6

 

 

 

 

1

 

24

59

7

35

6

8

 

 

 

 

6

589

24

9

1

35

 

68

5

69

1

89

3

47

2

47

 

 

 

 

8

7

16

 

4

 

 

7

 

 

9

3

146

 

5

 

 

 

 

 

5

2

146

 

 

 

 

 

A tout moment, peut apparaître un singleton. Il faut donc valider cette solution de case et s’en servir comme d’une clé qui donne une ouverture sur une nouvelle grille.

Le triplet 146 du bloc 8 élimine le 4 du bloc 5 colonne 6. Il en résulte le 2 comme singleton, puis le 4 colonne 4, puis 8 et 9 colonne 6.


 

 

Ecriture des candidats

 

Remplir toutes les cases par les symboles candidats.

Ma méthode consiste à commencer par le bloc contenant 2 cases vides puis la ligne contenant 2 cases vides puis la colonne contenant 2 cases vides.

On continue par les blocs lignes colonnes contenant 3 cases vides. Ensuite 4, 5 etc… jusqu’à remplir toute la grille.

Ici, on commence par le bloc 2. Contenant 2,3,7 en C4, on peut donc compléter le B2 par le 8 et le 9.

Puis la colonne 8 (3 cases libres : 7,8,9 à répartir). La première ligne contient le 8 et le 9, reste donc le 7 pour la case L1C8. Se déduisent le 9 pour L3C8 et 8 pour L9C8. Et suppression du7 dans L1C4 et du 9 dans L3C4. Etc…

 

 

 

 

 

 

 

 

 

 

 

 

8

23

4

9

 

7

1

 

9

 

1

27

6

5

8

3

 

 

2

 

 

37

1

8

6

9

 

 

 

1

 

4

59

7

35

6

8

 

 

 

 

6

589

2

9

1

35

 

68

5

69

1

89

3

47

2

47

 

 

 

 

8

7

16

 

4

 

 

7

 

 

9

3

146

 

5

 

 

 

 

 

5

2

146

 

8

 

 

Le 8 apparaît comme singleton en L2C7 par la technique de recouvrement primaire.

 

On continue jusqu’à remplir totalement la grille par les symboles candidats :

 

 

 

 

 

 

 

 

 

 

 

356

36

8

237

4

9

25

7

1

 

9

47

1

27

6

5

8

3

24

 

2

347

3457

37

1

8

6

9

45

 

36

1

239

4

59

7

35

6

8

 

348

3478

347

6

58

2

9

1

35

 

68

5

69

1

89

3

47

2

47

 

1356

2369

23569

8

7

16

123

4

2369

 

7

2468

246

9

3

146

12

5

26

 

13468

3469

3469

5

2

146

137

8

3679

 

 

 


 

 

Analyse des candidats dans les blocs, lignes et colonnes.

 

Passer en revue tous les  blocs lignes et colonnes. (Réduction, pointing, claiming etc…).

-          Dans un bloc, un symbole candidat se trouvant dans une seule ligne permet d’éliminer le même symbole candidat des deux autres blocs sur la même ligne.

-          Dans un bloc, un symbole candidat se trouvant dans une seule colonne permet d’éliminer le même symbole candidat des deux autres blocs sur la même colonne.

-          Dans une ligne, un symbole candidat se trouvant dans un seul bloc permet d’éliminer le même symbole candidat des deux autres lignes du bloc.

-          Dans une colonne, un symbole candidat se trouvant dans un seul bloc permet d’éliminer le même symbole candidat des deux autres colonnes du bloc.

 

A cette occasion, on en profite pour:

-          corriger les erreurs d’écritures : candidats inscrits alors que la solution correspondant à ce candidat existe dans le bloc la ligne ou la colonne.

-          Trouver d’autres paires cachées ou tierces etc…

 

En pratique :

Analyse de B1 :

-          le 6 en L1, sur une seule ligne. Sans de conséquence.

Analyse de B2 :

-          Rien de particulier.

Analyse de B3 :

-          Les 4 du bloc 3 dans la colonne 9 uniquement éliminent le 4 en L6C9, car si le 4 n’est pas en C9, il n’est donc pas en B3 ce qui est impossible. Il faut donc éliminer tous les 4 de C9 en dehors de B3.

-          On élimine donc le 4 de L6C9.

 

 

 

 

 

 

 

 

 

 

 

 

356

36

8

237

4

9

25

7

1

 

9

47

1

27

6

5

8

3

24

 

2

347

3457

37

1

8

6

9

45

 

36

1

239

4

59

7

35

6

8

 

348

3478

347

6

58

2

9

1

35

 

68

5

69

1

89

3

47

2

47

 

1356

2369

23569

8

7

16

123

4

2369

 

7

2468

246

9

3

146

12

5

26

 

13468

3469

3469

5

2

146

137

8

3679

 

 

Le 7 devient singleton donc solution de la case L6C9.

Analyse de B4 :

-          Le 2 unique en B4, puis le 9 est unique en B4, puis le 6 est unique en B4. Le 3 devient singleton en L4C1 donc solution de cette case. Le 5 devient singleton en L1C1 donc solution de cette case. Etc.

 

 

 

 

 

Ainsi, petit à petit, la grille peut être facilement remplie :

Analyse de B5 à B9, puis analyse de L1 à L9, puis analyse de C1 à C9.

 

 

 

 

 

 

 

 

 

 

5

6

8

3

4

9

2

7

1

 

9

7

1

2

6

5

8

3

4

 

2

3

4

7

1

8

6

9

5

 

3

1

2

4

9

7

5

6

8

 

8

4

7

6

5

2

9

1

3

 

6

5