L'etude des blocs par tableau simplifié (PAPA.04)

papa
Sudoka Expert
L'etude des blocs par tableau simplifié (PAPA.04) RangExpert

Inscrit le: 08 Juin 2006
Messages: 169

Posté le: Sam 16/09/2006 13:04 Sujet du message: L'etude des blocs par tableau simplifié (PAPA.04)

Bonjour,

le but de cette fiche est de montrer une méthode d'exploration de la grille, assez naturelle je crois.

I La procédure habituelle de résolution des grilles :

La démarche assez générale qui semble s'imposer dans la résolution des grilles est la suivante :

1° on comence à s'interesser à des problèmes sur des zones très réduites :
- soit une ligne pour un chiffre donné (seul candidat dans la ligne)
- soit une maison pour un chiffre donné (seul candidat dans la maison)
- soit une colonne pour un chiffre donné (seul candidat dans la colonne)
- soit une case et tous les chiffres (candidat orphelin)

le point commun de ces méthodes est qu'elles ne concernent que 9 "emplacements pour candidats" avec une contrainte bien définie : un et un seul est vrai. On va les appeler "méthodes 1D" (une dimension).

Pour comprendre cette terminologie, je vous invite a voir le tableau de sudoku en perspective avec la grille des 1 devant la grille des 2, devant la grille des 3 etc...

2° toujours dans les méthodes faciles, on fait de la réduction de blocs/licom qui consiste à s'interesser à un chiffre donné dans un bloc vertical ou horizontal donné.

Ici, on s'interesse a un ensemble de 9x3 "emplacements de candidats" avec 3 contraintes de type ligne/colonne et trois contraintes de maison. On va les appeler "méthodes 1,5D"

3° on aborde ensuite (ou plus ou moins en parallèle selon les cas) des zones un peu plus larges :

- une ligne/colonne/maison pour tous les chiffres (mise en évidence de paires, triplets etc... visibles ou cachés)
- un chiffre donné, mais sur toute l'etendue de la grille (swappage, coloriage unichiffre, pointage, X-wing, swordfish, gratte-ciel etc...)

Ce sont les méthodes "2D" qui s'interessent à des zones de 9x9 "emplacements potentiels de candidats"

Ainsi, la fameuse tournée des popotes qui donne le tableau des raps de base est le fruit de l'application des méthodes 1D et 1,5D et des paires visibles qui appartiennent aux méthodes 2D.

Le "tableau étincelant" est le fruit des méthodes 1D 1,5D et 2D.

III Les méthodes 2,5D

On utilise donc des restrictions successives du problème général (qui lui est en 3D) pour se simplifier la vie.

Une fois qu'on a appliqué les méthodes 1D 1,5D et 2D, on pourrait s'imaginer que l'on continue sur 2,5D avant de s'attaquer au problème général en 3D, est-ce le cas ?

Les restriction du problème à 2,5D sont les blocs horizontaux et verticaux qui contiennent 9x9x3 emplacements possibles de candidats. Il existe un certains nombre de méthodes qui se confinent dans les blocs :

- Les XYZ-Wing
- Les coups d'arbalètes
- Les RI
- Les chemins privés
- Certaines chaines courtes
- Certains XY-wings etc... etc...

Les méthodes choisies dépendent des sensibilités, mais on voit que si après le tableau étincelant on passait aux méthodes 2,5D , cela ne constituerait pas forcément un bouleversement méthodologique si important.

III Remarques :

Après ces considérations générales, je vais aborder ma méthode d'exploration des blocs appliquée a la dernière grille extra (la 86) , mais je fais juste une petite mise au point : il est inutile de me faire remarquer comme c'est fréquent sur ce forum "ce que tu montres, c'est en réalité une chaine mixte" ou "ca peut parfaitement être vu par swappage/coloriage etc...". Je ne m'interesse pas ici à la facon de DEMONTRER que tel ou tel candidat doit etre supprimé, mais a un méthode d'EXPLORATION de la grille et de simplification du problème. La mise en forme de la solution n'est pas au programme de cette fiche.

IV Exemple : la grille extra 86 :

Voici le "tableau étincelant" après les méthodes 1D 1,5D et 2D :

Code:

| a b c | d e f | g h i |
+-------------------------------------------------------------+
1 | 3 249 7 | 2458 128 1458 | 6 489 249 |
2 | 5 24 6 | 2478 9 48 | 1 3478 234 |
3 | 8 249 1 | 3 67 46 | 479 5 2479 |
+-------------------------------------------------------------+
4 | 1 7 89 | 589 38 2 | 3458 6 345 |
5 | 6 3 2 | 5789 4 589 | 58 79 1 |
6 | 4 5 89 | 1 67 3689 | 38 2 79 |
+-------------------------------------------------------------+
7 | 9 8 5 | 46 13 7 | 2 134 346 |
8 | 27 16 4 | 269 5 139 | 379 139 8 |
9 | 27 16 3 | 24689 128 1489 | 4579 149 45679 |
+-------------------------------------------------------------+

Commencons par le premier bloc horizontal :

Code:

| a b c | d e f | g h i |
+-------------------------------------------------------------+
1 | 3 249 7 | 2458 128 1458 | 6 489 249 |
2 | 5 24 6 | 2478 9 48 | 1 3478 234 |
3 | 8 249 1 | 3 67 46 | 479 5 2479 |
+-------------------------------------------------------------+

On peut se débarasser des chiffres placés.
Par ailleurs, les colonnes n'ont plus aucune importance (mis a part pour les RI qui doivent être recherchés dans la grille complete) car tous les candidats dans une même colonne sont aussi dans une même maison.
On supprime donc tout ca :

