SUDOKU VARIANTE
Vous souhaitez réagir à ce message ? Créez un compte en quelques clics ou connectez-vous pour continuer.

SUDOKU VARIANTE


 
portailportail  AccueilAccueil  Grilles en lignesGrilles en lignes  Tournois du forumTournois du forum  Dernières imagesDernières images  RechercherRechercher  S'enregistrerS'enregistrer  ConnexionConnexion  
Le Deal du moment :
SSD interne Crucial BX500 2,5″ SATA – 500 ...
Voir le deal
29.99 €

 

 TECHNIQUE DES ENSEMBLES QUASI COMP

Aller en bas 
AuteurMessage
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

TECHNIQUE DES ENSEMBLES QUASI COMP Empty





Dernière édition par Admin le Sam Juin 27 2009, 19:53, édité 1 fois
MessageSujet: TECHNIQUE DES ENSEMBLES QUASI COMP   TECHNIQUE DES ENSEMBLES QUASI COMP EmptyMer Juin 24 2009, 11:37

PhB
Sudoka Expert
Sudoka Expert


Inscrit le: 14 Déc 2005
Messages: 369












MessagePosté le: Lun 01/05/2006 23:16    Sujet du message: TECHNIQUE DES ENSEMBLES QUASI COMPLETS Répondre en citant

Bonsoir a tous,





Dans autre section du forum, YA nous a présenté une grille très intéressante. A un certain point, on bloque avant de sortir l’artillerie lourde (coloriage, arbalete,etc). On peut aussi débloquer la situation grâce a une nouvelle technique dite des ensembles quasi-complets (ou almost locked sets). Je vous soumets d’abord la grille.





La grille initiale


Code:



    ABC DEF GHI


   *-----------*


 1 |2..|..7|...|


 2 |.31|...|...|


 3 |..9|...|.26|


   |---+---+---|


 4 |...|...|8.5|


 5 |...|9..|...|


 6 |18.|.52|.4.|


   |---+---+---|


 7 |3.4|2..|...|


 8 |...|.35|1.8|


 9 |..6|...|...|


   *-----------*







…A suivre
_________________
PhB
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

TECHNIQUE DES ENSEMBLES QUASI COMP Empty



MessageSujet: Re: TECHNIQUE DES ENSEMBLES QUASI COMP   TECHNIQUE DES ENSEMBLES QUASI COMP EmptyMer Juin 24 2009, 21:47

ya
Sudoka Débutant
Sudoka Débutant


Inscrit le: 26 Avr 2006
Messages: 10












MessagePosté le: Mar 02/05/2006 0:05    Sujet du message: Répondre en citant

Pour rendre à César ce qui est à César, je précise que la grille ci-dessus a


