| | Technique : Chaînes de jumeaux/voisins | |
| | |
Auteur | Message |
---|
Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Technique : Chaînes de jumeaux/voisins Lun Juil 06 2009, 18:46 | |
| papyg Admin
Inscrit le: 11 Oct 2005 Messages: 1130
| Posté le: Jeu 07/09/2006 19:01 Sujet du message: Technique : Chaînes de jumeaux/voisins |
|
|
Technique : Chaînes de jumeaux/voisins : puissantes et accessibles à tous !
1 – Introduction
Je voulais d'abord intituler cette fiche "Les chaînes pour les nuls"... mais c'était offenser d'éminents participants au forum .
Mon but est en effet de vulgariser les "forcing chains" et autres "nice-loops", des outils puissants, en :
- les rendant accessible aux joueurs que les subtilités et le jargon de la logique rebutent
- les dé-diabolisant (une fausse connotation d'hypothèse leur colle à la peau...)
Ce type de chaînes est connu, sous différents noms, depuis près de 2 ans, mais leur formalisation a été progressive et ce n'est que depuis quelques mois qu'apparaissent des présentations plus abordables par tous les joueurs.
Elles englobent par ailleurs diverses techniques à base de chaînes ou figures : XY-wing, chaînes XY, X-wing, swordfish, turbot, cerf-volants, gratte-ciels,... Je n'ai bien sûr rien inventé, et emprunté massivement aux travaux exposés sur des forums anglais, notamment par Havard, R.E.S et Myth Jellies.
2 – Les bases
Les chaînes sont des suites de candidats liés chacun au suivant par un lien.
J'ai opté ici pour l'optique "suite de candidats", et non de cases. Elle me paraît plus facile d'accès et d'emploi pour l'ensemble des joueurs car, une fois assimilés les définitions et principes de base : - c'est une approche purement graphique - qui ne recourt plus au raisonnement logique
L'utilisation des deux notions simples de voisinage et de gémellité facilite l'emploi par tout joueur :
- des voisins partagent la même ligne, colonne, bloc 3x3 ou case (note 1)
Dès que l'un est présent (ci-après "vrai"), tous les autres sont exclus (ci-après "faux").
- des jumeaux sont voisins ET seuls dans leur ligne, colonne, bloc ou case (note 1)
L'un est nécessairement vrai et l'autre faux.
Exemple : voici un tableau des possibilités du seul candidat 3 (hors placés) :
Code: |
A B C D E F G H I +---------+---------+---------+ Les voisins d'un candidat sont en général nombreux (20 maxi); 1 | 3 3 | 3 | 3 3 | pour le 3 de a1 : b1, e1, g1, h1, a2, a7, c2 2 | 3 3 | | 3 3 | 3 | | 3 | 3 | +---------+---------+---------+ Voici les cases des jumeaux qu'on peut y trouver : 4 | 3 3 | | | d3–h3, b4–c4, e1–e9, d3–e1, b4–c4, g9–h8 5 | | | | 6 | | | | +---------+---------+---------+ 7 | 3 3 | 3 | | 8 | 3 | 3 | 3 | 9 | 3 | 3 | 3 | +---------+---------+---------+ | C'est, on va le voir, l'alternance jumeaux / voisins qui va donner toute la puissance aux chaînes.
Pour décrire les chaînes en mettant bien en évidence les maillons, éviter des confusions possibles résultant de l'emploi du signe =, commun sur les sites anglophones, et contrôler facilement leur validité, j'ai choisi :
- de citer le candidat devant sa case : 5c4 représente le 5 de c4
- le signe – (tiret, long de préférence) pour relier les jumeaux. Ex : 3d3–3h3 (ci-dessus), 4c7–9c7 pour une paire 49 en c7
- le signe / (slash, entre espaces de préférence) pour séparer les voisins.
- Propriété fondamentale des chaînes alternant jumeaux / voisins -
------------------Dans une chaîne alternant jumeaux / voisins de type a–b / c–d / ... / p–q ---------------où a, b, c, ... q représentent chacun un (note 2) candidat quelconque comme 5d4, 3e8,... ------------------------------qui sont jumeaux (liés par –) ou voisins (séparés par /)
-----------------une (au moins) des extrémités de la chaîne est vraie (= candidat présent).
C'est simple à comprendre :
- soit a vrai (et b faux, mais on ne peut plus rien déduire du reste de la chaîne)
- soit a faux --> b vrai (car jumeau de a) --> c faux (car voisin de b) --> d vrai ... p faux --> q vrai
(tous les jumeaux de droite sont vrais, dont celui en fin de chaîne)
Vous pouvez vérifier facilement que la chaîne fonctionne également dans l'autre sens : q faux => a vrai.
Des jumeaux peuvent remplacer des voisins (ils sont voisins par définition; note 2), mais pas l'inverse !. Pour éviter les erreurs et faciliter le contrôle de l'alternance, vitale, voisins/jumeaux, utiliser dans ce cas le /.
On va utiliser cette propriété fondamentale de 3 manières :
- la chaîne "ouverte" : élimination des éventuels voisins communs des extrémités (l'une étant forcément vraie)
- la chaîne "fermée" sur elle-même (extrémités identiques) : le candidat de départ/arrivée est vrai (l'un au moins doit l'être!)
(ce n'est en fait qu'un "sous-produit" de la chaîne ouverte : en ôtant son premier ou dernier maillon, la chaîne aboutit au même résultat)
- la "boucle" : l'arrivée est un voisin (ou jumeau) du départ et on peut tourner en rond; je la termine par /@ pour montrer le bouclage.
En "ouvrant" la boucle n'importe où entre deux voisins on obtient autant de chaînes qui éliminent les voisins communs des extrémités : les voisins communs des voisins sont éliminés
Une chaîne est soit :
- mono-candidat, plus simple d'emploi ... et à décrire (pas besoin de répéter le candidat) : la chaîne 3b7–b3 / c2–g2 est constituée :
- des candidats 3 jumeaux en b7, b3 (seuls dans leur colonne)
- des candidats 3 jumeaux en c2, g2 (seuls dans leur ligne)
- du lien de voisinage entre les candidats 3 de b3 et c2 (même bloc/maison)
mixte (multi-candidats), plus puissante mais un peu plus délicate à utiliser : la chaîne 3d3–3h3 / 4h3–4h7 / 4c7–9c7 est constituée : des candidats 3 jumeaux en d3, h3 du lien de voisinage entre le 3 et le 4 de h3 (même case) des candidats 4 jumeaux en h3, h7 du lien de voisinage entre le 4 de h7 et le 4 de c7 (même ligne) de la paire 49 en c7 (même case, 2 seuls candidats)
Notes :
1- Il existe une catégorie de jumeaux très spéciaux.... qui ne sont pas voisins et peuvent être vrais tous les deux, et de drôles de voisins... qui ne partagent pas la même ligne, colonne, bloc 3x3 ou case et s'excluent quand même !
2- Il existe un mode "groupes" où les éléments de la chaîne peuvent être des groupes de plusieurs candidats d'une ou plusieurs cases.
On en reparlera plus loin dans les utilisations avancées de ces chaînes.
En résumé :
- C'est une approche purement graphique : on repère les maillons de jumeaux et on cherche à les raccorder pour joindre
un point de départ à un point d'arrivée, le 1er candidat du maillon N devant être un voisin du 2ème candidat du maillon N-1.
- Il n'y a aucune hypothèse sur un quelconque candidat, ni dans la mise en oeuvre ni dans la représentation de ces chaînes.
Ceci devrait rassurer les "chatouilleux des hypothèses" qui considèrent encore que ce type de technique en relève .
- On peut jouer sur une feuille de papier A5 (1/2 A4) avec crayon et gomme. C'est bien entendu plus simple et,
surtout, il y a nettement moins de risque d'erreur si un ordinateur fait la mise à jour des RAPs.
- En version avancée "groupes" et "objets inclus" toutes les grilles des niveaux extrêmes des diverses publications peuvent sans doute être résolues.
3 – Exemples de chaînes mono-candidat
Vous avez sans doute déjà utilisé des chaînes sans le savoir.
La chaîne élémentaire, à un seul maillon ! :
Code: |
A B C D E F G H I 1 * * * | . . . | 1 1 . Les 1 de a2 et c2, seuls en ligne 2 sont jumeaux : c'est la chaîne a2–c2 2 1 . 1 | . . . | . . . Leurs éventuels voisins communs sont éliminés en b1, b2, b3, c1, c2, c3 3 * * * | . 1 1 | . . . ... vous n'avez pas déjà vu ça quelque part sous d'autres noms ? | On ne va évidemment pas parler de chaîne dans ce cas .
|
|
| |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique : Chaînes de jumeaux/voisins Lun Juil 06 2009, 18:47 | |
| Les chaînes à deux maillons : Très courantes, elles sont déjà puissantes et permettent de résoudre quasiment toutes les grilles parues dans la presse. Ces figures, assez faciles à repérer sur le tableau des candidats, éliminent les éventuels candidats des cases * : Code: | X-wing (boucle) Gratte-ciel Cerf-volant Turbot 1c3–c9 / e9–e3 /@ 2c3–c9 / e9–e2 3b7–b3 / c2–G2 4b7–b3 / g1–i3
A B C D E F G H I A B C D E F G H I A B C D E F G H I A B C D E F G H I 1 . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | 4 . . 2 . . . | . . . | . . . * * . | . 2 . | . . . . . 3———————————3 . . . . . | . . . | . \ . 3 * * 1 | * 1 * | * * * . . 2 | * | * | . . . . 3 . | . . . | . . . . 4 . | . . . | . . 4 ----|-----|---------- ----|-----|---------- --|------------------ --|------------------ 4 . . | | . | . | . . . . . | | . | . | . . . . | . | . . . | . . . . | . | . . . | . . . 5 . . | | . | . | . . . . . | | . | . | . . . . | . | . . . | . . . . | . | . . . | . . . 6 . . | | . | . | . . . . . | | . | . | . . . . | . | . . . | . . . . | . | . . . | . . . ----|-----|---------- ----|-----|---------- --|------------------ --|------------------ 7 . . | | . | . | . . . . . | | . | . | . . . . 3 . | . . . | * . . . 4 . | . . . | * . . 8 . . | | . | . | . . . . . | | . | . | . . . . . . | . . . | . . . . . . | . . . | . . . 9 * * 1 | * 1 * | * * * . . 2 | . 2 . | . . . . . . | . . . | . . . . . . | . . . | . . .
Nota : La distinction cerf-volant/turbot et une "scorie" de l'histoire, pourtant récente, du sudoku. Inutile de vous fatiguer à essayer de les distinguer parfaitement! |
Ces configurations n'existent pas toujours et ne sont pas toujours "efficaces" (s'il n'y a rien à éliminer dans les cases visées...), mais il arrive qu'elles foisonnent, comme dans ce cas réel pour le candidat 1 : Code: | D E F G H I Gratte-ciels Cerf-volants / Turbots +---------+---------+ 4 | 1 | 1 | d8–d4 / h4–h9 ——> -1 en f9, g8 d4–d8 / f9–h9 ——> -1 en h4 5 | | | d4–h4 / h9–f9 ——> -1 en d8, f6 h9–h4 / d4–f6 ——> -1 en f9 6 | 1 | 1 | d4–d8 / g8–g6 ——> -1 en f6 d8–d4 / f6–g6 ——> -1 en g8 +---------+---------+ g6–f6 / f9–h9 ——> -1 en g8, h4 f9–h9 / g8–g6 ——> -1 en f6 7 | | | d8–d4 / h4–g6 ——> -1 en g8 8 | 1 1 | 1 | ——> il ne reste que d4,f8,g6,h9 g8–g6 / f6–d4 ——> -1 en d8 9 | 1 | 1 | d4–d8 / g8–h9 ——> -1 en h4 +---------+---------+ |
... et on n'est pas sûr de les avoir tous ! Les chaînes à trois maillons et plus: Le nombre de configurations possibles et évidemment beaucoup plus important et les répertorier toutes est inutile. Mentionnons seulement des poissons exotiques connus, d'autant plus rares et difficiles à repérer qu'ils sont gros... : le swordfish (ou espadon), boucle à 3 maillons, le jellyfish (ou méduse), boucle à 4 maillons. En pratique il est très rare qu'une chaîne de plus de trois maillons ne puisse pas être remplacée par une plus courte. En reprenant le tableau des 3 du début, voici une chaîne à 3 maillons : Code: | A B C D E F G H I +---------+---------+---------+ Les jumeaux ont été repérés et reliés sur le tableau. 1 | 3 3 | 3 | 3 3* | 2 | 3 3 | | | 3 3* | La chaîne s'obtient en "raboutant" les maillons jumeaux, faciles 3 | | 3––|–––––––––3 | à repérer, par un lien de voisinage, également facile à voir : +---------+----|----+---------+ 4 | 3 3 | | | | 3h3–d3 / e1–e9 / g9–h8 : début en h3, fin en h8. 5 | | | | | 6 | | | | | Nota : les 3 de d3,e1 sont en fait jumeaux; seul leur voisinage +---------+----|----+---------+ est utilisé (et donc noté /) pour respecter l'alternance 7 | 3 3 | 3 | | | jumeaux/voisins. 8 | 3 | 3 | | 3 | Les candidats 3 voisins communs des 3 de h3 et h8, sont éliminés 9 | 3 | 3 | 3 / | en h1, h2. +---------+---------+---------+ | 4 – Exemples de chaînes mixtes Là encore certaines configurations connues ne sont que des cas particuliers de chaînes mixtes : Le XY-wing (ou Aile Delta, ou chaîne XY à trois maillons) : Code: | A B C D E F +------------+------------+ Il est connu. C'est la chaîne mixte 1a3–2a3 / 2b1–3b1 / 3e1–1e1 1 | * 23 * | . 13 . | qui élimine les voisins communs des extrémités 1a3 et 1e1, 2 | . . . | . . . | ç.à.d. les éventuels 1 présents en a1, c1, d3, e3 et f3. 3 | 12 . . | * * * | MAIS, sauf à l'intégrer dans une chaîne mixte plus longue, il vaut +------------+------------+ mieux l'écrire sous sa forme traditionnelle :12(a3)-23(b1)-31(c1). |
Les chaînes XY, les paires distantes, les boucles forcées sont également des chaînes mixtes. Exemple de chaîne mixte simple Code: | A B C D E F +------------+------------+ Cette chaîne fait un travail analogue à celui du XY-wing précédent. 1 | . 2x . | . 12 . | Hypothèses : 1 et 2 sont jumeaux en E1, x = autres candidats, 2 | . . 12 | . . . | 2b1 et 2c2 sont jumeaux, de même que 1a3 et 1c2 3 | 1x . . | * * * | La chaîne 1e1–2e1 / 2b1–2c2 / 1c2–1a3 part de 1e1 et arrive à 1e3. +------------+------------+ Elle élimine les éventuels candidats 1 en d3, e3 et f3... | Exemple de chaîne mixte fermée Code: | D E F G H I (extrait de la grille Extra 79; hors chiffres déjà en place) +----------------+----------------+ 1 | 123 | 258 358 1258 | Chaîne 1e6–1e1 / 3e1–3h1 / 5h1–5h6 / 1h6–1e6 2 | 27 157 | 127 | 3 | 247 234 457 | 38 278 | +----------------+----------------+ Début = fin de chaîne, donc e6=1. 4 | 24 47 | 78 | 5 | 278 17 | 178 | 6 | 68 16 | 258 158 258 | +----------------+----------------+ | Exemple de chaîne mixte avec candidats extrêmes différents Code: | D E F G H I (extrait de la grille Extra 83; hors chiffres déjà en place) +----------------+----------------+ 1 | 67 | 567 456 | Une chaîne subtile mais efficace 6d1–7d1 / 7f2–7g2 / 4g2–4i1 2 | 17 | 47 8 3 | 6i1 est voisin de 6d1 (même ligne) et de 4i1 (même case) 3 | 1678 68 | 567 9 | Il est donc éliminé. +----------------+----------------+ |
Nota 1 : penser à ce type de chaîne, très courant : pour éliminer 'a' en case X : - partir d'un voisin de 'a' dans une case Y - finir sur un candidat 'b' voisin de A dans X Nota 2 : en enlevant le dernier maillon d'une chaîne mixte fermée, on obtient ce type de chaîne... avec le même résultat. On peut le vérifier sur l'exemple précédent de chaîne fermée : 1e6–1e1 / 3e1–3h1 / 5h1–5h6 élimine 1h6, voisin commun de 1e6 et 5h6, d'où e6=1. Exemple de boucle mixte Code: | A B C D E F (hors chiffres déjà en place; 5b7-5f7 sont seuls en ligne 7) +----------------+----------------+ La boucle : 1a9–5a9 / 5b7–5f7 / 3f7–3f8 / 2f8–2d8 / 1d8–1d9 /@ 7 | 356x 1389 | 69 356 | En écriture condensée : 1a9–5 / b7–f7 / 3f7–f8 / 2–d8 / 1–d9 /@ 8 | 369 139 | 129 236 | Les "voisins communs des voisins (encadrant les /)" sont 9 | 15 5689 | 19 56 | éliminés : 5b9 (voisin de 5a9, 5b7), 6f7 (5f7, 3f7), +----------------+----------------+ 6f8 (3f8, 2f8), et 9d8 (2d8, 1d8).
| 5 – Utilisation Avancée - Groupes de candidats On n'a jusqu'ici utilisé la propriété fondamentale des chaînes alternant jumeaux / voisins qu'avec des chaînes de type a–b / c–d / ... / p–q. Mais on peut aussi mettre en oeuvre de chaînes de type a–(b+c) / d-e / ... / p–q où certains candidats (le deuxième ici) sont remplacés par des groupes de candidats comme (b+c). La notion de voisin / jumeau se transpose au groupe : - un groupe (b+c+...) est voisin d'un candidat x si chacun de ses éléments est voisin de x dans une même entité (ligne, colonne, bloc 3x3). - un groupe (b+c+...) est jumeau d'un candidat y s'ils sont voisins ET seuls dans leur entité La chaîne continue alors à fonctionner :
- soit a vrai
- soit a faux --> b vrai OU c vrai --> d faux ... p faux --> q vrai
Là encore, la chaîne fonctionne également dans l'autre sens : q faux => a vrai. De même, si on remplace un élément d'indice impair (le troisième par exemple) par un groupe a–b / (c+d)-e / ... / p–q , la chaîne fonctionne toujours dans les deux sens :
- soit a vrai
- soit a faux --> b vrai --> c faux ET d faux --> e vrai --> ... p faux --> q vrai
Un groupe peut aussi être voisin ou jumeau d'un autre groupe : - (a+b) est voisin de (c+d) si a ET b sont chacun voisins de c et de d dans une même entité (ligne, colonne, bloc 3x3) - (a+b) est jumeau de (c+d) s'ils sont voisins ET seuls dans leur entité (la somme des 2 groupes jumeaux regroupe l'ensemble des candidats de l'entité). Les chaînes à deux maillons ont une version "groupes" : Exemples de version "groupes" du gratte-ciel et du cerf-volant : Code: | Gratte-ciel Cerf-volant 1e3–e9 / c9–(c2-c3) 2b7–(b1+b3) / c2–g2
A B C D E F G H I A B C D E F G H I 1 . . . | . . . | . . . . 2 . | . . . | . . . 2 . . 1 | . . . | . . . . | 2———————————2 . . 3 * * 1 | . 1 . | . . . . 2 . | . . . | . . . ----|-----|---------- --|------------------ 4 . . | | . | . | . . . . | . | . . . | . . . 5 . . | | . | . | . . . . | . | . . . | . . . 6 . . | | . | . | . . . . | . | . . . | . . . ----|-----|---------- --|------------------ 7 . . | | . | . | . . . . 2 . | . . . | * . . 8 . . | | . | . | . . . . . . | . . . | . . . 9 . . 1 | . 1 . | . . . . . . | . . . | . . . | Exemples de chaînes mono-candidat avec groupes Code: | A B C D E F G H I (extrait grille Extra 83 / tableau des 7) +---------+---------+---------+ Pas de chaîne simple, mais plusieurs avec groupes : 1 | 7 | 7 | 7 | 7f2–(d1+d3) / d6–h6 / (h1+h3)–g2 => -7b2 2 | 7 | 7 | 7 | 7f4–f2 / g2–(g4+g5) / h6–d6 => -7d4 3 | 7 | 7 | 7 | 7h6–d6 / f4–f2 / g2–(h1+h3) => -7h5 +---------+---------+---------+ 4 | 7 7 | 7 7 | 7 | 5 | 7 7 | | 7 7 | 6 | | 7 | 7 | +---------+---------+---------+ |
| |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique : Chaînes de jumeaux/voisins Lun Juil 06 2009, 18:47 | |
| 6 – Utilisation Avancée - Inclusion d'objets (merci à Jean chaîne pour ses conseils) On va d'abord étendre les notions de voisins et jumeaux classiques en exprimant leurs relations d'une façon plus générale :
- le voisinage (noté x / y), utilise l'implication x vrai --> y faux, qu'on va re-écrire sous une forme logique équivalente :
Deux candidats (ou groupes de candidats) x et y sont voisins si l'un au plus est vrai (ou, ce qui revient au même, si l'un au moins est faux).
- la gémellité (notée x—y), n'utilise en réalité que l'implication x faux --> x vrai (alors que pour les jumeaux "classiques",
également voisins, on a de plus x vrai --> y faux), ce qu'on peut aussi écrire : Deux candidats (ou groupes de candidats) x et y sont jumeaux si l'un au moins est vrai. (ou, ce qui revient au même, si tous ne sont pas faux).
. La propriété fondamentale des chaînes reste inchangée avec cette définition étendue des jumeaux/voisins : l'une (au moins) des extrémités est vraie... mais les voisins/jumeaux ne partagent plus nécessairement la même ligne, colonne ou bloc 3x3 ! On remarque immédiatement que les deux extrémités d'une chaîne sont... jumeaux ! On appellera voisins/jumeaux distants ces nouveaux êtres qui ne partagent pas la même entité, si on veut les distinguer de nos voisins/jumeaux "classiques", .... et c'est eux qui vont nous permettre d'inclure divers objets dans les chaînes. Il suffit en effet qu'un objet Sudoku "produise" une relation de voisins/jumeaux distants entre deux candidats (ou groupes de candidats) pour pouvoir intégrer la relation dans une chaîne, comme maillon (jumeaux) ou articulation entre maillons (voisins), comme par exemple : - des jumeaux distants : a–b / x–y / e–f / ... / p–q, où x est voisin de b et y voisin de e - des voisins distants : a– x / y-d / e–f / ... / p–q, où x est jumeau de a et y jumeau de d Quels objets inclure ? Toute figure, construction/raisonnement logique produisant des relations de voisinage/géméllité, comme les X-wings et autres poissons éxotiques, les Rectangles Interdits, les ALS/ESC (ensembles sur-complets), ... Nota : - dans une case à N candidats, chaque candidat est jumeau distant du groupe constitué par les autres candidats et voisin de chacun des autres candidats (éventuellement groupés). - l'intégration des ALS/ESC (N+1 candidats pour N cases) est simplifiée : si par exemple dans un ESC de trois cases/4 candidats un candidat n'apparaît qu'une fois, il est jumeau distant de chacun des autres candidats (éventuellement groupés)... mais pas nécessairement voisin comme des jumeaux "classiques" ! Premier exemple : les RI. Dans un RI type 2, 3 ou diagonal, pour éviter la configuration interdite de 4 paires identiques, un ou plusieurs candidats doivent impérativement occuper l'une ou l'autre case du RI. Ils satisfont la relation de jumeaux distants : c faux --> d vrai ci-dessus. La grille Extra 89 en fournit un bel exemple : Code: | A B C D E F G H I +-------------------+-------------------+-------------------+ 1 | 26 45 45 | 1 269 36 | 239 7 8 | Le Ri 14 se situe en b7-b9-h7-h9. 2 | 12 7 9 | 28 25 358 | 1234 6 124 | 3 | 38 136 18 | 4 269 7 | 5 12 129 | Pour éviter la configuration +-------------------+-------------------+-------------------+ interdite (4 x 14), il faut que : 4 | 4 8 3 | 9 126 16 | 7 5 126 | - soit h9=2 5 | 167 9 15 | 267 3 1456 | 1246 8 1246 | - soit b7=3... soit b7=3 et h9=2 6 | 167 156 2 | 678 14567 14568 | 146 9 3 | +-------------------+-------------------+-------------------+ ce qu'on peut écrire (RI14) 2h9–3b7. 7 | 38 134 6 | 5 1478 2 | 19 14 179 | 8 | 9 2 147 | 67 1467 146 | 8 3 5 | 9 | 5 14 1478 | 3 1478 9 | 126 124 1267 | +-------------------+-------------------+-------------------+ |
Le RI s'intègre alors dans la chaîne 8e9–8c9 / 8c3–1c3 / 1h3–2h3 / (RI14) 2h9–3b7 / 3a7–8a7 qui élimine 8 en e7 et c9. Deuxième exemple : les paires de jumeaux. On va ici utiliser un éventuel candidat supplémentaire, sans lequel on aurait une paire de jumeaux dans deux cases. La grille Extra 91 en fournit un bel exemple : Code: | A B C D E F G H I +----------------------+----------------------+----------------------+ 1 | 8 24567 469 | 2459 259 2459 | 679 1 3 | 2 | 56 356 139 | 7 1359 8 | 4 69 2 | 3 | 247 2347 1349 | 12349 6 12349 | 8 79 5 | +----------------------+----------------------+----------------------+ 4 | 4567 345678 2 | 3456 357 345 | 1 78 9 | 5 | 57 1 46 | 259 8 259 | 27 3 46 | 6 | 9 34678 3468 | 12346 1237 1234 | 5 278 46 | +----------------------+----------------------+----------------------+ 7 | 26 268 5 | 2389 4 7 | 2369 269 1 | 8 | 1 24 7 | 2359 2359 6 | 239 45 8 | 9 | 3 9 468 | 1258 125 125 | 26 45 7 | +----------------------+----------------------+----------------------+ |
Examinons la ligne 2 : Code: | 2 | 56 356 139 | 7 1359 8 | 4 69 2 | |
L'absence du 3 en b2 créerait une paire 56 en ligne 2. Dans notre cas, c'est le 6 de la paire qui nous intéresse : 3b2 faux => 6(a2,b2) vrai, ç.à.d. des jumeaux distants. Et voici une chaîne basée là-dessus : 4b8–4c9 / 8c9–8c6 / 3c6–3(b6,b4) / (PJ56) 3b2–6(a2,b2) / 6h2–9h2 / 6h2–6h7 / 6a7–2a7 / 2b8–4b8 Les extrémités étant identiques, b8=4 et la grille s'effondre. Troisième exemple : les ALS/ESC. Rappel : un ALS/ESC comporte N+1 candidats pour N cases. Si un candidat est absent, les autres forment un ensemble complet (paire de jumeaux, triplet, quadruplet, ...). C'est une généralisation du cas précédent, une paires de jumeaux avec un candidat supplémentaire étant le plus simple ALS/ESC. On va utiliser cette propriété dans une chaîne : Code: | A B C D E F Colonnes A à F seules utiles; cases vides = chiffres placés. +-------------------+-------------------+ 1| 2345 | 4569 369 | 2| 347 3457 | 49 45 | Considérons l'ALS/ESC 14678 en C4,C5,C6,C7 : 3| 57 237 | 15 136 | si 4 est absent de C5,C6, 7 doit être en C5, C6 ou C7, soit +-------------------+-------------------+ 4C56 faux => 7C567 vrai, => relation jumeaux distants. 4| 89 168 | 129 | 5| 4679 1467 | 1257 25 | On a alors la chaîne suivante : 6| 479 147 | 1579 179 | 7f9—6f9 / 6(d8,d9)—6d1 / 4d1—4c1 / (ALS) 4(c5,c6)—7(c5,c6,c7) +-------------------+-------------------+ 7| 789 679 678 | 148 167 | 8| 2367 23678 | 1267 28 | 7c9, voisin commun des extrémités, est éliminé. 9| 578 23567 | 246 67 | +-------------------+-------------------+ |
Un autre exemple, avec 2 ALS, au point dur de la grille 92 (merci didier90) : Code: | A B C D E F G H I *------------------+------------------+------------------+ 1 | B68 | 4689 49 | 346 A349 | ALS A : 34689 en i1,i6,i7,i8 2 | 69 | | 69 | 3 | 789 B78 | 469 4689 | 456 459 | ALS B : 4678 en b1,b2,b9 +------------------+------------------+------------------+ 4 | | | | 5 | 38 | 49 49 | 35 356 356 | 6 | 38 | | A38 | +------------------+------------------+------------------+ 7 | 39 346 | 469 | A469 | 8 | 69 | 469 | 39 A34 | 9 | 79 B476 | 469 | 569 456 | +------------------+------------------+------------------+ |
Le 4 de i3 est voyeur des 4 de l'ALS A : s'il n'y a pas de 4 dans A le 8 est obligatoirement en i6, ce qui s'écrit 4i178—8i6. De même, pour l'ALS B on peut écrire : 8b13—4b9 car s'il n'y a pas de 8 dans B le 4 est obligatoirement en b9. D'où la chaîne suivante : (ALS A) 4(i1,i7,i8 )—8i6 / 8a6 - 8a3 / (ALS B) 8(b1,b3)—4b9 / 4h9—4(i7,i8 ) et 4i3 voisin commun des extrémités (qui se recouvrent ici en partie) 4i178 et de 4i78 est éliminé. Quatrième exemple : ALS+ groupes. Les chaînes mixtes avec groupes et objets inclus permettent de s'attaquer aux grilles les plus difficiles. En voici un exemple avec la grille Extra 108 au premier point de blocage : (seuls candidats restant à placer) Code: | A B C D E F G H I +--------------------+------------------+----------------+ 1 | 1378 | 168 167 | 167 1367 | 2 | 13467 1467 137 | 1247 16 | 236 | 3 | 14567 14678 1578 | 12478 1267 | 1267 26 | +--------------------+------------------+----------------+ 4 | 127 127 | 179 167 | 2679 | 5 | 1347 1247 1237 | 1789 15689 1567 | 2678 2679 2689 | 6 | | 78 | 78 | +--------------------+------------------+----------------+ 7 | 15 18 | 129 125 | 168 1369 3689 | 8 | 157 125789 | 159 | 128 129 289 | 9 | 16 126 129 | 19 | | +--------------------+------------------+----------------+ |
La chaîne (ALS)5e8—1(e8+e9) / 1e2—6e2 / 6(a2+b2)—6(a3+b3) / 6i3—2i3 / 2f3—2f7 élimine 5 en f7, d'où e8=5. A SUIVRE ..... o—o—o—o—o—o—o—o—o—o—o—o—o—o—o—o—o—o—o—o—o—o—o—o—o—o—o—o—o—o—o—o—o—o—o—o—o—o—o—o—o Ce post sera édité et complété en fonction de vos observations, remarques, propositions, ... et bien sûr de ma disponibilité ! PS : si certains tableaux sont trop larges pour tenir sur votre écran, passer par ICI pour éviter la bande à gauche du navigateur : papyg Dernière édition par papyg le Jeu 08/03/2007 14:54; édité 14 fois | |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique : Chaînes de jumeaux/voisins Lun Juil 06 2009, 18:48 | |
| | |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique : Chaînes de jumeaux/voisins Lun Juil 06 2009, 18:48 | |
| | |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique : Chaînes de jumeaux/voisins Lun Juil 06 2009, 18:48 | |
| | |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique : Chaînes de jumeaux/voisins Lun Juil 06 2009, 18:48 | |
| | |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique : Chaînes de jumeaux/voisins Lun Juil 06 2009, 18:49 | |
| | |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique : Chaînes de jumeaux/voisins Lun Juil 06 2009, 18:49 | |
| | |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique : Chaînes de jumeaux/voisins Lun Juil 06 2009, 18:49 | |
| papyg Admin
Inscrit le: 11 Oct 2005 Messages: 1130
| Posté le: Sam 09/09/2006 10:48 Sujet du message: |
|
|
Votre explication/démonstration de la boucle n'est évidemment pas criticable... mais comme vous l'avez constaté colle moins bien avec l'esprit de la fiche.
Concernant la représentation, votre boucle mixte de l'extra 84 (châpeau!) : e9#3 <-> d9=3 --> d9#7 <-> d2=7 --> d2#5 <-> e1=5 --> i1#5 <-> i1=3 --> i5#3 <-> h4 = 3 --> h4#9 <-> h7=9 --> f9,i9#9 <-> e9=9 --> e9#3 @
m'est personnellement difficile à lire.
Agressive à l'oeil, très longue et sans repères visuels, il m'est difficile de revenir au bon endroit si je la quitte des yeux pour suivre sur papier ou écran.
Dans ma notation :
3e9–3d9 / 7d9–7d2 / 5d2–5e1 / 5i1–3i1 / 3i5–3h4 / 9h4–9h7 / 9(f9,i9)–9e9 / @
je rapproche volontairement les jumeaux et sépare les voisins pour mieux visualiser les maillons et faciliter ainsi le suivi du chemin de 7 segments qu'on décrit.
Je travaille même en version condensée (qui contient toujours toute l'information) :
3e9–d9 / 7–d2 / 5–e1 / i1–3 / i5–h4 / 9–h7 / (f9,i9)–e9 / @
que je lis et se suis sur la grille toujours assez facilement (et que je trace au crayon en travaillant sur papier) :
Je pars du 3 en e9 vers son jumeau d9, d'où je repars avec le 7 pour son jumeau d2, ...
J'ai trouvé que je faisais nettement moins d'erreurs en recherchant un chemin graphique de cette façon putôt qu'en suivant une suite d'implications, peut-être parce qu'il y a N maillons à suivre au lieu de 2xN implications.
En raisonnant "implication", j'ai plus de mal en cours de recherche d'une chaîne, si je veux par exemple repartir dans une autre voie, de me rappeler si je suis avec un candidat = ou #, ou la nature du lien ... et suis souvent obligé de rapartir au départ ...
Mes c'est peut-être mes neurones qui s'évaporent avec l'âge, et j'adapte mes outils
papyg |
|
| |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique : Chaînes de jumeaux/voisins Lun Juil 06 2009, 18:49 | |
| | |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique : Chaînes de jumeaux/voisins Lun Juil 06 2009, 18:50 | |
| | |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique : Chaînes de jumeaux/voisins Lun Juil 06 2009, 18:50 | |
| | |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique : Chaînes de jumeaux/voisins Lun Juil 06 2009, 18:50 | |
| | |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique : Chaînes de jumeaux/voisins Lun Juil 06 2009, 18:50 | |
| valy21 Sudoka Débutant
Inscrit le: 15 Juil 2006 Messages: 14
| Posté le: Jeu 14/09/2006 0:43 Sujet du message: |
|
|
J'ai commencé de lire avec attention, papyg.
Une faute de frappe figure ici :
Citation: |
pour le 3 de a1 : b1, e1, g1, h1, a2, a7, c3
| Il s'agit du voisin c2 dans votre 1er schéma.
Et, si je ne m'abuse, le XY-Wing gagne des candidats sur DEUX maisons. Je parle de votre tout 1er exemple de XY-Wing, où il n'y a pas d'étoiles sur A1 et C1.
Je vais me trouver du temps pour approfondir votre fiche. @+ |
|
| |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique : Chaînes de jumeaux/voisins Lun Juil 06 2009, 18:51 | |
| | |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique : Chaînes de jumeaux/voisins Lun Juil 06 2009, 18:51 | |
| | |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique : Chaînes de jumeaux/voisins Lun Juil 06 2009, 18:52 | |
| | |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique : Chaînes de jumeaux/voisins Lun Juil 06 2009, 18:52 | |
| | |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique : Chaînes de jumeaux/voisins Lun Juil 06 2009, 18:53 | |
| | |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique : Chaînes de jumeaux/voisins Lun Juil 06 2009, 18:53 | |
| leon1789 Sudoka Expert
Inscrit le: 02 Aoû 2006 Messages: 495
| Posté le: Mar 03/10/2006 11:08 Sujet du message: |
|
|
Puisque vous avez introduit les ALS/ESC dans vos chaînes, je voudrais juste placer ici une remarque d'ordre théorique. Elle n'est (pour l'instant) que théorique car, comme on le verra, ce que je vais écrire est très "lourd" et ne diminue en rien la difficulté de résoudre une grille. Mais, l'important à mon avis, c'est de montrer que les chaînes mixtes (sans groupe a priori) contenant des ALS/ESC sont supplantées par les chaînes pures ALS/ESC. Pour montrer cela, il faut traduire les liens de voisinage et de jumellité en termes d'ALS.
papyg a écrit: |
Deuxième exemple : les paires de jumeaux.
On va ici utiliser un éventuel candidat supplémentaire, sans lequel on aurait une paire de jumeaux dans deux cases.
La grille Extra 91 en fournit un bel exemple :
Code: |
A B C D E F G H I +----------------------+----------------------+----------------------+ 1 | 8 24567 469 | 2459 259 2459 | 679 1 3 | 2 | 56 356 139 | 7 1359 8 | 4 69 2 | 3 | 247 2347 1349 | 12349 6 12349 | 8 79 5 | +----------------------+----------------------+----------------------+ 4 | 4567 345678 2 | 3456 357 345 | 1 78 9 | 5 | 57 1 46 | 259 8 259 | 27 3 46 | 6 | 9 34678 3468 | 12346 1237 1234 | 5 278 46 | +----------------------+----------------------+----------------------+ 7 | 26 268 5 | 2389 4 7 | 2369 269 1 | 8 | 1 24 7 | 2359 2359 6 | 239 45 8 | 9 | 3 9 468 | 1258 125 125 | 26 45 7 | +----------------------+----------------------+----------------------+ | Examinons la ligne 2 :
Code: |
2 | 56 356 139 | 7 1359 8 | 4 69 2 | | L'absence du 3 en b2 créerait une paire 56 en ligne 2.
Dans notre cas, c'est le 6 de la paire qui nous intéresse : 3b2 faux => 6(a2,b2) vrai, ç.à.d. des jumeaux distants. Et voici une chaîne basée là-dessus :
4b8-4c9 / 8c9-8c6 / 3c6-3(b6,b4) / (PJ56) 3b2-6(a2,b2) / 6h2-9h2 / 6h2-6h7 / 6a7-2a7 / 2b8-4b8
Les extrémités étant identiques, b8=4 et la grille s'effondre.
| On peut traduire exactement cela par cette chaîne d'als :
B --4-- C --8-- D --3-- E --6-- F --9-- G --6-- H
avec B als {2468} en cases a7 b7 c9 C als {134689} en cases c1 c2 c3 c5 c6 D als {345678} en cases a4 a5 b4 b6 c5 E als {356} en cases a2 b2 (comme papyg) F als {69} en case h2 G als {26789} en cases h3 h4 h6 h7 H als {26} en case a7
somme des libertés - nombre de charnières = 7-6 = 1
Tout candidat voyant 2 éléments est éliminé (règle 1). En particulier le 2 en b8 , d7 , g7 et h7 , voyeurs du 2 dans B et H.
Remarquer que : * les maillons 4b8-4c9 et 2b8-4b8 n'ont pas été traduits dans la chaîne d'als ** le maillon spécial (PJ56) 3b2-6(a2,b2) est parfaitement intégré dans la chaîne d'als (plus homogène) *** l'als H est incluse dans l'als B ! ... à creuser...
papyg a écrit: |
Troisième exemple : les ALS/ESC.
Rappel : un ALS/ESC comporte N+1 candidats pour N cases. Si un candidat est absent, les autres forment un ensemble complet (paire de jumeaux, triplet, quadruplet, ...).
C'est une généralisation du cas précédent, une paires de jumeaux avec un candidat supplémentaire étant le plus simple ALS/ESC.
On va utiliser cette propriété dans une chaîne :
Code: |
A B C D E F Colonnes A à F seules utiles; cases vides = chiffres placés. +-------------------+-------------------+ 1| 2345 | 4569 369 | 2| 347 3457 | 49 45 | Considérons l'ALS/ESC 14678 en C4,C5,C6,C7 : 3| 57 237 | 15 136 | si le 4 est absent de C5,C6, 7 doit être en C5, C6 ou C7, soit +-------------------+-------------------+ 4C56 faux => 7C567 vrai, donc la relation des "curieux jumeaux". 4| 89 168 | 129 | 5| 4679 1467 | 1257 25 | On a alors la chaîne suivante : 6| 479 147 | 1579 179 | 7f9-6f9 / 6(d8,d9)-6d1 / 4d1-4c1 / (ALS) 4(c5,c6)-7(c5,c6,c7) +-------------------+-------------------+ 7| 789 679 678 | 148 167 | 8| 2367 23678 | 1267 28 | 7c9, voisin commun des extrémités, est éliminé. 9| 578 23567 | 246 67 | +-------------------+-------------------+ |
| On peut traduire exactement cela par cette chaîne d'als :
A --6-- B --459-- C --6-- D --4-- E
avec A als {67} en case f9 B als {1245679} en cases d2, d4, d5, d6, d8 d9 C esc {4569} en case d1 (donc de liberté 3) D als {234569} en cases c1 f1 g1 h1 i1 E als {14678} en cases c4 c5 c6 c7 (comme papyg)
somme des libertés - nombre de charnières = 7-6 = 1
Tout candidat voyant 2 éléments est éliminé (règle 1). En particulier le 7 en c9, voyeur du 7 dans A et E.
Remarquer que : * le maillon spécial (ALS) 4(c5,c6)-7(c5,c6,c7) est parfaitement intégré dans la chaîne d'esc (plus homogène) ** le maillon groupé 6(d8,d9)-6d1 fait apparaître un ESC de liberté 3 et une charnière triple.
Dernière édition par leon1789 le Mer 04/10/2006 9:22; édité 1 fois |
|
| |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique : Chaînes de jumeaux/voisins Lun Juil 06 2009, 18:53 | |
| | |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique : Chaînes de jumeaux/voisins Lun Juil 06 2009, 18:54 | |
| | |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique : Chaînes de jumeaux/voisins Lun Juil 06 2009, 18:54 | |
| | |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique : Chaînes de jumeaux/voisins Lun Juil 06 2009, 18:54 | |
| | |
| | | Contenu sponsorisé
| Sujet: Re: Technique : Chaînes de jumeaux/voisins | |
| |
| | | | Technique : Chaînes de jumeaux/voisins | |
|
Sujets similaires | |
|
| Permission de ce forum: | Vous ne pouvez pas répondre aux sujets dans ce forum
| |
| |
| |