Code:

+-------------------------------------------+
1 | 249 | 2458 128 1458 | 489 249 |
2 | 24 | 2478 48 | 3478 234 |
3 | 249 | 67 46 | 479 2479 |
+-------------------------------------------+

On voit que l'on a un 1 et 5 clairement localisé en ligne 1 de la deuxième maison, un 6 en ligne 3 de la deuxième maison et un 3 en ligne 2 de la deuxième maison.

Dans ce cas, on supprime le candidat et on supprime une case par fusion de deux cases sur le segment concerné (ce qui fait deux case supprimées en ligne 1 de la maison 2) :

Code:

+------------------------------+
1 | 249 | 248 | 489 249 |
2 | 24 | 2478 48 | 2478 |
3 | 249 | 47 | 479 2479 |
+------------------------------+

A partir de ce tableau réduit, on est libre d'utiliser les méthodes de son choix...

Sans préjuger de la méthode employée, on trouve rapidement que le 8 est en première ligne de M3 donc en deuxième ligne de M2 et on simplifie à nouveau :

Code:

+-------------------------+
1 | 249 | 24 | 249 |
2 | 24 | 247 | 247 |
3 | 249 | 47 | 479 2479 |
+-------------------------+

Ici, plus grand chose à faire dans le bloc sauf que si on regarde un peu du cote des RI dans la grille non simplifiée, on voit que B1<>2.

Normalement, a ce stade, on doit répercuter les conséquences de nos eliminations sur toute la grille avec les méthodes 1D 1,5D et 2D mais pour la pédagogie, je vais examiner tous les blocs horizontaux et verticaux en partant à chaque fois du tableau étincelant.

____________________________________________________________

2ème bloc horizontal :

Code:

+-------------------------------------+
4 | 89 | 589 38 | 3458 345 |
5 | | 5789 589 | 58 79 |
6 | 89 | 67 3689 | 38 79 |
+-------------------------------------+

on supprime les 4 en première ligne de la 6eme maison et on fusionne et les 6 en troisième ligne de la 5eme maison pour obtenir le tableau simplifié :

Code:

+-----------------------------------+
4 | 89 | 589 38 | 358 |
5 | | 5789 589 | 58 79 |
6 | 89 | 3789 | 38 79 |
+-----------------------------------+

on place rapidement les 3 par la méthode de son choix (arbalète par exemple) :

Code:

+------------------------------+
4 | 89 | 589 | 58 |
5 | | 5789 589 | 58 79 |
6 | 89 | 789 | 79 |
+------------------------------+

____________________________________________________________

3eme bloc horizontal :

Code:

+---------------------------------------+
7 | | 46 13 | 134 346 |
8 | 27 16 | 269 139 | 379 139 |
9 | 27 16 | 24689 128 1489 | 4679 149 |
+---------------------------------------+

ici, on a une petite difficulté : le 8 est bien localise en troisième ligne de la 8eme maison mais il apparait sur 3 cases. Dans ce cas, il est difficile, voir impossible de fusionner pour faire apparaitre seulement deux groupes de chiffres, on laisse donc le 8 tranquile. Par ailleurs, il n'y a rien a tirer de ce bloc à ce stade.

NB : a mon avis cette ligne peut etre fusionée en inscrivant : 12469 1249 mais il faut que j'affine un peu les règles de fusion pour fournir un outil simple et cohérent.

____________________________________________________________

1er bloc vertical :

les simplifications sont telles que tout est vide.

____________________________________________________________

2eme bloc vertical :

Code:

| d e f |
+---------------------+
| 2458 128 1458 |
| 2478 48 |
| 67 46 |
+---------------------+
| 589 38 589 |
| 5789 67 3689 |
+---------------------+
| 46 13 |
| 269 139 |
| 24689 128 1489 |
+---------------------+

Je ne voit rien d'immédiat.

____________________________________________________________

3eme bloc vertical : un RI permet de supprimer le 4 en I9.

Code:

| g h i |
+---------------------+
| 479 3479 249 |
| 234 |
| 2479 |
+---------------------+
| 345 79 345 |
| 35 79 |
+---------------------+
| 379 349 |
| 4579 349 3579 |
+---------------------+

On rencontre quelques petits problèmes pour supprimer les 2 et fusionner. Par ailleurs, ce bloc ne donne rien d'interessant. Par ailleurs, on notera que j'ai fait quelques fusions en maison 9 qui demanderaient des explications plus détaillées... Je ferais ca dans un autre message.

____________________________________________________________

Voila ! vous avez l'idée générale. Il s'agit plus d'une méthodologie que d'une méthode en soi, mais par expérience, j'ai remarqué qu'elle me permettait de bien detecter les point faibles de la grille quelque soit la méthode utilisée ensuite (ALS, swappage, chaines etc...).

Cette étude exhaustive des blocs nous a permis de découvrir deux angles d'attaque faciles de la grille à partir du tableau étincelant :