été réalisée par Koalog (http://sudoku.koalog.com) et publiée dans le quotidien parisien Le Monde paru le 24 avril 2006 (datè du 25).
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

TECHNIQUE DES ENSEMBLES QUASI COMP Empty



MessageSujet: Re: TECHNIQUE DES ENSEMBLES QUASI COMP   TECHNIQUE DES ENSEMBLES QUASI COMP EmptySam Juin 27 2009, 19:54

PhB
Sudoka Expert
Sudoka Expert


Inscrit le: 14 Déc 2005
Messages: 369












MessagePosté le: Mer 03/05/2006 8:00    Sujet du message: Répondre en citant

Merci de cette precision. C'est toujours mieux de connaitre l'origine des grilles.





Voici le debut de partie jusqu'au point dur





Les évidents/candidats uniques





1. E2=2, A9=8, C1=8, H2=8, D3=8, D8=4, C5=5, H8=6





Décrassage plus poussé








2. H1+I1=1 => -1 en D1,E1


3. Chariot (2), G5+H5/G9+H9 => -2 en B5,B9


4. B7+B9=5 => -5 en B1,B3


5. A4+B4=9 => -9 en H4


6. Triplet G7+H7+I7=5x7x9 => élimine 5,7,9 en M9 & ligne 7


7. Triplet B7+E7+F7=1x8x6, comme B6=8 et C9=6 => B7=1 et E7+F7=6x8


8. Triplet A8+B8+C8=2x7x9 => B9=5


9. Triplet G9+H9+I9=2x3x4, comme H3=2 et H6=4 => H9=3 et G9+I9=2x4


10. Triplet B1+B3+B5=4x6x7 => élimine 4,6,7 en colonne B d’où B4+B8=2x9


11. H4+H5=1x7 => élimine 7 en M6 et colonne H d’où I1=1


12. G1+G3=3 => -3 en G5,G6





Tableau des Raps





Code:



    A      B      C        D      E      F        G      H      I


  *--------------------------------------------------------------------*


1 | 2      46     8      | 356    469    7      | 3459   59     1      |


2 | 4567   3      1      | 56     2      469    | 4579   8      479    |


3 | 457    47     9      | 8      14     134    | 3457   2      6      |


  |----------------------+----------------------+----------------------|


4 | 4679   29     237    | 1367   1467   1346   | 8      17     5      |


5 | 467    467    5      | 9      14678  13468  | 26     17     23     |


6 | 1      8      37     | 367    5      2      | 69     4      39     |


  |----------------------+----------------------+----------------------|


7 | 3      1      4      | 2      68     68     | 579    59     79     |


8 | 79     29     27     | 4      3      5      | 1      6      8      |


9 | 8      5      6      | 17     179    19     | 24     3      24     |


  *--------------------------------------------------------------------*





_________________
PhB
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

TECHNIQUE DES ENSEMBLES QUASI COMP Empty



MessageSujet: Re: TECHNIQUE DES ENSEMBLES QUASI COMP   TECHNIQUE DES ENSEMBLES QUASI COMP EmptySam Juin 27 2009, 19:55

PhB
Sudoka Expert
Sudoka Expert


Inscrit le: 14 Déc 2005
Messages: 369












MessagePosté le: Mer 03/05/2006 8:45    Sujet du message: Répondre en citant

Ensembles quasi-complets





Référence Ensembles quasi-complets – almost locked sets.





Définitions


• On appelle « ensemble complet » un ensemble de cases contenant autant de candidats que de cases.


• On appelle « ensemble quasi-complet » un ensemble possédant un candidat en excès par rapport au nombre de cases et où chaque candidat, ne doit pouvoir occuper AU PLUS UNE SEULE CASE


• On appelle « charnière » de 2 ensembles quasi-complets un candidat C commun aux deux ensembles mais qui ne peut exister simultanément dans les deux.


Règle


Dans la grille, on repère 2 ensembles de cases (appelons-les A et B). Chaque ensemble possède un candidat de plus que de cases. Les 2 ensembles ont en commun un chiffre (la charnière) qui ne peut figurer que dans l’un ou l’autre ensemble.


Si on peut trouver une case K dont un candidat x permet d’éliminer x simultanément dans A ET dans B, alors on peut éliminer le candidat x de la case K.


Démonstration


1. Par définition d’un ensemble quasi-complet, le nombre de candidats de chaque ensemble est supérieur d’une unité au nombre de cases.


2. Par définition de la charnière, elle appartient à A ou à B mais pas aux 2.


3. Si K=x élimine simultanément x de A et de B et, compte tenu que la charnière doit figurer dans A ou dans B, alors il y aura nécessairement un des 2 ensembles qui aura 1 candidat de moins que de cases, ce qui est impossible dans une grille de Sudoku. L’hypothèse est donc fausse et on peut éliminer le candidat x de la case K.
_________________
PhB


Dernière édition par PhB le Lun 05/06/2006 1:05; édité 1 fois
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

TECHNIQUE DES ENSEMBLES QUASI COMP Empty



MessageSujet: Re: TECHNIQUE DES ENSEMBLES QUASI COMP   TECHNIQUE DES ENSEMBLES QUASI COMP EmptySam Juin 27 2009, 19:55

PhB
Sudoka Expert
Sudoka Expert


Inscrit le: 14 Déc 2005
Messages: 369












MessagePosté le: Mer 03/05/2006 9:06    Sujet du message: Répondre en citant

Attaque de la position





Code:



    A      B      C        D      E       F         G      H      I


  *----------------------------------------------------------------------*


1 | 2      46     8      | 356    469     7       | 3459   59     1      |


2 | 4567   3      1      | 56     2       469     | 4579   8      479    |


3 | 457    47     9      | 8      14      134     | 3457   2      6      |


  |----------------------+------------------------+----------------------|


4 | 4<6>79 29     +237   | +1367  +1467   +1346   | 8      17     5      |


5 | *467   *467   5      | 9      14<6>78 134<6>8 | 26     17     +23    |


6 | 1      8      37     | 367    5       2       | 69     4      39     |


  |----------------------+------------------------+----------------------|


7 | 3      1      4      | 2      68      68      | 579    59     79     |


8 | 79     29     27     | 4      3       5       | 1      6      8      |


9 | 8      5      6      | 17     179     19      | 24     3      24     |


  *----------------------------------------------------------------------*










Le premier ensemble A (cases étoilées, ligne 5) contient 3 candidats {4,6,7} répartis sur 2 cases.


Le second ensemble B (cases repérées par un « + », maisons M4,M5,M6) contient 6 candidats {1,2,3,4,6,7} répartis sur 5 cases.


La charnière est constituée par le chiffre 7. On vérifie que la charnière est présente dans A ou dans B mais pas dans les 2 :


• Départ A : Si A5=7 ou B5=7, alors C1<>7 (même maison) et E5,F5<>7 à cause de H4+H5=1x7 (vis-à-vis)


• Départ B : Si C4,D4,E4=7 alors H2=7, ce qui élimine 7 de A5 et de B5.





On vérifie que A4=6 élimine 6 simultanément de l’ensemble A (même maison) et de l’ensemble B (même ligne). De même pour E5 et F5.





Le reste est facile. A5+B6=6 => G5=2 et la grille est débloquée.





Correction: il s'agit d'une application incorrecte de l'EQC, chaque candidat devant occuper au plus une seule case. L'ensemble marque (+) devrait ne pas occuper 2 lignes pour respecter la contrainte
_________________
PhB


Dernière édition par PhB le Lun 05/06/2006 1:09; édité 1 fois
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

TECHNIQUE DES ENSEMBLES QUASI COMP Empty



MessageSujet: Re: TECHNIQUE DES ENSEMBLES QUASI COMP   TECHNIQUE DES ENSEMBLES QUASI COMP EmptySam Juin 27 2009, 19:55

guillain
Sudoka Initié
Sudoka Initié


Inscrit le: 14 Fév 2006
Messages: 25
Localisation: Fontainebleau












MessagePosté le: Mer 03/05/2006 12:13    Sujet du message: Répondre en citant

Bonjour,





C'est très intéressant mais pas facile à repérer.





Comment choisit-on les ensembles A et B ? Dans cette grille, le choix de A me semble évident puisque les deux cases sont dans la même maison (et accessoirement sur la même ligne).


Mais pour B, je ne trouve pas de logique autre que « 6 candidats {1,2,3,4,6,7} répartis sur 5 cases ». Elles sont dans trois maisons et deux lignes différentes.


On choisit les cases comme on veut du moment que les trois points de la démonstration sont respectés (et dans ce cas, G9 ou I9 auraient aussi bien convenu que I5) ?
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

TECHNIQUE DES ENSEMBLES QUASI COMP Empty



MessageSujet: Re: TECHNIQUE DES ENSEMBLES QUASI COMP   TECHNIQUE DES ENSEMBLES QUASI COMP EmptySam Juin 27 2009, 19:56

ya
Sudoka Débutant
Sudoka Débutant


Inscrit le: 26 Avr 2006
Messages: 10












MessagePosté le: Mer 03/05/2006 12:37    Sujet du message: Répondre en citant

Bravo PhB, vous êtes un expert. Je suis heureux de constater que cette grille a une solution "logique". Ce qui m'amène à poser à la cantonade la question suivante : Nous savons que toute grille sudoku "normale" (conforme à la norme) a une solution et une seule. Cette solution doit-elle être "logique", c'est-à-dire sans faire d'hypothèses ? Sinon, quelles sont les hypothèses admises ?
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

TECHNIQUE DES ENSEMBLES QUASI COMP Empty



MessageSujet: Re: TECHNIQUE DES ENSEMBLES QUASI COMP   TECHNIQUE DES ENSEMBLES QUASI COMP EmptySam Juin 27 2009, 19:56

gpenet
Sudoka Expert
Sudoka Expert


Inscrit le: 27 Mar 2006
Messages: 174
Localisation: PARIS et BRETAGNE












MessagePosté le: Jeu 04/05/2006 11:53    Sujet du message: Répondre en citant

Bonjour PhB,





Voila un concept intéresant en soi, mais qui devrait en plus, je pense, bien s'intégrer en coloriage dans la famille des "quasi duos" au sens large.





Je garde précieusement en tous cas.





Cordialement





G. PENET
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

TECHNIQUE DES ENSEMBLES QUASI COMP Empty



MessageSujet: Re: TECHNIQUE DES ENSEMBLES QUASI COMP   TECHNIQUE DES ENSEMBLES QUASI COMP EmptySam Juin 27 2009, 19:56

PhB
Sudoka Expert
Sudoka Expert


Inscrit le: 14 Déc 2005
Messages: 369












MessagePosté le: Jeu 04/05/2006 16:58    Sujet du message: Répondre en citant

Bonjour Guillain,





Tout d’abord, veuillez m’excuser de ne pas vous avoir répondu plus tôt (boulot oblige).





Vous avez raison, la repérage de telles configurations requiert de la patience et du doigté. C’est, a mon avis, aussi difficile que de repérer un quadruplet.





Le second point que vous évoquez m’a également posé problème. Inconsciemment, nous raisonnons dans les limites des unités (lignes, colonnes ou maisons), ce qui amène à ne considérer que des liaisons « fortes » sans tenir compte du fait que toute case du Sudoku est en liaison (directe ou indirecte) avec toutes les autres. Si vous reportez au texte original, il n’est spécifié nulle part que les 2 ensembles A et B doivent obéir à d’autres contraintes que celles de l’énoncé -contiguite, appartenance a un 2 unites contigues, etc. (Par contre, l’exemple fourni illustre le propos en considérant 2 ensembles appartenant chacun à une maison, preuve qu’il y a une certaine restriction mentale à sortir de ce cadre). Les contraintes des ensembles quasi-complets sont très fortes en elles-mêmes et se suffisent (a mon avis).





Dire qu’il s’agit d’une technique « opératoire » qu’on peut appliquer tous le jours est très exagéré. Cependant, comme l’a remarqué gpenet, cette technique pourrait apporter un point de vue nouveau sur les liaisons entre les cases. Je pense aussi qu’il peut y avoir des affinités avec le coloriage.
_________________
PhB
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

TECHNIQUE DES ENSEMBLES QUASI COMP Empty



MessageSujet: Re: TECHNIQUE DES ENSEMBLES QUASI COMP   TECHNIQUE DES ENSEMBLES QUASI COMP EmptySam Juin 27 2009, 19:57

PhB
Sudoka Expert
Sudoka Expert


Inscrit le: 14 Déc 2005
Messages: 369












MessagePosté le: Jeu 04/05/2006 17:29    Sujet du message: Répondre en citant

Bonjour ya,





Il y a eu (et il y a toujours) des débats passionnés au sujet des « hypothèses », du même type que ceux qui agitent les partisans des sciences « molles » et ceux des sciences « dures ». Au fond, cette question est un peu académique et peut nous entraîner très loin. Si l’on est plus pragmatique on peut simplement dire que la recherche de solutions « logiques » évite, en principe, d’avoir recours à la chance ou aux circonstances. Tous les mouvements que vous utilisez :


• soit font référence à des figures étudiées dont on connaît à l’avance les propriétés (chariots/x-wings, swordfishes, xy-z wings, rectangles interdits, cerfs-volants, etc)


• soit emploient des propriétés ne conduisant pas forcement a des figures identifiables mais qui aboutissent a des résultats prévisibles (chaînage, arbalète, coloriage, .. ou ensembles quasi-complets)


La distinction en soi n’est pas très importante. On peut dire que l’ensemble fait partie d’un univers « sans hypothèse ». Tout ce qui sort de ce cadre peut relever du domaine de l’hypothèse. C’est donc un choix personnel, une contrainte esthétique en quelque sorte. Vous vous l’imposez ou non.





Est-ce que toute grille de Sudoku est soluble uniquement par la logique ? Je n’en sais rien dans l’absolu. Tout ce que je peux dire c’est que certaines grilles sont au dessus de mes forces.





NB: je ne suis pas un expert, juste un amateur (au sens noble, bien sur)
_________________
PhB
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

TECHNIQUE DES ENSEMBLES QUASI COMP Empty



MessageSujet: Re: TECHNIQUE DES ENSEMBLES QUASI COMP   TECHNIQUE DES ENSEMBLES QUASI COMP EmptySam Juin 27 2009, 19:57

ya
Sudoka Débutant
Sudoka Débutant


Inscrit le: 26 Avr 2006
Messages: 10












MessagePosté le: Ven 05/05/2006 13:44    Sujet du message: Répondre en citant

Merci PhB, de vos réflexions sur la logique plus ou moins nécessaire des grilles. Je suis certain qu'on peut imaginer des grilles impossibles à résoudre par des moyens logiques. Mais les grilles publiées ? J'ai posé la question à mon quotidien fournisseur de grilles Le Monde, mais sans réponse jusqu'à présent.


J'ai des restrictions sérieuses à vous soumettre concernant la définition des Ensembles-Quasi-Complets (EQC).


- La charnière ET le candidat à élimination x doivent appartenir aux 2 EQC.


- La charnière et x sont DIFFERENTS.


Plus grave, que se passe t-il si un candidat peut occuper 2 ou plus cases d'un EQC ? Alors, le nombre de cases est égal ou inférieur au nombre de candidats. Exit l'impossibilité !


Donc, un EQC comporte un candidat de plus que de cases. CHAQUE CANDIDAT NE PEUT Y OCCUPER QU'UNE SEULE CASE.


Une façon de réaliser cela (mais est-ce la seule ?)est de n'occuper qu'une ligne, ou colonne, ou bloc.


Dans la grille ci-dessus, l'EQC A=(A5,B5) est correct : même bloc 4.


Mais l'EQC B=(C4,D4,E4,F4,I5) est à mon avis incorrect : les candidats 2 et 3 peuvent être en I5 et en ligne 4.


Par contre, si on choisit l'EQC B=(D4,E4,F4,H4) (candidats 1,3,4,6,7) toutes cases dans la ligne 4, c'est correct : A4=6 élimine 6 dans la ligne 4 et le bloc 4, est impossible. G5=2 et la grille est débloquée. Ouf!


L'erreur remonte, je pense, au site Solving Sudokus, chapître Subsets, qui fait la confusion entre sigma(nd), somme des maximums d'occurence du candidat d, et sigma(d) nombre de candidats, qui ne sont égaux que si chaque candidat ne peut occuper qu'une case. D'ailleurs, dans l'exemple donné sur ce site, chaque EQC occupe un bloc, et donc respecte cette condition. Comme quoi un exemple ne fait pas démonstration...


PS Je pensais vous communiquer ceci par mail privé, mais comment fait-on pour en envoyer sur ce forum ?











[/list]
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

TECHNIQUE DES ENSEMBLES QUASI COMP Empty



MessageSujet: Re: TECHNIQUE DES ENSEMBLES QUASI COMP   TECHNIQUE DES ENSEMBLES QUASI COMP EmptySam Juin 27 2009, 19:58

PhB
Sudoka Expert
Sudoka Expert


Inscrit le: 14 Déc 2005
Messages: 369












MessagePosté le: Sam 06/05/2006 0:18    Sujet du message: Répondre en citant

Bonsoir ya,





Pour l’option messagerie privée, vous avez un bouton « mp » en bas de chaque message. Cependant, je trouverais dommage de ne pas faire participer d’autres membres du forum, s’ils sont intéressés. En tous cas, merci pour vos remarques, que je vais commenter.





ya a écrit:



..


J'ai des restrictions sérieuses à vous soumettre concernant la définition des Ensembles-Quasi-Complets (EQC).


- La charnière ET le candidat à élimination x doivent appartenir aux 2 EQC.


- La charnière et x sont DIFFERENTS.


..







Je suis tout à fait d’accord avec vous.





ya a écrit:



..


Plus grave, que se passe t-il si un candidat peut occuper 2 ou plus cases d'un EQC ? Alors, le nombre de cases est égal ou inférieur au nombre de candidats. Exit l'impossibilité !


Donc, un EQC comporte un candidat de plus que de cases. CHAQUE CANDIDAT NE PEUT Y OCCUPER QU'UNE SEULE CASE.


..







Là, je ne suis plus de votre avis. La règle pousse le raisonnement au point ou l’élimination des candidats conduit à obtenir MOINS de candidats que de cases. Il n’est pas dit qu’un candidat doive absolument occuper l’une des cases : ce candidat peut être éliminé par exemple (ou si vous préférez, un candidat peut occuper zéro case). Dans l’exemple, l’ensemble B ne contient qu’une fois le chiffre 2 en C4. Il y a aussi un candidat 2 en B4 qui est en dehors de l’ensemble B. On ne peut pas pour autant en conclure que C4=2.





La contrainte « CHAQUE CANDIDAT NE PEUT Y OCCUPER QU'UNE SEULE CASE » n’est pas forcément vraie et les restrictions supplémentaires que vous imposez doivent être levées.





La variante vous produisez manque à la contrainte de la charnière : elle doit être dans l’un ou l’autre ensemble mais pas dans les deux. Elle n’est pas vérifiée en H4=7 (si la charnière vaut 7, bien entendu). Ceci prouve que les contraintes initiales sont très fortes, en définitive.
_________________
PhB
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

TECHNIQUE DES ENSEMBLES QUASI COMP Empty



MessageSujet: Re: TECHNIQUE DES ENSEMBLES QUASI COMP   TECHNIQUE DES ENSEMBLES QUASI COMP EmptySam Juin 27 2009, 19:58

gpenet
Sudoka Expert
Sudoka Expert


Inscrit le: 27 Mar 2006
Messages: 174
Localisation: PARIS et BRETAGNE












MessagePosté le: Sam 06/05/2006 10:48    Sujet du message: Répondre en citant

Bonjour PhB,





Il me semble avoir maintenant une bonne idée du lien entre votre technique et le coloriage.





Pour respecter la volonté de papyg, je vous présenterai dans la journée un exemple (théorique) sur l'autre forum.





Cordialement





G. PENET
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

TECHNIQUE DES ENSEMBLES QUASI COMP Empty



MessageSujet: Re: TECHNIQUE DES ENSEMBLES QUASI COMP   TECHNIQUE DES ENSEMBLES QUASI COMP EmptySam Juin 27 2009, 19:58

PhB
Sudoka Expert
Sudoka Expert


Inscrit le: 14 Déc 2005
Messages: 369












MessagePosté le: Lun 08/05/2006 0:38    Sujet du message: Répondre en citant

Bonsoir,





Voici une autre application des ensembles quasi-complets dans le fil "une technique pour les quadruplets."
_________________
PhB
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

TECHNIQUE DES ENSEMBLES QUASI COMP Empty



MessageSujet: Re: TECHNIQUE DES ENSEMBLES QUASI COMP   TECHNIQUE DES ENSEMBLES QUASI COMP EmptySam Juin 27 2009, 19:59

gb
Sudoka Expert
Sudoka Expert


Inscrit le: 07 Mai 2006
Messages: 83












MessagePosté le: Mar 09/05/2006 19:12    Sujet du message: Répondre en citant

Bonjour, j'ai une réponse à la question de ya


Citation:
Ce qui m'amène à poser à la cantonade la question suivante : Nous savons que toute grille sudoku "normale" (conforme à la norme) a une solution et une seule. Cette solution doit-elle être "logique", c'est-à-dire sans faire d'hypothèses





La réponse est : toute grille, unisolu ou pas, peut être étudiée entièrement par la logique et sans faire la moindre hypothèse.





La démonstration (forcément assez abstraite!) de cette affirmation sort peut-être du cadre de ce forum... mais l'idée centrale est : il existe un procédé de rédaction universel qui ne sera jamais pris en défaut et qui :


#prouve qu'il n'y a pas de solu quand c'est le cas


#prouve qu'il y a solu unique quand c'est le cas


#trouve toutes les solus quand la grille est multi solu.





Alignements, paires, n-uplets, chaines, ensembles quasicomplets, mono/multi/coloriages ou toute autre technique passée, présente ou à venir, peuvent tous se ramener à ce modèle unique.


A défaut de démonstration, je peux m'engager à mettre sous ladite forme la preuve d'unicité de toute grille que vous voudrez bien me soumettre. J'ai déjà semé quelques exemples deci delà dans les messages de ces derniers jours.





Cordialement, gb





ps : évidemment, j'exclus le rectangle interdit sous toutes ses formes qui ne peut s'appliquer dans le cas d'une grille sans ou multisolu, et qui ne peut bien sûr DEMONTRER l'unicité d'une solution... puisqu'il l'admet !





pps : ya, j'ai posté un exemple dans ce fil que tu as démarré dans la rubrique "autour de la grille".
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

TECHNIQUE DES ENSEMBLES QUASI COMP Empty



MessageSujet: Re: TECHNIQUE DES ENSEMBLES QUASI COMP   TECHNIQUE DES ENSEMBLES QUASI COMP EmptySam Juin 27 2009, 19:59

ya
Sudoka Débutant
Sudoka Débutant


Inscrit le: 26 Avr 2006
Messages: 10












MessagePosté le: Mar 23/05/2006 21:15    Sujet du message: Répondre en citant

PhB a écrit :


La contrainte « CHAQUE CANDIDAT NE PEUT Y OCCUPER QU'UNE SEULE CASE » n’est pas forcément vraie et les restrictions supplémentaires que vous imposez doivent être levées.





Désolé PhB de vous contredire : je maintiens ma position sur les EQC, en la nuançant légèrement :


Dans un EQC, chaque candidat, sauf la charnière et le candidat x à supprimer, ne doit pouvoir y occuper QU'UNE SEULE CASE.


Celà résulte de la démonstration : chaque EQC comporte N cases, N+1 candidats. L'union de 2 EQC enlève à l'un d'eux 2 candidats : la charnière et le candidat x. Si chaque candidat restant ne peut y occuper qu'une seule case, il y aura N-1 cases occupées pour N cases, et donc impossibilité. Sinon, TOUTES LES CASES POURRONT ETRE REMPLIES, et aucune conclusion ne pourra être tirée.


Pour vous convaincre, voici un contre-exemple (parmi bien d'autres, faciles à fabriquer) où l'application de vos critères conduit à une erreur.


Soit la grille que j'ai soumise au forum, et sa solution :





2xx|xx7|xxx solution 268|547|391


x31 xxx xxx --------- 531|629|784


xx9|xxx|x26 --------- 479|813|526


----------------------------------------


xxx|xxx|8x5 --------- 923|164|875


xxx|9xx|xxx --------- 645|978|213


18x|x52|x4x --------- 187|352|649


----------------------------------------


3x4|2xx|xxx --------- 314|286|957


xxx|x35|1x8 --------- 792|435|168


xx6|xxx|xxx --------- 856|791|432





Au point "dur" (votre message du 3 mai 2006 7.00 pm)


C4=237 D4=1367 F4=1346 A6=B7=1 C7=D8=4.





Prenons pour EQC 1 : D4=1367 A6=1 B7=1 : 3 cases, 4 candidats 1,3,6,7


pour EQC 2 : F4=1346 C7=4 D8=4 : 3 cases, 4 candidats 1,3,4,6


Charnière 6, hypothèse à éliminer C4=3.


Tous vos critères sont remplis : N cases, N+1 candidats, la charnière 6 et le candidat à élimination appartiennent aux 2 EQC et sont différents. La charnière 6 appartient à l'un ou l'autre des EQC, l'hypothèse C4=3 élimine 3 des 2 EQC. Donc selon vos critères C4=3 est impossible. Voyez la solution !


L'erreur provient de ce que le candidat 1 peut occuper (et occupe) 3 cases dans l'EQC 1, et le candidat 4 3 cases dans l'EQC 2.
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

TECHNIQUE DES ENSEMBLES QUASI COMP Empty



MessageSujet: Re: TECHNIQUE DES ENSEMBLES QUASI COMP   TECHNIQUE DES ENSEMBLES QUASI COMP EmptySam Juin 27 2009, 20:00

PhB
Sudoka Expert
Sudoka Expert


Inscrit le: 14 Déc 2005
Messages: 369












MessagePosté le: Mar 23/05/2006 22:53    Sujet du message: Répondre en citant

Bonsoir, ya





Ne soyez pas desole ... surtout quand vous avez raison ! Votre demonstration par l'absurde m'a convaincu.





Le fait d'avoir les elements d'un EQC distribues sur plusieurs unites (lignes, colonnes ou maisons) autorise leur repetition, ce qui va a l'encontre du but recherche. Donc, en pratique, il pourrait y avoir plusieurs cas de figure:


- si l'EQC est dans une seule unite, pas de probleme mais les contraintes etant deja tellement fortes, le phenomene doit etre rare


- si l'EQC est dans plusieurs unites, il faut etre sur qu'il n'y a pas repetition des candidats (cas de figure encore plus rarissime a mon avis)





Je reviens sur votre formulation:





ya a écrit:
...


Désolé PhB de vous contredire : je maintiens ma position sur les EQC, en la nuançant légèrement :


Dans un EQC, chaque candidat, sauf la charnière et le candidat x à supprimer, ne doit pouvoir y occuper QU'UNE SEULE CASE.


....





En vue de corriger l'article precite, je dirais "Dans un EQC, chaque candidat, ne doit pouvoir occuper AU PLUS UNE SEULE CASE", sachant que la charniere et un candidat surnumeraire peuvent occuper 0 ou 1 case.





Qu'en pensez-vous ?





PS: je suis un peu decu. Cet EQC avait une bonne tete pourtant. Maintenant, il me semble encore plus inaccessible que l'huitre perliere de Loumtom... A moins que vous me demontriez le contraire ?





Un coup de chapeau a ya et aussi a Guillain qui avait subodore un loup

_________________
PhB
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

TECHNIQUE DES ENSEMBLES QUASI COMP Empty



MessageSujet: Re: TECHNIQUE DES ENSEMBLES QUASI COMP   TECHNIQUE DES ENSEMBLES QUASI COMP EmptySam Juin 27 2009, 20:00

gb
Sudoka Expert
Sudoka Expert


Inscrit le: 07 Mai 2006
Messages: 83












MessagePosté le: Mar 23/05/2006 23:18    Sujet du message: Répondre en citant

Bonjour !


Ma proposition est de remplacer la notion d'


#"ensemble quasicomplet" : groupe de n candidats dont n-1 sont justes,


par la notion plus faible de


#"lien": groupe de candidats dont au moins un est juste.


C'est une notion plus faible, ce qui permet de l'utiliser avec beaucoup moins de précautions sur les conditions d'applications que la notion d'eqc.





A titre documentaire, voici une démarche pour résoudre la grille de ya. Je vais rédiger les étapes non triviales en termes de déplacement de liens.





1) choix uniques jusqu'à 31 cases remplies.


2) Eliminer {b5=2, h4=9, i9=9, i9=3, i9=7, g9=9, g9=3, g9=5, g9=7} (alignements bc4=2, gi6=9, paires gi9=24). Puis choix uniques (h9=3%B, b9=5%L, b7=1%B) jusqu'à 34 cases remplies.


