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

SUDOKU VARIANTE


 
portailportail  AccueilAccueil  Grilles en lignesGrilles en lignes  Tournois du forumTournois du forum  Dernières imagesDernières images  RechercherRechercher  S'enregistrerS'enregistrer  ConnexionConnexion  
Le Deal du moment : -43%
-100€ Pack rééquipement Philips Hue ...
Voir le deal
129.99 €

 

 Le pointage des "bons candidats" (PAPA.01)

Aller en bas 
AuteurMessage
Admin
Admin
Admin


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

Le pointage des "bons candidats" (PAPA.01) Empty
MessageSujet: Le pointage des "bons candidats" (PAPA.01)   Le pointage des "bons candidats" (PAPA.01) EmptyMer Juin 24 2009, 22:03

papa
Sudoka Expert
Le pointage des "bons candidats" (PAPA.01) RangExpert


Inscrit le: 08 Juin 2006
Messages: 169


Posté 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.
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
Admin
Admin
Admin


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

Le pointage des "bons candidats" (PAPA.01) Empty
MessageSujet: Re: Le pointage des "bons candidats" (PAPA.01)   Le pointage des "bons candidats" (PAPA.01) EmptyMer Oct 28 2009, 19:24

papa
Sudoka Expert
Le pointage des "bons candidats" (PAPA.01) RangExpert


Inscrit le: 08 Juin 2006
Messages: 169


Posté le: Mar 25/07/2006 15:43

Un petit ajout concernant cette technique :

Si l'on admet l'unicité de la solution et que l'on n'estime pas moralement répréhensible d'utiliser des techniques de type "rectangle interdit", on peut se servir de cette méthode pour elliminer quelques configs et quelques candidats supplémentaires, je m'explique :

Si nous avons un chiffre formant ce type de rectangle sans autre alternative possible que de passer par l'un des deux diagonales :

-------------------------------
+ _ _ 1 + _ 1 _ + _ _ _ +
+ _ _ 1 + _ 1 _ + _ _ _ +
+ _ _ _ + _ _ _ + _ _ 1 +
-------------------------------
+ _ _ _ + _ _ _ + 1 _ _ +
+ 1 _ _ + _ _ _ + _ _ _ +
+ _ _ _ + 1 _ _ + _ _ _ +
-------------------------------
+ _ _ _ + _ _ _ + _ 1 _ +
+ _ _ _ + _ _ 1 + _ _ _ +
+ _ 1 _ + _ _ _ + _ _ _ +
-------------------------------

Ce rectangle devient alors "interdit" pour tous les autres chiffres, ce qui signifie que toute config comprenant l'une ou l'autre des diagonales devra être bannie.

Par exemple (toujours en prenant l'exemple traité précedemment), toutes les configs de 8 passant par :

-------------------------------
+ _ _ _ + _ 8 _ + _ _ _ +
+ _ _ 8 + _ _ _ + _ _ _ +
+ _ _ _ + _ _ _ + _ _ _ +
-------------------------------
+ _ _ _ + _ _ _ + _ _ _ +
+ _ _ _ + _ _ _ + _ _ _ +
+ _ _ _ + _ _ _ + _ _ _ +
-------------------------------
+ _ _ _ + _ _ _ + _ _ _ +
+ _ _ _ + _ _ _ + _ _ _ +
+ _ _ _ + _ _ _ + _ _ _ +
-------------------------------
ou bien par
-------------------------------
+ _ _ 8 + _ _ _ + _ _ _ +
+ _ _ _ + _ 8 _ + _ _ _ +
+ _ _ _ + _ _ _ + _ _ _ +
-------------------------------
+ _ _ _ + _ _ _ + _ _ _ +
+ _ _ _ + _ _ _ + _ _ _ +
+ _ _ _ + _ _ _ + _ _ _ +
-------------------------------
+ _ _ _ + _ _ _ + _ _ _ +
+ _ _ _ + _ _ _ + _ _ _ +
+ _ _ _ + _ _ _ + _ _ _ +
-------------------------------
devront être bannies.

On note au passage une application assez interessante qui vient élargir la notion de rectangle interdit :

Prenons un chiffre dont les cadidats ont cette configuration sur le premier bloc vertical :

-------------------------------
+ 4 _ 4 + _ _ _ + _ _ _ +
+ _ _ _ + _ _ _ + _ _ _ +
+ _ _ _ + _ _ _ + _ _ _ +
-------------------------------
+ _ 4 4 + _ _ _ + _ _ _ +
+ _ _ _ + _ _ _ + _ _ _ +
+ _ _ _ + _ _ _ + _ _ _ +
-------------------------------
+ 4 4 _ + _ _ _ + _ _ _ +
+ _ _ _ + _ _ _ + _ _ _ +
+ _ _ _ + _ _ _ + _ _ _ +
-------------------------------

Toute config d'un autre chiffre passant par

-------------------------------
+ 7 _ _ + _ _ _ + _ _ _ +
+ _ _ _ + _ _ _ + _ _ _ +
+ _ _ _ + _ _ _ + _ _ _ +
-------------------------------
+ _ _ 7 + _ _ _ + _ _ _ +
+ _ _ _ + _ _ _ + _ _ _ +
+ _ _ _ + _ _ _ + _ _ _ +
-------------------------------
+ _ 7 _ + _ _ _ + _ _ _ +
+ _ _ _ + _ _ _ + _ _ _ +
+ _ _ _ + _ _ _ + _ _ _ +
-------------------------------
ou bien par
-------------------------------
+ _ _ 7 + _ _ _ + _ _ _ +
+ _ _ _ + _ _ _ + _ _ _ +
+ _ _ _ + _ _ _ + _ _ _ +
-------------------------------
+ _ 7 _ + _ _ _ + _ _ _ +
+ _ _ _ + _ _ _ + _ _ _ +
+ _ _ _ + _ _ _ + _ _ _ +
-------------------------------
+ 7 _ _ + _ _ _ + _ _ _ +
+ _ _ _ + _ _ _ + _ _ _ +
+ _ _ _ + _ _ _ + _ _ _ +
-------------------------------
doit être bannie.

Ca donne d'ailleurs à réfléchir sur des configuration de type RI qui ne seraient pas des rectangles... Mais ca fera l'objet d'un fiche séparée.
Revenir en haut Aller en bas
https://sudokuvariante.forumactif.com
 
Le pointage des "bons candidats" (PAPA.01)
Revenir en haut 
Page 1 sur 1
 Sujets similaires
-
» Des RI pas très rectangulaires (PAPA.02)
» Les Chemins Privés (PAPA.03)
» GN09 grilles à thème "multi fishes"
» L'etude des blocs par tableau simplifié (PAPA.04)
» "Samourai" ou comment se faire harakiri !

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