1° le placement du 8 en H1
2° le placement des 3 dans le deuxième bloc (c'est celui qui a été majoritairement utilisé dans le forum)

Cordialement,

Papa

P.S. : A venir : une petite fiche sur les règles de fusion et le "jumellage" dont je n'ai pas parlé pour le moment.

Dernière édition par papa le Sam 16/09/2006 17:19; édité 2 fois

papa
Sudoka Expert
L'etude des blocs par tableau simplifié (PAPA.04) RangExpert

Inscrit le: 08 Juin 2006
Messages: 169

Posté le: Sam 16/09/2006 16:07 Sujet du message:

Maintenant que nous avons vu les principes généraux des tableaux simplifiés, on va rentrer un peu plus dans le detail et reprendre les tableaux précédents :

1er bloc horizontal :

Code:

+-------------------------------------------------------------+
1 | 3 249 7 | 2458 128 1458 | 6 489 249 |
2 | 5 24 6 | 2478 9 48 | 1 3478 234 |
3 | 8 249 1 | 3 67 46 | 479 5 2479 |
+-------------------------------------------------------------+

Regle n°1 sur les fusions :
Quand un chiffre localisé sur un segment se trouve sur deux cases uniquement, on peut supprimer le chiffre et fusioner les deux cases.

Regle n°2 sur les fusions :
Quand deux chiffres sont localisé sur un segment, on peut supprimer les chiffres et fusioner les trois cases.

ceci s'applique au 1, au 5 et au 6 en maison 2 et au 3 en maison 3 :

Code:

+------------------------------+
1 | 249 | 248 | 489 249 |
2 | 24 | 2478 48 | 2478 |
3 | 249 | 47 | 479 2479 |
+------------------------------+

observons la première ligne de la maison 3 : toutes les combinaisons de deux chiffres parmi 2489 sont possibles. Pourquoi ? aucun des deux groupes (489 et 249) ne possède 2 chiffres qu'il aurait lui seul.
On peut donc noter ceci : (2489)x2

Idem pour la troisième ligne de la maison 3 que l'on peut noter (2479)x2

Par contre, il en va très differement de la deuxième ligne de la maison 2 dans laquelle un groupe possède deux chiffres en propre : le 2 et le 7. Dans ce cas, la ligne ne peut pas contenir a la fois 2 et 7, on doit utiliser la notation (2478 48).

Code:

+------------------------------+
1 | 249 | 248 | (2489)x2 |
2 | 24 | 2478 48 | 2478 |
3 | 249 | 47 | (2479)x2 |
+------------------------------+

regle n°1 sur le jumelage :
quand deux case d'un même segment n'ont pas plus d'un chiffre n'appartenant pas a leur voisine, on peut les jumeller.

____________________________________________________________

2eme bloc horizontal :

Code:

+-------------------------------------------------------------+
4 | 1 7 89 | 589 38 2 | 3458 6 345 |
5 | 6 3 2 | 5789 4 589 | 58 79 1 |
6 | 4 5 89 | 1 67 3689 | 38 2 79 |
+-------------------------------------------------------------+

devient :

Code:

+-----------------------------------+
4 | 89 | 589 38 | 358 |
5 | | (5789)x2 | 58 79 |
6 | 89 | 3789 | 38 79 |
+-----------------------------------+

____________________________________________________________

3eme bloc horizontal :

Code:

+-------------------------------------------------------------+
7 | 9 8 5 | 46 13 7 | 2 134 346 |
8 | 27 16 4 | 269 5 139 | 379 139 8 |
9 | 27 16 3 | 24689 128 1489 | 4579 149 45679 |
+-------------------------------------------------------------+

devient :

Code:

+---------------------------------------+
7 | | 46 13 | (1346)x2 |
8 | 27 16 | 269 139 | (1379)x2 |
9 | 27 16 | 24689 128 1489 | 4679 149 |
+---------------------------------------+

En maison 3, on se trouve dans la configuration délicate d'un chiffre localisé (le 8) mais réparti sur 3 cases.

On doit alors regarder si il n'y a pas une case possédant deux chiffres ou plus en propre. Ce n'est pas le cas ici : seul le 6 est représenté uniquement dans la première case. on peut alors fusionner et jumeller :

Code:

+---------------------------------+
7 | | 46 13 | (1346)x2 |
8 | 27 16 | 269 139 | (1379)x2 |
9 | 27 16 | (12469)x2 | 4679 149 |
+---------------------------------+

regle n°3 sur les fusions :
quand les trois cases d'un même segment n'ont pas plus d'un chiffre en propre et qu'un chiffre a ete localisé dans le segment, on peut les fusionner et le jumeller toutes les trois.

Il n'y a pas beaucoup plus a apprendre des bloc verticaux, je vais donc énoncer les règles suivantes sur des exemples virtuels :

regle n°2 sur le jumelage :
quand les trois case d'un même segment n'ont pas plus d'un chiffre n'appartenant pas a un de leurs voisines, ni que deux casess ont plus deux chiffres n'appartenant pas à la troisième, on peut les jumeller toutes les trois.

ex : 12 23 13 => (123)x3
ex : 145 12 123 => 145 (123)x2 pas de jumellage à cause du 4 et du 5
ex : 146 1456 12 => (1456)x2 12 pas de jumellage a cause du 456 sur deux cases (on ne peut pas avoir simultanément 4, 5 et 6 sur ce segment).
ex : 1456 15 46 => aucun jumellage possible.

Regle n°4 sur les fusions dans les systèmes jumellés :
Quand un chiffre est localisé sur un segment avec des case jumelées, on procède de la facon suivante :
si tout le segment est jumellé, on enlève le chiffre localisé et on réduit de un le facteur du jumelage (x2 est supprimé et x3 devient x2).
si on a deux cases jumelles et une séparée, on supprime le x2 et on complète la case seule par les éléments du système jumellé.

ex : (1456)x2 123 : on veut supprimer le 1 et fusionner, cela devient : 456 23456

Il existe donc quelques rares cas ou l'on ne peut pas se débarasser d'un chiffre localisé dans un segment, mais il faut que :
- le segment contienne 3 cases avec des candidats et que le chiffre localisé soit dans ces trois cases.
- aucun jumellage ne soit possible.
- une case contienne au moins deux chiffres en propre.
Dans ce cas précis, on ne se débarassera pas du chiffre localisé.

Voila ! ca peut paraitre un peu fastidieux au début, mais avec un peu d'habitude et une fois qu'on a compris la logique, ca va très vite et ca permet de bien faciliter la recherche dans un bloc quelque soit votre méthode de prédilection.

____________________________________________________________

Il existe encore une dernière méthode de simplification en plus de la fusion et du jumellage :

Par exemple, si j'ai un segment avec : 1234 12, je ne peut pas faire de jumellage, mais je peut me simplifier largement la vie en l'écrivant 234 12 sans perte d'information. La seule conséquence de ce retrait est qu'il n'y a plus qu'une seule facon d'avoir 1 et 2 dans le segment alors qu'il y en avait deux avant (12 et 21). Ca peut faciliter sensiblement la vie quand on fait des chaines.

Si il y a une demande de ce cote la, je peut eventuellement donner des règles pour ce genre de simplification.

Dernière édition par papa le Sam 16/09/2006 19:01; édité 2 fois

PhB
Sudoka Expert
L'etude des blocs par tableau simplifié (PAPA.04) RangExpert

Inscrit le: 14 Déc 2005
Messages: 369

Posté le: Sam 16/09/2006 16:08 Sujet du message: Re: L'etude des blocs par tableau simplifié (PAPA.04)

Bonjour papa,

Merci de nous proposer vos approches, qui sont toujours agreables a lire.
J'ai sans doute lu un peu vite votre article et j'aurais besoin de vos lumieres sur ceci:

papa a écrit:

Code:

+------------------------------+
1 | 249 | 248 | 489 249 |
2 | 24 | 2478 48 | 2478 |
3 | 249 | 47 | 479 2479 |
+------------------------------+

A partir de ce tableau réduit, on est libre d'utiliser les méthodes de son choix...

Sans préjuger de la méthode employée, on trouve rapidement que le 8 est en première ligne de M3 donc en deuxième ligne de M2 ...

et vous concluez :

"Cette étude exhaustive des blocs nous a permis de découvrir deux angles d'attaque faciles de la grille à partir du tableau étincelant :
1° le placement du 8 en H1 "
...

Or, il me semble que vous n'avez justement pas explique pourquoi le 8 est en premiere ligne de M3 ? Aurais-je loupe une etape ?

Merci de m'eclairer,
_________________
PhB

papa
Sudoka Expert
L'etude des blocs par tableau simplifié (PAPA.04) RangExpert

Inscrit le: 08 Juin 2006
Messages: 169

Posté le: Sam 16/09/2006 16:30 Sujet du message:

PhB :

En fait, le tableau simplifié peut servir de base a toutes sortes de méthodes, et j'ai préféré ne pas choisir, mais puisque nous evoquons un cas précis, je vais montrer que de nombreuses méthodes peuvent s'appliquer dans ce tableau :

Code:

+------------------------------+
1 | 249 | 248 | (2489)x2 |
2 | 24 | 2478 48 | 2478 |
3 | 249 | 47 | (2479)x2 |
+------------------------------+

1° les ALS :

ALS 1 : 2479x2 et 2489x2 en maison 3
ALS 2 : 48 et 47 en maison 2
charnière : le 7
voyeurs : les 8 en maison 2 - ligne 1 (M2L1) et en maison 1 -ligne 2 (M1L2)

2° le swappage : sur les 2 de la deuxième maison

Code:

+--------------------------------+
1 | 249 | 2=/4/#8# | (2489)x2 |
2 | 2/=4| =2/478 4/=8| 2478 |
3 | 249 | 47 | (2479)x2 |
+--------------------------------+

3° les chaines de jumeaux-voisins :

2(M2L1) - 2(M2L2.1) / 2(M1L2) - 4(M1L2) / 4(M2L2.2) - 8(M2L2.2)

4° Les raisonnements par impossibilité :

M2L1=8 => M2L2.2=4 et M2L2.1=2 => rien de possible en M1L2

Je ne suis pas un expert du coloriage, mais je pense que ca doit bien fonctionner aussi.

Enfin, ma méthode personnelle est ce que j'apelle le "pointage", que j'ai évoqué dans une autre fiche et qui marche très bien ici aussi.

Dans tous les cas, on conclue qu'on a 8 en M3L1 et en M2L2. Un retour au tableau nous permet donc de dire H1=8, mais rien de plus précis pour M2L2 puisque le 8 etait candidat dans deux cases.

Le but est de montrer que ce type de tableau s'adapte a toutes les techniques existantes...

PhB
Sudoka Expert
L'etude des blocs par tableau simplifié (PAPA.04) RangExpert

Inscrit le: 14 Déc 2005
Messages: 369

Posté le: Sam 16/09/2006 19:30 Sujet du message:

Bonsoir papa, Je n'avais pas bien saisi l'objectif de votre presentation. Si je vous suis bien, il s'agit d'une approche raisonnee de la grille pour mieux "sentir" son potentiel en quelque sorte. J'ai vu que vous avez poste une deuxieme partie, que je vais m'empresser de lire. Merci et a bientot, _________________ PhB

papa
Sudoka Expert
L'etude des blocs par tableau simplifié (PAPA.04) RangExpert

Inscrit le: 08 Juin 2006
Messages: 169

Posté le: Dim 17/09/2006 1:03 Sujet du message:

Bonsoir PhB, En fait, il y a plusieurs aspects : Il s'agit d'abord de proposer une approche de la grille par restrictions successives. Comme on l'a vu, c'est quelques chose que nous faisons deja sans nous en rendre compte. Il fallait le formaliser un peu. Partant de la, si on suppose qu'une méthode possible après le tableau etincelant est la recherche en 2,5D (a savoir bloc par bloc), autant faire les choses bien et se doter d'outils pour débrousailler le terrain au maximum. Donc oui, il s'agit bien d'une approche raisonnée qui permet de faire ressortir les éléments potentiellement interessants d'un bloc en effacant ceux dont on ne peut rien tirer et de mettre tout ca en forme le plus clairement possible. Ca ne permet pas de faire directement les eliminations, mais ca permet de les voir beaucoup mieux. Si on utilise les méthodes classiques, c'est surtout une facon d'eclaicir le problème et de se simplifier la vie. Pour moi, c'est un peu plus : j'ai conçu ces tableaux comme suports d'une méthode de pointage qui me permet d'explorer les blocs de facon systématique. A l'arrivée, si le pointage a été bien fait, je suis sur d'avoir fait le tour des méthodes 2,5D à l'exception notable de celles utilisant l'unicité de la solution (RI et Cie). Une telle recherche exhaustive ouvre la possibilité de faire un "tableau super-etincelant" dans lequel on aurait épuisé les méthodes 1D 1,5D 2D et 2,5D. Mais l'expérience montre que dans les grille extra, la recherche par blocs est généralement suffisante pour trouver la solution. J'ai l'intention de parler un de ces jours de la méthode de pointage, mais j'attend que les tableaux simplifiés soient adoptés...

PhB
Sudoka Expert
L'etude des blocs par tableau simplifié (PAPA.04) RangExpert

Inscrit le: 14 Déc 2005
Messages: 369

Posté le: Dim 17/09/2006 16:25 Sujet du message:

Bonjour papa, Je trouve votre approche de plus en plus intéressante… et frustrante en même temps. Je m’en expliquerai dans un instant. D’abord, parlons de l’intérêt : si c’est une sorte de « poêle a frire » permettant de détecter le métal des candidats intéressants, c’est un progrès considérable, surtout si vous travaillez à la main. On se pose souvent la question de savoir par où commencer. Cette méthode rappelle aussi la notion de pseudo case que papyg avait employée à propos de la résolution de RI récalcitrants. Sauf que là, il s’agit de « pseudo cases généralisées ». Pour la frustration : après avoir passe le cap des définitions, ce serait bien de mettre en pratique : comment exploite t’on le tableau simplifié ? Parlez-nous vite de votre méthode de pointage ! Merci de nous faire partager vos lumieres, _________________ PhB

papa
Sudoka Expert
L'etude des blocs par tableau simplifié (PAPA.04) RangExpert

Inscrit le: 08 Juin 2006
Messages: 169

Posté le: Jeu 21/09/2006 14:15 Sujet du message:

Bon, je vais mettre cette approche en pratique sur la première grille venue : la 88.

Je me lance sans connaitre le résultat a l'avance, ca risque d'être un flop, mais ca permettra de toute facons d'expliquer la méthode.

Un petit rappel du tableau des raps issu des méthodes 1D 1,5D et des paires visibles :

Code:

*--------------------------------------------------------------------*
| 1479 2479 124 | 37 239 8 | 3679 23679 5 |
| 5 6 3 | 17 1249 12479 | 789 279 2789 |
| 789 2789 28 | 367 2369 5 | 1 4 2379 |
|---------------------- ---------------------- ----------------------|
| 3 4578 9 | 2 456 46 | 478 1 478 |
| 2 458 458 | 15 7 149 | 3489 39 6 |
| 47 1 6 | 8 49 3 | 5 279 2479 |
|---------------------- ---------------------- ----------------------|
| 148 3 7 | 9 1258 12 | 46 56 14 |
| 149 4(5)9 145 | 13567 1356 167 | 2 8 13479 |
| 6 2589 1258 | 4 1358 17 | 379 3579 1379 |
*--------------------------------------------------------------------*

Les méthodes 2D sont ici particulièrement décevantes : seul le 5 de B8 peut être elliminé par swappage.

Une approche que je vais develloper ici consiste a explorer les blocs.

____________________________________________________________

1er bloc horizontal :

1479_2479_124|37__239_______|3679_23679_____
_____________|17__1249_12479|789__279___2789
789__2789_28_|367_2369______|___________2379

La méthode consiste a avoir d'un coté sa grille avec le bloc tel qu'il est montré ci-dessus et de l'autre un bloc simplifié pour griffoner et faire ses raisonnements.

Si on veut etre parfaitement systématique et capable de repérer des raisonnements semblables a celui que j'ai montre pour la grille 87, la première étape consiste a repérer les RI et autres figures interdites potentielles :

1479_2479_124|37__239_______|3679_23679_____
_____________|17__1249_12479|789__279___2789
789__2789_28_|367_2369______|___________2379

Il y a deux RI et une boucle interdite dans les 2 et les 9 rouges, il faudra s'en souvenir au moment du pointage...

Maintenant, on rédige le tableau simplifié :
279__|37_239|2379
_____|279___|279x2
279x2|2379__|2379

Je vais alors essayer d'envisager des solutions possibles de ce système :

tous les candidats qui participent à une solution sans RI seront jugés bons et pointés dans le bloc.

279__|37_239|2379
_____|279___|279x2
279x2|2379__|2379
ET
279__|37_239|2379
_____|279___|279x2
279x2|2379__|2379

Je pointe ensemble les 3 configurations possible partant du 2 en haut à gauche : en violet, les candidats considérés comme bons.
1479_2479_124|37__239_______|3679_23679_____
_____________|17__1249_12479|789__279___2789
789__2789_28_|367_2369______|___________2379

Partons maintenant du 7 en haut et à gauche :

279__|37_239|2379
_____|279___|279x2
279x2|2379__|2379

On pointe quelques candidats supplémentaires en faisant bien attention a ne prendre en compte aucune configuration contenant un RI:
1479_2479_124|37__239_______|3679_23679_____
_____________|17__1249_12479|789__279___2789
789__2789_28_|367_2369______|___________2379

L'étau es reserre : on termine avec le 9 en haut à gauche.

279__|37_239|2379
_____|279___|279x2
279x2|2379__|2379
et
279__|37_239|2379
_____|279___|279x2
279x2|2379__|2379

Au final tous les candidats du bloc ont été pointés sauf le 7 en bas à gauche.

Vu la facon dont le pointage a été fait, c'est une démonstration en soi que le 7 est a supprimer, mais a ce niveau, il vaut mieux faire un petit raisonnement pour vérifier.

Si I3=7 alors 3 est dans D3 ou D4
Si I3=7 alors 7 est dans A1 ou A2 et D1=3

C'est incompatible donc I3<>7

Debriefing ;

Vu comme ca, ca a l'air un peu long et fastidieux, mais avec un peu d'habitude, c'est assez rapide. On a débusqué sans coup férir un petit raisonnement simple mais pas forcément facilement detectable lors d'une recherche aléatoire. Le résultat reste quand même un peu décevant avec un seul candidat supprimé. Mais il y a une petite chose, pas forcément très visible que nous avons établie : il n'y a rien d'autre que ca a tirer de quelque raisonnement que ce ce soit portant exclusivement sur ce bloc !

Je vais traiter les autres blocs dans des messages a venir...

papa
Sudoka Expert
L'etude des blocs par tableau simplifié (PAPA.04) RangExpert

Inscrit le: 08 Juin 2006
Messages: 169

Posté le: Jeu 21/09/2006 15:40 Sujet du message:

Le 2eme bloc : ___4578____\|___456_46_\|478______478 ___458__458\|15_____149\|3489_39 47_________\|___49_____\|_____279_2479 le bloc simplifié : 4578_\|45_\|478x2 458x2\|459\|489 47___\|49_\|479 On va explorer successivement les valeurs de la case centrale : 4578_\|45_\|478x2 458x2\|459\|489 47___\|49_\|479 4578_\|45_\|478x2 458x2\|459\|489 47___\|49_\|479 4578_\|45_\|478x2 458x2\|459\|489 47___\|49_\|479 On va faire attention au RI dans ce ce dernier cas... Je vous épargne le pointage : tout le bloc est validé. Rien a en tirer ! ____________________________________________________________ 3eme bloc horizontal : 148__________\|______1258_12_\|46__56___14 149_49___145_\|13567_1356_167\|_________13479 ____2589_1258\|______1358_17_\|379_3579_1379 On note tout d'abord un élément evident dans les RI potentiels : On n'a pas le droit d'avoir 4 en I8 sous peine de se retrouver avec un RI de 1 et 4, le rouge (pour la démonstration, on passe par l'intermédiaire du 49 de B8). Le 4 de A7 saute par ricochet. bloc simplifié : 18___\|158____\|15 159x2\|1357x2_\|1379 1589_\|1358_17\|13579x3 On va faire suivant le chiffre dans la case en troisième ligne et première colonne : 18___\|158____\|15 159x2\|1357x2_\|1379 1589_\|1358_17\|13579x3 18___\|158____\|15 159x2\|1357x2_\|1379 1589_\|1358_17\|13579x3 18___\|158____\|15 159x2\|1357x2_\|1379 1589_\|1358_17\|13579x3 18___\|158____\|15 159x2\|1357x2_\|1379 1589_\|1358_17\|13579x3 Avant de reporter tout ca, on voit que les 3 en L2C3 et L3C2 sont absents. Pourquoi ? 3 en E9 => 28 en B9 et C9 => A7=1 3 en E9 => 28 en B9 et C9 => 5 en H9 => (146) en G7-H7-I7 très facile quand on y pense, mais pas si évident à voir comme ca... Quand on reporte les pointages dans la grille, pas de nouvelle surprise. Dernière édition par papa le Jeu 21/09/2006 17:26; édité 1 fois