3) Eliminer {h1=1, i5=1, i6=7, g6=7, i5=7, g5=7, h7=7} (paire h45=17). Puis choix unique i1=1%B, 35 cases remplies.


4) Eliminer {d6=6} (partir de {a5b5=467). Puis choix uniques jusqu'à 43 cases remplies.


5) Eliminer {f2=6} (partir de be1=4). Puis choix uniques jusqu'à 81 cases remplies.





Détail de l'étape 4 :


Code:
         a      b      c        d      e      f        g      h      i


ligne 4| .      .      .      | .      .      .      | 8      17     5      |


ligne 5| 467    467    5      | 9      .      .      | 236    17     23     |


ligne 6| 1      8      37     | 367    5      2      | 369    4      39     |
Un des candidats a5=4,6,7 est juste. Mais a5=4 donne b5=67%c.


Donc un des candidats a5=6,a5=7,b5=6,b5=7 est juste. Mais a5 ou b5=6 donne g6=6%B, et a5 ou b5=7 donne d6=7%L.


Donc un des candidats g6=6, d6=7 est juste et élimine d6=6.





Détail de l'étape 5 :


Code:
         a      b      c        d      e      f        g      h      i


ligne 1| 2      46     8      | 356    469    7      | 359    59     1      |


ligne 2| .      3      1      | 56     2      69     | .      8      4      |


