papaSudoka Expert
Inscrit le: 08 Juin 2006
Messages: 169Posté le: Dim 23/07/2006 10:01 Sujet du message: Le pointage des "bons candidats" (PAPA.01)En réponse a l'article
Le Swappage Loumtomique.(01). , j'ai dit qu'il existe un technique générale qui explore de facon systématique les emplacements a elliminer pour un chiffre donné.
En fait, c'etait légèrement innexact : cette technique permet d'explorer
les candidats a ne pas elliminer. Elle peut difficilement montrer qu'un candidat doit être elliminé.
Si par exemple on coche tous les candidats pour un chiffre donné, on peut être absolument certain qu'il n'y a plus rien a tirer de ce chiffre avec la panoplie de techniques suivantes :
Xwing
Charette/gratte-ciel
Turbot
Espadon/swordfish
Cerf-volant
Jellyfish
Réduction de blocs
swappage loumtomien
coloriage d'un chiffre
Car elle ont toutes en commun de raisonner sur les candidats d'un seul chiffre à la fois.
L'approche se fait donc en deux temps :
1° cocher tous les candidats que la méthode va désigner comme "bons".
2° pour ceux qui restent, montrer de facon explicite qu'ils sont "mauvais". Pour cette deuxième étape, on peut parfaitement avoir recours aux méthodes précitées.
Par ailleurs, il n'est pas à exclure que le côté systématique de cette technique nous permette de voir des elliminations qui n'auraient pas été vues par les techniques évoquées précédemment.
Je vais aborder cette méthode en deux parties : la théorie puis la pratique.
Théorie : Dans la solution finale du Sudoku, chaque chiffre, vu séparément, sera dans une configuration (ou
'config' pour aller plus vite) avec un seul représentant dans chaque ligne, chaque colonne et chaque case.
-> Si pour un candidat dans une case donnée il est impossible de trouver une config passant cette case, on peut affirmer que ce candidat est a rejeter.
Exemple tiré du problème
"jolie fleur" :
Les candidats sont inscrits en
bleu.
-------------------------------
+ o _ _ + _ o
5 +
5 _ o +
+ _ o _ + _
5 5 +
5 o
5 +
+ _ _ 5 + _ _ _ + o _ _ +
-------------------------------
+ _ _ _ + 5 _ o + _ _ _ +
+ o
5 _ + _ o _ +
5 _ o +
+
5 5 _ + o _ o +
5 _
5 +
-------------------------------
+
5 5 o + _
5 5 + o _ _ +
+ _ o _ + _ _ _ + _ 5 _ +
+ o
5 _ + _ o
5 + _ _ o +
-------------------------------
Nous allons maintenant regarder les configs possibles pour le chiffre 5 :
Il en existe deux que nous marquerons respectivement en
violet et en
rouge :
-------------------------------
+ o _ _ + _ o
5 +
5 _ o +
+ _ o _ + _
5 5 +
5 o
5 +
+ _ _ 5 + _ _ _ + o _ _ +
-------------------------------
+ _ _ _ + 5 _ o + _ _ _ +
+ o
5 _ + _ o _ +
5 _ o +
+
5 5 _ + o _ o +
5 _
5 +
-------------------------------
+
5 5 o + _
5 5 + o _ _ +
+ _ o _ + _ _ _ + _ 5 _ +
+ o
5 _ + _ o
5 + _ _ o +
-------------------------------
Pour tous les candidats restés en bleu, on constate que lorsque l'on tente de construire une config passant par eux, on aboutit très rapidement a des contradictions, on peut donc tous les supprimer !
Une fois ces opérations effectuées, on est certains qu'il n'existe plus aucun raisonnement basé uniquement sur le chiffre 5 qui nous premettent de supprimer de nouveaux candidats : en effet, chaque emplacement fait maintenant partie d'une config respectant toutes les règles de placement et pouvant très bien participer a la solution de la grille. On ne pourra avancer qu'en utilisant des techniques impliquant d'autres chiffres que le 5.
Le tableau final des 5 :
-------------------------------
+ o _ _ + _ o
5 +
5 _ o +
+ _ o _ + _
5 _ + _ o
5 +
+ _ _ 5 + _ _ _ + o _ _ +
-------------------------------
+ _ _ _ + 5 _ o + _ _ _ +
+ o
5 _ + _ o _ +
5 _ o +
+
5 _ _ + o _ o + _ _
5 +
-------------------------------
+
5 _ o + _
5 _ + o _ _ +
+ _ o _ + _ _ _ + _ 5 _ +
+ o
5 _ + _ o
5 + _ _ o +
-------------------------------
Pour les amateurs, il s'agissait ici d'une configuration de "jellyfish" ou "méduse" en francais.
Pratique : Quand on voit ca, on se dit : c'est très joli, mais comment faire pour lister toutes ces configs avec mon papier et mon crayon et ensuite les superposer pour voir quels candidats restent sur le carreau ?
En fait, ce n'est pas si difficile : Il suffit de montrer pour chaque candidat qu'il existe une config passant par lui pour qu'on soit certains de le garder.
La différence avec les autres techniques est que l'on va determiner systématiquement "qui on garde" au lieu de rechercher "qui on supprime". C'est d'ailleurs cela qui fait que la technique de superposition est systématique alors que les autres non.
Je vais illustrer la méthode de recherche systématique par un exemple tiré de
"Grille Extra 66" ou j'ai appliqué cette méthode.
Après les premiers placements, on parvient au tableau des candidats suivant :
| Code: |
o ! ....A ....B ....C ! .....D .....E .....F ! ...G ....H ...I !
o o-------------------o----------------------o-----------------!
1 ! ....2 ....9 13468 ! ...367 ..1678 ..3678 ! ...5 ..478 .348 !
2 ! ...78 ..378 ..138 ! .....4 ..1789 .....5 ! 2379 ....6 .238 !
3 ! 45678 .3678 34568 ! .23679 ..6789 236789 ! .379 .4789 ...1 !
o o-------------------o----------------------o-----------------!
4 ! ..678 .3678 ....9 ! ..3567 ..5678 .....4 ! ...1 ....2 .358 !
5 ! ....1 ..368 .3468 ! ..3569 .....2 ..3689 ! ..39 .4589 ...7 !
6 ! ..478 ....5 ....2 ! .....1 ...789 ..3789 ! ...6 ..489 .348 !
o o-------------------o----------------------o-----------------!
7 ! ....3 ....2 ..568 ! ..5679 .45679 ...679 ! ..48 ....1 ..56 !
8 ! ....9 ....4 ...56 ! .....8 .....3 .....1 ! ..27 ...57 .256 !
9 ! ..568 ....1 ....7 ! ...256 ...456 ....26 ! ..48 ....3 ...9 !
o o-------------------o----------------------o-----------------! |
Nous allons effectuer la recherche systématique pour les 4 premiers chiffres.
Comme le principe de base est de rechercher "qui on conserve", on va procéder par pointage : Quand un candidat est reconnu comme appartenant a au moins une config, on le pointe.
On va ainsi procéder par ellimination jusqu'à trouver les candidats que l'on ne peut pas pointer. Ici, le pointage se materialisera par la couleur rouge.
les 1 : -------------------------------
+ _ _
1 + _
1 _ + _ _ _ +
+ _ _
1 + _
1 _ + _ _ _ +
+ _ _ _ + _ _ _ + _ _ 1 +
-------------------------------
+ _ _ _ + _ _ _ + 1 _ _ +
+ 1 _ _ + _ _ _ + _ _ _ +
+ _ _ _ + 1 _ _ + _ _ _ +
-------------------------------
+ _ _ _ + _ _ _ + _ 1 _ +
+ _ _ _ + _ _ 1 + _ _ _ +
+ _ 1 _ + _ _ _ + _ _ _ +
-------------------------------
La, c'est facile, on a deux configs qui forment une croix et on peut pointer nos 1 les yeux fermés. Le repérage de ce genre de figure peut largement alléger la tache de pointage.
=> On pointe tout le monde.
Les 2 maintenant : -------------------------------
+ 2 _ _ + _ _ _ + _ _ _ +
+ _ _ _ + _ _ _ +
2 _
2 +
+ _ _ _ +
2 _
2 + _ _ _ +
-------------------------------
+ _ _ _ + _ _ _ + _ 2 _ +
+ _ _ _ + _ 2 _ + _ _ _ +
+ _ _ 2 + _ _ _ + _ _ _ +
-------------------------------
+ _ 2 _ + _ _ _ + _ _ _ +
+ _ _ _ + _ _ _ +
2 _
2 +
+ _ _ _ +
2 _
2 + _ _ _ +
-------------------------------
Cette fois on a deux rectangles qui forment deux systèmes indépendants (bleu et violet). On peut tout cocher sans trop réfléchir (a part peut-être la première fois).
=> On pointe tout le monde
Les 3 :
-------------------------------
+ _ _
3 +
3 _
3 + _ _
3 +
+ _
3 3 + _ _ _ +
3 _
3 +
+ _
3 3 +
3 _
3 +
3 _ _ +
-------------------------------
+ _
3 _ +
3 _ _ + _ _
3 +
+ _
3 3 +
3 _
3 +
3 _ _ +
+ _ _ _ + _ _
3 + _ _
3 +
-------------------------------
+ 3 _ _ + _ _ _ + _ _ _ +
+ _ _ _ + _ 3 _ + _ _ _ +
+ _ _ _ + _ _ _ + _ 3 _ +
-------------------------------
La, ca commence a être un peu plus délicat, on prend une première config :
-------------------------------
+ _ _
3 +
3 _
3 + _ _
3 +
+ _
3 3 + _ _ _ +
3 _
3 +
+ _
3 3 +
3 _
3 +
3 _ _ +
-------------------------------
+ _
3 _ +
3 _ _ + _ _
3 +
+ _
3 3 +
3 _
3 +
3 _ _ +
+ _ _ _ + _ _
3 + _ _
3 +
-------------------------------
+ 3 _ _ + _ _ _ + _ _ _ +
+ _ _ _ + _ 3 _ + _ _ _ +
+ _ _ _ + _ _ _ + _ 3 _ +
-------------------------------
Dans les maisons M1/M2/M3, on voit assez facilement qu'on pourra trouver des configs incluant tous les candidats oranges : on peut donc cocher tout ce qui est rouge et tout ce qui est orange.
-------------------------------
+ _ _
3 +
3 _
3 + _ _
3 +
+ _
3 3 + _ _ _ +
3 _
3 +
+ _
3 3 +
3 _
3 +
3 _ _ +
-------------------------------
+ _
3 _ +
3 _ _ + _ _
3 +
+ _
3 3 +
3 _
3 +
3 _ _ +
+ _ _ _ + _ _
3 + _ _
3 +
-------------------------------
+ 3 _ _ + _ _ _ + _ _ _ +
+ _ _ _ + _ 3 _ + _ _ _ +
+ _ _ _ + _ _ _ + _ 3 _ +
-------------------------------
On peut continuer et cocher encore tout ce qui est en rouge et en orange.
-------------------------------
+ _ _
3 +
3 _
3 + _ _
3 +
+ _
3 3 + _ _ _ +
3 _
3 +
+ _
3 3 +
3 _
3 +
3 _ _ +
-------------------------------
+ _
3 _ +
3 _ _ + _ _
3 +
+ _
3 3 +
3 _
3 +
3 _ _ +
+ _ _ _ + _ _
3 + _ _
3 +
-------------------------------
+ 3 _ _ + _ _ _ + _ _ _ +
+ _ _ _ + _ 3 _ + _ _ _ +
+ _ _ _ + _ _ _ + _ 3 _ +
-------------------------------
Puis
-------------------------------
+ _ _
3 +
3 _
3 + _ _
3 +
+ _
3 3 + _ _ _ +
3 _
3 +
+ _
3 3 +
3 _
3 +
3 _ _ +
-------------------------------
+ _
3 _ +
3 _ _ + _ _
3 +
+ _
3 3 +
3 _
3 +
3 _ _ +
+ _ _ _ + _ _
3 + _ _
3 +
-------------------------------
+ 3 _ _ + _ _ _ + _ _ _ +
+ _ _ _ + _ 3 _ + _ _ _ +
+ _ _ _ + _ _ _ + _ 3 _ +
-------------------------------
Ca y est, tout le monde a été coché. On est maintenant certains qu'il n'y a rien a tirer des 3 pour le moment.
Ou ca devient plus intéressant : les 4 -------------------------------
+ _ _
4 + _ _ _ + _
4 4 +
+ _ _ _ + 4 _ _ + _ _ _ +
+
4 _
4 + _ _ _ + _
4 _ +
-------------------------------
+ _ _ _ + _ _ 4 + _ _ _ +
+ _ _
4 + _ _ _ + _
4 _ +
+
4 _ _ + _ _ _ + _ _
4 +
-------------------------------
+ _ _ _ + _
4 _ +
4 _ _ +
+ _ 4 _ + _ _ _ + _ _ _ +
+ _ _ _ + _
4 _ +
4 _ _ +
-------------------------------
En orange on a un rectangle indépendant du reste
En rouge et violet deux configs possible.
La ou ca devient interessant, c'est qu'il reste deux candidats en bleu qu'on ne parvient pas a faire rentrer dans une config. Une méthode de swapage loumtomien peut venir confirmer qu'effectivement, ce sont des candidats a supprimer.
Bon... Je crois que vous avez le principe général. C'est vrai que c'est peut-etre un peu lourd, mais ca reste quand meme un simple pointage tout a fait faisable sur papier.
Par ailleurs, vu que cette méthode a un coté systématique, je pense qu'elle est a conseiller dès qu'une grille résiste un peu, ne serais-ce que pour ne pas chercher des X-Wing ou des étals de poissonniers la ou il n'y en a pas !
En bonus, si vous avez aprécié mes petites grilles coloriées, je vous en laisse une vierge pour faire des copier-coller.
-------------------------------
+ _ _ _ + _ _ _ + _ _ _ +
+ _ _ _ + _ _ _ + _ _ _ +
+ _ _ _ + _ _ _ + _ _ _ +
-------------------------------
+ _ _ _ + _ _ _ + _ _ _ +
+ _ _ _ + _ _ _ + _ _ _ +
+ _ _ _ + _ _ _ + _ _ _ +
-------------------------------
+ _ _ _ + _ _ _ + _ _ _ +
+ _ _ _ + _ _ _ + _ _ _ +
+ _ _ _ + _ _ _ + _ _ _ +
-------------------------------
Cordialement,
Papa.
portail 
Accueil 
Grilles en lignes 
Tournois du forum 
Dernières images 
Rechercher 
S'enregistrer 
Connexion 