papa
Sudoka Expert
L'etude des blocs par tableau simplifié (PAPA.04) RangExpert

Inscrit le: 08 Juin 2006
Messages: 169

Posté le: Jeu 21/09/2006 17:14 Sujet du message:

On n'est pas non plus obligés de tout faire dans l'ordre :

ici, le deuxième bloc vertical qui contient beaucoup de cases à deux candidats semble avoir un plus gros potentiel...

le bloc :

Code:

*----------------------*
| 37 239 8 |
| 17 1249 12479 |
| 367 2369 5 |
|----------------------|
| 2 456 46 |
| 15 7 149 |
| 8 49 3 |
|----------------------|
| 9 1258 12 |
| 13567 1356 167 |
| 4 158 17 |
*----------------------*

quelques RI potentiels : 17 en D2-G2-D8-G8
12 en E2-F2-E7-G7
36 en D3-E3-D8-E8

1367x3|2369x2_1249|12479
15____|456____49__|46_149
13567_|125____1356|1267x3

Et la, bingo !

on part du couple 15 en deuxième ligne et première colonne du tableau (ce qui finallement est équivalent a faire un swappage généralisé du bloc).

On part du 1 et on fait les premiers placements dans la ligne et la colonne :
1367x3|2369x2_1249|12479
15____|456____49__|46_149
13567_|125____1356|1267x3