ligne 3| .      .      9      | 8      14     134    | .      2      6      |
Un des candidats b1=4,e1=4 est juste. Mais b1=4 donne d1 ou e1=6%L, et e1=4 donne f2=9%B.


Donc un des candidats d1=6,e1=6,f2=9 est juste et élimine f2=6.





Normalement, je n'ai pas besoin d'ajouter d'autres explications à cette méthode de déplacement des liens (quand un lien n'élimine rien, on le déplace à un endroit où il élimine quelque chose). Mais si besoin, je reste à disposition pour des explications complémentaires.





Cordialement, gb





annexe : la notation %L,C,B,c signifie : seul choix restant dans la Ligne, Colonne, Boite, case considérée.
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

TECHNIQUE DES ENSEMBLES QUASI COMP Empty



MessageSujet: Re: TECHNIQUE DES ENSEMBLES QUASI COMP   TECHNIQUE DES ENSEMBLES QUASI COMP EmptySam Juin 27 2009, 20:01

ya
Sudoka Débutant
Sudoka Débutant


Inscrit le: 26 Avr 2006
Messages: 10












MessagePosté le: Mer 24/05/2006 10:46    Sujet du message: Répondre en citant

Bonjour PhB.


OK pour votre formulation : Dans un EQC, chaque candidat DOIT OCCUPER AU PLUS UNE CASE.


