| | | TECHNIQUE DU COLORIAGE |  |
| | |
| Auteur | Message |
|---|
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:45 | |
|
PhB
Sudoka Expert
Inscrit le: 14 Déc 2005
Messages: 369
|
 Posté le: Jeu 30/03/2006 19:02 Sujet du message: |
 |
|
Cher gpenet,
Jai essaye hier soir de manipuler les propositions logiques que lon pouvait tirer du schéma sans utiliser le résultat de la case B2 (B2=5). Je nai pas réussi. Je retente aujourdhui avec votre schema :
| Code: |
A B. .C | D . E . F. | G . H . .I
*----------+-------------+-------------*
1! 5.--.-- | -- -- . 58 .| --. 578. -- |1
! A ! Cc ! daC !
2! - 26.-- | -- .--. 68. | --. 8. . 8.|2
! ab ! BC ! d a !
3! - 5- -- | --. --. 5- .| --. -- . --.|3
! b ! - B ! !
+----------+-------------+-------------+
! ! ! !
8!-. 5 --. | --. --. --. | --. -- . -- |8
! A ! ! !
! ! ! !
+----------+-------------+-------------+
|
ligne1 :
- Pour les 5, OU exclusif(A,C,d)
Ligne2 :
- Pour les 8, OU exclusif(a,C,d)
- Un seul 2 en B2, 2=a, alors a=1 ?
Colonne F :
- Pour les 5, OU exclusif(B,C)
Colonne H :
- Pour les 8, OU exclusif(C,d) mais je ne comprends pas pourquoi le 8a de H4 disparaît de votre configuration simplifiee. Pour moi, on devrait avoir OU exclusif(a,C,d)
Maison 3 :
- Pour les 8, OU exclusif(a,C,d)
Cases a 3 candidats :
- H2, OU exclusif (a,d,C)
Je regroupe les propositions logiques :
- OU exclusif(B,C)
- OU exclusif(C,d)
- OU exclusif(a,C,d)
- OU exclusif(A,C,d)
Jai du me tromper car je vois une contradiction maintenant:
- si C et d sont exclusifs, alors d=c
- si a est exclusif de (C et d), alors a=non(C et d)=non(C et c)=non(0)=1
- si A est exclusif de (C et d), alors A=non(C et d)=non(C et c)=non(0)=1
a et son contraire A ne peuvent pas avoir la même valeur logique ? Où est lerreur ?
_________________
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, 20:47 | |
|
gpenet
Sudoka Expert
Inscrit le: 27 Mar 2006
Messages: 174
Localisation: PARIS et BRETAGNE
|
Posté le: Ven 31/03/2006 9:22 Sujet du message: reponse à PhB et suite |
|
|
Bonjour PhB et encore bravo pour l'énergie dépensée pour suivre,
Nous allons donc continuer.
Commençons par cette phrase :
"mais je ne comprends pas pourquoi le 8a de H4 disparaît de votre configuration simplifiee."
Heureusement que j'avais pris la précaution d'usage en écrivant
"Sauf erreur ou omission,"
le 8a aurait du rester. Vous avez donc parfaitement assimilé le concept de simplification.
Comme vous allez le voir, les conlusions qu'il autorise sont déjà présentes, je ne le rajoute donc pas (ce qui m'évite de modifier le texte préparé).
Par contre, on peut éliminer le 8c en F1 que j'avais laissé (omission). On avait donc l'erreur et l'omission.
Pour la suite, vous avez été trop impatient et vous n'avez pas suivi le mode d'emploi esquissé en fin de message.
| Code: |
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" |
Vous tatonnez et sentez bien que quelquechose va venir, mais sans savoir comment asseoir votre raisonnement.
Sans surprise, compte-tenu de votre passé et de ce que je pressentais en faisant cette grille épurée (c'est une première pour moi), vous allez vers les tenailles, alors que je voulais vous pousser en priorité vers le "ou simple". Nous allons sortir le rouleau compresseur et boucler le cas de tenailles. La démarche est de toutes façons la même au départ.
Commençons par la réponse à la question. Comme je l'ai écrit précédemment, je traite les conflits de lettres prises deux à deux, et je n'ai actuellement rien de plus à proposer pour les triangulaires que vous avez detectées.
Voici ma liste de conflits et des conséquences logiques de base qui en découlent :
| Code: |
5.--.-- | -- -- . 5 .| --. 578. -- ||1
A C 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 |
Pour faciliter la présentation, je balaie la grille de haut en bas.
Je cherche pour l'exemple toutes les situations conduisant à la même conclusion.
Je note à chaque fois le trois conséquences logiques
(toujours sauf erreur ou omission)
| Code: |
1- 5A5C ligne 1 AC donne "ou ac" A=>c C=>a
2- 5A5d ligne 1 Ad "ou aD" A=>D d=>a
3- 5C5d ligne 1 Cd "ou cD" C=>D d=>c
8C8d colonne H
8C8d ligne 2
case H1 Cd
4- case H1 da "ou AD" d=>A a=>D
8a8d ligne 2
5- case H1 aC "ou Ac" a=>c C=>A
8C8a ligne 2
6- 5A5b boite 1 Ab "ou aB" A=>B b=>a
5b 5A colonne B
7- 5C5B boite 2 CB "ou bc" C=>b B=>c
case F2
colonne F
8- case B2 ab "ou AB" a=>B b=>A |
Si j'ai bien compté, il y a 16 manières de trouver les conflits,
donc des raccordements de nappes et il y a 8 combinaisons possibles de "ou simple".
c'est, je pense un premier résultat inattendu à priori. Il y a beaucoup de liaisons entre nappes.
Nous avons maintenant deux grandes voies pour poursuivre, chacune pouvant être décisive ou sèche.
====================================
A) La première, que vous préfèrerez sans doute est la visualisation de conflits.
exemple : 1-C=>a 5-a=>c donc C=>c, impossible, "C" n'est pas dans la solution.
B) La deuxième, par laquelle nous terminerons est l'exploitation des "ou simples".
====================================
Examinons donc les conflits du type indiqué. C'est tentant puisque la grille épurée suffit normalement pour aller au bout de l'exercice.
Reprenons le cas indiqué 1- C=>a 5- a=>c. Il n'est pas nécessaire d'en dire plus, mais on peut vouloir retrouver des configurations familières pour se convaincre du bien fondé de la conlusion logique (ne serait-ce que pour se vérifier).
L'origine est ici 1- 5A5C ligne 1 5- case H1 aC
Regardons la ligne 1 on voit bien que 5C en F1
. interdit 5A, en A1 donc force 7a en H1
. force 8C en H1
. donc deux valeurs en compétition sur H1, ce qui est impossible.
La tenaille n'est pas ma spécialité, mais soryu vous monterait immédiatement une "autotenaille" sur ce constat.
Pour détecter tous les conflits de ce type, la méthode consiste à enchaîner les implications du type C=>a de façon à former ls chaines les plus longues possibles.
Essayons l'exercice ici
Reprenons la liste des implications (je rappelle pour contrôle l'origine du conflit):
1) A=>c C=>a AC
2) A=>D d=>a Ad
3) C=>D d=>c Cd
4) d=>A a=>D ad
5) a=>c C=>A aC
6) A=>B b=>a Ab
7) C=>b B=>c CB
 a=>B b=>A ab