On trouve encore quelques placements :

1367x3|2369x2_1249|12479
15____|456____49__|46_149
13567_|125____1356|1267x3

En troisième colonne, le 6 placé met le 1 en troisième ligne
En deuxième colonne, le 2 et 5 mettent aussi le 1 en troisième ligne.

donc D5=5 et c'est un massacre !

Refaisons le raisonnement sur le bloc non simplifié :

D5=1 => 367 en D1-D2-D3 => 29 en E1-E3
D5=1 => E5=5 tout ca nous fait E7-E9=18

Par ailleurs :
E5=5 => F4=6 => F7-F8-F9=127

C'est impossible ! La grille est finie.

PhB
Sudoka Expert
L'etude des blocs par tableau simplifié (PAPA.04) RangExpert

Inscrit le: 14 Déc 2005
Messages: 369

Posté le: Jeu 21/09/2006 21:58 Sujet du message:

De passage sur le forum, je viens de voir le gros travail que vous avez fait. Bravo, la presentation est superbe ! Pour le contenu, accordez-moi un peu de temps. Je prepare un article "coloriage pour les nuls" qui me prend beaucoup de temps. Et, vous allez rire, ce travail sera base sur la grille 88 ! Apres ca, je me plonge dans votre methode. _________________ PhB

papa
Sudoka Expert
L'etude des blocs par tableau simplifié (PAPA.04) RangExpert