Ma démonstration permet de ne pas appliquer cette contrainte à la charnière et au candidat surnuméraire. Je ne sais pas si le cas peut se produire.


Je pense que ce bug doit être signalé au site "Solving Sudoku", qui a publié un exemple d'EQC où cette contrainte est réalisée, mais sans le dire.


Effectivement, cette contrainte rend son application assez rare.


PS Je suis toujours aussi novice. Comment fait-on sur ce forum pour citer un correspondant ("PhB a écrit"). Comment fait-on pour aligner une grille ? Y a t-il quelque part une doc à ce sujet ? Merci.
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


Nombre de messages : 3594
Age : 59
Localisation : pas bien loin ...
Date d'inscription : 15/01/2009

TECHNIQUE DES ENSEMBLES QUASI COMP Empty



MessageSujet: Re: TECHNIQUE DES ENSEMBLES QUASI COMP   TECHNIQUE DES ENSEMBLES QUASI COMP EmptySam Juin 27 2009, 20:01

gpenet
Sudoka Expert
Sudoka Expert


Inscrit le: 27 Mar 2006
Messages: 174
Localisation: PARIS et BRETAGNE












MessagePosté le: Mer 24/05/2006 11:21    Sujet du message: Répondre en citant

Bonjour,





Je suis pour le moment d'assez loin ces débats, mais je ne suis pas d'accord sur la rareté du phénomène. On y reviendra le moment venu.





Si les deux EQC sont en bout de chaînes de coloriage, dont éloignés l'un de l'autre, le phénomène n'a aucune raison d'être exceptionnel.





Cordialement





G. PENET
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Contenu sponsorisé





TECHNIQUE DES ENSEMBLES QUASI COMP Empty
MessageSujet: Re: TECHNIQUE DES ENSEMBLES QUASI COMP   TECHNIQUE DES ENSEMBLES QUASI COMP Empty

Revenir en haut Aller en bas
 
TECHNIQUE DES ENSEMBLES QUASI COMP
Revenir en haut 
Page 1 sur 1
 Sujets similaires
-
» Technique XYZ-wing
» Technique ALS / EQC / ESC
» Une technique pour les quadruplets?
» Technique : Chaînes de jumeaux/voisins
» Technique XY-wing

Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
SUDOKU VARIANTE :: Historique de Sudoku Factory :: Tactiques-
Sauter vers: