Cinq techniques pour terminer toute grille de sudoku

Khoan Vo Khac

Description

De nombreux livres ont prolongé l'œuvre de référence d'Andrew C. Stuart, "The Logic of Sudoku". Mais ces livres présentent deux défauts : d'une part, la théorie est basée sur des exemples ; d'autre part, elle utilise le tableau des candidatures à toutes les cases libres – peu de joueurs l'utilisent, car il est touffu et surtout très long et fastidieux à établir. La démarche de ce guide est l'opposée de celle de Stuart ; par ailleurs, elle est proche de celle suivie par les joueurs. Cette théorie est entièrement abstraite, les techniques sont exposées dans leur grande généralité, avec toute la rigueur mathématique. Pratique, efficace, indispensable, cet ouvrage donne toutes les règles et techniques, associées à six niveaux de difficulté : facile, moyen, difficile, expert, grand expert et très grand expert. Accessible à tous, riche de 118 exemples accompagnés de leurs solutions détaillées, voici l'arme ultime pour devenir champion de sudoku !

Sujets

• Loisirs
• Jeux et divertissements
• Sciences
• Activities
• Mathematics
• Games
• Mathématiques
• Science formelle
• Sudoku
• Solution
• Méthode
• Science

Informations

• Publié par: Société des écrivains
• Date de parution: 22 avril 2016
• Nombre de lectures: 10
• EAN13: 9782342050585
• Langue: Français

Extrait

Cinq techniques pour terminer toute grille de sudoku
Khoan Vo Khac
Société des écrivains

Le Code de la propriété intellectuelle interdit les copies ou reproductions destinées à une utilisation collective. Toute représentation ou reproduction intégrale ou partielle faite par quelque procédé que ce soit, sans le consentement de l’auteur ou de ses ayants cause, est illicite et constitue une contrefaçon sanctionnée par les articles L 335-2 et suivants du Code de la propriété intellectuelle.


Société des écrivains
175, boulevard Anatole France
Bâtiment A, 1er étage
93200 Saint-Denis
Tél. : [phone]
Cinq techniques pour terminer toute grille de sudoku
 
Toutes les recherches ont été entreprises afin d’identifier les ayants droit. Les erreurs ou omissions éventuelles signalées à l’éditeur seront rectifiées lors des prochaines éditions.

 
 
 
Retrouvez l’auteur sur son site Internet :
http://khoan-vokhac.societedesecrivains.com
 
 
 
À mes étudiants des maîtrises Miage, Mime et Maf
À mes élèves – ingénieurs de l’École Polytechnique
À tous ceux qui aiment raisonner
 
 
 
Introduction
 
 
 
Le meilleur ouvrage théorique concernant les grilles de sudoku est The Logic of Sudoku , par Stuart [1]
Ce livre est actuellement épuisé. De nombreux autres livres ont prolongé l’œuvre de Stuart.
 
Mais ces livres présentent pour moi deux défauts . D’une part, la théorie est basée sur des exemples. D’autre part, elle utilise le tableau des candidatures à toutes les cases libres ; peu de joueurs l’utilisent, car il est touffu et surtout très long et fastidieux à établir. Ma démarche est l’opposée de celle de Stuart ; par ailleurs, elle est proche de celle suivie par les joueurs.
 
Ma théorie est entièrement abstraite, les techniques sont exposées dans leur grande généralité, avec toute la rigueur mathématique. Elle donne toutes les règles et techniques , réparties dans les cinq premiers chapitres, associées à six niveaux de difficulté : facile, moyen, difficile, expert, grand expert et très grand expert. La première règle se trouve au premier chapitre . C’est la règle de base, appelée ici règle de placement simple . Cette règle permet de terminer deux tiers des grilles proposées dans les divers magazines : de faciles grilles. Les deux règles suivantes ( règle d’affectation simple et règle d’alignement ) se trouvent au chapitre II et sont nécessaires pour terminer les grilles de niveau moyen . Au chapitre III se trouvent trois autres règles, relatives à la technique du multiplet . Ces six règles permettent de terminer 90 % des grilles proposées actuellement, et 100 % de celles proposées dans [2], [3], [4], [5] et [6].
Les règles suivantes sont destinées surtout aux experts . Cinq de ces règles se trouvent au chapitre IV et utilisent la technique d’attache d’un symbole. La seule règle de répartition quasi idéale condense les configurations dites X-wing, swordfish, jellyfish, sous leurs diverses formes (basic, finned, sashami, franken, mutant et kraken).
Les dernières règles se trouvent au chapitre V , traitant les trois types de chaînes à plusieurs symboles  ; elles sont réservées surtout aux grands et très grands experts. Le chapitre VI ( principe du dilemme ) est rédigé pour permettre aux joueurs de terminer facilement une grille, sans passer par les techniques des chapitres IV et V.
 