Inscrit le: 08 Juin 2006
Messages: 169

Posté le: Ven 06/10/2006 12:47 Sujet du message:

Après avoir testé la méthode des blocs sur un bon nombre de grilles, je reviens compléter la fiche. Cette fois, mon intention est de montrer une étude de bloc "idéale" pour donner une idée ce qu'on cherche exactement à faire. Bien sur, comme vous allez le voir, cette étude est lourde (a moins bien sur de la laisser faire à son ordinateur), mais elle a le mérite de montrer tout ce qu'il est possible de faire en se restreignant à un seul bloc. Pour faire quelque chose de parfaitement exhaustif, je propose une étude en deux temps : 1° La recherche de toutes les configurations autocohérentes du bloc. 2° La suppression de tout ce qui ne mène pas à une solution unique. I La recherche de toutes les configurations autocohérentes : Nous allons prendre pour exemple le premier bloc vertical obtenu après épuisement des méthodes 1D, 1.5D et 2D dans la grille extra 93. 128__128__1246 89____________ _____249__246_ ============= 489__2489_____ 1268_128__12__ 46____________ ============= _____124__124_ 24____________ On trouve un bon nombre de configurations possibles : n°1 \| n°2 \| n°3 \| n°4 \| ================ 124 \| 124 \| 126 \| 126 \| 8__ \| 8__ \| 8__ \| 8__ \| _96 \| _96 \| _94 \| _94 \| ================ 94_ \| 98_ \| 94_ \| 98_ \| 281 \| 612 \| 281 \| 612 \| 6__ \| 4__ \| 6__ \| 4__ \| ================ _12 \| _12 \| _12 \| _12 \| 4__ \| 4__ \| 4__ \| 4__ \| n°5 \| n° 6 \| n°7 \| n°8 \| n°9 \|n°10\|n°11 \|n°12\| ================================= 182 \| 182 \| 186 \| 186 \| 184 \| 184 \| 186 \| 186 \| 9__ \| 9__ \| 9__ \| 9__ \| 9__ \| 9__ \| 9__ \| 9__ \| _46 \| _46 \| _42 \| _42 \| _26 \| _26 \| _24 \| _24 \| ================================= 49_ \| 89_ \| 49_ \| 89_ \| 49_ \| 89_ \| 49_ \| 89_ \| 821 \| 621 \| 821 \| 621 \| 812 \| 612 \| 812 \| 612 \| 6__ \| 4__ \| 6__ \| 4__ \| 6__ \| 4__ \| 6__ \| 4__ \| ================================= _14 \| _14 \| _14 \| _14 \| _41 \| _41 \| _41 \| _41 \| 2__ \| 2__ \| 2__ \| 2__ \| 2__ \| 2__ \| 2__ \| 2__ \| n°13\|n°14\| ======== 214 \| 216 \| 8__ \| 8__ \| _96 \| _94 \| ======== 94_ \| 94_ \| 182 \| 182 \| 6__ \| 6__ \| ======== _21 \| _21 \| 4__ \| 4__ \| n°15\|n°16\|n°17\| ============ 814 \| 816 \| 821 \| 9__ \| 9__ \| 9__ \| _26 \| _24 \| _46 \| ============ 49_ \| 49_ \| 49_ \| 182 \| 182 \| 182 \| 6__ \| 6__ \| 6__ \| ============ _41 \| _41 \| _14 \| 2__ \| 2__ \| 2__ \| Cette liste nous suggère un certain nombre de commentaires. Nous avons fourni les 17 solutions autocohérentes possibles pour ce bloc. C'est un travail un peu fastidieux, mais il faut se souvenir que nous voulons montrer ici une procédure "idéale" sans trop nous préocuper pour l'instant de sa faisabilité armé d'un papier et d'un crayon. 1° Tout candidat n'appartenant à aucune de ces 17 solutions doit être supprimé : c'est le cas pour B4#2. On peut vérifier sans peine que B4=2 mène à une impossibilité. 2° On remarque que beaucoup de configurations autocohérentes peuvent se déduire les unes des autres par des permutations (chiffres rouges et chiffres bleus) dans les segments (ou pseudo-cases) verticaux. Les méthodes de fusion et de jumellage permettent de s'abstraire d'une bonne partie de ces permutations et de diminuer drastiquement le nombre de configurations autocohérentes. Ceci permet d'arriver beaucoup plus vite au résultat B4#2 3° On peut se dire qu'à ce stade, un aussi médiocre résultat ne justifie pas l'emploi d'une méthode d'une telle lourdeur... Mais attendez la suite... ____________________________________________________________ II La suppression de tout ce qui ne mène pas à une solution unique : Prenons deux de nos 17 configurations autocohérentes, la n°7 et la n°11 : n°7 \|n°11\| ======== 186 \| 186 \| 9__ \| 9__ \| _42 \| _24 \| ======== 49_ \| 49_ \| 821 \| 812 \| 6__ \| 6__ \| ======== _14 \| _41 \| 2__ \| 2__ \| Chaque ligne contient les mêmes chiffres, pas forcément dans le même ordre. On peut alors affirmer que si l'une est solution, l'autre l'est nécéssairement aussi : - elles sont toutes les deux compatibles avec les contraintes du bloc. - vues du reste de la grilles, elles sont strictement équivalentes dans chaque ligne. Ceci nous amène à dévelloper le concept de "signature" : La "signature" d'un bloc est l'ensemble des chiffre qu'il contient, vus étage par étage (ligne par ligne pour les blocs verticaux et colonne par colonne pour les blocs horizontaux) indépendament de leur ordre dans chaque étage. Si deux (ou plus) configurations autocohérentes possèdent la même signature, et que l'on a unicité de la solution, les configurations en question doivent être supprimées. Appliquons cette règle a nos 17 configurations autocohérentes, je note ~ la relation "à la même signature que" : n°1 ~ n°13 n°3 ~ n°14 n°5 ~ n°17 n°7 ~ n°11 ~ n°16 n°8 ~ n°12 n°9 ~ n°15 Ce qui nous permet de supprimer 13 configurations sur 17 !!! Nous voyons que ce concept que je n'avait malheureusement pas dévellopé lorsque j'ai commencé à rédiger cette fiche permet de faire une recherche de type RI, mais à la fois beaucoup plus générale et parfaitement exhaustive lorsqu'on limite notre champ d'étude à un bloc. Par ailleurs, si les tableaux simplifiés sont bien adaptés à la première étape de recherche des configurations autocohérentes, ils sont particulièrement mal adaptés à la deuxième etape. Or nous allons bientôt voir que dans le cas présent, c'est la deuxième étape qui est cruciale. Il y a donc sans doute pas mal de choses à améliorer pour rendre la recherche par bloc facile et efficace. Mais revenons à nos moutons, seules 4 configurations autocohérentes ont survécu : n°2 \| n°4 \| ======== 124 \| 126 \| 8__ \| 8__ \| _96 \| _94 \| ======== 98_ \| 98_ \| 612 \| 612 \| 4__ \| 4__ \| ======== _41 \| _41 \| 2__ \| 2__ \| n° 6 \|n°10\| ======== 182 \| 184 \| 9__ \| 9__ \| _46 \| _26 \| ======== 89_ \| 89_ \| 621 \| 612 \| 4__ \| 4__ \| ======== _14 \| _41 \| 2__ \| 2__ \| Si maintenant on superpose ces 4 configurations restantes, on constate que beaucoup de candidats ont disparu, en particulier, on a nécessairement A1=1 et A5=6. Le nouveau tableau des candidats est : 1__28__246 89________ ___249_46_ ========= 89_89_____ 6__12__12_ 4_________ ========= ___14__14_ 2_________ Pour mémoire, le tableau initial était : 128__128__1246 89____________ _____249__246_ ============= 489__2489_____ 1268_128__12__ 46____________ ============= _____124__124_ 24____________ En conclusion, je dirais que nous avons maintenant une procédure permettant l'étude complète et exhaustive d'un bloc, y compris sur les questions relatives à l'unicité. Reste à trouver des racourcis et des simplifications pour la rendre plus rapide et aisée, quitte à l'affaiblir et à la rendre moins exhaustive. Le but des premiers messages de cette fiche était de proposer un raccourci possible, malheureusement, force est de constater que dans le cas traité ici, la simplification du bloc nous aurait fait passer à côté des raisonnement basés sur l'unicité qui représentaient un très gros potentiel ! Ajoutons que cette approche se distingue radicalement des approches habituellement utilisées. On constate frequement que les chaînes, le coloriage, les ALS etc... aboutissent souvent aux mêmes elliminations. La méthode décrite ici va passer à coté de tout raisonnement dépassant les limites d'un bloc, par contre elle permet des elliminations pratiquement impossibles à trouver par les méthodes usuelles. Ils suffit de tenter d'utiliser les méthode classiques sur l'exemple que je viens de traiter pour s'en convaincre.

» Le pointage des "bons candidats" (PAPA.01)
» classique19
» Des RI pas très rectangulaires (PAPA.02)
» Les Chemins Privés (PAPA.03)
» SSB 002 - La Puissance de Phares et Balises