|
| | TECHNIQUE DU COLORIAGE |  |
| | |
| Auteur | Message |
|---|
Admin
Admin
Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009
 | Sujet: TECHNIQUE DU COLORIAGE  Lun Juin 22 2009, 23:15 | |
|
PhB
Sudoka Expert
Inscrit le: 14 Déc 2005
Messages: 369
|
 Posté le: Lun 27/03/2006 18:41 Sujet du message: TECHNIQUE DU COLORIAGE |
 |
|
Bonsoir,
J'ouvre cette discussion pour pouvoir parler specifiquement de cette technique qui s'ajoute a notre panoplie.
Principe
Dans une grille en cours de résolution, un chiffre donné peut être présent dans de multiples paires de cases. Lidée est de mettre ces paires en rapport pour former une chaîne dont chaque maillon aurait une couleur et le double de ce maillon (dans la même unité, ligne colonne ou maison) aurait la couleur complémentaire. Lobjectif est de tomber sur une case non résolue qui posséderait simultanément 2 couleurs. On peut alors éliminer ce chiffre de cette case.
Un exemple valant mieux quun long discours
Exemple
Voici une grille partiellement remplie :
| Code: |
ABC DEF GHI
*-----------*
1 |7..|.8.|..9|
2 |...|6.5|.7.|
3 |..4|...|1..|
|---+---+---|
4 |.6.|...|.2.|
5 |1..|.7.|..8|
6 |.5.|...|.3.|
|---+---+---|
7 |..1|...|4..|
8 |.7.|2.8|...|
9 |3..|.9.|..7|
*-----------*
|
et le tableau des raps.
| Code: |
A B C D E F G H I
*-----------------------------------------------------------------------------*
1 | 7 123 56 | 134 8 1234 | 2356 456 9 |
2 | 289 12389 2389 | 6 14 5 | 23>8n 7 234 |
3 | 56 23>8n 4 | 79 23 79 | 1 56>8b 2356 |
|-------------------------+-------------------------+-------------------------|
4 | 489 6 3789 | 134589 35 1349 | 579 2 145 |
5 | 1 2349 239 | 359 7 2369 | 569 4569 8 |
6 | 2489 5 2789 | 1489 26 12469 | 679 3 146 |
|-------------------------+-------------------------+-------------------------|
7 | 25689 289 1 | 357 356 367 | 4 5689 256 |
8 | 4569 7 569 | 2 14 8 | 3569 1569 356 |
9 | 3 24>8? 2568 | 145 9 146 | 256>8b 1568 7 |
*-----------------------------------------------------------------------------*
|
On sintéresse aux chiffres « 8 » et spécialement ceux qui sont repérés par le signe « > ». La lettre a droite du chiffre repéré indique la couleur n=noir, b=blanc (complémentaire de noir, conventionnellement)
On remarque les couples de cases comportant des « 8 » :
- B3+H3=8
- G2+H3=8
- B9+G9=8
Si on attribue la couleur noire a G2:8(n) alors H3 aura la couleur complémentaire soit H3:8(b).
G2 est liée a G9:8(n) qui reçoit aussi la couleur complémentaire, soit G9:8(b)
De même, B3 est liée a H3:8(b) et reçoit la couleur complémentaire, soit B3:8(n).
Maintenant, que se passe til en B9 qui est a lintersection de 2 cases coloriées ? Si la case B9 porte un « 8 », alors
- elle formerait un couple de cases avec B3:8(n) et donc aurait la couleur complémentaire, B9:8(b)
- elle formerait un couple de cases avec G9:8(b) et donc aurait la couleur complémentaire, B9:8(n)
Comme une case ne peut avoir simultanément 2 couleurs, alors il faut en conclure que la case B9 ne comporte pas de « 8 ».
Remarque
Cette technique du coloriage simple suppose une grille en cours de résolution « tachetée » façon léopard avec un nombre suffisant de cases en couple pour pouvoir développer des chaînes.
_________________
PhB |
|
Dernière édition par Admin le Ven Juin 26 2009, 19:48, édité 2 fois | |
|  | | Admin
Admin
Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009
| | Sujet: Re: TECHNIQUE DU COLORIAGE Mer Juin 24 2009, 13:56 | |
| | |
| | | | Admin
Admin
Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009
| | Sujet: Re: TECHNIQUE DU COLORIAGE Ven Juin 26 2009, 19:50 | |
|
PhB
Sudoka Expert
Inscrit le: 14 Déc 2005
Messages: 369
|
Posté le: Lun 27/03/2006 23:05 Sujet du message: |
|
|
Bonsoir gd11,
Pourquoi un point d'interrogation a B9 et non pas a G9 ?
La "chaine" des cases en couple est constituee par les maillons B3-H3-G2-G9 (B3=H3 sont sur la meme ligne, H3=G2 font partie de la meme maison et G2=G9 se trouvent dans la meme colonne). Les connexions se font par l'intermediaire d'elements qui font partie de 2 unites (ligne, colonne ou maison). L'ordre ou le point de depart est conventionnel, de meme que l'attribution des couleurs.
Sur la ligne 9, il y a 4 cases pouvant comporter un "8" mais seule, la case B9 se trouve a l'intersection de 2 maillons de la chaine. B9 ne fait donc pas partie de la chaine initiale, d'ou le point d'interrogation. En revanche, G9 faisant partie de la chaine initiale, est colorie.
En fait, le coloriage des elements d'une chaine correspond a l'application d'une regle : il faut un point de depart et le reste en decoule automatiquement par alternance des couleurs.
Je pense qu'il faut bien comprendre le principe de depart du coloriage avant d'aborder ce que gpenet va nous apprendre. Chi va piano....
_________________
PhB |
|
| |
| | | | Admin
Admin
Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009
| | Sujet: Re: TECHNIQUE DU COLORIAGE Ven Juin 26 2009, 19:50 | |
| | |
| | | | Admin
Admin
Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009
| | Sujet: Re: TECHNIQUE DU COLORIAGE Ven Juin 26 2009, 19:51 | |
|
gpenet
Sudoka Expert
Inscrit le: 27 Mar 2006
Messages: 174
Localisation: PARIS et BRETAGNE
|
Posté le: Mar 28/03/2006 10:59 Sujet du message: |
|
|
Bonjour PhB,
Je pense que ce message n'est pas venu par hasard, je me risquerai donc à proposer un résumé en plusieurs étapes de ma méthode de coloriage.
Je serai contraint de définir quelques termes que j'utilise couramment pour garantir une lecture correcte du texte.
Cette grille en vaut une autre pour commencer. Je la connaissais sans le 7 en B8, (qui ne la rend pas plus facile).
Disons tout de suite que la solution que je connais dépasse les capacités de mon coloriage.
J'ai quelques écarts avec votre grille de candidats, mais qui ne concernent pas les 8. On peut donc repartir de votre raisonnement que je reformulerai, ne m'en veuillez pas pour préparer la suite.
Historiquement, le coloriage a bien commencé en traitant les différentes occurences d'un chiffre unique dans la grille des candidats.
On peut donc pour faciliter la présentation ne conserver que le candidat traité, ce qui donne ici la grille des 8:
| Code: |
A B C D E F G H I
*--------------------------------*
1 | # - - | - # - | - - # |
2 | 8 8 8 | # - # | 8 # - |
3 | - 8 # | - - - | # 8 - |
|----------+----------+----------|
4 | 8 - 8 | 8 - - | - # - |
5 | - - - | - # - | - - # |
6 | 8 - 8 | 8 - - | - - - |
|----------+----------+----------|
7 | 8 8 - | - - - | - 8 - |
8 | - - - | - - # | - - - |
9 | - 8 8 | - - - | 8 8 - |
*--------------------------------* |
Dans cette grille (ce qui ne contredit pas votre formulation), on s'interesse aux "jumeaux dans un objet"
- objet => ligne colonne ou boite/maison
- jumeaux => deux occurences seulement du chiffre dans l'objet.
Ces jumeaux sont en "liaison forte" de base :
- si l'un est présent l'autre est absent
- l'un des deux au moins est présent.
c'est en logique une condition "ou exclusif".
Les jumeaux ici sont :
- B3H3; G2H3 ; G2G9 que vous utilisez
- D4D6 que vous n'avez pas utilisé.
On note effectivement l'enchaînement B3 H3 G2 G9 qui donne
- si B3 #H3 G2 #G9
- si #B3 H3 #G2 G9
Etat que l'on peut indiquez par toute convention de notation binaire.
Vous avez choisi N et B pour les couleurs Noir,Blanc.
Pour faciliter l'extension du concept, comme l'ont fait naturellement tous ceux qui ont travaillé ce thème, j'ai choisi d'utiliser la lettre A avec la variation (casse en jargon typographique) A majuscule, a minuscule.
Je commence arbitrairement par colorier B3 en a, le tableau devient
| Code: | A B C D E F G H I
*--------------------------------*
1 | # - - | - # - | - - # |
2 | 8 8 8 | # - # | 8 # - |
.a.
3 | - 8 # | - - - | # 8 - |
.a. .A.
|----------+----------+----------|
4 | 8 - 8 | 8 - - | - # - |
.b.
5 | - - - | - # - | - - # |
6 | 8 - 8 | 8 - - | - - - |
.B.
|----------+----------+----------|
7 | 8 8 - | - - - | - 8 - |
8 | - - - | - - # | - - - |
9 | - 8 8 | - - - | 8 8 - |
.A.
*--------------------------------* |
J'en ai profité pour marquer les jumeaux D4D6 en utilisant cette fois la lettre B.
Dans mon jargon, je dis que j'ai maintenant une nappe A,a et une nappe B,b.
Pour la suite, la conclusion sera la même, mais je présenterai un autre raisonnement dont l'utilité apparaîtra mieux dans le prochain exemple.
Avant d'aller à la conclusion, je voudrais résumer le coloriage d'une manière qui me semble plus conforme à l'esprit de ce travail.
Dans la grille :
- deux occurences du chiffre ayant le même marquage (même lettre même casse) sont présentes ensemble ou absentes ensemble.
- deux occurences du chiffre ayant la même lettre mais des casses opposées sont en situation de "ou exclusif".
Il y a certes par construction un chemin qui conduit de l'une à l'autre, mais on peut oublier ce chemin (cette chaîne) et ne raisonner que sur les couples.
Ici, le couple interessant est bien celui que vous indiquez : B3=8a, G9=8A.
Il y a donc un 8 en B3 ou en G9
On peut faire pour conclure le raisonnement de type tenaille qui est le vôtre, Je préfère rapprocher cette situation de celle bien connue du XYWing. On verra dans l'exemple suivant qu'elle et plus puissante.
Comme dans un XYWing, toute case " sous influence commune " de B3 et G9 ne peut contenir de 8.
nota : "sous influence commune" = case dans un objet contenant B3 et dans un objet contenant G9.
Ici les cases concernées sont B9 et G3, le 8 en B9 est éliminé.
Rien de neuf donc dans le contenu à ce stade, seulement un coup d'oeil un peu particulier sur la situation, mais c'est important.
Avant de passer à la généralisation sur plusieurs chiffres, qui fera l'objet d'un second message, je crois utile de compléter l'analyse de cette situation par plusieurs remarques.
1) La nappe B,b ne sert à rien ici. Ce ne sera pas toujours le cas et nous verrons plus tard comment augmenter la puissance de feu du coloriage par le raccordement de nappes.
2) Si dans un même objet on trouve deux occurences de la même lettre dans la même casse,
Cette casse est interdite et c'est la casse opposée qui appartient à la solution.
3) Une remarque très importante sur la cohérence du coloriage.
J'aurais pu schématiser le chemin B3 H3 G2 G9 ainsi
| Code: |
8
| \
8 __________ __8
| .
|
8 |
Dans la pratique, les chaines peuvent être longues et former des boucles internes.
Une question se pose : peut-on avoir dans ce coloriage une boucle créant une incohérence (on revient avec une casse différente).
On démontre simplement (voir remarque 2) que dans un sudoku (donc une solution à la grille), c'est impossible.
Je vous laisse faire la démonstration.
Je propose de faire une pause ici, ce qui permettra d'avoir de premières réactions ou questions avant d'aborder l'extension à plusieurs lettres que je propose de traiter en reprenant l'exemple de la grille 30 qui est à la fois très simple et très riche pour un départ.
Cordialement
G. PENET |
|
| |
| | | | Admin
Admin
Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009
| | Sujet: Re: TECHNIQUE DU COLORIAGE Ven Juin 26 2009, 19:52 | |
|
gpenet
Sudoka Expert
Inscrit le: 27 Mar 2006
Messages: 174
Localisation: PARIS et BRETAGNE
|
Posté le: Mar 28/03/2006 17:47 Sujet du message: coloriage généralisé principe |
|
|
Bonjour PhB,
Peu de commentaires encore sur le premier texte, je ferai donc un tout petit pas ici en l'attente de réactions pour recadrer le texte vers plus ou moins de détails.
Après le coloriage monochiffre, tentons maintenant de généraliser la méthode.
La généralisation se fait uniquement sur les "liaisons fortes".
Dans un premier temps, on ne considèrera que deux type de liaisons fortes :
- les jumeaux utilisés dans l'exemple précédent,
- les cases duo (deux candidats dans la case).
Il est clair que dans une case duo, on respecte les lois identifiées pour une "liaison forte" :
- si l'un des chiffres est présent l'autre est absent
- l'un des deux au moins est présent.
On arrive ainsi à l'expression la plus simple du coloriage généralisé (formulation de MGRF sur le forum Figaro).
Cette fois encore, l'illustration par l'exemple va montrer la simplicité du concept.
J'ai donc choisi de reprendre le premier coloriage de la grille 30 qui me semble parfaitement adapté à une première approche.
Bien évidemment nous ne traiterons que la partie du coloriage qui a été utile.
Voici la situation de départ. Jj'ai fait le marquage des candidats de la manière qui me semble la plus lisible, ce qui est possible ici avec la sortie en mode "code":
| Code: |
#6 . 34578.# 9 .||1
13. .358 . 1238. ||2 => 1 jumeaux en ligne 2
aA A
347. 3457. 237 . ||3
479. 4789 .78 . .||4
379 .#2 . .367 . ||5
#5 . #1 . .367. .||6
1279.679 . #5 . ||7
127. 67. . #4 . ||8
#8 . 369 . 13 . .||9 =>3 jumeaux en ligne 9
a aA
G . . . H . . . . I. . . . |
Les colonnes A à G ne servent pas, une fois précisé les jumeaux 1 en ligne 2 et 3 en ligne 9.
La base du coloriage est ici les jumeaux de "1" G2 I2 I9 qui se fait comme dans l'exercice prédédent.
==>1a en G2; 1A en I2; 1a en I9
On poursuit en complétant les cases duo G2 et I9
==>3A en G2; 3A en I9
On termine par les jumeaux de 3 en ligne 9,
==> 3a en H9.
Il n'y a pas de possibilité de poursuivre, nous avons donc une nappe de coloriage complète.
Le résumé de coloriage proposé plus tôt reste valable :
Dans la grille :
- deux occurences du chiffre ayant le même marquage (même lettre même casse) sont présentes ensemble ou absentes ensemble.
- deux occurences du chiffre ayant la même lettre mais des casses opposées sont en situation de "ou exclusif".
Il y a par construction un chemin qui conduit de l'une à l'autre, mais on peut oublier ce chemin (cette chaîne) et ne raisonner que sur les couples.
Par bonheur, on retrouve ici un couple qui resssemble au précédent :
G2=3A, H9=3a.
Il y a donc un 3 en G2 ou en H9.
Toute case " sous influence commune " de G2 et H9 ne peut contenir de 3.
Ici les cases concernées sont H1,H2,H3,G7,G8,G9,
Les 3 en H1,H2,H3 sont éliminés.
On peut bien sûr construire cas par cas un raisonnement identique à celui de PhB, c'est plus long et, à mon avis, moins naturel.
Que tirer de cet exemple.
1) En se limitant aux liaisons fortes, mais en traitant toutes les lettres, On peut générer des situations similaires à celle du coloriage mono-chiffre, avec les mêmes conclusions.
2) La règle de cohérence s'applique encore, avec ici une extension propre au coloriage multi-chiffres, On ne peut dans une boucle se fermant sur une case duo trouver deux fois la même casse. (Je vous laisse le montrer, c'est toujours très simple)
Voici les points clés du coloriage généralisé. J'attends maintenant les premiers commentaires
Cordialement
G. PENET |
|
| |
| | | | Admin
Admin
Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009
| | Sujet: Re: TECHNIQUE DU COLORIAGE Ven Juin 26 2009, 19:52 | |
| | |
| | | | Admin
Admin
Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009
| | Sujet: Re: TECHNIQUE DU COLORIAGE Ven Juin 26 2009, 19:53 | |
| | |
| | | | Admin
Admin
Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009
| | Sujet: Re: TECHNIQUE DU COLORIAGE Ven Juin 26 2009, 19:53 | |
| | |
| | | | Admin
Admin
Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009
| | Sujet: Re: TECHNIQUE DU COLORIAGE Ven Juin 26 2009, 19:54 | |
|
gpenet
Sudoka Expert
Inscrit le: 27 Mar 2006
Messages: 174
Localisation: PARIS et BRETAGNE
|
Posté le: Mar 28/03/2006 20:56 Sujet du message: tenailles ou coloriage |
|
|
Bonjour PhB,
Je réagis très simplement à votre parallèle tenailles/coloriage.
Je dois dire que je n'ai pas de vue doctrinale sur le sujet, et que je privilégie le pragmatisme.
Il se trouve qu'un des "piliers du forum Figaro" comme vous m'avez gentiment appelé, est un fanatique de l'approche tenaille et qu'il a beaucoup "challengé" sur les avantages comparés des deux méthodes.
Je fais probablement partie d'un très petit groupe qui a essayé (avec succès je pense) de comprendre son approche.
La synthèse que je présenterai ici s'il y a assez de courageux pour aller au bout de l'exercice tente de priviléfier, selon mon point de vue, le meilleur de chacune des voies, sachant qu'elles se recoupent largement.
Pour les situations dérivées des conditions "ou", je crois réellement qu'il faut préférer les voies "directes" dont celle décalquée du XYWing. Quand nous serons dans la phase la plus difficile, celle des raccordements de nappes en cascade, une présentation style "tenaille" (et même "autotenaille" pour reprendre l'expression de l'auteur) apporte davantage de clarté, et je l'ai adopté volontiers.
Je confirme en tous cas qu'il n'y a pas opposition de méthode (sous réserve de s'accorder sur le contenu de la tenaille, car il en est de puissantes qui dépassent ce que je proposerai en coloriage), mais différentes manières de voir la même réalité.
Cordialement
G.PENET |
|
| |
| | | | Admin
Admin
Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009
| | Sujet: Re: TECHNIQUE DU COLORIAGE Ven Juin 26 2009, 19:54 | |
| | |
| | | | Admin
Admin
Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009
| | Sujet: Re: TECHNIQUE DU COLORIAGE Ven Juin 26 2009, 19:55 | |
| | |
| | | | Admin
Admin
Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009
| | Sujet: Re: TECHNIQUE DU COLORIAGE Ven Juin 26 2009, 19:55 | |
| | |
| | | | Admin
Admin
Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009
| | Sujet: Re: TECHNIQUE DU COLORIAGE Ven Juin 26 2009, 19:56 | |
| | |
| | | | Admin
Admin
Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009
| | Sujet: Re: TECHNIQUE DU COLORIAGE Ven Juin 26 2009, 19:56 | |
| | |
| | | | Admin
Admin
Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009
| | Sujet: Re: TECHNIQUE DU COLORIAGE Ven Juin 26 2009, 19:58 | |
| | |
| | | | Admin
Admin
Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009
| | Sujet: Re: TECHNIQUE DU COLORIAGE Ven Juin 26 2009, 19:58 | |
|
gpenet
Sudoka Expert
Inscrit le: 27 Mar 2006
Messages: 174
Localisation: PARIS et BRETAGNE
|
Posté le: Mer 29/03/2006 14:56 Sujet du message: réponses aux questions |
|
|
Bonjour à tous,
Maintenant, des réponses plus générales.
Je confirme tout d'abord à PhB, le coloriage est plein d'embuches (sauf quand il est réalisé par un esclave), et demande un peu de soin.
C'est d'autant plus vrai que, comme on va le voir, on en tire dse conséquences logiques sans garde-fou.
Pour l'oeuf de Colomb, c'est vrai, mais beaucoup ont fait le chemin.
Je pense par contre que le travail réalisé sur l'utilisation du résultat n'est pas si répandu, peut-être parce que ceux qui sont entrés dans cette technique avaient un acquis sur les tenailles qui a bloqué leurs neurones.
Je réponds rapidement aux travaux pratiques de PhB.
| Code: |
A B C D E F G H I
*-----------------------------------------------------------*
1| 35 257 1 | 4 23 258 | 6 578 9 |
2| 4 256 369 | 7 239 2568 | 1 58 238 |
3| 8 2567 3679 | 1 239 256 | 347 457 237 |
|-------------------+-------------------+-------------------|
4| *12a9 3 5 | *2A9a 6 127 | 479 4789 78 |
5| 19 8 67 | 5 4 17 | 379 2 367 |
6| *2A9a 467 467 | *239A 8 27 | 5 1 367 |
|-------------------+-------------------+-------------------|
7| 6 14 48 | 28 127 3 | 279 79 5 |
8| 35 15 38 | 28 127 9 | 27 6 4 |
9| 7 9 2 | 6 5 4 | 8 3 1 |
*-----------------------------------------------------------* |
1) techniquement, rien à dire,
2) compte-tenu de la complexité du coloriage, j'aurais préalablement traité la paire 28 en colonne D.
3) Votre coloriage autorise une réduction en ligne 4. Laquelle ?
Nous reviendrons plus tard à la grille 30 dont j'ai préparé, pour l'exemple, le coloriage final.
Avant, pour mieux répondre à GD11, je vous propose une fin de coup en coloriage que voici :
| Code: |
# 7 45a9a. 4a5A. | 3a8A. 1a3A. 8a9A. . | 1A4a. . # 6 . # 2 ||1
# 6 4a9A . # 3 . | 1A9a. # 2 . # 5 . . | # 8 . . 1a4A. # 7 ||2
# 1 # 2 . # 8 . | # 7 . # 4 . # 6 . . | # 5 . . # 9 . # 3 ||3
# 8 # 6 . 4A5a. | # 2 . 5A7a. 4C7A9b. | 3a49B . 3A4a. # 1 ||4
# 9 4a5A . # 2 . | 1a6A. 1A5a. # 3 . . | 4A6a. . # 7 . # 8 ||5
# 3 # 7 . # 1 . | 6a9A. # 8 . 4c9C. . | 4C6A9b. # 2 . # 5 ||6
# 2 # 1 . # 6 . | 3A8a. # 9 . 7a8A. . | 3a7A. . # 5 . # 4 ||7
# 4 # 3 . # 7 . | # 5 . # 6 . # 1 . . | # 2 . . # 8 . # 9 ||8
# 5 # 8 . # 9 . | # 4 . 3a7A. # 2 . . | 1a37a . 1A3a. # 6 ||9
A . B. . . C . . | D . . E . . F . . . | G . . . H . . I |
Ce coloriage est assez simple, je ne le commenterai pas ici faute de temps, mais on peut y revenir à la demande.
Les deux réponses à GD11 tout d'abord.
- les conflits : regardons en boite 1 : B2 contient 4a, C1 contient 4a. C'est impossible, donc "a" ne figure pas dans la solution.
- On notera que l'on arrive à la même conclusion en regardant la case A2 qui contient 5a et 9a, autre impossibilité.
- Les boucles : il y en a partout. En voici une : D2 8A, D7 8a F7 8A F2 8a
Ce qui est remarquable, c'est qu'aucune boucle ne peut se fermer en créant une impossibilité. Pour ceux qui ont cherché sans la trouver la démonstration, on peut regarder à nouveau la boite 1 :
Si on pouvait fermer la boucle sur les 4 en B2=>C1, on aurait un conflit. Comme les 4 ne sont pas jumeaux en boite 1, ceci n'intervient pas en coloriage, sauf erreur de l'opérateur...
Retour ce soir pour répondre aux questions que pourraient susciter ce texte et pour une description des différentes sorties possibles par la condition "ou".
Cordialement
G. PENET |
|
| |
| | | | Admin
Admin
Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009
| | Sujet: Re: TECHNIQUE DU COLORIAGE Ven Juin 26 2009, 19:59 | |
| | |
| | | | Admin
Admin
Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009
| | Sujet: Re: TECHNIQUE DU COLORIAGE Ven Juin 26 2009, 20:41 | |
|
gpenet
Sudoka Expert
Inscrit le: 27 Mar 2006
Messages: 174
Localisation: PARIS et BRETAGNE
|
Posté le: Mer 29/03/2006 18:09 Sujet du message: suite |
|
|
Bonjour à tous,
Je vais essayer de ne pas perdre le fil de ce partage d'expérience.
Si je résume rapidement,
- Nous avons vu quel regard porter sur le coloriage mono-chiffre de PhB pour préparer la suite.
- Dans un deuxième temps, nous avons fait la généralisation au coloriage multi-chiffres via les cases duo.
- Dans les deux cas, nous avons opéré une réduction de candidats par des figures qui s'apparentent à un XYWing (effet de "ou").
- Dans une digression forcée par Didier (par ma faute), nous avons vu apparaitre des conflits mis en évidence par le coloriage qui permettent d'éliminer en bloc ou de qualifier en bloc les cases ayant certaines marques.
Je vous propose ici un petit inventaire des situations génératrices de réductions (de celles que je connais en tous cas).
========================================
1) les conflits
Je n'en connais que deux, qui sont illustrés dans le dernier exemple que j'ai donné :
- une lettre se retrouve deux fois dans une case (même lettre même casse) case B1 dernier exemple
- la lettre se retrouve deux fois dans le même objet associée au même chiffre. B2 et C1 dernier exemple
Alors cette lettre ne peut figurer dans la solution.
Inversement la lettre de casse opposée est qualifiée.
2) La condition "ou"
Notons tout d'abord que les effets sont les mêmes pour
. le "ou exclusif" {"a" et non "b"} ou {"b" et non "a"}
. le "ou simple". "a seul" ou "b seul " ou "les deux"
Il y a trois cas classiques de réduction de candidats.
J'appelle "x" et "y" les deux lettres qui sont en condition "ou"
2.1) x et y dans la même case. Il ne peut y avoir d'autre candidat dans la case. C'et trivial.
2.2 ) x et y associé au même chiffre (que l'on soit dans le même objet ou non)
C'est l'exemple que nous avons vu deux fois déja
Alors, dans toute case sous influence commune des deux chiffres, il ne peut y avoir le chiffre.
(si 2x et 2y sont les composants du ou, "sous influence commune" veut dire
que la case est dans le même objet que 2x et dans le même objet que 2y).
Cette situation est bien connue, c'est celle du XYWing.
Notons tout de même le cas particulier qui a échappé à PhB: si on est dans le même objet, on a saturé l'objet et on peut donc éliminer le chiffre ailleurs dans l'objet. Dans son exemple, le 2 en F4 peut être éliminé.
2.3) x et y associé à deux chiffres différents dans le même objet.
exemple : 5x689____3456y
Cette situation est spécifique comme le 2.1 du coloriage multi-chiffre.
Elle est moins triviale. Elle est donc à regarder avec attention.
Dans la première case, le 6 peut être éliminé, dans la deuxième, le 5 peut être éliminé.
J'ai noté qu'en général une seule des cases donne lieu à simplification.==================================
Avec ces outils, en nombre très limité, on a toute la panoplie que j'utilise (hormis un cas qui viendra en fin de parcours.)
On peut déja les appliquer sans limite à l'intérieur d'une nappe, c'est souvent insuffisant, nous allons donc apprendre à le utiliser en raccordant les nappes.
Je propose pour terminer ce volet de faire le coloriage de la grille 30 qui intervient après le coup 27.
| Code: |
35.257.#1 | #4 .23. 58 .| #6. 578. #9 ||1
aA A A aA Cc daC
#4 256.39.| #7 .39. 568.| #1. 58. .28.||2
a b Aa aA BC Dd Aa
#8 56 .79.| #1. 29. 56 .| #3. #4 . 27.||3
bB aA Aa Bb aA
#2.#3 .#5.| #9. #6 .#1. | #4. 78. .78.||4
Aa aA
#1.#8 .#6.| #5. #4. #7. | #9. #2 . #3 ||5
#9.47 .47.| #3. #8. #2 | #5. #1 . #6 ||6
Aa aA
#6 14 .48.| 28. 17. #3 | 27. #9 . #5 ||7
Aa Aa aA aA Aa
35.15 .38.| 28. 17. #9. | 27. #6 . #4 ||8
Aa aA aA Aa Aa aA
#7.#9 .#2 | #6 .#5 #4. | #8. #3 . # 1 |9
A B. .C .| D . E . F. | G . H . .I |
On peut commencer le coloriage n'importe ou.
Ici, l'ordinateur a sans doute commencé en détectant A1=35, E1=23, deux cases duo reliées par des jumeaux, situation prometteuse pour une belle nappe.
- en débutant avec 3a en A1, on obtient A1 3a5A et E2 2a3A (le 3A par jumeaux)
Vous pouvez continuer de proche en proche, par exemple :
-2A en B2 (jumeaux) 2A9a en E3 (2 jumeaux et duo) 3a9A en E2 (3 jumeaux et duo)
-7a9A en C3 (9 jumeau et duo) 7A en B1(7 jumeau dans la boite) 7a en H1 (7 jumeau dans la ligne)
etc...
La nappe B commence par les jumeaux de 6 qui n'ont pu être reliés à la nappe A.
- par exemple départ B2(6b) F2 (6B).
Elle peut aussi être initiée par les jumeaux de 5 en ligne 3.
La nappe C est initiée par les jumeaux de 8 en colonne F non encore traités.
Enfin la nappe D se réduit à la case duo H1 qui n'était pas traitée non plus.
On peut trouver étrange de colorier cette case, on verra qu'elle peut être précieuse dans les raccordements de nappes.
Quelles conséquences tirer de ce coloriage?
Allons du plus simple au plus complexe.
- Regardons la case B1 : elle contient 2A et 7A qui sont donc presents ensemble ou absent ensemble.
Ici la conclusion s'impose, "A" n'est pas dans la solution donc "a" l'est.
Si nous n'étions dans un exemple, ceci suffirait et on terminerait la grille.
- La logique est alors, sans succès ici de tenter d'appliquer l'arsenal de recettes décrit plus haut à l'une des nappes.
Ensuite, il faut pousser plus loin et raccorder les nappes.
Nous allons seulement en examiner le principe ici et renvoyer au prochain tour la mise en pratique.
Les cases clé pour le raccordement des nappes sont celles qui mettent en évidence un conflit. On va donc avoir une grande similitude entre les conditions de génératiosn de conflit et les conflits avérés décrits plus haut.
Attention tout de même, ce n'est qu'une similitude, la situation est différente.
Regardons la grille :
- en case H, on a le marquage "daC" sans autre candidat.
On peut en deduire qu'il y aura une des trois lettres et une seule.
Dans la pratique,je n'exploite pour le moment que les incompatibilités prises deux à deux (voir ci-après)
- Plus classique, la case F2 contient deux chiffres marqués respectivement B et C et un chiffre non marqué. (s'il n'y avait pas le troisième chiffre, on conluerait simplement qu'on a mal colorié et on fusionnerait le deux nappes).
Il en résulte quelques conséquences logiques faciles à démontrer.
. On ne peut avoir "B" et "C" donc on a
.{"b" ou "c" ou les deux} (ou simple b,c)
. "B" => "c" ("B" implique "c")
. "C" implique "b"
La première relation est utilisable directement, comme pour le "ou exclusif".
Les deux autres seront utilisées dans l'étape ultime d'exploitation d'un coloriage. Attention, ce sont sauf à apporter la preuve du contraire, des relations non symétriques. x=>y n'implique pas y=>x
- La boite 1 contient 5A en A1 et 5b en B3.
Cette situation est très similaire à la précédente. On ne peut avoir simultanément "A" et "b" donc
. un {ou simple a,B} . A => B b=>"a"
Nous avons ainsi épuisé les situations de raccordement de nappes que j'ai identifiées.
Essayez de faire la liste des situations de conflit dans cette grille et des "ou" qui en découlent.
Certains auront des surprises.
Nous comparerons nos listes au prochain tour.
Cordialement
G. PENET |
|
| |
| | | | Admin
Admin
Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009
| | Sujet: Re: TECHNIQUE DU COLORIAGE Ven Juin 26 2009, 20:42 | |
| | |
| | | | Admin
Admin
Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009
| | Sujet: Re: TECHNIQUE DU COLORIAGE Ven Juin 26 2009, 20:42 | |
|
gpenet
Sudoka Expert
Inscrit le: 27 Mar 2006
Messages: 174
Localisation: PARIS et BRETAGNE
|
Posté le: Mer 29/03/2006 20:16 Sujet du message: réponse à GD11 |
|
|
Bonjour GD11,
Je pense que quand on a beaucoup pratiqué la tenaille, on a du mal à s'en débarasser.
Comme tout le monde, quand une grille résiste, je passe aux techniques de simulation (ou tenailles).
Je sais donc que ce qui est un impossibilité dans un cas devient une condition d'élimination dans l'autre.
Il me semble qu'ici il y a confusion des genres.
Je confirme le marquage indiqué.
Reprenons la définition d'un lien fort :
- si x est présent, y est non présent
- si y est présent, x est non présent
- il y a au moins un des deux de présents.
Toute case duo répond à cette définition. Il n'y a pas de vrai et de fausse case duo.
Que dit ensuite le coloriage.
=> dans la solution (il est important de préciser ce point)
les 3 en G2 et I9 sont tous deux présents ou tous deux absents.
les 1 en G2 et I9 sont tous deux présents ou tous deux absents.
Que dites vous avec la tenaille :
- Si j'essaye 3 en G2, alors I9=1.
.......
On voit immédiatement la différence de démarche.
3 en G2 n'est pas dans la solution
(ce que je vois dans votre tenaille, et je vous fais confiance, mais que j'ignore en coloriage).
Il n'est donc pas surprenant que l'on ne soit pas en phase avec le coloriage.
Evidemment, les réductions opérées en coloriage doivent s'appuyer sur d'autres effets logiques.
On est dans la petite différence que je tentais d'exprimer entre hypothèse et déduction logique.
L'autre remarque est plus simple :
Si "a" est faux , alors "A" est vrai. C'est la construction du coloriage.
Le dire n'est d'ailleurs pas indispensable, certains diraient que c'est un pléonasme..
Eliminez tous les candidats marqué 'a", vous aurez immédiatement validé tous les candidats marqués "A"
Cordialement
G. PENET |
|
| |
| | | | Admin
Admin
Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009
| | Sujet: Re: TECHNIQUE DU COLORIAGE Ven Juin 26 2009, 20:43 | |
| | |
| | | | Admin
Admin
Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009
| | Sujet: Re: TECHNIQUE DU COLORIAGE Ven Juin 26 2009, 20:43 | |
| | |
| | | | Admin
Admin
Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009
| | Sujet: Re: TECHNIQUE DU COLORIAGE Ven Juin 26 2009, 20:44 | |
|
gpenet
Sudoka Expert
Inscrit le: 27 Mar 2006
Messages: 174
Localisation: PARIS et BRETAGNE
|
Posté le: Jeu 30/03/2006 7:52 Sujet du message: reponse a didier et complement pour GD11 |
|
|
Bonjour Didier,
Ayant entre-temps répondu à GD11 qui faisait lui-même référence à votre message, je ne suis pas tout-à-fait sur de bien comprendre votre message.
Je suppose que vous revenez sur la question :
" et si j'ai d'autres cases duo 13...."
Je pensais avoir répondu, mais sans doute pas de façon claire. Si sur la grille il y a plusieurs cases duo identiques, elles appartiendront à la même nappe si on trouve un chemin pour les raccorder, sinon elles appartiendront à des nappes différentes.
C'est une Lapalissade, mais je n'ai pas de meilleure réponse. Dit autrement, il n'y a aucune garantie que l'on saura les raccorder. Je pense avoir des contre-exemples mais il me faut les rechercher. Nous en verrons surement .
Ceci étant dit, je peux être dans l'erreur et il se peut qu'elles soient toutes raccordables, mais il faudrait le démontrer. Le sujet ne m'a pas effleuré avant votre question car la réponse n'est pas utile ici. (Ce qui ne veut pas dire qu'elle est sans intérêt).
J'en profite pour compléter ma réponse à GD11.
L'hypothèse faite (G2=3) conduit à une incohérence avec le coloriage (I9=1 donc A=>a).
Je rejette cette méthode aussi longtemps que je trouve une démarche de déduction logique sans hypothèse.
Il n'empêche que l'on a ainsi démontré que "A" est impossible.
Quand tous les moyens "déductifs" ont été épuisés, il ne reste plus que les hypothèses de ce type.
Si on a fait le coloriage, rien n'interdit alors de l'utiliser pour faire plus court.
Pour ceux qui affectionnent les tenailles "plus respectables", le coloriage est d'ailleurs un bon moyen pour les detecter plus sûrement.
Cordialement
G. PENET |
|
| |
| | | | Admin
Admin
Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009
| | Sujet: Re: TECHNIQUE DU COLORIAGE Ven Juin 26 2009, 20:44 | |
|
gpenet
Sudoka Expert
Inscrit le: 27 Mar 2006
Messages: 174
Localisation: PARIS et BRETAGNE
|
Posté le: Jeu 30/03/2006 9:02 Sujet du message: suite |
|
|
Bonjour à tous,
PhB s'est lancé courageusement dans l'aventure, Bravo.
Pour le moment, l'essai n'est pas concluant, je vais donc essayer de clarifier l'exercice.
Nous avons un avantage, nous savons ce que nous cherchons :
- des cases contenant plusieurs lettres (et non la même lettre avec les deux casses)
- des objets contenant le même chiffre associé à plusieurs lettres.(ici encore des lettres différentes et pas la même lettre avec les eux casses).
Je ferai d'ailleurs une petite digression qui peut clarifier le sujet.
- si une case contient "A" et "a", il y a toujours incompatibilité (c'est d'ailleurs ainsi que nous avons contruit le coloriage), mais que va nous indiquer le trio logique à en déduire :
. on a un {ou simple "a" "A} on sait déja qu'il est exclusif.
. on a A=>A et a=>a ce qui était vrai par construction
_ si on a dans un objet par exemple 2A 2a (jumeaux de 2 dans l'objet par exemple) on aboutit aux mêmes conlusions.
Nous ne sommes pas en opposition avec ce qui a été écrit, simplement dans ce cas, il n'y a rien d'utile à en retirer.
Quand on sait ce que l'on cherche, un bon moyen pour trouver est d'éliminer ce qui ne sert à rien.
Ici, pour faciliter la lecture on peut éliminer:
- les candidats non marqués
- les cases connues
- les candidats marqués dont on a vérifié
. qu'il n'appartiennent pas à une case contenant plusieurs lettres,
. qu'ils ne sont associé ni dans leur ligne, ni dans leur colonne, ni dans leur boite au même chiffre marqué d'une autre lettre.
Commençons par réécrire la grille sans les candidats non marqués et sans les chiffres connus
Les lignes 5 et 9 disparaissent complêtement.
| Code: | 35.27.-- | -- .23. 58 | --. 578. -- ||1
aA AA aA Cc daC
-- 26.39.| -- .39. 68.| --. 58. .28.||2
ab Aa aA BC Dd Aa
-- 56 79.| --. 29. 56 | --. -- . 27.||3
bB aA Aa Bb aA
--.-- --.| --. -- .--.| --. 78. .78.||4
Aa aA
--.47 47.| --. --. -- | --. -- . -- ||6
Aa aA
-- 14 48.| 28. 17. -- | 27. -- . -- ||7
Aa Aa aA aA Aa
35.15 38.| 28. 17. --.| 27. -- . -- ||8
Aa aA aA Aa Aa aA
A B. C .| D . E . F. | G . H . .I
|
Regardons la boite 7:
- le 3A en A9 est relié en ligne à 3a en colonne a 3a (sans autre lien), il peut être ignoré.
idem pour le 5a en A9 relié en ligne à 5A et en colonne à 5A
- Au contraire,
.le 5C en F1, relié en colonne à 5B en F3 sera gardé et réciproquement.
.le 5A en A1 est relié en ligne au 5C en F1, il ne peut être supprimé.
Attention, ne pas aller trop vite dans cet exercice. Il peut être incomplet, son but n'est que de faciliter la lecture ultérieure.
Sauf erreur ou omission, on aboutit à cette grille épurée
| Code: |
5.--.-- | -- -- . 58 .| --. 578. -- ||1
A Cc daC
- 26.-- | -- .--. 68.| --. 8. . 8.||2
ab BC d a
- 5- --| --. --. 5- .| --. -- . --.||3
b - B
-. 5 --.| --. --. --. | --. -- . -- ||8
A
A B. .C | D . E . F. | G . H . .I |
Evidemment, à ce stade, j'aurai un peu de mal à commenter la tentative de PhB.
Je comprends bien son idée de couleur fictive, c'est un concept que j'ai moi-même utilisé dans mes tatonnements. Si on prend le problème dans le bon sens, c'est un concept inutile.
Donc je reviens à la question initiale :
Quels sont dans cette grille les situations de conflit,
Quelle est la liste des "ou simple" de raccordement de nappes qui en résulte.
Je reprens un exemple de chaque type :
- en case F2 on a BC donc un "ou bc"
- en boite 1 on a A1 5A; B3 5b donc un "ou aB"
Je vous laisse poursuivre, je termine l'exercice de mon côté.
Cordialement |
|
| |
| | | | Contenu sponsorisé
| | Sujet: Re: TECHNIQUE DU COLORIAGE | |
| |
| | | | | | TECHNIQUE DU COLORIAGE | |
|
Sujets similaires | |
|
| | Permission de ce forum: | Vous ne pouvez pas répondre aux sujets dans ce forum
| |
| |
| |
portail 
Accueil 
Grilles en lignes 
Tournois du forum 
Dernières images 
Rechercher 
S'enregistrer 
Connexion 
C'est l'oeuf de Colomb! L'idee de genie est d'avoir marie les 2 approches, ce qui ouvre des perspectives tout a fait passionnantes.