Les règles sont exposées dans leur généralité , avec précision et concision . Comme elles sont très abstraites, je les ai illustrées par beaucoup d’exemples pour montrer leur efficacité et permettre aux lecteurs de les assimiler aisément. Chaque grille-exemple est guidée du début jusqu’à la fin. La moitié de ces exemples ont été proposées dans quelques revues périodiques françaises. Le premier exemple est sûrement le plus facile, alors que le dernier est probablement le plus difficile au monde.
Le livre est calqué sur les Éléments d’Euclide ; ce dernier a fondé la géométrie à partir des résultats connus des architectes égyptiens (au temps des Pharaons), en les énonçant abstraitement et en les démontrant avec rigueur.
 
 
 
Présentation du jeu
 
 
 
Lignes, colonnes, secteurs, unités et cases
Une grille de sudoku possède neuf lignes ou neuf rangées notées L1, L2…, L9 de haut en bas, et neuf colonnes notées C1, C2…, C9 de gauche à droite.
L’intersection de la ligne Li et de la colonne Cj se note LiCj et se nomme un point, une cellule ou une case .
Elle se divise aussi en neuf secteurs ou régions ou blocs , souvent des carrés à 3 colonnes et 3 lignes consécutives, notés S1, S2, …, S9 dans le sens de la lecture occidentale .
Une colonne, une ligne ou un secteur s’appelle aussi une zone ou une unité, parfois une salle ou une maison.
Symboles (ou motifs) utilisés
Neuf symboles (dits aussi motifs) sont nécessaires. Les motifs 1, 2, 3, 4, 5, 6, 7, 8, 9 sont souvent utilisés.
Mais ces chiffres peuvent être remplacés par neuf lettres, ou neuf signes du zodiaque, ou des portraits de célébrités.
Règlement ou but du jeu
Une grille de départ, peu remplie, est donnée. La remplir avec comme règlement  : un seul symbole par case, chaque symbole au moins une fois dans toute unité. Chaque symbole y figurera alors exactement une fois. Formulation mathématique . De l’ensemble G des 81 cases vers l’ensemble S des 9 symboles, trouver une application, dont la restriction à une partie de G est donnée et dont la restriction à chacune des 27 unités est surjective . Comme chaque unité a le même nombre d’éléments que S, elle est alors bijective . Une grille de Sukoku se nomme aussi un carré latin sectorisé .
S1   S2   S3
S4   S5   S6
S7   S8   S9
 
 
 
 
Chapitre I. Technique de placement simple
 
 
 
1.1. Case permise à un symbole
Une case est dite permise à un symbole s’il est absent dans les trois zones auxquelles elle appartient. Le symbole est alors dit permis dans la case ou candida t à la case, ou il la convoite . Dans le cas contraire, la case est dite interdite ou bannie au symbole (ou le symbole est dit interdit ou banni dans la case).
1.2. Règle de placement simple
Dans une zone donnée, un symbole est placé à l’unique case qui lui est permise, dite case forcée .
Cette règle achève les 673 premières grilles de [4], 126,123, 121, 103, 96, 93, 91, 89, 87, 86, 74, 68, 65, 62, 60, 59, 56 à 46, 44 à 41, 39 à 34, 32 à 25, 23 à 18, 16 à 12, 10 à 5, 3 de [3].
1.3. Comment procéder ?
- Essayer de placer chaque symbole dans les unités.
- Choisir une unité et essayer d’y placer les symboles manquants. Il est conseillé de choisir une séquence d’unités de même nature , puis de changer la nature de la séquence. La dernière unité sera très aisément remplie.
Nota bene S’il reste à caser n fois (souvent n = 2, 3 ou 4) un symbole s donné et si les cases que convoitent s sont les sommets d’un 2n-polygone parfait (définition au 4.3.1), alors il ne pourra être placé. Dès qu’une de ces cases est occupée, s sera placé dans toutes les unités.

Exemple 1.a.


3
1
.
.
.
2
4
.
.
.
5
6
4
3
.
2
7
.
.
.
4
5
.
.
3
8
.
.
.
1
.
.
.
.
2
3
.
.
.
.
2
5
6
1
.
2
.
.
1
6
.
.
.
.
4
.
.
.
8
1
.
.
2
1
9
.
.
4
7
.
6
5
.
8
3
.
.
9
1
.
.
 
