|
| Technique ALS / EQC / ESC | |
| | Auteur | Message |
---|
Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Technique ALS / EQC / ESC Ven Juil 03 2009, 11:41 | |
| leon1789 Sudoka Expert
Inscrit le: 02 Aoû 2006 Messages: 495
| Posté le: Mer 25/10/2006 22:42 Sujet du message: Technique ALS / EQC / ESC |
|
|
Fruit de discussions intenses avec Didier et dxp... sans oublier ceux qui, un jour ou l'autre, m'ont posé des questions et par la même occasion m'ont fait avancer dans cette réflexion.
0. Objectifs
1. Définitions zone, ensemble sur-complet, degré de liberté, charnière, degré de contrainte, voyeur, réseau.
2. La règle i
3. La règle i face aux techniques classiques
3.a) Techniques classiques 100% ESC ensemble complet, als classique, als avec double-charnière, Sue de Coq, chaîne d'ESC, boucle d'ESC
3.b) Techniques classiques avec ou sans ESC alignement, x-wing, wxyz-wing, multivalue x-wing, finned swordfish, chaînes mixtes (et dérivées), Death Blossom
4. Traduire un raisonnement en réseau d'ESC.
5. Règle i par l'exemple (jolis coups)
6. La règle i +
7. Le règle i+ par l'exemple
0. Objectifs
Quels sont mes objectifs ? Ils sont multiples, plus ou moins précis, et presque contradictoires. En gros, c'est comprendre une technique -- dont la théorie est la plus simple possible (une seule règle...après quelques définitions...) -- qui soit la plus efficace possible (obtenir une ou plusieurs éliminations de candidats avec relativement "peu" d'informations) -- qui ne soit pas ultra-difficile à mettre en oeuvre (sur des grilles non extrêmes tout au moins...) -- qui donne lieu à une rédaction assez facile (et une lecture relativement rapide) d'une solution
La simplicité et l'efficacité sont malheureusement antinomiques, comme très souvent... Résultat, à qui est destinée cette page ? Assurément aux lecteurs avertis, malheureusement encore une fois...
|
|
| |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique ALS / EQC / ESC Ven Juil 03 2009, 11:41 | |
| 1. Définitions (je reprends les définitions rappelées par Didier dans http://www.sudoku-factory.com/forumsudoku/viewtopic.php?t=421) 0) Au sudoku, une zone est une ligne, une colonne ou une maison. Remarque : dans un carré latin (un jeu plus "simple" que le sudoku), une zone est une ligne ou une colonne. Au sudoku X, une zone est une ligne, une colonne, une maison ou une des deux grandes diagonales. 1) Un Ensemble Sur Complet est un ensemble de cases qui appartiennent à une même zone. Le degré de liberté (ou la liberté tout court...) d'un ESC est la différence X entre le nombre de candidats dans cet ESC et son nombre de cases. Remarque : si la différence est nulle, c'est-à-dire nombre de cases = nombre de candidats, alors il est usuel d'appeler ceci un ensemble complet. notation : esc(X), et en implicite si X = 1 alors on ignore le X et on note esc. Dans la pratique, mis à part les ensembles complets bien sûr, on utilise le plus souvent des ESC de degré de liberté 1, voire 2, assez rarement 3, et quasiment jamais davantage. exemples ( http://www.sudoku-factory.com/forumsudoku/viewtopic.php?p=3915#3915 ) Code: | a b c | d e f | g h i | |----------------------|----------------------|----------------------| 1 | 24689 267 3 | 579 24579 2459 | 479 1 4678 | 2 | 469 67 5 | 8 3479 1 | 3479 2 3467 | 3 | 12489 127 79 | 379 23479 6 | 5 479 3478 | |----------------------|----------------------|----------------------| 4 |C.15 C.15 8 | 4 A.2579 259 | 6 3 157 | 5 | 7 356 4 | 356 1 35 | 2 8 9 | 6 | 1356 9 2 | 3567 3567 8 | 47 457 1457 | |----------------------|----------------------|----------------------| 7 | 3569 3567 1 | 2 8 3459 | 3479 45679 34567 | 8 | 23569 4 B.69 | 1 3569 7 | 8 569 2356 | 9 | 23569 8 B.679 | 3569 34569 3459 | 1 45679 234567 | |----------------------|----------------------|----------------------|
|
l'esc A est de liberté 3 l'esc B est de degré de liberté 1 l'esc C est de liberté 0 (il est donc complet) 2) Une charnière est un candidat commun à plusieurs ESC qui ne peut pas appartenir réellement à tous les ESC à la fois. (Parfois, au final, ce candidat commun n'appartient à aucun des ESC...) Le degré de contrainte (ou la contrainte tout court...) d'une charnière est la différence Y entre le nombre d'ESC qu'elle relie et le nombre maximum de ces ESC dans lesquels elle peut exister simultanément. Dans la pratique, on considére uniquement des charnières de degré de contrainte maximum (N-1 si elle relie N ESC), c'est-à-dire une charnière qui ne peut appartenir qu'à un seul des ESC qu'elle relie. notation : charn[Y], en implicite si Y = 1 alors on ignore le Y et on note charn. exemples Code: | a b c | d e f | g h i | |----------------------|----------------------|----------------------| 1 | 24689 267 3 | 579 24579 E.2459 | 479 1 4678 | 2 | 469 67 5 | 8 3479 1 | 3479 2 3467 | 3 | 12489 127 79 | 379 23479 6 | 5 479 3478 | |----------------------|----------------------|----------------------| 4 |C.15 C.15 8 | 4 A.2579 E.259 | 6 3 D.157 | 5 | 7 356 4 | 356 1 35 | 2 8 9 | 6 | 1356 9 2 | 3567 3567 8 | 47 457 1457 | |----------------------|----------------------|----------------------| 7 | 3569 3567 1 | 2 8 3459 | 3479 45679 34567 | 8 | 23569 4 B.69 | 1 3569 7 | 8 569 2356 | 9 | 23569 8 B.679 | 3569 34569 3459 | 1 45679 234567 | |----------------------|----------------------|----------------------|
|
5 est charnière entre A et C et son degré de contrainte est 1 (le 5 ne peut être réellement que dans 1 seul de ces 2 esc) 1 est charnière entre A et D et son degré de contrainte est 1 5 est charnière entre A, C et D et son degré de contrainte est 2 (le 5 ne peut être réellement que dans 1 seul de ces 3 esc) 5 est charnière entre A, C et E et son degré de contrainte est 1 (le 5 n'est être que dans au maximum 2 de ces 3 esc à la fois, en l'occurence C et E) 3) Un voyeur d'un ESC est un candidat z d'une case C tel que : -- la case C n'appartient pas à l'ESC ; -- le chiffre z fait partie des candidats de l'ESC ; -- la case C et toutes les cases de l'ESC contenant le candidat z sont dans une zone commune. ( Attention, cette zone ne contient pas nécessairement l'ESC en entier, mais seulement ses cases où le chiffre z est candidat...). On dit aussi que le candidat z de C voit les candidats z de l'ESC (z de C est un voyeur de l'ESC). En langage "logique", on peut dire : C=z implique ESC#z, ou encore, si z est C alors obligatoirement z n'est plus candidat de l'ESC. En clair, familièrement parlant, z en C passe l'envie à l'ESC de contenir z... Exemples : Code: | a b c | d e f | g h i | |----------------------|----------------------|----------------------| 1 | 24689 267 3 | 579 24579 E.2459 | 479 1 4678 | 2 | 469 67 5 | 8 3479 1 | 3479 2 3467 | 3 | 12489 127 79 | 379 23479 6 | 5 479 3478 | |----------------------|----------------------|----------------------| 4 |C.15 C.15 8 | 4 A.2579 E.259 | 6 3 D.157 | 5 | 7 356 4 | 356 1 35 | 2 8 9 | 6 | 1356 9 2 | 3567 3567 8 | 47 457 1457 | |----------------------|----------------------|----------------------| 7 | 3569 3567 1 | 2 8 3459 | 3479 45679 34567 | 8 | 23569 4 B.69 | 1 3569 7 | 8 569 2356 | 9 | 23569 8 B.679 | 3569 34569 3459 | 1 45679 234567 | |----------------------|----------------------|----------------------|
|
Sans vouloir être exhaustif !!! -- le 5 de a6 est un voyeur des 5 de l'esc C. De même pour le 5 de b5. -- le 2 en e2 voit le(s) 4 de l'esc E. -- mais le 9 de d9 n'est pas un voyeur des 9 de l'esc B... car 9 est candidat dans la case c8, qui n'est pas en vue de la case d9. 4) Un réseau d'ESC est un ensemble d'ESC liés par des charnières de manière quelconque. exemple Code: | a b c | d e f | g h i | |----------------------|----------------------|----------------------| 1 | 24689 267 3 | 579 24579 E.2459 | 479 1 4678 | 2 | 469 67 5 | 8 3479 1 | 3479 2 3467 | 3 | 12489 127 79 | 379 23479 6 | 5 479 3478 | |----------------------|----------------------|----------------------| 4 |C.15 C.15 8 | 4 A.2579 E.259 | 6 3 D.157 | 5 | 7 356 4 | 356 1 35 | 2 8 9 | 6 | 1356 9 2 | 3567 3567 8 | 47 457 1457 | |----------------------|----------------------|----------------------| 7 | 3569 3567 1 | 2 8 3459 | 3479 45679 34567 | 8 | 23569 4 B.69 | 1 3569 7 | 8 569 2356 | 9 | 23569 8 B.679 | 3569 34569 3459 | 1 45679 234567 | |----------------------|----------------------|----------------------|
|
Code: | C(0)--5[2]--A | / 1 / |/ D(2) |
Ce réseau schématisé signifie exactement (ni plus, ni moins) : -- C est un ensemble complet, -- A est un esc de degré de liberté un, -- D est un esc de degré de liberté deux, -- le chiffre 1 est charnière entre C et D, -- le chiffre 5 est charnière de degré de contrainte deux entre A, C et D. | |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique ALS / EQC / ESC Ven Juil 03 2009, 11:50 | |
| 2. La règle i (je reprends la règle i énoncée dans http://www.sudoku-factory.com/forumsudoku/viewtopic.php?p=3640#3640 ) La donnée : un réseau 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é de chaque ESC du réseau, puis on retranche la somme des degrés de contrainte de chaque charnière du réseau 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 candidat Z voyeur de i+1 éléments (tous les éléments confondus, charnières ou non) de l'ensemble des ESC est éliminé : en effet, si ce candidat Z était correct, il provoquerait un système sous-complet (car i-(i+1) = -1 < 0, pas assez de candidats pour remplir toutes les cases...), ce qui est évidemment interdit au sudoku ! Précision importante -- voir un élément Z propre (i.e. pas 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 plusieurs ESC, c'est être en vue de toutes les occurences de Y dans tous les ESC liés par cette charnière Y. 3. La règle i face aux techniques classiques 3.a) Techniques classiques 100% ESC ensemble complet somme des libertés - somme des contraintes = 0 - 0 = 0 : la règle i=0 s'applique comme d'habitude. En clair, on élimine tout candidat voyant l'un des éléments de l'esc A. als classique somme des libertés - somme des contraintes = 2 - 1 = 1 : la règle i=1 s'applique comme d'habitude : on élimine tout candidat voyant simultanément un élément de l'esc A et un de l'esc B. als avec double-charnière somme des libertés - somme des contraintes = 2 - 2 = 0 : la règle i=0 s'applique comme d'habitude. Sue de Coq Le Sue de Coq est un cas particulier de ceci : Code: | A -- wx -- B(2) -- yz -- C |
somme des libertés - somme des contraintes = 4 - 4 = 0 : la règle i=0 s'applique. chaîne d'ESC Code: | A -- w -- B -- x -- C -- y -- D -- z -- E |
somme des libertés - somme des contraintes = 5 - 4 = 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 !) boucle d'ESC Code: | A --w-- B | | z x | | D --y-- C |
somme des libertés - somme des contraintes = 4 - 4 = 0 : la règle i=0 s'applique. 3.b) Techniques classiques avec ou sans ESC Ici, je vais montrer (par des exemples) comment la règle i peut "retrouver de manière automatique" les résultats des techniques classiques (plus ou moins évoluées) . Bien sûr, pas question de comparer la règle i et les méthodes du type Rectangle Interdit et B.U.G. puisque ces dernières utilisent un méta-principe du jeu (l'existence d'une solution et son unicité) Par ailleurs, je ne parlerai pas non plus de multicoloriage (bien que ce soit une technique très puissante, donc importante !) parce que, d'une part je ne m'y connais pas assez pour être objectif, et d'autre part je trouve que le multicoloriage ne joue pas dans la même catégorie : la rédaction d'une solution en multicolriage ressemble trop à une démonstration au long cours... ce qui va à l'encontre de mon objectif "rédaction facile et une lecture rapide" Pour exactement les deux mêmes raisons, je ne parlerai pas non plus du système "ensembles forts / contrainte" développé par gb (si j'ai bien compris dxp). alignement Citation: | http://www.sudoku-factory.com/forumsudoku/viewtopic.php?t=459
Code: |
a b c d e f g h i -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 1 ! 8 125 A.256! 3 126 7 ! 4 129 29 ! 2 ! 3 9 A.26 ! 45 126 45 ! 28 128 7 ! 3 ! 124 124 7 ! 8 9 12 ! 3 5 6 ! -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 4 ! 124 1245 B.1258! 269 128 12689 ! 7 2389 2359 ! 5 ! 9 3 B.1258! 7 4 128 ! 6 28 25 ! 6 ! 6 7 A.28 ! 29 5 3 ! 289 4 1 ! -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 7 ! 257 6 3 ! 1 28 2589 ! 29 279 4 ! 8 ! 127 12 9 ! 246 3 246 ! 5 267 8 ! 9 ! 25 8 4 ! 2569 7 2569 ! 1 2369 239 ! -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
| Les 1 en colonne c sont tous en maison 4. On peut donc éliminer tous les autres 1 de la maison 4 : a4#1 et b4#1
|
Traduction en ESC : esc A : cases a1(256) a2(26) c6(28 ) toutes les cases (non remplies) de la colonne c sauf c4 et c5 esc B : cases c4(1258 ) c5(1258 ) de liberté 2 somme des libertés - somme des contraintes = 3-3 = 0 Donc on applique la règle i=0. Sont éliminés tous les candidats voyant un (0+1) élément du réseau. En particulier a4#1 et b4#1 car ils voient le 1 de B. | |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique ALS / EQC / ESC Ven Juil 03 2009, 11:51 | |
| x-wing Citation: | http://www.sudoku-factory.com/forumsudoku/viewtopic.php?t=166
Code: |
a b c d e f g h i +----------------+----------------+----------------+ |B.17 4 3 | 9 8 B.67* | 2 5 A.167* | <--- ligne 1 | 6 789 1789 | 4 2 5 | 138 38 178 | | 2 578 578 | 37 36 1 | 68 9 4 | +----------------+----------------+----------------+ | 9 568 2568 | 13 135 4 | 1568 7 1268 | | 3 57 257 | 6 157 8 | 49 24 129 | | 4 1 5678 | 2 57 9 | 568 68 3 | +----------------+----------------+----------------+ | 8 2 17 | 5 16 367 | 49 346 69 | | 17 69 69 | 17 4 23 | 38 238 5 | | 5 3 4 | 8 9 D.26* | 7 1 C.26* | <--- ligne 9 +----------------+----------------+----------------+
| En ligne 1, le chiffre 6 ne peut être qu'en colonne f ou i. En ligne 9, où le 6 ne peut également être qu'en colonne f ou i. Ici, le 6 est éliminé en f7, i4 et i7.
|
Traduction en ESC : Code: | B --17-- A(2) | | 6 6 | | D ---2--- C
|
esc A : case i1(167) de liberté 2 esc B : cases a1(17) d1(67) toutes les cases (non remplies) de la ligne 1 sauf i1 esc C : case i9(26) esc D : cases d9(26) toutes les cases (non remplies) de la ligne 9 sauf i9 somme des libertés - somme des contraintes = 5-5 = 0 Donc on applique la règle i=0. Sont éliminés tous les candidats voyant un (0+1) élément du réseau. En particulier i4#6 et i7#6 car ils voient le 6 de A--C et f7#6 car il voit le 6 de B--D. xyz-wing Citation: | http://www.sudoku-factory.com/forumsudoku/viewtopic.php?t=167
Code: |
a b c d e f g h i *----------------+----------------+----------------* 1|A.389 B.89 35 | 4 7 1 | 2 59 6 | 2| 69 1 56 | 29 28 589 | 3 7 4 | 3| 7 2 4 | 369 39 569 | 1 8 59 | *----------------+----------------+----------------* 4| 4 56 2 | 136 18 68 | 9 35 7 | 5|C.39 79 37 | 5 4 2 | 68 16 18 | 6| 1 56 8 | 3679 39 679 | 4 235 25 | *----------------+----------------+----------------* 7| 268 3 67 | 1279 12 79 | 5 4 18 | 8| 28 78 9 | 127 5 4 | 68 16 3 | 9| 5 4 1 | 8 6 3 | 7 29 29 | *----------------+----------------+----------------*
| A1= 389 (XYZ) , B1= 89 (YZ) , A5= 39 (XZ) et sa Conséquence Z = 9 n'est plus en case A2(69)
|
Traduction en ESC : Code: | B --8-- A(2) --3-- C |
esc A : case a1(389) de liberté 2 esc B : case b1(89) esc C : case a5(39) somme des libertés - somme des contraintes = 4-2 = 2 Donc on applique la règle i=2. Sont éliminés tous les candidats voyant trois (2+1) éléments du réseau. En particulier a2#9 car il voit les 9 de A,B et C. wxyz-wing Voici un exemple intéressant pour deux raisons : 1) le voyeur voit tous les éléments du réseau. 2) le réseau n'est pas linéaire, mais plutôt en T... Citation: | http://www.scanraid.com/AdvanStrategies.htm#WXYZ
Code: |
+----------------+-----------------+---------------+ | 1479 8 4579 | 13579 2 157 | 35 49 6 | | 2 6 59A| 4 39 8 | 35 1 7 | | 1479 3 4579B| 6 79C 157 | 8 49D 2 | +----------------+-----------------+---------------+ | 5 2 1 | 79 6 47 | 49 3 8 | | 69 7 69 | 8 14 3 | 2 5 14 | | 3 4 8 | 25 19 25 | 6 7 19 | +----------------+-----------------+---------------+ | 47 5 2 | 137 8 9 | 147 6 34 | | 8 19 347 | 137 347 6 | 179 2 5 | | 467 19 3467 | 1237 5 1247 | 1479 8 39 | +----------------+-----------------+---------------+
| Un wxyz-wing permet déliminer le 9 en a3.
|
Traduction en un réseau d'ESC : Code: | A --5-- B(3) --7-- C | 4 | D
|
somme des libertés - somme des contraintes = 6-3 = 3 Tout candidat voyant quatre (3+1) éléments du réseau est éliminé. Par exemple a3#9 car il voit les 9 de A, B, C, et D ! multivalue x-wing Citation: | http://www.scanraid.com/FishyStrategies.htm#MXW
Code: |
a b c d e f g h i *----------------+----------------+----------------* 1| 4 179 379 | 19 57 679 | 239 8 2569 | 2|A.16* 189 5 | 1238 28 39 | 39 7 B.69* | <--- ligne 2 3| 2 689 379 | 689 4 5679 | 35 39 1 | *----------------+----------------+----------------* 4| 7 2 6 | 4 9 8 | 1 5 3 | 5| 3 4 8 | 5 6 1 | 29 7 29 | 6| 9 5 1 | 7 3 2 | 4 6 8 | *----------------+----------------+----------------* 7| 8 69 4 | 2369 1 359 | 359 23 7 | 8|D.15* 179 2 | 289 78 4 | 6 139 C.59* | <--- ligne 8 9| 156 3 79 | 269 257 679 | 8 12 4 | *----------------+----------------+----------------* | éliminations du 1 en a9, et aussi des 9 en i1 et i5.
|
Traduction en ESC : Code: | A --6-- B | | 1 9 | | D --5-- C
|
somme des libertés - somme des contraintes = 4-4 = 0 Donc on applique la règle i=0. Sont éliminés tous les candidats voyant un (0+1) élément du réseau. En particulier i9#1 car il voit le 1 de A--D, et aussi i1#9 et i5#9 car ils voient le 9 de B--C. | |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique ALS / EQC / ESC Ven Juil 03 2009, 11:51 | |
| finned swordfish Citation: | http://www.sudoku-factory.com/forumsudoku/viewtopic.php?t=424
Code: |
*-----------------------------------------------------------* | 5 A.68* 2 | 7 B.4689* B.49 | 1 C.34 C.3469* | <-- ligne 1 | 4 1 69 | 3 2 5 | 69 8 7 | | 789 678 3 | 469 4689 1 | 2 456 4569 | |-------------------+-------------------+-------------------| | 6 5 4 | 8 3 2 | 7 9 1 | | 2 38 7 | 49 1 49 | 356 356 3568 | | 38 9 1 | 5 7 6 | 4 2 38 | |-------------------+-------------------+-------------------| |D.39 D.346* 5 | 2 E.469* 7 | 8 1 F.469* | <-- ligne 7 | 1 2 69 | 469 5 8 | 369 7 3469 | |G.79 G.467* 8 | 1 H.469* 3 |I.569* I.456* 2 | <-- ligne 9 *-----------------------------------------------------------* | swordfish de 6 : b1 e1 i1--- b7 e7 i7----- b9 e9 (g9 +h9) elimination du 6 de i8
|
Traduction en réseau d'ESC : Code: | A --8--B(2)--49-- C(2) / \ | / \ | 6[2] 6[2] 6 | | | |-D(2)---49[2]-------F(2) | | | | E(2)--| \ | G(2)---49[2]-------I(2) | | H(2)-/
(la charnière liant B(2) E(2) et H(2) passe derrière, sans croiser d'autre charnière...)
|
somme des libertés - somme des contraintes = 17-16 = 1 Donc on applique la règle i=1. Sont éliminés tous les candidats voyant deux (1+1) éléments du réseau. En particulier i8#6 car il voit les 6 de C--F et I. chaîne mixte fermée Citation: | http://www.sudoku-factory.com/forumsudoku/viewtopic.php?t=426
Code: |
..a. ..b. ..c. .d. .e. .f. .g .h .i
1 .18. .128 1246 B.68 .7. 248 .3 .9 .5 2 E.89. ..3. ..5. .1. 289 248 .6 24 .7 3 ..7. .249 .246 .3. .69 .5. 24 .1 .8 4 E.489 2489 ..3. .5. .28 .1. .7 .6 24 5 D.1268 C.128 C.12. C.268 .4. .7. .9 .5 .3 6 E.46. ..5. ..7. .9. .26 .3. .1 .8 24 7 ..3. .124 .124 .7. .5. .6. .8 24 .9 8 E.24. ..7. ..8. .24 .1. .9. .5 .3 .6 9 ..5. ..6. ..9. 248 .3. .28 24 .7 .1
| 1 - 8.a1/8 - 6.d1/6.D5 - 6.a5/1.a5 - 1.a1 =>a1=1.
|
Traduction en ESC : Code: | B --6-- C --128-- D(3) --6-- E
|
somme des libertés - somme des containtes = 6-5 = 1 Tout candidat voyant deux (1+1) éléments est éliminé (règle i=1). En particulier le 8 en a1, voyeur des 8 de B et E. chaînes mixtes avec als/eqc Citation: | http://www.sudoku-factory.com/forumsudoku/viewtopic.php?t=400
Code: |
a b c d e f g h i +----------------------+----------------------+----------------------+ 1 | 8 24567 469 | 2459 259 2459 | 679 1 3 | 2 | 56 356 139 | 7 1359 8 | 4 69 2 | 3 | 247 2347 1349 | 12349 6 12349 | 8 79 5 | +----------------------+----------------------+----------------------+ 4 | 4567 345678 2 | 3456 357 345 | 1 78 9 | 5 | 57 1 46 | 259 8 259 | 27 3 46 | 6 | 9 34678 3468 | 12346 1237 1234 | 5 278 46 | +----------------------+----------------------+----------------------+ 7 | 26 268 5 | 2389 4 7 | 2369 269 1 | 8 | 1 24 7 | 2359 2359 6 | 239 45 8 | 9 | 3 9 468 | 1258 125 125 | 26 45 7 | +----------------------+----------------------+----------------------+ | Examinons la ligne 2 :
Code: |
2 | 56 356 139 | 7 1359 8 | 4 69 2 | | 4b8-4c9 / 8c9-8c6 / 3c6-3(b6,b4) / (PJ56) 3b2-6(a2,b2) / 6h2-9h2 / 6h2-6h7 / 6a7-2a7 / 2b8-4b8 Les extrémités étant identiques, b8=4 et la grille s'effondre.
|
Traduction en ESC : Code: | B --4-- C --8-- D --3-- E --6-- F --9-- G --6-- H |
avec B esc {2468} en cases a7 b7 c9 C esc {134689} en cases c1 c2 c3 c5 c6 D esc {345678} en cases a4 a5 b4 b6 c5 E esc {356} en cases a2 b2 F esc {69} en case h2 G esc {26789} en cases h3 h4 h6 h7 H esc {26} en case a7 somme des libertés - somme des containtes = 7-6 = 1 Tout candidat voyant deux (1+1) éléments est éliminé (règle i=1). En particulier le 2 en b8 , d7 , g7 et h7, voyeurs des 2 de B et H. Citation: | http://www.sudoku-factory.com/forumsudoku/viewtopic.php?t=400
Code: |
a b c d e f +-------------------+-------------------+ 1| 2345 | 4569 369 | 2| 347 3457 | 49 45 | 3| 57 237 | 15 136 | +-------------------+-------------------+ 4| 89 168 | 129 | 5| 4679 1467 | 1257 25 | 6| 479 147 | 1579 179 | +-------------------+-------------------+ 7| 789 679 678 | 148 167 | 8| 2367 23678 | 1267 28 | 9| 578 23567 | 246 67 | +-------------------+-------------------+ | 7f9—6f9 / 6(d8,d9)—6d1 / 4d1—4c1 / (ALS) 4(c5,c6)—7(c5,c6,c7) 7c9, voisin commun des extrémités, est éliminé.
|
Traduction en ESC : Code: | A --6-- B --459-- C(3) --6-- D --4-- E |
avec A esc {67} en case f9 B esc {1245679} en cases d2, d4, d5, d6, d8 d9 C esc {4569} en case d1 (donc de liberté 3) D esc {234569} en cases c1 f1 g1 h1 i1 E esc {14678} en cases c4 c5 c6 c7 somme des libertés - somme des contraintes = 7-6 = 1 Tout candidat voyant deux (1+1) éléments est éliminé (règle i=1). En particulier le 7 en c9, voyeur des 7 de A et E. Citation: | http://www.sudoku-factory.com/forumsudoku/viewtopic.php?t=400
Code: |
a b c d e f g h i +--------------------+------------------+----------------+ 1 | 1378 | 168 167 | 167 1367 | 2 | 13467 1467 137 | 1247 16 | 236 | 3 | 14567 14678 1578 | 12478 1267 | 1267 26 | +--------------------+------------------+----------------+ 4 | 127 127 | 179 167 | 2679 | 5 | 1347 1247 1237 | 1789 15689 1567 | 2678 2679 2689 | 6 | | 78 | 78 | +--------------------+------------------+----------------+ 7 | 15 18 | 129 125 | 168 1369 3689 | 8 | 157 125789 | 159 | 128 129 289 | 9 | 16 126 129 | 19 | | +--------------------+------------------+----------------+
| La chaîne (ALS)5e8--(e8+e9) / 1e2--6e2 / 6(a2+b2)--6(a3+b3) / 6i3--2i3 / 2f3--2f7 élimine 5 en f7, d'où e8=5.
|
Traduction en ESC : Code: | A --1-- B --6-- C(2) --14578-- D(4) --6-- E --2-- F |
avec als A {159} en cases e8 e9 als B {16} en case e2 esc C {1345678} en cases a2 b2 c1 c2 c3 (liberté 2) esc D {145678} en cases a3 b3 (liberté 4) esc E {26} en case i3 esc F {12567} en cases f1 f3 f4 f5 somme des libertés - somme des contraintes = 10-9 = 1 On applique la règle i=1 : le 5 de f7 est éliminé car il voit les 5 de A et F. | |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique ALS / EQC / ESC Ven Juil 03 2009, 11:52 | |
| Death Blossom Citation: | http://www.scanraid.com/AdvanStrategies.htm#DB
Code: |
*-----------------------------------------------------------* | 3 6 1 | 58 58 4 | 9 2 7 | | 459 7 49 | 2 3 69 | 8 15 1456 | | 2459 258 489 | 7 69 1 | 356 35 456 | |-------------------+-------------------+-------------------| | 8 A.124* 4679 | 135 4579 239 | 1256 579 12569 | | 129 3 5 | 6 C.79* 8 | 4 C.179* C.129* | | 1469 A.124* 679 | 15 4579 29 | 1256 8 3 | |-------------------+-------------------+-------------------| | 156 158 68 | 4 2 7 | 13 359 589 | | 47 A.48* 3 | 9 1 5 | 27 6 B.28* | | 157 9 2 | 38 68 36 | 157 4 15 | *-----------------------------------------------------------* | élimination du 1 de a5
|
Traduction en ESC : somme des libertés - somme des contraintes = 3-2 = 1 Tout candidat voyant deux (1+1) éléments est éliminé (règle i=1). En particulier le 1 en a5, voyeur des 1 de A et C. 4. Traduire un raisonnement en réseau d'ESC. Exemple 1 Cas d'un videur... http://www.sudoku-factory.com/forumsudoku/viewtopic.php?t=434 Code: | a b c d e f g h i +-------------------+-------------------+-------------------+ 1 | 348 7 2 | 158 1358 138 | 6 9 458 | 2 |B689 1 B68 | 25 4 689 |B25 7 3 | 3 | 5 A469 346(8)| 7 2389 3689 | 1 A248 A48 | +-------------------+-------------------+-------------------+
|
papa a écrit: | Un videur : C3=8 => I1=8 C3=8 => A1=3 On n'a alors alors plus que deux chiffres possibles (1 et 5) pour les 3 cases D1-E1-F1 donc C3#8
|
Quasi-traduction en ESC : deux ESC de liberté 2 liés par une triple charnière ! somme des libertés - somme des contraintes = 4-3 = 1 on applique la règle 1 : tout candidat voyeur de deux éléments de la chaîne est éliminé. Par exemple le 8 en c3, voyant les 8 de A et de B Exemple 2 cas d'un forcing net avec des ensembles complets... http://www.sudoku-factory.com/forumsudoku/viewtopic.php?t=318 Code: | o ! a b c ! d e f ! g h i ! o o-------------o-------------o-------------o 1 ! 24 9 8 ! 245 7 256 ! 1 26 3 ! 2 ! 124 6 5 ! 124 3 9 ! 24 7 8 ! 3 ! 7 3 124 ! 124 8 26 ! 249 269 5 ! o o-------------o-------------o-------------o 4 ! 348 1 34 ! 7 59 38 ! 6 59 2 ! 5 ! 368 7 36 ! 23 59 238 ! 59 1 4 ! 6 ! 5 2 9 ! 6 4 1 ! 3 8 7 ! o o-------------o-------------o-------------o 7 ! 9 8 23 ! 35 6 7 ! 25 4 1 ! 8 ! 16 5 16 ! 8 2 4 ! 7 3 9 ! 9 ! 23 4 7 ! 9 1 35 ! 8 25 6 ! o o-------------o-------------o-------------o
|
Loumtom a écrit: | (...) montrer que h1= 6.
* d1= 4 --> a1= 2 --> h1= 6. * d2= 4 --> g2= 2 ---> h1= 6. * d3= 4 --> g3= 29 et c3= 12. ---> Triplette 269 f3(26); g3(29); h3(269) ---> c3= 1 ---> A1/A2= 24 --> a9= 3 --> f9= 5 --> h9= 2 --> h1= 6.
|
Quasi-traduction en ESC : Code: | A --4-- B --2-- C --1-- E --24-- F --1-- G --3-- H | 4 | D
|
avec A als {24} en case a1 B als {2456} en cases d1,f1,f3 C esc {124} en case d2 (liberté 2) D als {24} en case g2 E esc {124} en case d3 (liberté 2) F als {12469} en cases c3,f3,g3,h3 G als {1234} en cases a1,a2,a9 H als {235} en cases f9,h9 somme des libertés - nombre de contraintes = 10-8 = 2 On applique la règle i=2 : tout candidat z voyeur de trois (2+1) éléments z dans le réseau est éliminé. Par exemple le 2 en h1 qui voit les 2 de A, D et H. Exemple 3 cas d'éliminations multiples... http://www.sudoku-factory.com/forumsudoku/viewtopic.php?t=464 papa a écrit: |
Code: |
a b c | d e f | g h i | |-------------------|-------------------|-------------------| 1 | | 356 2345 2345 | 25 256 | 2 | 56 | 1568 158 | 16 | 3 | 4568 568 456 | 156 125 | 1256 | |-------------------|-------------------|-------------------| 4 | 25 357 | 1357 1357 | 1237 | 5 | 24 37 | 1347 | 12 1237 | 6 | 456 4567 | 3457 345 | 37 | |-------------------|-------------------|-------------------| 7 | 158 257 | 13578 12359 | 13 15 1589 | 8 | 568 256 | 12358 1235 | 136 1568 | 9 | 1568 5678 | 1578 1578 159 | 15689 | |-------------------|-------------------|-------------------|
|
Si (C7=5 ou bien F7=5 ou bien I7=5) => H7=1 Ou alors Si (I7=1) => H7=5
On a G7=3 => G8=6 => B8#6 et C8#6 mais aussi : A7=8 => D7=7 (on a supprimé les choix 1,3,5 et 8 ) donc B9=7 (B9#6) De plus A9=1 (A9#6)
On n'a alors plus aucun candidat 6 possible en maison 7.
Donc C7#5 ; F7#5 ; I7#5 et I7#1
|
Pour traduire fidèlement ce raisonnement, il faut "atomiser" (comme dxp le dit) le dernier bloc horizontal : vu la preuve de papa, cette idée est assez naturelle. Donc tous les ESC seront réduits à une seule case, sauf esc Z = maison 7 privée de a7 et c7 (ça aussi, c'est assez naturel vu la conclusion de papa). esc Z en cases a9, b8, b9, c8 : de liberté 2 Code: | G7 --1[2]-- A7(2) --8-- Z(2) --6-- G8(2) --1[2]-- H7 | | | | | H7 ------5[2] 25 3---- G7 \ | \ C7(2) \ | \ 7 \ | A7(2) --8-- D7(4) --3-- G7 | \ | / | \-------1[3]-------/ | | 5---------- H7
|
somme des libertés - somme des contraintes = 20-18 = 2 on applique la règle i=2 : tout candidat voyant trois (2+1) élément du réseau est éliminé. i7#1 car voyant la charnière 1 entre G7 A7 H7 (en haut à gauche) , la charnière 1 entre G8 H7 G7 (en haut à droite) et la charnière 1 entre A7 D7 G7 H7 (en bas). c7#5, f7#5, i7#5 car voyant le 5 de H7 (à droite), la charnière 5 entre H7, A7, D7 (en haut), la charnière 5 entre A7 et H7 (en bas). | |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique ALS / EQC / ESC Ven Juil 03 2009, 11:52 | |
| 5. Règle i par l'exemple (jolis coups) Jusqu'à présent, j'ai surtout montré que les réseaux d'esc et la règle i surclassent les techniques habituelles. Toutes les traductions que l'on a vues sont là uniquement pour des raisons pédagogiques (???), théoriques, pour le moins artificielles, voire même un peu contre-nature... L'intérêt principal des réseaux d'esc, c'est leur efficacité à éliminer plusieurs candidats d'un seul petit coup ! (chose très rares avec les techniques classiques, je trouve) Allez, un peu d'auto-satisfaction ... Exemple 1 ...Comment Papa illustre la règle i=0... http://www.sudoku-factory.com/forumsudoku/viewtopic.php?t=422 Code: | A B C D E F G H I +----------------------+----------------------+----------------------+ 1 | 8 24567 469 | 2459 259 2459 | 679 1 3 | 2 |=56 =356 139 | 7 135 8 | 4 =69 2 | 3 | 24 2347 1349 | 12349 6 12349 | 8 79 5 | +----------------------+----------------------+----------------------+ 4 |+4567 +34568 2 | 3456 357 345 | 1 78 9 | 5 |+57 1 +46 | 259 8 259 | 27 3 46 | 6 | 9 +3468 3468 | 12346 1237 1234 | 5 278 46 | +----------------------+----------------------+----------------------+ 7 |*26 *268 5 | 2389 4 7 | 2369 *269 1 | 8 | 1 24 7 | 2359 2359 6 | 239 45 8 | 9 | 3 9 468 | 1258 125 125 | 26 45 7 | +----------------------+----------------------+----------------------+
|
papa a écrit: | ALS 1 : A4-A5-B4-B6-C5 (345678) ALS 2 : A7-B7-H7 (2689) ALS 3 : A2-B2-H2 (3569)
Charnière entre 1 et 2 : le 8 Charnière entre 1 et 3 : le 3 Charnière entre 2 et 3 : le 9
Un vrai cas d'école !!!
Ca donne un système complet et permettre de tuer : - tout ce qui fait sortir les charnières de leurs 2 ALS : b3#3, h3#9 - tout ce qui fait sortir les non-charnières de leur ALS : c6#46, d7#2, g7#26, e2#5, b1#5
| Exemple 2 ...une belle brochette d'éliminations... http://www.sudoku-factory.com/forumsudoku/viewtopic.php?t=510 Code: | a b c d e f g h i +------------------------+------------------------+------------------------+ 1 |5 3789 139 |A)128 6 123789 |C)28 12389 4 | 2 |169 3689 2 |A)18 A)19 4 |5 1389 7 | 3 |B)179 4 B)139 |B)1258 B)12579 B)123789|C)268 C)12389 C)126 | +------------------------+------------------------+------------------------+ 4 |69 2 469 |3 14 5 |19 7 8 | 5 |8 5 49 |124 1247 127 |19 6 3 | 6 |3 1 7 |9 8 6 |24 245 25 | +------------------------+------------------------+------------------------+ 7 |1679 3679 13569 |124568 12459 1289 |24678 12458 1256 | 8 |4 69 8 |7 1259 129 |3 125 1256 | 9 |2 67 156 |14568 3 18 |4678 1458 9 | +------------------------+------------------------+------------------------+
A --28-- B(2) --139-- C(2)
|
somme des libertés - somme des contraintes = 5-5 = 0 (système complet) Alors ça fait mal comme dit papa : voyeurs des 1,9 de A : d3#1, e3#1, f1#1, f3#1, a2#9, b2#9, e3#9, f1#9, f3#9, h2#9, e7#9, e8#9 (e2=9) voyeurs des 2,8 de A-B : f1#2, f1#8 voyeurs des 2,8 de C : h1#2, h1#8, h2#8 Exemple 3 ...un coup net et sans bavure... http://www.sudoku-factory.com/forumsudoku/viewtopic.php?p=4419#4419 Code: | a b c d e f g h i +--------------------+--------------------+--------------------+ 1 | 6 134 5 | 8 2 34 | 7 9 13 | 2 | 29 1348 14 | 157 349 57 | 1256 12568 135 | 3 | 29 138 7 | 15 39 6 | 125 1258 4 | +--------------------+--------------------+--------------------+ 4 | 4 67 89 | 36 1 389 | 59 357 2 | 5 | 1 5 289 | 234 7 23489 | 49 34 6 | 6 | 3 67 29 | 246 5 249 | 149 147 8 | +--------------------+--------------------+--------------------+ 7 | 8 14 14 | 9 6 257 | 3 25 57 | 8 | 57 9 3 | 2457 8 2457 | 12456 12456 157 | 9 | 57 2 6 | 3457 34 1 | 8 45 9 | +--------------------+--------------------+--------------------+
eqc A en g3(125), i1(13), de liberté 2 als B en a3(29), b3(138), d3(15), e3(39), h3(1258), de liberté 1 eqc C en a3(29), e3(39), g3(125) de liberté 2 als D en c4(89), f4(389), g4(59), de liberté 1
A(2) --25-- B --1-- C(2) --5-- D
|
somme des libertés - somme des contraintes (charnières) = 6-4 = 2 Tout candidat voyant trois (2+1) éléments du réseau est éliminé. Par exemple, le 3 de f1 voyant les 3 de A, de C, et D ...et la grille se termine avec les choix uniques. 6. La règle i+ Suite à l'idée de Didier dans http://www.sudoku-factory.com/forumsudoku/viewtopic.php?p=3640#3640 , et d'autres plus récentes, voici la règle i+, cousine de la règle i comme son nom l'indique La naissance de la règle i+ est due à une condition d'application assez restrictive de la règle i : celle qui impose que les charnières de chaque ESC soient distinctes. En effet, assez souvent, lorsqu'on veut utiliser la règle i, on tombe sur cet obstacle : un ESC possède malheureusement des charnières égales... et tout tombe à l'eau ! Le remède que j'ai trouvé dans http://www.sudoku-factory.com/forumsudoku/viewtopic.php?p=3640#3640 est théoriquement valable, mais quelque peu artificiel : il consiste à dupliquer les ESC "malades" autant de fois que nécessaire pour les écrire avec des charnières distinctes. Malheureusement, d'une part, cette solution est un peu choquante psychologiquement (aucune autre technique n'a jamais dupliqué artificiellement quoi que ce soit !), et d'autre part elle génère aussi par effet de bord la duplication d'un certain nombre des autres ESC, même si ces derniers ont des charnières en bonne et due forme ! Je me souviens d'un réseau-pieuvre qui prenait tout l'écran... une horreur amusante... A ce jour, ma préférance va toujours à la règle i pour des raisons d'esthétisme : -- la règle i est plus simple à énoncer que la règle i+ ; -- la règle i est plus homogène dans ses hypothèses et ses conclusions que la règle i+ (tous les esc sont traités de la même manière, sans distinction particulière). Mais force est de constater que la règle i+ a de bons avantages en pratique (Didier confirmera sans problème !) : -- la règle i+ peut s'employer plus souvent que la règle i. La règle i+ se résume à l'exploitation d'une suite de sous-réseaux d'ESC, les sous-réseaux étant liés entre eux par une ou plusieurs charnières... Pour déduire une règle d'élimination adaptée à un réseau, il faut agir en plusieurs étapes (autant que de sous-réseaux). Les contraintes à respecter : -- dans les sous-réseaux, les charnières d'un ESC doivent être différentes. -- un ESC (d'un certain sous-réseau) liés à des sous-réseaux précédents doit avoir ses charnières différentes.
Je veux dire qu'un ESC (d'un certain sous-réseau) liés à des sous-réseaux suivants n'est pas obligé d'avoir ses charnières différentes. Remarque : la règle i est le cas particulier de la règle i+ lorsqu'il n'y a qu'un seul sous-réseau. | |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique ALS / EQC / ESC Ven Juil 03 2009, 11:53 | |
| 7. La règle i+ par l'exemple Pour l'essentiel, je reprends des exemples de Didier90. Exemple 1. http://www.sudoku-factory.com/forumsudoku/viewtopic.php?t=477 Code: | *-----------------------------------------------------------* | 35 1 7 | 35 4 6 | 2 9 8 | | 6 2 4 | 8 9 1 | 7 5 3 | |A58 9 B38 | 57 2 C37 | 6 4 1 | |-------------------+-------------------+-------------------| | 1 46 29 | 246 7 E49 | 3 8 5 | | 2347 467 239 | 2346 5 8 | 1 67 29 | |G237 8 5 | 236 1 F39 | 4 67 29 | |-------------------+-------------------+-------------------| | 9 3 6 | 1 8 D47 | 5 2 47 | |G28 47 28 47 3 5 | 9 1 6 | |G47 5 1 | 9 6 2 | 8 3 47 | *-----------------------------------------------------------*
+------------ A --------------+ sous-réseau 1 | | .8.............................8.......... | | B -3- C -7- D -4- E -9- F -3- G sous-réseau 2
|
Voilà comment la règle i+ peut s'appliquer... Ca se fait deux temps (car il y a deux sous-réseaux). 1er temps/ on regarde le sous-réseau 1 (c'est l'esc A uniquement) : somme des libertés - somme des contraintes = 1-0 = 1 conclusion partielle : le(s) voyeur(s) que l'on éliminera devra(ont) voir au moins un (1) élément du sous-réseau 1 (c'est-à-dire l'esc A dans cet exemple). 2nd temps// on regarde l'ensemble du réseau : somme des libertés - somme des contraintes = (1+6)-(0+7) = 0 conclusion finale : tout candidat voyant un (0+1) élément du réseau total, dont un (1) élément du sous-réseau 1 (c'est-à-dire l'esc A dans cet exemple), est éliminé. Ainsi, a1#5 et d3#5 voyant le 5 de l'esc A. Exemple 2. http://www.sudoku-factory.com/forumsudoku/viewtopic.php?t=421&start=15 didier90 a écrit: |
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 D57 1 | 8 C47 A2457 | | 12567 24567 12457 | 8 9 345 |A12356 1367 A2567 | *--------------------------------------------------------------------------------------*
|
A(2) : g7 g9 i7 i8 i9 (123567) B : h4 h5 h6 (1468) C : h2 (47) D : e6 e2 (357) E : d1 d3 f3 (2369) F : g3 (36)
on peut eliminer les candidats 1 et 6 de h9 qui voient tous les candidats de A et de B
|
En effet, on a le réseau suivant : Code: | B --4-- C sous-réseau 1 / \ ........7...7........... / \ A(2) D | | 3 3 sous-réseau 2 | | F --6-- E
|
Appliquons la règle i+ avec les deux sous-réseaux : 1er temps/ on regarde le sous-réseau 1: somme des libertés - somme des contraintes = 2-1 = 1 conclusion partielle : le(s) voyeur(s) que l'on éliminera devra(ont) voir au moins un (1) élément du sous-réseau 1. 2nd temps// on regarde l'ensemble du réseau : somme des libertés - somme des contraintes = (2+5)-(1+5) = 1 conclusion finale : tout candidat voyant deux (1+1) éléments du réseau total, dont un (1) élément du sous-réseau 1, est éliminé. Ainsi, h9#1 voyant dans les 1 des esc B (du sous-réseau 1) et A, h9#6 voyant les 6 dans les esc B (du sous-réseau 1) et A, et aussi h9#7 voyant les 7 dans les esc C (du sous-réseau 1) et A. Exemple 3. http://www.sudoku-factory.com/forumsudoku/viewtopic.php?t=421&postdays=0&postorder=asc&start=35 Citation: | Le tableau des RAPs faisant apparaître uniquement les candidats :
Code: |
Tableau de Bonjour sur une grille de daily-sudoku-puzzle.com du 22-10-2006
9_|_______258___128___|_157___2578________|_______157_________| 8_|_______24568_12468_|_157___24578_24____|_______157___58____| 7_|_58__________148___|_______458_________|_18________________|
6_|_1568__34568_468___|___________________|_18____134___368___| 5_|_12____24__________|___________________|_______14__________| 4_|_678___368___678___|___________________|_____________368___|
3_|_27__________27____|_59____345_________|_49__________35____| 2_|_68____689_________|_579___2457__24____|_479___56__________| 1_|_______69__________|_______37__________|_79____36__________|
____a_____b_____c_____|_d_____e_____f_____|_g_____h_____i_____|
| Le raisonnement : si g6=8 alors g7=1 (EQC c7=48 ), EQC i4i6=36, i3=5, h2=6, a2=8, a7=5, b6=5, b4=3, c4=8 (EQC c7=4), i4=6, a6=6, c6=4 (contredit c7=4) donc g6#8.
TRADUCTION :
esc A : g7(18 ) esc B : c7(148 ) liberté 2 esc C : i4(368) i6(368) esc D : i3(35) esc E : h2(56) esc F : a2(68 ) esc G : a7(85) esc H : a6(1568 ) c6(468 ) g6(18 ) h6(134) i6(368 ) esc I : b6(34568 ) liberté 4 esc J : b1(69) b2(689) b4(368 ) b5(24) b7(24568 ) b8(258 ) esc K : i4(368) liberté 2 esc L : a4(678) liberté 2 esc M : a3(27) a5(12) a6(1568 ) a7(58 ) liberté 2 esc N : c4(678 ) liberté 2 esc O : c6(468 ) liberté 2
|
Code: | C --3-- D --5-- E --6-- F | | I(4) --2468-- H ---5--- G | | \ | 5 8[3] | / | J --3-- K(2) --6[2]-- L(2) | | | | | | | N(2) --7-- M(2) | | | 6 | | 8[2] ----- O(2) | | A --1-- B(2) -------4 |
(La charnière 7 entre L, M et N est de degré de contrainte 1, ce qui veut dire que 7 peut faire partie des 3-1=2 esc parmi L,M,N... en effet, rien ne contredit que 7 soit à la fois dans M et N.) On peut utiliser la règle i habituelle avec ce réseau pour obtenir un premier critère d'élimination sur cette grille : somme des libertés - somme des contraintes = 24-21 = 3 Ainsi, tout candidat voyant quatre (3+1) éléments quelconques du réseau est éliminé. En fait, le réseau précédent ne suffit pas pour traduire le raisonnement de Bonjour. En effet, il faut "détailler" au niveau de la charnière 7 de l'esc L. Code: | C --3-- D --5-- E --6-- F | | I(4) --2468-- H ---5--- G | | \ | 5 8[3] SOUS-RESEAU 1 | / | J --3-- K(2) --6[2]-- L(2) | | | | | | | | | .................|.....7..7.|.......... | | | | | / \ / N(2) -/ M(2) | | | 6 SOUS-RESEAU 2 | | 8[2] ---- O(2) | | A --1-- B(2) ------4 |
Que voit-on avec ce réseau d'ESC : -- tous les ESC ont des charnières distinctes... sauf l'esc L. -- le réseau d'ESC est partagé en deux sous-réseaux : le partage n'est pas fait au hasard bien entendu, mais il est "provoqué" par les deux charnières égales de l'esc L. Appliquons la règle i+... 1er temps/ On regarde le premier sous-réseau (privé des charnières le reliant à l'autre sous-réseau) : Code: | C --3-- D --5-- E --6-- F | | I(4) --2468-- H ---5--- G | | \ | 5 8[2] | / J --3-- K(2) ----6---- L(2) |
On compte comme d'habitude : somme des libertés - somme des contraintes = 15-13 = 2 conclusion partielle : le(s) voyeur(s) que l'on éliminera devra(ont) voir au moins deux (2) éléments du sous-réseau 1. 2nd temps// On regarde les deux sous-réseaux ensembles (avec les charnières qui les relient) : somme des libertés - somme des contraintes = (15+9)-(13+9) = 2 conclusion définitive : tout candidat voyant trois (2+1) éléments du réseau total, dont deux (2) éléments du sous-réseau 1, est éliminé ! Par exemple le 8 de g6 est éliminé car il voit les 8 de C et K (dans le réseau 1) et A ! Résumons un peu : Sur cet exemple, on a donc plusieurs critères d'élimination de voyeur : * (règle i sur le réseau entier) tout candidat voyant quatre éléments quelconques du réseau est éliminé (insuffisant pour prouver g6#8 ) ; ** (règle i+ sur le réseau entier) tout candidat voyant trois éléments du réseau, dont deux éléments du sous-réseau 1, est éliminé (permettant de prouver g6#8 ). Exemple 4. http://www.sudoku-factory.com/forumsudoku/viewtopic.php?t=568 Code: | a b c | d e f | g h i | |-------------------|-------------------|-------------------| 1 | 1 25 2457 | 8 6 2359 | 347 79 379 | 2 | 45678 9 3 | 247 247 25 | 478 678 1 | 3 | 4678 68 47 | 13479 3479 139 | 5 2 3689 | |-------------------|-------------------|-------------------| 4 | 458 1258 1245 | 267 278 268 | 9 3 25678 | 5 | 389 238 29 | 5 1 4 | 278 678 2678 | 6 | 3589 7 6 | 239 2389 2389 | 1 4 258 | |-------------------|-------------------|-------------------| 7 | 3679 4 8 | 12369 239 12369 | 237 5 2379 | 8 | 2 35 579 | 349 3489 389 | 6 1 3789 | 9 | 369 136 19 | 12369 5 7 | 238 89 4 | |-------------------|-------------------|-------------------| |
papa a écrit: | 2° faisons un zoom sur les 4 pseudo-cases concernées , (D2,E2,F2) ; (D3,E3,F3) ; (G2,H2,I2) et (G3,H3,I3).
Code: |
(2457)x3 | (4678)x2 ----------+--------- n.b. : dans cette notation, on voit entre parenthèses les chiffres pouvant aller (13479)x3 | 3689 dans chaque pseudo-case avec xn indiquant le nombre 'n' d'emplacements disponibles.
|
Il apparait clairement sur ce diagramme que (D2,E2,F2)=(2,4,7) conduit rapidement à une impasse : il ne reste plus aucune possibilité pour la dernière pseudo-case.
Donc F2=5, ce qui donne une paire (2,5) en (B1,C1) etc... la grille tombe. |
papa, vous avez déniché un beau réseau d'ESC, et utiliser la règle i+ sans le savoir (visiblement). En plus, vous dîtes exactement ce qu'il faut pour la mettre en oeuvre facilement : preuve que cette règle est plus naturelle que l'on croit ! Code: | esc A {2457} sur 3 cases def2, de liberté 1 esc B {4678} sur 2 cases gh2, de liberté 2 esc C {3689} sur 1 case i3, de liberté 3 esc D {13479} sur 3 cases def3, de liberté 2
+------- A -------+ sous-réseau | | ................................ | | 47 47 | | D --39-- C --68-- B
|
liberté globale du sous-réseau = 1 -> le voyeur doit voir un élément de ce sous-réseau (esc A, en clair) liberté globale du réseau entier = 8-8 = 0 -> le voyeur doit voir un élément du réseau => conclusion finale : tout candidat voyant un ( 0+1) élément du réseau, dont un ( 1) du sous-réseau est éliminé : en clair, tout voyeur d'élément de A est éliminé. => 2 et 5 appartiennent définitivement à l'esc A => f2=5 comme disait papa. (pour 2, on le savait déjà, dommage) ---------------------------------------------------------- A suivre... Dernière édition par leon1789 le Ven 30/03/2007 10:05; édité 25 fois | |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique ALS / EQC / ESC Ven Juil 03 2009, 11:53 | |
| | |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique ALS / EQC / ESC Ven Juil 03 2009, 11:53 | |
| | |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique ALS / EQC / ESC Ven Juil 03 2009, 11:54 | |
| | |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique ALS / EQC / ESC Ven Juil 03 2009, 11:54 | |
| | |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique ALS / EQC / ESC Ven Juil 03 2009, 11:54 | |
| | |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique ALS / EQC / ESC Ven Juil 03 2009, 11:54 | |
| | |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique ALS / EQC / ESC Ven Juil 03 2009, 11:55 | |
| | |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique ALS / EQC / ESC Ven Juil 03 2009, 11:55 | |
| Loumtom Sudoka Expert
Inscrit le: 27 Aoû 2005 Messages: 682
| Posté le: Dim 03/12/2006 23:34 Sujet du message: Premiers Elements de Réponse. |
|
|
jean chaîne a écrit: |
Bonsoir Leon J'aimerai perfectionner ma technique, et pour cela essayer de comprendre cet article, mais j'aurai besoin de trois définitions et ça ne suffira peut être pas: que signifie ALS ? qu'est ce qu'un voyeur ? qu'est ce qu'un videur ? Merci |
Bonsoir jean chaine,
"ALS" est le Sigle anglo-saxon (Almost Locked Set) pour "EQC" (ensemble quasi-complet) Tout comme Léon, je lui préfère la Transcription "ESC" (ensemble Sur-Complet) plus Souple
Les Bases : * Un Als/Eqc/Esc "classique" est un ensemble (de cases) qui contient 1 candidat de plus que de cases // Un tel ensemble doit appartenir à une meme zone (meme Lligne, même Colonne ou même Maison)
Une Bonne Explication par l'Exemple !
Code: |
A B C D E F G H I +--------------------+-------------------+----------------------+ 1 | 2 9 1378 | 5 168 A.17 |A.167 A.1367 4 | 2 | 1346 1467 137 | 24 16 9 | 5 8 B.236 | 3 | 146 14678 5 | 248 3 127 | 9 12<6>7 B.26 | +--------------------+-------------------+----------------------+ |
--o Esc A : 3 cases f1,g1, et h1 : 4 candidats (différents) 1,3,6,7 : (meme zone : Ligne 1.) --o Esc B : 2 cases i2, i3 : 3 candidats (différents) 2,3,6. ; (meme zone : Maison 3.)
Naturellement, un Esc Tout Seul ne suffit pas : On met en Relation un Jeu de 2 ESC à minima.
--o Ce jeu d'Esc A et B ont un candidat commun particulier : le 3 Il appartient soit a A soit a B mais ne peut pas appartenir aux 2 ensembles simulanément. Soit il est en H1 (il appartient a l'Esc A mais pas à B) Soit il est en I2 (il appartient à B mais plus à A) Ce Candidat commun Particulier porte le nom de Charnière.
--o Propriétés d'Eliminations : Tout candidat "z" autre que le candidats charnière (donc ici #3) d'une Case hors du jeu d'ESC Et qui "Voit" Tous les Candidats "z" Communs aux Deux ESC choisis peut être Eliminé! On l'appelle le Voyeur.
Application : le 6 de H3 . Voici d'ailleurs ce qui se passe en Posant h3= 6
Code: |
A B C D E F G H I +--------------------+-------------------+----------------------+ 1 | 2 9 1378 | 5 168 A.17 |A.1/7 A.1//7 4 | 2 | 1346 1467 137 | 24 16 9 | 5 8 B./3/ | 3 | 146 14678 5 | 248 3 127 | 9 =6 B.2/ | +--------------------+-------------------+----------------------+ | L'ensemble B est alors cohérent, mais il y a un gros problème avec l'ensemble A : 2 candidats qui sont à placer en 3 cases : c'est bien sur impossible ! // l'Ensemble A est Devenu un Ensemble Sous-Complet : // Il y a Plus de Cases que de Candidats à pourvoir.
* Il vient se greffer sur ces bases différentes possibilités :
--o Pour un jeu de 2 ESC, la présence de doubles charnières : // c'est ici d'ailleurs le cas, le 6 aurait pu etre pris aussi comme charnière ... // mais il n'y a pas de Voyeur 3 a éliminer. // En revanche, il y a d'autres propriétes pour d'autres éliminations.
--o Extension via un jeu de n ESC ...
--o Charnière "Volante" qui n'est pas dans la meme zone ...
--o ESC ayant n (>1) candidats de plus que de cases (les degrés de liberte ou liberté tout court) ...
--o Et "For More" :
Http://sudoku-factory.com/forumsudoku/viewtopic.php?t= * * 259 : Les Ensembles Quasi-Complets. * lun.2006.05.01. / Phb. * 427 : ALS ESC EQC * mar.2006.09.27 / Didier. * 443 : Technique ALS / EQC / ESC * mer.2006.10.25. / Leon.
+ La Solution de Papa de la SFE 108 dont je me suis servi pour l'exemple. Http://sudoku-factory.com/forumsudoku/viewtopic.php?t=479&start=3 (puis 5)*
Maintenant, Vous Etes Paré pour l'Apprentissage... Attention : on a vite de Chavirer et de Faire Naufrage !
Sudocalement votre Loumtom. |
|
| |
| | | Admin Admin
Nombre de messages : 3594 Age : 59 Localisation : pas bien loin ... Date d'inscription : 15/01/2009
| Sujet: Re: Technique ALS / EQC / ESC Ven Juil 03 2009, 11:55 | |
| | |
| | | Contenu sponsorisé
| Sujet: Re: Technique ALS / EQC / ESC | |
| |
| | | | Technique ALS / EQC / ESC | |
|
Sujets similaires | |
|
| Permission de ce forum: | Vous ne pouvez pas répondre aux sujets dans ce forum
| |
| |
| |