Essayons par tatonnements d'esquisser les chaines longues; on pourrait avoir un schéma du genre :
(sauf erreur, et avec des omissions)
| Code: | d=>A=>c
=>D
C=>a=>D
=>c
=>A=>B=>c
=>D
d=>a=>D
=>c
=>c
C=>b=>a=>B
=>A |
On détecte ici en regardant les morceaux ci-dessus plusieurs chaines conflictuelles :
C=>a=>c déja mentionné
d=>A=>D donc "d" n'est pas dans la solution
(4) (2)
b=>a=>B donc "b" n'est pas dans la solution
(6) (
et des chemins plus longs pour montrer la même chose.
Curieusement, on ne retrouve pas ici la certitude déjà établie que "A n'est pas dans la solution.
Il y a une autre configuration, que je ne vois pas ici qui mérite réflexion, celle du type :
x=>y=>y=>x
Je sais, soryu l'a largement expliqué, qu'elle montre que les liaisons dans la tenaille sous-jacente sont fortes, je n'ai pas eu le temps d'en exploiter les conséquences.
Nous en avons teminé avec la méthodologie de détection des boucles.
Il est très tentant si on procède comme je l'ai fait ici de commencer par cette recherche, plus meurtrière que les effets de "ou simple" que nous allons voir.
Je l'aurais sans doute mise en priorité si elle n'était venu très tard dans ma démarche et si j'avais imaginé tout de suite cette grille épurée. Mon principe est en effet de privilégier ce qui peut se faire simplement à la main. (la simplicité et toujours relative en coloriage).
Mais attention, il se peut que seul le "ou" soit productif.
========================================
Regardonc le maintenant.
Nous en resteront ici au principe et nous terminerons le traitement des "ou" dans un message séparé.
Nous avons détecté ici huit "ou simple"
1- "ou ac"
2- "ou aD"
3- "ou cD"
4- "ou AD"
5- "ou Ac"
6- "ou aB"
7- "ou bc"
8- "ou AB"
ce qui veut dire que sur chacune de ces associations de lettres, on peut rechercher une des sorties de "ou", dont je rappelle la liste:
Soient "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.
2.2 ) x et y associé au même chiffre (que l'on soit dans le même objet ou non)
Alors, dans toute case sous influence commune des deux chiffres, il ne peut y avoir le chiffre.
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
Si c'est insuffisant, il reste une arme secrète que l'on peut sortir immédiatement si on a fait la recherche des conflits.
Prenons une chaine non conflictuelle commençant par une des lettres de notre liste de "ou simple"
Par exemple A=>B=>c (je triche un peu pour la démonstration, puisque la chaîne complète est conflictuelle, mais je n'ai pas ici d'autre issue).
en 4) on a "ou AD" on en déduit ici que l'on a aussi "ou AB" et "ou Ac".(ici on les a deja)
On peut essayer de construire le triangle de toutes les associations ou valides
| Code: |
A a B b C c D d
A - x x x x
a x-
B - - - x
b - - x - x
C - - - - - x
c - - - - x - x
D - - - - - - - x
d - - - - - - x - |
J'ai commencé de le faire, je propose de le compléter avant de passer au dernier acte. Malheureusement pour l'exemple , j'ai le sentiment que je vais vérifier, que dans ce cas précis, la liste ne s'allongera pas du fait des chaines d'implications.
C'est l'inconvénient du travail sur des exemples pris au hasard.
Cordialement et bon courage pour la lecture
G. PENET
ps: pour GD11 : Je confirme l'existence de contre-exemples sur le problème des cases duo identiques.
Je prépare sous cette forme un exemple de ce type qui donne aussi une très belle sortie par une chaine analogue à celles présentées ici. |
|
| |
| | | | 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:50 | |
|
PhB
Sudoka Expert
Inscrit le: 14 Déc 2005
Messages: 369
|
Posté le: Ven 31/03/2006 23:53 Sujet du message: |
|
|
Cher gpenet,
Je nen suis pas a préférer telle approche plutôt que telle autre (chaînes vs. Ou). Jessaie simplement de comprendre et, a ce jeu, jéprouve quelques difficultés.
Primo
Je ne comprends pas votre formulation :
| Code: |
1- 5A5C ligne 1 AC donne "ou ac" A=>c C=>a
|
5A5C (ligne 1) signifie que A et C sexcluent mutuellement. Vous écrivez « ou ac ». Je comprends « a et c sexcluent mutuellement », ce qui logiquement revient au même mais oblige a une petite gymnastique. Cest la suite qui me pose problème:
| Code: |
Table de vérité (1=vrai, 0=faux).
On rappelle que a=non(A) et c=non(C)
*---*---*---*---*-----------*-----------*-------*------*------*
! ! ! ! ! OU ! OU ! OU ! ! !
! A ! C ! a ! c ! Excl.(A,C)! Excl.(a,c)! (a,c) ! A=>c ! C=>a !
*---*---*---*---*-----------*-----------*-------*------*------*
! 0 ! 0 ! 1 ! 1 ! 0 ! 0 ! 1 ! 1 ! 1 !
! 0 ! 1 ! 1 ! 0 ! 1 ! 1 ! 1 ! 1 ! 1 !
! 1 ! 0 ! 0 ! 1 ! 1 ! 1 ! 1 ! 1 ! 1 !
! 1 ! 1 ! 0 ! 0 ! 0 ! 0 ! 0 ! 0 ! 0 !
*---*---*---*---*-----------*-----------*-------*------*------*
|
Daprès la table de vérité, {OU Excl.(a,c)} est équivalent à {OU Excl.(A,C)}.
Par contre, {A=>c} est équivalent à {C=>a} qui est équivalent à {OU(a,b)}. Il ne sagit pas du OU exclusif (fromage OU dessert) mais du OU simple (le beurre ET/OU largent du beurre).
Comment (et pourquoi) passe ton du OU exclusif au OU simple ?
Secundo
Je ne comprends pas mieux la suite :
| Code: |
1- 5A5C ligne 1 AC donne "ou ac" A=>c C=>a
2- 5A5d ligne 1 Ad "ou aD" A=>D d=>a
3- 5C5d ligne 1 Cd "ou cD" C=>D d=>c
|
Si les 3 cinq sont sur une même ligne, il ny a quune seule case capable daccueillir ce chiffre (règle de base du Sudoku), les 2 autres cases étant vides de cinq. Lorsque vous présentez les OU (exclusifs, je suppose) les uns au dessous des autres, vous en inférez sans doute que ces propositions sont vraies simultanément. Je linterprète donc comme {{ou ac} et {ou aD} et {ou cD}}. Si cest le cas, ce nest pas équivalent a lexclusivité simultanée des 3 conditions (a,c,D).
| Code: |
Table de vérité (1=vrai, 0=faux).
*---*---*---*-------*-------*--------*----------------*-------*------*------*------------*-------------*
! ! ! ! ! ! ! OU Ex.(a,c) et ! ! ! ! OU(a,c) et ! Exclusivité !
! ! ! ! OU Ex.! OU Ex.! OU Ex. ! OU Ex.(a,D) et ! OU ! OU ! OU ! OU(a,D) et ! Simultanée !
! a ! c ! D ! (a,c) ! (a,D) ! (c,D) ! OU Ex.(c,D) ! (a,c) ! (a,D)! (c,D)! OU(c,D) ! de (a,c,D) !
*---*---*---*-------*-------*--------*----------------*-------*------*------*------------*-------------*
! 0 ! 0 ! 0 ! 0 ! 0 ! 0 ! 0 ! 0 ! 0 ! 0 ! 0 ! 0 !
! 0 ! 0 ! 1 ! 0 ! 1 ! 1 ! 0 ! 0 ! 1 ! 1 ! 0 ! 1 !
! 0 ! 1 ! 0 ! 1 ! 0 ! 1 ! 0 ! 1 ! 0 ! 1 ! 0 ! 1 !
! 0 ! 1 ! 1 ! 1 ! 1 ! 0 ! 0 ! 1 ! 1 ! 1 ! 1 ! 0 !
! 1 ! 0 ! 0 ! 1 ! 1 ! 0 ! 0 ! 1 ! 1 ! 0 ! 0 ! 1 !
! 1 ! 0 ! 1 ! 1 ! 0 ! 1 ! 0 ! 1 ! 1 ! 1 ! 1 ! 0 !
! 1 ! 1 ! 0 ! 0 ! 1 ! 1 ! 0 ! 1 ! 1 ! 1 ! 1 ! 0 !
! 1 ! 1 ! 1 ! 0 ! 0 ! 0 ! 0 ! 1 ! 1 ! 1 ! 1 ! 0 !
*---*---*---*-------*-------*--------*----------------*-------*------*------*------------*-------------*
|
Lexclusivité simultanée de (a,c,D) signifie que seule lune des 3 valeurs logiques est vraie alors que les 2 autres sont fausses.
Aucune de ces combinaisons de OU ne traduisent lexclusivité simultanée de (a,c,D).
Tertio
Vous dites plus loin:
| Code: |
exemple : 1-C=>a 5-a=>c donc C=>c, impossible, "C" n'est pas dans la solution.
|
C=>c (C implique son contraire) est parfaitement possible. Cette proposition est equivalente a dire que C est Faux (le faux peut impliquer le vrai). La conclusion est identique mais il y a (il me semble) une petite entorse a la logique.
Bref, je nage pour linstant et il m'est difficile d'aller plus loin dans le raccordement des nappes. Merci de bien vouloir méclairer.
_________________
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, 20:51 | |
|
gpenet
Sudoka Expert
Inscrit le: 27 Mar 2006
Messages: 174
Localisation: PARIS et BRETAGNE
|
Posté le: Sam 01/04/2006 9:37 Sujet du message: réponse aux interrogations de PhB |
|
|
Cher PhB,
Désolé, j'ai bien vu dans le message précédent qu'il y avait un problème, j'ai pensé à l'attrait visuel de la grille, je n'ai pas pensé à un accrochage sur ce que j'avais présenté. Je reprends donc le texte initial:
| Code: |
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ération 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.
- 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" |
Je n'ai fait qu'appliquer à chaque conflit visible sur la grille cette règle. Si on cale sur le premier exemple, on n'a donc aucune chance de continuer.
Détaillons à nouveau la ligne 1. Je reprends pas à pas vos remarques
| Code: | 1- 5A5C ligne 1 AC donne "ou ac" A=>c C=>a
5A5C (ligne 1) signifie que A et C sexcluent mutuellement. |
Oui donc #{A et B}
| Code: | Vous écrivez « ou ac ».
Je comprends « a et c sexcluent mutuellement », |
Non, c'est une rédaction abrégée de ce qui est écrit au dessus :
on a { "a" ou "c" ou les deux}, donc un {ou simple "a" "c"} que j'écris "ou ac" en forme abrégée.
| Code: |
Daprès la table de vérité, {OU Excl.(a,c)} est équivalent à {OU Excl.(A,C)}.
Par contre, {A=>c} est équivalent à {C=>a} qui est équivalent à {OU(a,b)}. Il ne sagit pas du OU exclusif (fromage OU dessert) mais du OU simple (le beurre ET/OU largent du beurre). |
Sous réserve de la correction de la coquille {OU(a,c)} et non {OU(a,b)}, je dirais que vous venez de vérifier et de redémontrer les trois propriétés que j'indiquais. Une fois rectifiéé la signification de "ou ac", on devrait donc être en accord.
... Et vous devez donc pouvoir défiler sans problème la table des conflits.
Voyons maintenant votre remarque suivante :
| Code: | 1- 5A5C ligne 1 AC donne "ou ac" A=>c C=>a
2- 5A5d ligne 1 Ad "ou aD" A=>D d=>a
3- 5C5d ligne 1 Cd "ou cD" C=>D d=>c
Si les 3 cinq sont sur une même ligne, il ny a quune seule case capable daccueillir ce chiffre (règle de base du Sudoku), les 2 autres cases étant vides de cinq. Lorsque vous présentez les OU (exclusifs, je suppose) les uns au dessous des autres, vous en inférez sans doute que ces propositions sont vraies simultanément. Je linterprète donc comme {{ou ac} et {ou aD} et {ou cD}}. Si cest le cas, ce nest pas équivalent a lexclusivité simultanée des 3 conditions (a,c,D). |
Comme je l'indiquais, Je ne traite pas les conflits triangulaires (voire plus) en bloc. Je prends les composants deux à deux. Il est possible que les conflits triangulaires apportent autre chose, mais en ce qui me concerne, celà reste à découvrir.
Je traite donc ici les trois combinaisons "AC", "Ad" et "Cd".
On retrouvera, par la combinaison en chaîne, des implications que vous essayez de démontrer directement.
Enfin cette remarque
| Code: | exemple : 1-C=>a 5-a=>c donc C=>c, impossible, "C" n'est pas dans la solution.
C=>c (C implique son contraire) est parfaitement possible.
Cette proposition est equivalente a dire que C est Faux (le faux peut impliquer le vrai).
La conclusion est identique mais il y a (il me semble) une petite entorse a la logique. |
Cette fois, c'est vraiment un tout petit problème de vocabulaire, nous disons exactement la même chose.
Quand je dis "n'est pas dans la solution", c'est strictement équivalent à "C" est Faux, votre conclusion. Si "C" est faux, il n'est pas dans la solution. Pardon pour le raccourci.
=================================
Il faut effectivement assurer cette position intermédiaire avant de poursuivre, j'attends donc votre réaction.
Cordialement
G. PENET
ps; je n'étais pas très content de ma présentation graphique de la mise en ordre des relations d'implication. J'ai essayé une variante que je vous livre ici .
1) A=>c C=>a 2) A=>D d=>a 3) C=>D d=>c 4) d=>A a=>D
5) a=>c C=>A 6) A=>B b=>a 7) C=>b B=>c a=>B b=>A
| Code: |
d=>>>>>>>>>>>>>>A
C=>>>>>>>>>>>>>>A
C=>b b=>>>>>>>>>A
A=>c
A=>D
A=>B B=>c
b=>a
C=>>>>>>a
d=>>>>>>a
a=>>>>>>>>>B
a=>>>>>>>>>D
a=>>>>>>>>>>>>c
C=>>>>>>>>>>>>>>>>>>>D
d=>>>>>>>>>>>>>>>>>>>>>>c |
|
|
| |
| | | | 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:52 | |
|
PhB
Sudoka Expert
Inscrit le: 14 Déc 2005
Messages: 369
|
Posté le: Sam 01/04/2006 12:12 Sujet du message: Re: réponse aux interrogations de PhB |
|
|
Ah, je crois comprendre le nud du pb. Je vais y revenir a linstant. Auparavant, je voulais vous remercier des efforts que vous déployez pour faire comprendre votre méthode. Votre patience mérite aussi des éloges.
| gpenet a écrit: |
...
Détaillons à nouveau la ligne 1. Je reprends pas à pas vos remarques
| Code: | 1- 5A5C ligne 1 AC donne "ou ac" A=>c C=>a
5A5C (ligne 1) signifie que A et C sexcluent mutuellement. |
Oui donc #{A et C}
.....
p.s. : je me suis permis de corriger la petite coquille (B au lieu de C)
|
Pour moi, le « Oui donc #{A et C} » nest pas équivalent au OU exclusif, ainsi que le montre la table ci-dessous:
| Code: |
Table de vérité (1=vrai, 0=faux).
On rappelle que a=non(A) et c=non(C)
A.C <=> « A et C »
*---*---*---*---*-----------*-----------*-----*-----*-------------*-----*----------*
! ! ! ! ! OU ! OU ! ! ! ! ! !
! A ! C ! a ! c ! Excl.(A,C)! Excl.(a,c)! A.c ! a.C ! OU(A.C,a.C) ! A.C ! Non(A.C) !
*---*---*---*---*-----------*-----------*-----*-----*-------------*-----*----------*
! 0 ! 0 ! 1 ! 1 ! 0 ! 0 ! 0 ! 0 ! 0 ! 0 ! 1 !
! 0 ! 1 ! 1 ! 0 ! 1 ! 1 ! 0 ! 1 ! 1 ! 0 ! 1 !
! 1 ! 0 ! 0 ! 1 ! 1 ! 1 ! 1 ! 0 ! 1 ! 0 ! 1 !
! 1 ! 1 ! 0 ! 0 ! 0 ! 0 ! 0 ! 0 ! 0 ! 1 ! 0 !
*---*---*---*---*-----------*-----------*-----*-----*-------------*-----*----------*
|
Donc OU Excl.(A,C)= OU (A.c,a.C) mais ce nest pas équivalent à Non(A.C).
_________________
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, 20:53 | |
|
gpenet
Sudoka Expert
Inscrit le: 27 Mar 2006
Messages: 174
Localisation: PARIS et BRETAGNE
|
Posté le: Sam 01/04/2006 12:56 Sujet du message: |
|
|
Cher PhB,
En premier lieu, même si j'ai le sentiment que nous sommes maintenant dans un cours particulier (les curieux du départ sont devenus très discrets), c'est sans regret et non sans intérêt personnel que je poursuis le dialogue.
J'attends évidemment votre suite, mais je corrige tout de suite votre remarque.
si #(AB), alors ou simple (et non exclusif) ab.
si #(AB ) on a trois possibilités (l'équivalent de votre table de vérité)
#A et B alors "a"
A et #B alors "b"
#A et #B alors "a" et "b"
Je pense que nous sommes en accord sur cette proposition, que vous avez d'ailleurs retrouvée. C'est un ou simple : {l'un, l'autre ou les deux} et non un ou exclusif.
Cordialement
G. PENET
ps : Permettez moi de rajouter ce post-scriptum.
Votre besoin de démontrer ce qui est "par construction" peut avoir une autre origine.
Quand on a fait une supposition dont on examine les conséquences, on sort de la grille (on place dedans un chiffre qui n'a pas lieu d'y être) et on montre que l'on aboutit à une impasse.
Alors, les propriétés que j'utilise ici n'existent plus.
En coloriage, (ce qui me permet d'affirmer que l'on est dans un cheminement sans hypothèse), on ne sort jamais de la grille. On regarde les implications logiques et on visualise celles qui nous intéressent par le marquage.
Mon programe fait les deux, mais dans des séquences bien différentes, ce qui fait que je n'ai jamais fait la confusion entre les deux situations.
Camouflage disait gentiment LOUMTOM, je crois vraiment que non, vos difficultés tendraient à le prouver.
Dernière édition par gpenet le Dim 02/04/2006 9:13; édité 1 fois |
|
| |
| | | | 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: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, 20:54 | |
|
PhB
Sudoka Expert
Inscrit le: 14 Déc 2005
Messages: 369
|
Posté le: Sam 01/04/2006 23:22 Sujet du message: |
|
|
Cher gpenet,
Ce message sétale sur une durée assez longue et traduit mon (long) cheminement
A ce point de la discussion, je bute sur un problème sans en voir la sortie. Peut-être ma pensée chemine telle dans une ornière dont je ne sais pas sortir ?
Mon ornière, la voici : en ce qui concerne les « 5 », les conditions A et C sont mutuellement exclusives. Vous me dites quon ne peut avoir les 2 conditions vraies simultanément. Ca a lair de dire la même chose mais, en réalité, je nen suis pas convaincu (pour le moment) sans pouvoir létablir formellement. Doù cette impression de dialogue de sourds.
A moi de bouger, donc :
Premier pas
La différence entre ces 2 propositions tient au fait que le OU exclusif(A,C) nautorise pas que A et C vaillent 0 simultanément tandis que le OU(a,c) le permet.
Second pas
Il ny a que 2 conditions logiques à respecter dans une même unité
Dans ce cas, il faut au moins que lune des 2 soit vraie mais il ne faut pas quelles le soient ensemble : nous sommes bien dans le cas dapplication du OU exclusif.
Il y a plus de 2 conditions logiques à respecter dans une même unité (je n'ai pas essaye + de 3)
On peut simplifier le problème en les prenant 2 a 2. Dans ces conditions, il faut réduire la contrainte pour autoriser que les 2 conditions soient fausses simultanément. Nous sommes alors dans les conditions dapplication du OU simple (ce que vous faites). Cependant, il faut rajouter une contrainte supplémentaire qui assure que lune au plus des 3 conditions soit vraie tandis que les 2 autres sont fausses. Si on ne le fait pas, on pourrait alors avoir les 3 conditions fausses dans une unité, ce qui ne se peut pas. Il me semble que vous ne le faites pas pour le moment.
Plutôt que de prendre les conditions 2 par 2 et dassurer in fine que lune au plus des conditions soit vraie (ce qui est long et compliqué), on peut opérer différemment:
- prendre 2 conditions sous la contrainte dun OU simple,
- assurer ensuite que la troisième condition satisfasse à toutes les contraintes.
Explication
Reprenons lexemple des « 5 » :
| Code: |
Table de vérité (1=vrai, 0=faux, X=0 ou 1).
On rappelle que a=non(A) et c=non(C)
A.C <=> « A et C »
*---*---*---*---*--------*-----*----------------*
! ! ! ! ! ! ! Valeur désirée !
! A ! C ! a ! c ! OU(a,c)! a.c ! pour d !
*---*---*---*---*--------*-----*----------------*
! 0 ! 0 ! 1 ! 1 ! 1 ! 1 ! 1 !
! 0 ! 1 ! 1 ! 0 ! 1 ! 0 ! 0 !
! 1 ! 0 ! 0 ! 1 ! 1 ! 0 ! 0 !
! 1 ! 1 ! 0 ! 0 ! 0 ! 0 ! X !
*---*---*---*---*--------*-----*----------------*
|
1/ Le OU(a,c) assure que les 2 conditions A et C ne peuvent valoir « 1 » simultanément. Par contre, elles peuvent valoir « 0 » simultanément,
2/ La dernière condition « d » doit assurer la compatibilité de lensemble des conditions aux règles du Sudoku. Cest pourquoi jai appelle la dernière contrainte « valeur désirée pour d » :
- Si A et C sont fausses simultanément, alors d est vraie (première ligne du tableau),
- Si A ou C est vraie tandis que lautre est fausse, alors d est nécessairement fausse (deuxième ligne du tableau)
- Si A et C sont vraies simultanément (impossible au Sudoku) alors la valeur de d est indifférente. En réalité, cette condition est interceptée par OU(a,c) qui vaut 0.
La table de vérité de « valeur désirée pour d » est égale a celle de a.c (a et c).
En conclusion, lensemble des contraintes est rendu par les 2 propositions suivantes :
- OU(a,c) est vraie et
- d=a.c
En bon français, cela donne :
Si, dans une unité, un même chiffre est présent 3 fois muni de 3 conditions logiques inconnues X, Y et Z, alors :
- 2 quelconques des 3 conditions logiques ne doivent pas être vraies simultanément [<=> OU(x,y)],
- la troisième nest vraie que si les 2 autres sont fausses simultanément et fausse dans tous les autres cas [<=> Z=x.y]
En reprenant lexemple complet :
Jai rajoute les conditions E et F en B1 et B2 pour couvrir la totalité des raps
| Code: |
A B C D E F G H I
*--------------------------------------------------------*
1 | 3a5A 2A5E7A 1 | 4 2a3A 5C8c | 6 5d7a8C 9 |
2 | 4 2a5F6b 3A9a | 7 3a9A 56B8C| 1 5D8d 2A8a |
3 | 8 5b6B 7a9A | 1 2A9a 5B6b | 3 4 2a7A |
|--------------------+-----------------+------------------|
4 | 2 3 5 | 9 6 1 | 4 7A8a 7a8A |
5 | 1 8 6 | 5 4 7 | 9 2 3 |
6 | 9 4A7a 4a7A | 3 8 2 | 5 1 6 |
|--------------------+-----------------+------------------|
7| 6 1A4a 4A8a | 2a8A 1a7A 3 | 2A7a 9 5 |
8| 3A5a 1a5A 3a8A | 2A8a 1A7a 9 | 2a7A 6 4 |
9| 7 9 2 | 6 5 4 | 8 3 1 |
*---------------------------------------------------------*
|
1/ Case B1 : OU(a,a) est vraie <=> a=1, A=0 doù E=1 et F=0 et b=0, B=1
2/ Maison M1(5) : A1=5A, B3=5b : OU(a,B) est vraie <=> si a=1 et B=1, cest toujours vérifié
3/ maison M3 (H1) : OU(A,c) est vrai et d=A.c <=> si A=0, OU(A,c) est vrai si et seulement si c=1 soit C=0. D=1 et d=0
4/ Ligne 1 (5) : A1=5A, B1=5E, F1=5C et H1=5d : les valeurs sont compatibles.
3/ Maison M3 (8) => H1=8C, H2=8d et I2=8a : OU(A,c) est vraie et d=A.c=0 <=> si A=0 alors OU(A,c)=1 est équivalent a c=1 donc C=0
On a donc :
a=1 & A=0
b=0 & B=1
c=1 & C=0
d=0 & D=1
E=1
F=0
Conclusion partielle
Ouf ! je suis arrivé au bout, ce qui est satisfaisant pour lesprit. Les difficultés se sont aplanies. Il me semble quà une ou deux nuances près, nous ne sommes plus très éloignés. Je nai pas exploré la voie des implications qui semblent plus systématiques et prometteuses. Maintenant, la balle est dans votre camp et jattends vos réactions.
Post-scriptum
Avant de lire les contributions de gd11 et dArnaud javais aussi limpression diffuse que cette discussion tournait un peu au débat de spécialistes. Ces 2 interventions tombent a point nommé pour vous montrer que vous ne parlez pas dans le désert et jen suis heureux. Je suis daccord avec Arnaud pour dire que le coloriage généralisé cest de la dynamite : puissant mais a manipuler avec précautions. Je suis maintenant persuadé que nous arriverons a une formulation claire et bien comprise de tous.
_________________
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, 20:55 | |
|
gpenet
Sudoka Expert
Inscrit le: 27 Mar 2006
Messages: 174
Localisation: PARIS et BRETAGNE
|
Posté le: Dim 02/04/2006 8:40 Sujet du message: réponse à PhB |
|
|
Cher PhB,
Je crois que nous commençons à cerner votre difficulté.
Par malheur, si je puis dire, nous avons une configuration avec trois éléments marqués qui excite votre curiosité et vous avez du mal à vous en dégager.
Une remarque préliminaire :
La situation normale dans une grille qui présente un conflit du, type
5x____5y dans un même objet est d'avoir, outre ces deux occurences du 5, une ou plusieurs autres occurences non marquées. Dans le cas contraire, on aurait des jumeaux, "x" et "y" appartiendraient à la même nappe.
Il se peut que les occurences supplémentaires soient aussi marquées, comme ici 5A__5C__5d en ligne 1. Les règles établies dans le cas général s'appliqueront encore à chacun des couples AC,Ad,Cd.
On peut dire la même chose pour une case : la situation classique est une case du type 2x5y67, donc deux chiffres marqués et d'autres prétendants, on peut avoir une case avec un ou plusieurs des candidats excédentaires marqués, Les règles établies dans le cas général continueront de s'appliquer aux couples de lettres pris deux à deux . En case F1 on a 5d7a8C donc on traitera les couples ad,aC,dC.
Comme je l'ai indiqué, je n'ai personnellement travaillé que le cas général. Il y a peut-être quequechose à sortir des configurations particulières, mais c'est une voie à explorer.
Après ce long préalable, je pars dans votre texte.
| Code: |
Mon ornière, la voici : en ce qui concerne les « 5 », les conditions A et C sont mutuellement exclusives. Vous me dites quon ne peut avoir les 2 conditions vraies simultanément. Ca a lair de dire la même chose mais, en réalité, je nen suis pas convaincu (pour le moment) sans pouvoir létablir formellement. Doù cette impression de dialogue de sourds. |
Pour être très exact, je dis "on ne peut avoir "A" et "C". C'est la règle du sudoku: un seul chiffre par case, une seule occurence du chiffre dans un objet.
"A" et "C" ne forment pas un "ou exclusif". Comme je l'ai dit plus haut, il y a en général un autre candidat qui peut figurer dans la grille. Je n'ai pas fait attention, mais il y avait cette petite erreur dans votre raisonnement, sans doute induite par le fait que l'on avait trois candidats marqués dans la ligne.
| Code: |
Premier pas
La différence entre ces 2 propositions tient au fait que le OU exclusif(A,C) nautorise pas que A et C vaillent 0 simultanément tandis que le OU(a,c) le permet. |
pas de "OU exclusif (A,C)" donc. {"A", ou "C", ou ni l'un ni l'autre }
Par contre, conséquence de
{pas( "A" et "C")}, on a bien le OU(a,c).{ "a" ou "c" ou les deux.}
| Code: |
Second pas
Il ny a que 2 conditions logiques à respecter dans une même unité
Dans ce cas, il faut au moins que lune des 2 soit vraie mais il ne faut pas quelles le soient ensemble : nous sommes bien dans le cas dapplication du OU exclusif. |
Et alors, nous sommes à l'intérieur de la même nappe, par une case duo ou par des jumeaux.
| Code: | | Il y a plus de 2 conditions logiques à respecter dans une même unité (je n'ai pas essaye + de 3) |
En général, deux candidats marqués, les autre non marqués, donc un seul cas à considérer.
On peut trouver trois, voire quatre candidats marqués (il me semble l'avoir eu dans une même case). auquel cas
| Code: | | On peut simplifier le problème en les prenant 2 a 2. |
| Code: |
Dans ces conditions, il faut réduire la contrainte pour autoriser que les 2 conditions soient fausses simultanément. Nous sommes alors dans les conditions dapplication du OU simple (ce que vous faites). Cependant, il faut rajouter une contrainte supplémentaire qui assure que lune au plus des 3 conditions soit vraie tandis que les 2 autres sont fausses. Si on ne le fait pas, on pourrait alors avoir les 3 conditions fausses dans une unité, ce qui ne se peut pas. Il me semble que vous ne le faites pas pour le moment. |
Si c'est un vrai sudoku, cette contrainte est respectée, sinon la grille n'aurait pas de solution.
Redémontrer que la contrainte est respectée est par définition résoudre la grille (au moins partiellement).
Vous faites une démonstration dans le cas spécifique de trois valeurs. Elle n'est pas simple (pour être honnête, je n'ai pas vérifiée). Il faudrait en construire autant qu'il y a de possibilités.
Si vous poursuivez le cheminement que je vous propose, vous verrez que le raisonnement sur les couples est suffisant. Une fois encore, il n'y a rien à démontrer, la grille doit avoir, par définition, une solution et une seule.
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: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, 20: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, 20:57 | |
| | |
| | | | 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:58 | |
|
gpenet
Sudoka Expert
Inscrit le: 27 Mar 2006
Messages: 174
Localisation: PARIS et BRETAGNE
|
Posté le: Dim 02/04/2006 23:34 Sujet du message: |
|
|
Bonsoir PhB,
J'ai le sentiment que nous avons éliminé les problème et que vous avez fait seul , à travers les exemples traités en parallèle la fin du parcours, c'est-à-dire les actions de type "ou simple".
Si ce n'était pas le cas, dites-le, je produirai la fin de l'exemple.
Je vais essayer de répondre à votre dernière question
| Code: | | quelle est votre contribution personnelle dans tout ce "corpus" ? Est-ce que cette methode vous a entierement ete donnee ou bien l'avez-vous perfectionnee |
Comme je l'ai indiqué, la partie "coloriage" a été abordée par plusieurs auteurs.
Quand l'idée m'est venue d'explorer cette piste, je suis allé voir en particulier le site ou est présenté la méthode MEDUSA, et j'y ai trouvé une analyse très bien faite des sorties par condition 'ou simple' qui m'a fait gagner du temps.
J'avais déjà finalisé le coloriage quand je suis allé sur ce site, j'ai retrouvé les mêmes choix à une petite variante près.
Je n'ai par contre aucune référence sur le raccordement des nappes tel que je le pratique. Il faudrait fouiller dans le WEB pour trouver une référence et personne jusqu'à maintenant ne m'a signalé une approche similaire. Si elle existe donc comme c'est probable, elle doit encore être assez confidentielle.
J'ai aussi dans ma poche un joker de coloriage que je n'ai pas mentionné parcequ'il aurait inutilement compliqué cette présentation. C'est une ouverture vers des extensions de la méthode. Je puis vous en parler si vous le souhaitez.
Il y a enfin sur le forum du Figaro une démarche étrangement voisine basée elle sur une approche par des tenailles (d'un type très particulier) . Je pense que la vulgarisation de cette méthode passerait par la même technique de coloriage, mais que la présentation des "actions" pourrait être un peu différente.
Au final donc, tant que l'on a pas trouvé d'autre référence, on peut considérer cette démarche comme originale.
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:58 | |
|
gpenet
Sudoka Expert
Inscrit le: 27 Mar 2006
Messages: 174
Localisation: PARIS et BRETAGNE
|
Posté le: Lun 03/04/2006 8:30 Sujet du message: coloriage fin : réduction par les "ou" |
|
|
Bonjour à tous,
Visiblement, PhB qui est à l'initiative de cette présentation est maintenant satsifait. Il y manque tout de même la conclusion en termes d'éliminations par les "ou simples".
Je la livre donc ici pour ceux qui viendraient avec retard sur ces échanges et leur trouveraient un aspect d'inachevé.
Nous avons détecté ici huit "ou simple"
1- "ou ac" 2- "ou aD" 3- "ou cD" 4- "ou AD"
5- "ou Ac" 6- "ou aB" 7- "ou bc" 8- "ou AB"
En regardant la table des implications, on peut étendre cette liste et j'arrive au tableau final :
| Code: | A a B b C c D d
A - x x x x
a - - x x x
B - - - x x x
b - - - - x
C - - - - - x
c - - - - - - x
D - - - - - - - x
d - - - - - - - - |
La dernière étape est de voir si ces "ou" permettent de faire des réductions de candidats.
Il nous faut pour cela reprendre la grille coloriée.
(On oublie bien sur, pour l'exercice, toutes les conclusions antérieures)
Je déroulerai l'exercice pour les lettres "A" et "a".
Comme nous sommes dans une présentation destinée à faciliter la compréhension de la méthode, je passerai encore par une grille simplifiée.
On notera que b,C,d ne sont en "ou" qu'avec la lettre de leur nappe.
Si on a déjà traité les nappes prises isolément, on peut éliminer ces lettres pour faciliter la lecture du tableau.
On notera également dns la suite que chacune des actions trouvées est indépendante des autres.
Je rappelle la grille d'origine :
| 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 |
==============================================
et notre table des "ou" pour les lignes "A" et "a"
| Code: |
A a B b C c D d
A - x x x x
a - - x x x |
"A" est en "ou" avec BcD (je suppose traité a)
Je présente donc la grille des candidats ou le marquage inutile est parti
| Code: |
35.257.#1 | #4 .23. 58 .| #6. 578. #9 ||1
A A A A c
#4 256.39.| #7 .39. 568.| #1. 58. .28.||2
A A B D A
#8 56 .79.| #1. 29. 56 .| #3. #4 . 27.||3
B A A B A
#2.#3 .#5.| #9. #6 .#1. | #4. 78. .78.||4
A A
#9.47 .47.| #3. #8. #2 | #5. #1 . #6 ||6
A A
#6 14 .48.| 28. 17. #3 | 27. #9 . #5 ||7
A A A A A
35.15 .38.| 28. 17. #9. | 27. #6 . #4 ||8
A A A A A A
A B. .C .| D . E . F. | G . H . .I |
Le plus facile, pour détecter les actions possibles est de regarder les lettres "c" et "B" et de voir comment elles peuvent se combiner en condition "ou" avec la lettre "A"
en boite 1 on a 5A 6B donc pas de 6 en A1 et pas de 5 en B3
- le 5 en B3 disparait
- il était marqué "b", donc "b" n'est pas dans la solution.
A1=5A et D2=5D interdisent D1=5
- 5 était marqué "d", "d" n'est pas dans la solution
A1=5A et F3=5B interdisent 5 en F1
- 5 était marqué "C", "C" n'est pas dans la solution
à priori, rien d'autre avec le A
==============================================
| Code: |
A a B b C c D d
A - x x x x
a - - x x x |
"a" est en "ou" avec BcD. Faisons le même exercice
| Code: | 35.257.#1 | #4 .23. 58 .| #6. 578. #9 ||1
a a c a
#4 256.39.| #7 .39. 568.| #1. 58. .28.||2
a a a B D a
#8 56 .79.| #1. 29. 56 .| #3. #4 . 27.||3
B a a B a
#2.#3 .#5.| #9. #6 .#1. | #4. 78. .78.||4
a a
#9.47 .47.| #3. #8. #2 | #5. #1 . #6 ||6
a a
#6 14 .48.| 28. 17. #3 | 27. #9 . #5 ||7
a a a a a
35.15 .38.| 28. 17. #9. | 27. #6 . #4 ||8
a a a a a a
A B. .C .| D . E . F. | G . H . .I |
.
F1=8c H4=8a interdisent 8 en H1
-ce 8 était marqué "C", "C" n'est pas dans la solution
.On peut aussi éliminer ce 8 par F1 8c H1 7a
.B2=2a F2=6B élimine le 6 en B2. "b" n'est pas dans la solution
.B2=2a H2=5D élimine le 5 en B2.
.H2=5D I2=8a élimine le 8 en H2. "d" n'est pas dans la solution
Voici donc comment on peut conclure sur la réduction par les "ou", qui est souvent, si le coloriage intervient en début de partie, une phase indispensable.
J'ai cette fois terminé la partie "méthodologie". Je proposerai pour en finir un résumé et un exemple d'extension que je pratique.
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, 21:01 | |
|
gpenet
Sudoka Expert
Inscrit le: 27 Mar 2006
Messages: 174
Localisation: PARIS et BRETAGNE
|
Posté le: Mar 04/04/2006 17:28 Sujet du message: |
|
|
Bonjour à tous,
Je voudrais terminer cette présentation du coloriage généralisé par une petite synthèse (résumé des explications précédentes).
==================================
Le coloriage est une des méthodes de résolution des grilles qui peut être décomposée en deux phase :
- une phase de coloriage pur,
- une phase d'exploitation du coloriage.
Le coloriage traite les "liaisons fortes".
La base de ces liens est formée par les cases duo et les cases jumeaux.
Le coloriage traite donc tous les chiffres simultanément.
Deux chiffres sont en lien fort élémentaire si (ou exclusif):
- un des deux est présent sur la grille finale
- et pas les deux.
Si on affecte une lettre avec les casses "Majuscule" et "minuscule" à une liaison forte (duos ou jumeaux),
on peut de proche en proche étendre le marquage et former ainsi une nappe.
Les chiffres marqués de la même casse sont "présents ensemble" ou "absents ensemble" dans la grille finale.
Si par cette méthode on ne traite pas toutes les liaisons fortes, on redémarre une nouvelle nappe avec une lettre différente.
On note que ce coloriage est obligatoirement cohérent si la grille est un sudoku.
Ainsi se termine le coloriage qui se résume alors à un ensemble de nappes.
======================================
La phase d'exploitation du coloriage peut elle-même se décomposer en plusieurs temps :
- les conflits immédiatement détectables, permettant normalement de poser tout de suite un chiffre sur la grille,
- les réductions par condition "ou" sur une nappe prise isolément
et si celà, comme c'est malheureusement souvent le cas, est insuffisant
- Un raccordement des nappes et une sortie
. par des implications interdites
. par des effets de "ou simple" entre lettres de nappes différentes.
_________________________________
Les conflits immédiatement détectables :
- même lettre (et même casse) dans une seule case
- même lettre (et même casse) associée à un même chiffre dans un objet.
__________________________________
Les réductions par condition "ou".
nota : mêmes effets pour le "ou simple" et le "ou exclusif"
- deux occurences d'un chiffre marquées par deux lettres en "ou" :
Ce chiffre ne peut être dans les cases sous influence commune des deux occurences.
- dans une case présence de deux chiffres marqués par les lettres d'un "ou" et alors pas d'autre chiffre dans la case
- dans un objet deux chiffres différents associés aux lettres d'un "ou"
6x... ____ 7y...
Alors le 7 ne peut être dans la case 6x..., le 6 ne peut être dans la case 7y...
_____________________________________
Le raccordement de nappes :
- chaque fois que l'on a un conflit entre deux lettres différentes :
2x3y..dans une case 2x.. ____ 2y.. dans un objet, on peut écrire
non(x et y) ce qui se traduit par trois relations logiques vraies
{X ou Y}; x=>Y; y=>X le "ou" est un "ou simple" : l'un, l'autre ou les deux
_____________________________________
Les conflits issus du raccordement de nappes.
L'enchainement des implications peut déboucher sur deux cas spécifiques :
- X=>a=>C=>x qui implique {"X" absent de la solution}
- X=>a=>C=>X qui indique une boucle infinie aux propriétés particulières. (les liaisons sont fortes)
_____________________________________
Les "ou simples" issus du raccordement de nappes
- Le traitement est le même que dans une napppe,
- On note que si "x ou y" et si y=>Z alors aussi "x ou Z"
On peut donc, en combinant les implications logiques indiquées plus haut multiplier les possibilités de réduction de candidats par les "ou".
========================================
Au plan pratique (un avis personnel):
- éliminer les cas simples : conflits directs et "ou" en nappe unique,
- Ne pas hésiter à faire la grille de candidats épurée pour bien identifier les raccordements de nappes,
- Voir s'il y a des chaines d'implication du type X....=>x
- Dresser la table des "ou" possibles pour une lettre pour faire la recherche en une fois.
=========================================
J'en ai terminé avec ce que j'ai présenté en détail.
Je voudrais exprimer ici que ceci est le fruit d'un travail de groupe et mentionner quelques acteurs qui ont permis, à des degrés divers, de déboucher sur cette formulation.
Au départ de cette recherche, MGRF m'a accompagné et a apporté une formulation plus simple que la mienne de la règle de coloriage.
Notre ami de mots-croisés m'a facilité le contact avec le site MEDUSA qui nous avait précédé dans l'exercice, au moins dans la partie coloriage et la sortie par le "ou simple sur nappe".
JOEL64 et soryu enfin ont apporté des éclairages différents sur l'utilisation des implications A=>b qui ont permis de finaliser la formulation qui vous est proposée.
=============================================
Je ne serais pas complet sans mentionner mon joker et donner une ouverture pour améliorer encore les possibilités du coloriage pour résoudre les grilles qui résistent encore.
Nous avons vu que le coloriage traite des "liaisons fortes".
Au delà des deux cas évidents mentionnés (duos et jumeaux), on peut trouver des liaisons plus complexes qui offrent des ponts supplémentaires.
J'en ai identifié une qui est très fréquente et que j'appelle "maillon double" :
La voici schématiquement
| -- 6. -- |
| -- -- -- |
| 6. 6. 6. | -- -- 6. | -- -- --
Le 6 de la première ligne et le 6 extérieur à la boite sont liés par la condition "présents ensemble ou absents ensemble" mentionnés plus haut. Ils peuvent entrer dans le coloriage.
Il y a certainement d'autres configurations de ce type avec à la clé un enrichissement du coloriage. c'est une voie de recherche.
On peut aussi explorer la voie esquissé par PhB : spécificités des conflits triangulaires.
J'en ai terminé avec ma synthèse et bon courage à ceux qui ont suivi cet exercice.
Cordialement
G. PENET
Dernière édition par gpenet le Ven 07/04/2006 7:01; édité 1 fois |
|
| |
| | | | 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, 21:02 | |
| | |
| | | | 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, 21:02 | |
| | |
| | | | 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, 21:03 | |
| | |
| | | | 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, 21:03 | |
| | |
| | | | 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, 21:05 | |
|
gpenet
Sudoka Expert
Inscrit le: 27 Mar 2006
Messages: 174
Localisation: PARIS et BRETAGNE
|
Posté le: Ven 07/04/2006 14:03 Sujet du message: |
|
|
Bonjour PhB,
Comme je vous l'indiquais dans un autre message, nous avons quelques divergences.
Je pense que votre courage mérite un diagnostic de vos points d'accrochage.
Voici tout d'abord la solution complète proposée par mon ordinateur au point où vous êtes.
| Code: |
6u9U . . # 5 . . # 2 . | # 4 . # 8 . . # 1 . . | 7v9V. . 3e679. . 3E67 . . 1
4689 . . 3g46o . 3G48s. | 6a9A . # 7 . . 5p69. . | # 1 . . 2f4569 . 2F4568r. 2
468r9. . 1b7B. . 1B7b . | # 3 . # 2 . . 5P69. . | 458q9 . 4569 . . 4568 . . 3
45L6 . . 146O7b. 1457 . | # 8 . 146j9I. # 2 . . | 4579. . 13E4579. 13e457 . 4
# 3 . . 12N4. . 1458h. | 1c7C . 149i. . 4C7c. . | # 6 . . 12459I . 12458H . 5
2n46j8s. # 9 . . 1478 . | # 5 . 146J. . # 3 . . | 2478Q . 1247 . . 12478. . 6
# 1 . . 2t48k . # 6 . | 7A9a . # 3 . . 478K9A. | 2457. . 2457 . . 2457 . . 7
2N45l. . 234 . . 3g45L. | 1C6A7. 1c4C. . 46a7. . | 2t3m47. # 8 . . # 9 . . 8
# 7 . . 3m48K . # 9 . | # 2 . # 5 . . 4K8k. . | 3M4m. . 1d6D . . 1D6d . . 9
A. . . . B . . . C. . . | D. . . E . . . F . . . | G . . . H. . . . I. . . . |
On peut oublier A3=8r I2=8r
A6=8s C2=8s
B7=2t G8=2t
trois liaisons doubles du type indiqué dans ma conclusion.
Comparons maintenant les solutions.
Une remarque de fond tout d'abord. Vous n'avez pas jugé utile de colorier les cases A1 et G1, des duos isolés.
J'ai fait la même erreur au début, ici elles sont vitales puisqu'elles créent des ponts pour le chemin de la soluton finale.
Même remarque, mais sans incidence pour les cases H9 et I9.
Nous avons ensuite une divergence sur les nappes A,a et C,c chez moi; C,c chez vous.
| Code: |
| - . - . . - . . | 1
| 6a9A . - . . 569. .| 2
| - . - . . 569. .| 3
| - . 1469. - . | 4
| 1c7C . 149. .4C7c. | 5
| - . 146. .# 3 . | 6
| 7A9a . # 3 . 4789A.| 7
| 1C6A7. 1c4C. 46a7. | 8
| - . - . 48. . | 9
| D. . . E . . F . . |
D E F
*-----------------------*
1 | 4 - - |
2 | 6C9c - 569 |
3 | 3 - 569 |
+-------------------------+
4 | 8 1469 2 |
5 | 1c7C 149 4C7c |
6 | 5 146 3 |
+-----------------------+
7 | 7c9C 3 4789c |
8 | 1C6c7 1c4C 46C7 |
9 | 2 5 48 |
|
Je vois deux sources d'erreur possible dans votre coloriage :
- le plus probable, vous avez traité les 7 de la colonne D en jumeaux en oubliant celui de D8,
- dans un geste généreux, vous avez colorié le 1 en D8 après le 6.
Il faut aussi regarder N,n chez vous et M,m K,k chez moi
| Code: |
A B C D E F G H I
*-------------------------------------------------------*
7 | - 248N - | - - 478n9c | 2457 - - |
8 | - 234 - | - - 46C7 | 23N47 - - |
9 | - 3N48n - | - - 4n8N | 3n4N - - |
*-------------------------------------------------------*
- . 248k . - | - .- . 478K9. | 2457. . - . - . . 7
-. . 234 . .-. | -. -. . 46a7. .| 2t3m47. - . - . 8
- . 3m48K .- | - - . .4K8k. | 3M4m. . - . - . . 9
A. . B . . .C. | D. E . .F . . .| G . . .H. . I |
Cette fois encore il est probable que vous avez traité les 4 en jumeaux en ligne 9
Il y a au moins un manque de coloriage : le 2 en B5 est jumeau avec A6. Je vous laisse poursuive le comparatif.
Situations de conflits
2.1/ D8(1C6c7) : 7 est exclu de la combinaison (la lettre c figure en négatif et en positif dans la même case)
2.1/ B9(3N48n) : 4 est exclu de la combinaison pour les mêmes raisons.
Ici, par erreur de coloriage, on supprime un 4 qui appartient à la solution
652481937
834679152
971325864
467812593
315794628
298563471
186937245
523146789
749258316
Je ne poursuis pas car après ce premier lot d'errreurs, on peut avoir des incohérences.
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, 21:06 | |
|
PhB
Sudoka Expert
Inscrit le: 14 Déc 2005
Messages: 369
|
Posté le: Sam 08/04/2006 20:45 Sujet du message: |
|
|
Cher gpenet,
Jai énormément de mal à me sortir de ce coloriage. Je ne sais pas exploiter les implications après un certain point (cf infra). Merci de vos lumières.
Coloriage
| Code: |
A B C D E F G H I
*------------------------------------------------------------------------------*
1 | 6u9U 5 2 | 4 8 1 | 7v9V 3E679 3e67 |
2 | 4689 3A46B 3a48w | 6C9c 7 5D69 | 1 2F4569 2f4568 |
3 | 4689 1G7g 1g7G | 3 2 5d69 | 458H9 4569 4568 |
|-------------------------+-------------------------+--------------------------|
4 | 45I6 146b7G 1457 | 8 146J9K 2 | 4579 13e4579 13E457 |
5 | 3 12m4 1458L | 1s7S 149k 4S7s | 6 12459K 12458l |
6 | 2M46J8w 9 1478 | 5 146j 3 | 2478h 1247 12478 |
|-------------------------+-------------------------+--------------------------|
7 | 1 2t48P 6 | 7c9C 3 478p9c | 2457 2457 2457 |
8 | 2m45i 234 3A45I | 1S6c7 1s4S 46C7 | 2t3N47 8 9 |
9 | 7 3N48p 9 | 2 5 4p8P | 3n4N 16 16 |
*------------------------------------------------------------------------------*
|
Relations logiques OU/Implications
#1 [B2:B2-36] Non[Et(A,B)] <=> Ou(a,b) A=>b B=>a
#2 [B2:B9-3 ] Non[Et(A,N)] <=> Ou(a,n) A=>n N=>a
#3 [C8:C8-35] Non[Et(A,I)] <=> Ou(a,i) A=>i I=>a
#4 [B2:D2-6 ] Non[Et(B,C)] <=> Ou(b,c) B=>c C=>b
#5 [F7:F7-89] Non[Et(c,p)] <=> Ou(C,P) c=>P p=>C
#6 [F5:F9-4 ] Non[Et(C,p)] <=> Ou(c,P) C=>P p=>c
#7 [B4:E4-6 ] Non[Et(b,J)] <=> Ou(B,j) b=>j J=>B
#8 [B4:B4-67] Non[Et(b,G)] <=> Ou(B,g) b=>g G=>B
#9 [A8:A8-25] Non[Et(m,i)] <=> Ou(I,M) i=>M m=>I
#10[E4:E4-69] Non[Et(J,K)] <=> Ou(j,k) J=>k K=>j
#11[A6:A6-26] Non[Et(M,J)] <=> Ou(j,m) J=>m M=>j
#12[F9:G9-4 ] Non[Et(N,p)] <=> Ou(n,P) N=>P p=>n
. . . . . . . . . . . . . . . . . . . . . . . . .
#13[A1:B2-6 ] Non[Et(u,B)] <=> Ou(U,b) u=>b B=>U
#14[A1:A6-6 ] Non[Et(u,J)] <=> Ou(U,j) u=>j J=>U
#15[A1:G1-9 ] Non[Et(U,V)] <=> Ou(u,v) U=>v V=>u
#16[D5:D7-7 ] Non[Et(c,S)] <=> Ou(C,s) c=>s S=>C
#17[F5:F9-4 ] Non[Et(p,S)] <=> Ou(P,s) p=>s S=>P
#18[A8:G8-2 ] Non[Et(m,t)] <=> Ou(M,T) m=>T t=>M
#19[C2:C2-38] Non[Et(a,w)] <=> Ou(A,W) a=>W w=>A
#20[A6:A6-28] Non[Et(M,w)] <=> Ou(m,W) M=>W w=>m
#21[A6:A6-86] Non[Et(J,w)] <=> Ou(j,W) J=>W w=>j
#22[A6:C5-8 ] Non[Et(L,w)] <=> Ou(l,W) L=>W w=>l
Déductions logiques
w=>A=>b=>j
J=>B=>a=>W
w=>A=>n
N=>a=>W
N=>P
p=>n
w=>A=>i=>M=>W
w=>m=>I=>a=>W
J=>m=>I=>a=>W
w=>A=>i=>M=>j
J=>B=>U=>v
V=>u=>b=>j
J=>B=>c=>P
p=>C=>b=>j
J=>B=>c=>s
S=>C=>b=>j
J=>k
K=>j
J=>m=>T
T=>M=>j
J=>W
w=>j
G=>B=>a
G=>B=>U=>v
w=>m=>I=>a=>W donc w est faux et W est vrai
Simultaneite de M,J,w. On doit avoir:
- Non(Et(M,J)) <=> Ou(m,j)<=> M=>j <=> J=>m et
- w=m.j
Or w=m.j est faux donc Ou(M,J) est vrai <=> m=>J
Si J=>m et m=> J alors m=J et M=j. Dans ce cas, A6=(2j6J), 4 et 8 sont éliminés.
| Code: |
A B C D E F G H I
*------------------------------------------------------------------------------*
1 | 6u9U 5 2 | 4 8 1 | 7v9V 3E679 3e67 |
2 | 4689 3A46B 3a4A | 6C9c 7 5D69 | 1 2F4569 2f4568 |
3 | 4689 1G7g 1g7G | 3 2 5d69 | 458H9 4569 4568 |
|-------------------------+-------------------------+--------------------------|
4 | 45I6 146b7G 1457 | 8 146J9K 2 | 4579 13e4579 13E457 |
5 | 3 12J4 1458L | 1s7S 149k 4S7s | 6 12459K 12458l |
6 | 2j6J 9 1478l | 5 146j 3 | 2478h 1247 12478 |
|-------------------------+-------------------------+--------------------------|
7 | 1 2t48P 6 | 7c9C 3 478p9c | 2457 2457 2457 |
8 | 2J45i 234 3A45I | 1S6c7 1s4S 46C7 | 2t3N47 8 9 |
9 | 7 3N48p 9 | 2 5 4p8P | 3n4N 16 16 |
*------------------------------------------------------------------------------*
|
_________________
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, 21:07 | |
| | |
| | | | 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 