Placer symbole 1 dans les secteurs S2 puis S3,
symbole 2 dans les secteurs S1 et S7 puis S8,
symbole 3 dans S9 puis S8 puis S5 puis S4,
symbole 4 dans S5 puis S4 puis S6 puis S9,
symbole 5 dans S3 et S8 puis S7 puis S4 puis S6,
symbole 6 dans S4 et S8 puis S7 et S2 puis S3,
7 dans S7 puis S9 puis S6 puis S5 puis S2, S4 puis S1
motif 8 dans S6, S9 et S5 puis S2 puis S1 puis S4,
symbole 9 dans S1, S2, S3, S4, S5, S6 et S9.
 
Conseil : Placer chaque symbole dans tous les secteurs .
La même technique termine les grilles 1 à 8 de [4].
gr1 : 1, 2, 3, 5, 7, 9, 4, 6, 8 ; gr2 : 1, 3, 4, 5, 6, 7, 9, 8, 2
gr3 : 3, 4, 7, 6, 2, 5, 9, 1, 8 ; gr4 : 3, 4, 7, 9, 1, 8, 2, 5, 6
gr5 : 5, 3, 9, 1, 2, 4, 6, 7, 8 ; gr6 : 2, 3, 5, 6, 7, 8, 1, 4, 9
gr7 : 5, 4, 7, 6, 8, 1, 2, 3, 9 ; gr8 : 6, 7, 9, 1, 3, 2, 4, 5, 8
 
Exemple 1.b.
 
 
5
.
6
.
.
8
9
.
1
4
.
.
.
2
.
.
.
.
3
.
.
1
.
5
.
.
.
.
4
3
2
1
.
6
.
7
.
.
.
8
.
.
.
.
3
6
2
.
3
.
4
.
1
9
.
.
8
.
.
.
3
.
2
.
.
5
.
.
.
.
6
.
2
.
4
6
.
3
5
.
.
 
Placer symbole 3 dans les secteurs S7 et S2 puis S3,
symbole 2 dans les secteurs S8 et S1 puis S3 puis S6,
symbole 1 dans S8 et S9 puis S7 puis S1 puis S4,
symbole 4 dans S6 puis S9 puis S3 puis S2 puis S8,
symbole 5 dans les secteurs S3, S4, S6 et S8 puis S5,
symbole 6 dans les secteurs S7 et S3 puis S2 puis S5,
symbole 8 dans S4 et S6 puis S3 puis S1 et S9 puis S8,
symbole 9 dans S1, S4 puis S2, S5 puis S8 puis S9 puis S7,
symbole 7 dans S1, S2, S3, S4, S5, S7, S8 et S9.
 
Conseil : Commencer par placer les symboles figurant plusieurs fois dans la grille de départ, si possible dans l’ordre décroissant des nombres de fois (3 : 6 fois, 2 : 5 fois).
Par le même procédé, remplir les grilles, pages 12 et 110, de [2], avec l’ordre suivant des symboles à placer.
p. 12 : 8, 2, 3, 7, 9, 4, 1, 5, 6, p. 110 : 1, 5, 8, 7, 9, 6, 2, 3, 4.
 
Exemple 1.c.
( Télé 7 jours , 21 au 27 décembre 2013, 100 €)
 
7
.
.
2
.
9
4
.
1
.
.
2
.
5
.
8
.
.
9
3
.
1
.
.
.
7
.
2
.
.
7
.
6
3
.
4
.
7
.
.
.
.
.
1
.
8
.
5
3
.
4
.
.
7
.
1
.
.
.
3
.
8
6
.
.
4
.
6
.
7
.
.
6
.
9
5
.
2
.
.
3
 
Placer symbole 7 dans les secteurs S2 et S7 puis S8,
symbole 3 dans les secteurs S2 et S7 puis S3 et S4,
symbole 1 dans les secteurs S1, S4, S8 et S9 puis S5,
symbole 2 dans S5 et S7 puis S9 puis S3 et S6,
symbole 4 dans S1, S4 et S9 puis S2 puis S8,
symbole 6 dans S2 et S4 puis S6 puis S3 puis S1,
symbole 5 dans S1, S3, S5 et S7 puis S6 puis S9,
symbole 8 dans S1, S2, S6, S7 et S8 puis S5,
symbole 9 dans S3, S4, S5, S6, S8 et S9.
 
Conseil : Commencer par placer 7 (figurant