| ALS ESC EQC | |
|
|
|
Auteur | Message |
---|
Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: ALS ESC EQC Ven Juil 03 2009, 17:47 | |
| | |
|
| |
Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: ALS ESC EQC Ven Juil 03 2009, 17:47 | |
| PhB Sudoka Expert
Inscrit le: 14 Déc 2005 Messages: 369
| Posté le: Jeu 28/09/2006 0:49 Sujet du message: |
|
|
Bonsoir Didier,
Votre premier exemple d’ Ensembles Sur Complets me laisse dubitatif. Laissons de cote, pour le moment, les généralisations et parlons d’ESC.
1/ si j’ai bien compris, la différence entre EQC et ESC semble porter sur la définition de la charnière : - Pour l’EQC, une charnière est exclusivement dans l’un ou l’autre sous-ensemble mais pas dans les deux. - Pour l’ESC, une simple « liaison jumeau » est requise, ce qui me semble une contrainte moins forte (Je la comprends comme « liaison jumeau par rapport à la colonne D »). A la limite, le candidat de la charnière pourrait habiter dans les 2 sous-ensembles.
2/ le coup que vous expliquez me semble heureux. En effet B9=9 ici a la bonne idée de forcer D6=1 puis E9=2 et G9=2, ce qui dépend d’autres facteurs non explicités dans l’énoncé. On pourrait avoir : - A = b5 d5 (159) réduit à (15) par B9=9 - B = d9 e9 f9 g9 (12359) réduit à (1235) par B9=9, tout en ayant un seul exemplaire du 1 en colonne D
Les 2 ensembles seraient alors complets et on ne pourrait pas éliminer 9 de B9, comme dans la configuration ci-dessous :
Code: |
B C ! D E F ! G ---------+--------------+--- 6 ! 19 ! 15 ! ---------+--------------+---- 9 ! <9> ! 135 235 239 ! 123 ---------+--------------+---- D6+D9=1 B9=9 voit tous les candidats 9 des 2 sous-ensembles.
|
Donc, - soit l’ensemble sur complet a les mêmes contraintes que l’EQC (alors c’est un EQC) - soit quelque chose m’échappe. _________________ PhB |
|
| |
|
| |
Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: ALS ESC EQC Ven Juil 03 2009, 17:48 | |
| | |
|
| |
Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: ALS ESC EQC Ven Juil 03 2009, 17:48 | |
| | |
|
| |
Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: ALS ESC EQC Ven Juil 03 2009, 17:48 | |
| | |
|
| |
Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: ALS ESC EQC Ven Juil 03 2009, 17:48 | |
| | |
|
| |
Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: ALS ESC EQC Ven Juil 03 2009, 17:48 | |
| | |
|
| |
Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: ALS ESC EQC Ven Juil 03 2009, 17:49 | |
| leon1789 Sudoka Expert
Inscrit le: 02 Aoû 2006 Messages: 495
| Posté le: Dim 01/10/2006 6:41 Sujet du message: |
|
|
En fait il y a seulement une régle qui gère les cas de figure généraux déjà vus dans ce post, ou d'autres antérieurs...
(message repris dans http://www.sudoku-factory.com/forumsudoku/viewtopic.php?p=3917)
La donnée : un ensemble quelconque d'ESC (dont les degrés de liberté sont quelconques) tel que chaque ESC possède au moins autant de charnières que son dégré de liberté, chaque ESC doit avoir ses charnières distinctes. (remarque : ces ESC peuvent avoir des cases communes, ou être inclus les uns dans les autres, voire même être égaux... bref, il n'y a aucune contrainte à ce niveau !) Enfin, on somme les degrés de liberté des ESC puis on retranche le nombre total de charnières du système (une charnière simple compte un, une double compte deux, etc )
Si le résultat vaut 0, on applique la règle i=0 Si le résultat vaut 1, on applique la règle i=1 Si le résultat vaut 2, on applique la règle i=2 etc.
Régle i : le système est globalement de degré de liberté i. Conséquence : tout voyeur de i+1 éléments (tous les éléments confondus, charnières ou non) de l'ensemble des ESC est éliminé car il provoque un système sous-complet (i-(i+1) = -1 < 0, pas assez de candidats pour remplir toutes les cases...).
Précision importante -- voir un élément Z non-charnière d'un ESC, c'est être en vue de toutes les occurences de Z dans cet ESC. -- voir un élément Y charnière entre deux ESC, c'est être en vue de toutes les occurences de Y dans ces deux ESC.
Exemples (théoriques car il faudra un peu de temps pour trouver des situations réelles, surtout pour les réseaux non linéaires) : d'une part A(d) désigne un ESC de degré de liberté d, et d'autre part les charnière Y sont écrites --Y--
Code: |
als classique : A(1) -- x -- B(1) | (somme des libertés) 2 - 1 (charnière) = 1 : la règle i=1 s'applique comme d'habitude.
Code: |
als double-charnière : A(1) -- xy -- B(1) | (somme des libertés) 2 - 2 (charnières) = 0 : la règle i=0 s'applique comme d'habitude.
Code: |
chaîne : A(1) -- w -- B(1) -- x -- C(1) -- y -- D(1) -- z -- E(1) | (somme des libertés) 5 - 4 (charnières) = 1 : la règle i=1 s'applique. A noter que l'on peut avoir w=y, et dans ce cas, tout voyeur de ces deux charnières est éliminé (même si ce voyeur est dans E par exemple !)
Code: |
Sue de Coq : A(1) -- wx -- B(2) -- yz -- C(1)
| (somme des libertés) 4 - 4 (charnières) = 0 : la règle i=0 s'applique.
Code: |
boucle : A(1) -- w -- B(1) -- x -- C(1) -- y -- D(1) -- z -- A(1) @ | (somme des libertés) 4 - 4 (charnières) = 0 : la règle i=0 s'applique.
des exemples linéaires :
Code: |
A(1) -- xy -- B(2) Règle i=1. |
Code: |
A(1) -- wx -- B(2) -- y -- C(1) -- z -- A(1) @ Règle 0 |
Code: |
A(1) -- wx -- B(2) -- y -- C(1) -- z -- D(1) Règle 1 |
Code: |
A(1) -- w -- B(2) -- y -- C(1) -- xz -- D(1) Règle 1 (et règle 0 sur dernier maillon) |
Code: |
A(1) -- x -- B(2) -- y -- C(1) -- z -- D(1) Règle 2 (et règle 1 sur dernier maillon) |
Code: |
A(1) -- x -- B(2) -- y -- C(2) -- z -- D(1) Règle 3 |
des exemples non linéraires (réseaux) :
Code: |
A(1) B(1) | | x z | | C(1) -- y -- D(2) Règle 1 (6-5 = 1) | | \ / u v \ E(1) /
|
Code: |
A(1) -- w -- B(2) | | x z | | C(1) -- y -- D(2) Règle 1 (7-6 = 1) | | \ / u v \ E(1) /
|
Code: |
A(1) -- w -- B(1) | | x z | | C(1) -- y -- D(2) Règle 0 (6-6 = 0) | | \ / u v \ E(1) /
|
Code: |
B(1) | z | C(2) -- vw -- D(2) -- xt -- A(2) Règle 2 (8-6 = 2) | u | E(1)
|
Code: |
B(1) | z | C(1) -- vw -- D(2) -- xt -- A(1) Règle 0 (6-6 = 0) | u | E(1)
|
Code: |
C(1) -- w -- D(3) -- t -- A(1) Règle 3 (6-3 = 3) | x | E(1)
|
Ca me rappelle un peu la théorie des graphes en maths : (sudoku) ESC, charnières,... et (graphes math) sommets, arêtes,...
Dernière édition par leon1789 le Mer 25/10/2006 23:02; édité 15 fois |
|
| |
|
| |
Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: ALS ESC EQC Ven Juil 03 2009, 17:49 | |
| | |
|
| |
Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: ALS ESC EQC Ven Juil 03 2009, 17:49 | |
| | |
|
| |
Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: ALS ESC EQC Ven Juil 03 2009, 17:49 | |
| | |
|
| |
Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: ALS ESC EQC Ven Juil 03 2009, 17:50 | |
| leon1789 Sudoka Expert
Inscrit le: 02 Aoû 2006 Messages: 495
| Posté le: Dim 01/10/2006 14:58 Sujet du message: |
|
|
didier90 a écrit: |
Code: |
*-----------------------------------------------------------------------------* | 1 8 B69 | 237 27 5 |D69 23 4 | |A236 5 A2346 | 9 F14 A23 |E16 7 8 | | 23 7 B49 | 48 6 18 | 159 23 159 | |-------------------------+-------------------------+-------------------------| | 4 39 356 | 23678 89 236789 | 5789 1 5679 | | 8 139 7 | 346 5 1369 | 2 49 69 | | 56 2 16 | 4678 14 16789 | 4789 459 3 | |-------------------------+-------------------------+-------------------------| | 25 14 8 | 267 3 267 | 1479 459 179 | | 9 6 123 | 5 27 4 | 137 8 17 | | 7 34 35 | 1 89 89 | 345 6 2 | *-----------------------------------------------------------------------------*
| on a A - 4 - B - 9 - D - 6 - E - 1 - F - 4 - A
| cette boucle d'ESC n'est pas "valide" car les charnières ratachées à A ne sont pas distinctes : F - 4 - A et A - 4 - B ! et puis, il y a aussi le problème du 9 qui n'est pas charnière entre B et D
Bon, on ne veut pas être venu pour rien alors imaginons quand même que la chaîne soit bonne... On compte : somme des degrés de liberté - nombre de charnières = 6 - 6 = 0. On applique donc la régle 0 : --> éliminer tout voisin d'un élément non-charnière 2, 3 ou 6 de A, même si celui-ci se situe dans un autre ESC ! (par exemple le 6 de B out) --> idem pour les autres éléments non-charnières de B, C, D, E, F... (sur cet exemple, il n'y en a pas) --> éliminer tout voyeur de la charnière 4 de A--B s'il n'appartient pas ni à A ni à B, et même si celui-ci se situe dans un autre ESC ! (par exemple le 4 de F out ) --> idem pour toutes les autres charnières 9 pour B--D, 6 pour D--E, 1 pour E--F, et 4 pour F--A... |
|
| |
|
| |
Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: ALS ESC EQC Ven Juil 03 2009, 17:50 | |
| | |
|
| |
Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: ALS ESC EQC Ven Juil 03 2009, 17:50 | |
| | |
|
| |
Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: ALS ESC EQC Ven Juil 03 2009, 17:51 | |
| leon1789 Sudoka Expert
Inscrit le: 02 Aoû 2006 Messages: 495
| Posté le: Dim 01/10/2006 21:05 Sujet du message: |
|
|
C'est quand même super intéressant ces chaînes d'ESC !!!!!!!!
didier90 a écrit: |
exemple 3
Code: |
*--------------------------------------------------------------------* | 1457 1457 2 | 6 35 9 | 1345 8 147 | | 159 158 6 | 7 358 4 | 2 135 19 | | 4579 3 5789 | 1 58 2 | 6 457 479 | |----------------------+----------------------+----------------------| | 6 2457 3579 | 589 1 37 |B489 247 2478 | | 8 1257 579 | 59 4 67 |B19 1267 3 | | 13479 147 379 | 89 2 367 |B1489 1467 5 | |----------------------+----------------------+----------------------| | 25 56 4 | 3 7 8 |B15 9 126 | | 237 678 1 | 4 9 5 |C38 23 268 | | 35 9 358 | 2 6 1 | 7 A345 A48 | *--------------------------------------------------------------------*
|
A h9 i9 (3458) C g8 (38 ) B g4 g5 g6 g7 (14589)
y charnière entre AB = 5 y1 charnière entre AC = 8 y2 charnière entre BC = 8
z commun a A et C on peut éliminer le 3 de h8 qui voie tous les 3 de A et C
|
Code: |
A(2) -- 5 -- B(1) -- 8 -- C(1) -- 8 -- A @ |
deux charnières égales dans C donc la règle générale ne s'applique pas...
Il se trouve que l'on peut effectivement éliminer le 3 en h8, mais ceci reste un cas "exceptionnel" à la règle générale. J'ai dû me faire une preuve perso (à la main ) du bien fondé de l'élimination. J'ai constaté que, malgré le défaut de la chaîne, celui-ci est compensé par le voyeur z de A et C précisément... Ce que je veux dire, c'est qu'on ne peut pas faire la même élimination avec un z commun a A et B (d'où le caractère d'exception de l'exemple proposé) :
B ne contient pas z --> B contient 8 et 5 --> A ne contient pas 5 et C ne contient pas 8 --> ??? (on ne peut pas continuer, et pour cause...) pas de conclusion, donc pas d'élimination.
Bref, l'élimination proposée me paraît très "spécifique", surtout à la vue de l'exemple qui suit :
didier90 a écrit: |
exemple 4
Code: |
*--------------------------------------------------------------------------------------* | 23579 24579 23457 |E239 8 23569 | 346 3467 1 | | 358 45 6 | 1 D35 7 | 9 2 48 | | 23789 1 2378 |E239 4 E2369 |F36 5 678 | |----------------------------+----------------------------+----------------------------| | 125679 25679 1257 | 2479 167 8 | 12456 B146 3 | | 1235689 2569 12358 | 2349 136 2349 | 7 B1468 24569 | | 4 2679 12378 | 5 1367 239 | 126 B168 269 | |----------------------------+----------------------------+----------------------------| | 1567 8 1457 | 347 2 345 |A1356 9 A567 | | 257 3 9 | 6 C57 1 | 8 C47 A2457 | | 12567 24567 12457 | 8 9 345 |A12356 1367 A2567 | *--------------------------------------------------------------------------------------*
|
A g7 g9 i7 i8 i9 (123567) ESC(2) B h4 h5 h6 (1468) C h6 e6 (547) D e2 (35) E d1 d3 f3 (2369) F g3
charnieres entres les membres de l'equipe y entre B C = 4 y1 entre CD = 5 y2 entre D E = 3 y3 entre E F = 6 charnieres entre A et les membres de l'equipe 7 entre A et C 3 entre A et E donc deux charnieres
z = 1 et 6 commun entre A et B on peut eliminer les candidats 1 et 6 de h9 qui voie tous les candidats de A et de B
| Un réseau : super !
Code: |
A(2) -- 7 -- C(1) -- 4 -- B(1) | | 3 5 | | E(1) -- 3 -- D(1) | 6 | F(1) | deux charnières égales dans E donc la règle générale ne s'applique pas...
z désigne un élément non charnière de B (1 ou 6 ou 8 ).
B ne contient pas z --> B contient 4 --> C ne contient pas 4 --> C contient 7 et 5 --> A ne contient pas 7 (*) et D ne contient pas 5 --> D contient 3 --> E ne contient pas 3 --> ??? (et oui, on ne peut pas continuer et pour cause...)
(*) A ne contient pas 7 (seulement) et peut très bien ne pas contenir z non plus ! Pas de conclusion, donc pas d'élimination !! Je Ne Suis Pas d'Accord Avec les Eliminations Proposées !! Je demande donc à voir une preuve, car pour moi, le raisonnement est faux.
Remarque : dans cette histoire, visiblement F ne sert à rien. |
|
| |
|
| |
Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: ALS ESC EQC Ven Juil 03 2009, 17:51 | |
| | |
|
| |
Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: ALS ESC EQC Ven Juil 03 2009, 17:51 | |
| | |
|
| |
Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: ALS ESC EQC Ven Juil 03 2009, 17:51 | |
| leon1789 Sudoka Expert
Inscrit le: 02 Aoû 2006 Messages: 495
| Posté le: Lun 02/10/2006 10:13 Sujet du message: |
|
|
didier90 a écrit: |
de quelle regle generale parle tu | ...de la règle i que j'ai énoncée au-dessus A la différence de la tienne, elle porte sur des voyeurs regardant n'importe quels ESC du système (dans la règle 1 le voyeur doit voir deux ESC quelconques, dans la règle 2 le voyeur doit voir trois ESC quelconques, etc.) Dans ta règle, le voyeur doit regarder l'esc A(x) absolument et un autre ESC quelconques.
Il y a des grosses différences dans les deux règles : * les charnières quelconques pour toi, charnières différentes pour un ESC fixé pour moi, ** les voyeurs quelconques pour moi, regardant l'esc A(x) pour toi. *** les ESC quelconques pour moi, de degré de liberté 1 sauf A(x) pour toi.
didier90 a écrit: |
soit A ESC(x) soit une équipe d'ESC (de 1 a N menbres) y charnière entre A et M un des membre de l'équipe z candidat commun entre A et M1 M1 étant un des membres de l'équipe (z diffèrent de y)
on peut éliminer tous candidats z qui voient tous les z de A et de M1
Remarque x est définie par le nombre de membres de l'équipe qui ont une charnière avec A (par exemple si 3 membres de l'équipe ont une charnière avec A on peut avoir A ESC(3))
| Le problème, c'est que ta règle m'a l'air fausse. Exemple :
Code: |
A(2) --1-- C --2-- B \ / 3 3 \ / D
| Imaginer une grille avec A (13 45) sur deux cases , B (2 5) sur une case , C (123 6) sur trois cases , D (3 7) sur une case chiffre 1 charnière de AC, chiffre 2 charnière de CB, chiffre 3 charnière de AD et DC ! chiffre 5 commun à A et B.
Les conditions de ta règle semblent remplies, mais on ne peut pas conclure l'élimination de tout candidat 5 voyeur des 5 de A et de B car la configuration A(34) B(2) C(136) D(7) est viable.
PS : dans ta règle, je n'ai pas bien compris le rôle de y. |
|
| |
|
| |
Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: ALS ESC EQC Ven Juil 03 2009, 17:52 | |
| | |
|
| |
Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: ALS ESC EQC Ven Juil 03 2009, 17:52 | |
| | |
|
| |
Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: ALS ESC EQC Ven Juil 03 2009, 17:52 | |
| | |
|
| |
Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: ALS ESC EQC Ven Juil 03 2009, 17:52 | |
| | |
|
| |
Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: ALS ESC EQC Ven Juil 03 2009, 17:53 | |
| | |
|
| |
Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: ALS ESC EQC Ven Juil 03 2009, 17:53 | |
| | |
|
| |
Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: ALS ESC EQC Ven Juil 03 2009, 17:53 | |
| | |
|
| |
Contenu sponsorisé
| Sujet: Re: ALS ESC EQC | |
| |
|
| |
| ALS ESC EQC | |
|