Grilles Extra n°05-06

Admin
Admin

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

Grilles Extra n°05-06 Empty

Dernière édition par Admin le Dim Juin 28 2009, 15:24, édité 1 fois

Sujet: Grilles Extra n°05-06 Grilles Extra n°05-06 Empty

Mer Juin 24 2009, 11:55

papyg
Admin
Admin

Inscrit le: 11 Oct 2005
Messages: 1127

Posté le: Mer 21/12/2005 15:44 Sujet du message: Grilles Extra n°05-06

Et voici deux nouvelles grilles extrêmement difficiles :

Extra 05

Code:

+-------+-------+-------+

| . . . | . . . | . 6 5 |

| 7 . . | . . . | . 8 . |

| . . . | 4 1 8 | . 3 . |

+-------+-------+-------+

| . . 5 | 3 . . | 6 . 9 |

| . . 3 | . . . | 2 . . |

| 8 . 1 | . . 7 | 3 . . |

+-------+-------+-------+

| . 8 . | 9 3 5 | . . . |

| . 6 . | . . . | . . 1 |

| 5 4 . | . . . | . . . |

+-------+-------+-------+

Extra 06

Code:

+-------+-------+-------+

| . . . | 1 5 3 | . . . |

| . . 1 | . . . | 4 2 . |

| . 6 9 | . . . | . 7 1 |

+-------+-------+-------+

| 8 . . | . . . | . . 3 |

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

| 4 . . | . . . | . . 7 |

+-------+-------+-------+

| 6 4 . | . . . | 9 1 . |

| . 7 5 | . . . | 8 . . |

| . . . | 4 2 8 | . . . |

+-------+-------+-------+

Va falloir s'arracher !

papyg

Admin
Admin

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

Grilles Extra n°05-06 Empty

Sujet: Re: Grilles Extra n°05-06 Grilles Extra n°05-06 Empty

Mer Juin 24 2009, 22:00

gaston97
Sudoka Débutant

Inscrit le: 20 Déc 2005
Messages: 1

Posté le: Mer 21/12/2005 17:59 Sujet du message:

bonjour à tous, voilà deux grilles intéressantes j'ai résolu la 1ère en 12 minutes (j'utilise un tableur pour calculer les candidats restant, mais pour le reste, je fais tout à la main) HINT: quand vous serez bloqués après 30 coups, testez le 2 successivement dans les cases B4 et B6, il y a alors une case qui prend la même valeur; cette dernière case remplie débloque la grille la 2ème m'a demandé un peu moins de 20 minutes : elle est sensiblement plus difficile que la précédente; là aussi un test sur une valeur successivement dans deux cases la débloque (la valeur c'est le 2, les cases ...) bien sûr ces solutions ne sont pas uniques ni même probablement les meilleures, mais ce sont les premières!

Admin
Admin

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

Grilles Extra n°05-06 Empty

Sujet: Re: Grilles Extra n°05-06 Grilles Extra n°05-06 Empty

Dim Juin 28 2009, 15:27

papyg
Admin
Admin

Inscrit le: 11 Oct 2005
Messages: 1127

Posté le: Lun 26/12/2005 19:03 Sujet du message:

C'est vrai qu'avec l'aide d'un tableur qui vous donne tout cuit les possibilités restantes et en particulier les cases ou chiffres n'ayant plus qu'une possibilité, parfois difficiles à dénicher, cela beaucoup plus vite.

Avez-vous une estimation du temps que vous auriez mis avec juste un crayon et une gomme ? Et comment ces grilles se comparent-elles, suivant votre critère "temps" par rapport à d'autres "diaboliques", "infernales", ect... ?

De même, repérer une case invariante quelle que soit une ou deux cases de départ est assez laborieux sans tableur.

D'autres ont-ils trouvé des stratégies plus ou moins faciles à mettre en oeuvre ?

Pour la grille Extra 05, la situation sur laquelle on bute est la suivante :

Code:

A B C D E F G H I

+----------------+----------------+----------------+

| 9 1 8 | 27 27 3 | 4 6 5 |

| 7 3 4 | 56 569 69 | 1 8 2 |

| 2 5 6 | 4 1 8 | 9 3 7 |

+----------------+----------------+----------------+

| 4 27 5 | 3 8 12 | 6 17 9 |

| 6 79 3 | 15 459 149 | 2 17 8 |

| 8 29 1 | 26 269 7 | 3 5 4 |

+----------------+----------------+----------------+

| 1 8 2 | 9 3 5 | 7 4 6 |

| 3 6 79 | 8 247 24 | 5 29 1 |

| 5 4 79 | 1267 267 126 | 8 29 3 |

+----------------+----------------+----------------+

Je suppose que votre solution à partir de là est :

B4=2 --> F4=1 --> D5=5 --> D2=6 --> F2=9

B6=2 --> D6=6 --> E6=9, D2=5 --> F2=9

Voici celle que j'avais trouvée; dans ce type de blocage, j'essaie en général une case près du centre n'ayant que 2 possibilités, ici F4 :

F4=2 --> D6=6, F8=4

--> D2=5, E6=9

--> D5=1 ET F5=1, impossible

Donc F4<>2, et le reste est facile.

La solution proposée par mon solveur est l'occasion de présenter une autre technique, celle de la "boucle bi-directionnelle", qui permet d'éliminer des possibilités.

Voici le raisonnement :

Supposons F4=2. On en déduit :

D6=6 --> D2=5 --> D5=1 --> F4=2.

On peut aussi partir de F4=1 et tourner en sens inverse.

C'est une boucle bi-directionnelle pour laquelle chaque maillon de la boucle doit contenir une valeur particulière à l'une des extrémités, et les cases liées (même ligne, colonne ou bloc/maison) aux extrémités de chaque maillon ne peuvent contenir cette valeur :

F4 ou D6 doit contenir 2, donc 2 peut être éliminé de E6

D6 ou D2 doit contenir 6, donc 6 peut être éliminé de D9

D2 ou D5 doit contenir 5

D5 ou F4 doit contenir 1

Cela ne suffit pas ici pour terminer la grille, puisqu'il a fallu au solveur un deuxième coup de boucle bi-directionnelle puis un XY-wing pour en venir à bout, mais c'est une technique qui peut être utile et ne semble pas trop compliquée à mettre en oeuvre.

Pour la grille Extra 06, le point bloquant était:

Code:

A B C D E F G H I

+-------------+-------------+-------------+

| 7 2 4 | 1 5 3 | 6 8 9 |

| 3 8 1 | 7 6 9 | 4 2 5 |

| 5 6 9 | 28 48 24 | 3 7 1 |

+-------------+-------------+-------------+

| 8 59 26 | 25 14 47 | 125 69 3 |

| 1 35 27 | 9 37 6 | 25 4 8 |

| 4 35 26 | 38 18 25 | 125 69 7 |

+-------------+-------------+-------------+

| 6 4 8 | 35 37 57 | 9 1 2 |

| 2 7 5 | 6 9 1 | 8 3 4 |

| 9 1 3 | 4 2 8 | 7 5 6 |

+-------------+-------------+-------------+

Je suppose que vous êtes parti de C4/C6 pour montrer que D5 était invariant (je ne précise pas plus, pour laisser à tous le plaisir de trouver le cheminement).

En partant de la case F6, j'avais trouvé :

F6=5 --> D4=2 --> D3=8

F6=5 --> B6=3 --> D6=8, impossible

Donc F6<>5, et le reste est facile.

Là encore, mon solveur n'a pas été bien brillant et a dû faire appel à trois chaînes/boucles forcées.

Quelqu'un a t'il trouvé mieux ?

papyg

Admin
Admin

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

Grilles Extra n°05-06 Empty

Sujet: Re: Grilles Extra n°05-06 Grilles Extra n°05-06 Empty

Dim Juin 28 2009, 15:27

Arzbie
Sudoka Débutant

Inscrit le: 16 Sep 2005
Messages: 19

Posté le: Lun 26/12/2005 21:44 Sujet du message:

papyg a écrit:

De même, repérer une case invariante quelle que soit une ou deux cases de départ est assez laborieux sans tableur.

D'autres ont-ils trouvé des stratégies plus ou moins faciles à mettre en oeuvre ?

Pour la grille Extra 05, la situation sur laquelle on bute est la suivante :

Code:

A B C D E F G H I

+----------------+----------------+----------------+

| 9 1 8 | 27 27 3 | 4 6 5 |

| 7 3 4 | 56 569 69 | 1 8 2 |

| 2 5 6 | 4 1 8 | 9 3 7 |

+----------------+----------------+----------------+

| 4 27 5 | 3 8 12 | 6 17 9 |

| 6 79 3 | 15 459 149 | 2 17 8 |

| 8 29 1 | 26 269 7 | 3 5 4 |

+----------------+----------------+----------------+

| 1 8 2 | 9 3 5 | 7 4 6 |

| 3 6 79 | 8 247 24 | 5 29 1 |

| 5 4 79 | 1267 267 126 | 8 29 3 |

+----------------+----------------+----------------+

Je suppose que votre solution à partir de là est :

B4=2 --> F4=1 --> D5=5 --> D2=6 --> F2=9

B6=2 --> D6=6 --> E6=9, D2=5 --> F2=9

Je ne me rapelle plus très bien, mais je crois avoir utilisé un autre chemin.

En fait, j'ai d'abord fait un essai sur une des cases de la maison 2 (je crois), qui m'a mené à une contradiction ; je savais donc que c'était l'autre valeur que devait prendre cette case de départ, mais je me suis entêté à trouver un raisonnement qui, partant des différentes possibilités d'une des cases où j'avais abouti à une contradiction, prouvait que la case de départ ne pouvait prendre que la bonne valeur.

Après quoi, j'ai utilisé cette valeur l'esprit tranquille pour finir.

Mais je ne peux pas être plus précis, depuis j'ai fait la Extra_06 et la 162-4...

papyg a écrit:

Pour la grille Extra 06, le point bloquant était:

Code:

A B C D E F G H I

+-------------+-------------+-------------+

| 7 2 4 | 1 5 3 | 6 8 9 |

| 3 8 1 | 7 6 9 | 4 2 5 |

| 5 6 9 | 28 48 24 | 3 7 1 |

+-------------+-------------+-------------+

| 8 59 26 | 25 14 47 | 125 69 3 |

| 1 35 27 | 9 37 6 | 25 4 8 |

| 4 35 26 | 38 18 25 | 125 69 7 |

+-------------+-------------+-------------+

| 6 4 8 | 35 37 57 | 9 1 2 |

| 2 7 5 | 6 9 1 | 8 3 4 |

| 9 1 3 | 4 2 8 | 7 5 6 |

+-------------+-------------+-------------+

...

Donc F6<>5, et le reste est facile.

papyg

Objection : moi j'ai 359 en B6 à ce stade ; faute de frappe ?

Là j'ai réussi à remplir les cases H4 H6 B4 et C6, mais j'étais encore bloqué.

Ensuite c'est G5 qui ne pouvait valoir que 2, quelque soit l'hypothèse sur les valeurs d'une autre case, mais ne me demandez pas laquelle (peut-être D3 ?) Embarassed

Tout à la main (à part la mise au propre de l'état de bloquage) ça m'a pris... un temps certain !

JJB

Admin
Admin

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

Grilles Extra n°05-06 Empty

Sujet: Re: Grilles Extra n°05-06 Grilles Extra n°05-06 Empty

Dim Juin 28 2009, 15:28

papyg
Admin
Admin

Inscrit le: 11 Oct 2005
Messages: 1127

Posté le: Mar 27/12/2005 12:48 Sujet du message: Solution de la grille Extra 06

Arzbie a tout a fait raison, j'ai dû faire une fausse manip car les possibilités restantes en B6 sont bien 359... --> et ça fiche en l'air ma solution ! (je m'étonnais d'ailleurs d'en avoir trouvé une aussi simple...) papyg

Admin
Admin

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

Grilles Extra n°05-06 Empty

Sujet: Re: Grilles Extra n°05-06 Grilles Extra n°05-06 Empty

Dim Juin 28 2009, 15:28

PhB
Sudoka Expert

Inscrit le: 14 Déc 2005
Messages: 369

Posté le: Jeu 29/12/2005 22:24 Sujet du message:

Pour resoudre ce genre de grille, japplique une methode « bestiale » qui peut aider dans certains cas particuliers. Cette methode consiste a reperer des paires alternees (de type (a,b) sur 2 cases) parmi les cases non resolues, en ligne, colonne ou maison. Si une telle paire est trouvee, elle debloque la situation, en general (mais pas toujours).

Application

Grille 05 apres le 46eme coup:

Code:

A B C D E F G H I

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

1 | 9 1 8 | 27 27 3 | 4 6 5 |

2 | 7 3 4 | 56 569 69 | 1 8 2 |

3 | 2 5 6 | 4 1 8 | 9 3 7 |

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

4 | 4 27 5 | 3 8 12 | 6 17 9 |

5 | 6 79 3 | 15 459 149 | 2 17 8 |

6 | 8 29 1 | 26 269 7 | 3 5 4 |

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

7 | 1 8 2 | 9 3 5 | 7 4 6 |

8 | 3 6 79 | 8 247 24 | 5 29 1 |

9 | 5 4 79 | 1267 267 126 | 8 29 3 |

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

Je minteresse a la ligne 8 qui possede 4 cases non resolues :

Code:

A B C D E F G H I

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

8 | 3 6 79 | 8 247 24 | 5 29 1 |

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

1/ Je repere les chiffres restant a placer (dans lordre) : 2,4,7,9

2/ Je repere toutes les combinaisons 2 a 2 : 2/4, 2/7, 2/9, 4/7, 4/9, 7/9

3/ Je compte toutes les combinaisons 2 a 2 ayant 2 occurrences : 2/4 (en E8 et F8 ) et cest la seule !

4/ Je reduis : ici le 7 est exclu de E8 et jelimine tous les 2 et les 4 en dehors de E8 et F8

Jobtiens ceci :

Code:

A B C D E F G H I

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

8 | 3 6 79 | 8 24 24 | 5 9 1 |

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

etc

Cette technique ne permet pas daller jusquau bout. Plus tard, on tombe sur la situation suivante :

Code:

A B C D E F G H I

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

5 | 6 79 3 | 15 459 149 | 2 17 8 |

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

quon resoud en remarquant quon ne peut faire quune seule paire alternee 4/9, ce qui donne B5=7

Nota Bene

Cette technique ne marche pas toujours. Cependant, elle est interessante car systematique et ne requiert pas de « visualiser » de configurations particulieres.
_________________
PhB

Admin
Admin

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

Grilles Extra n°05-06 Empty

Sujet: Re: Grilles Extra n°05-06 Grilles Extra n°05-06 Empty

Dim Juin 28 2009, 15:28

papyg
Admin
Admin

Inscrit le: 11 Oct 2005
Messages: 1127

Posté le: Jeu 29/12/2005 23:16 Sujet du message: Technique "bestiale" ou "empirique" ?

La technique utilisée par PhB semble empirique (ça marche mais pas toujours) et sauf démonstration que je ne vois pas, n'a aucun fondement théorique. Elle peut donc aussi mener à des éliminations intempestives et des impasses. En ce sens, cela me paraît relever de l'essai-erreur et pas de la résolution logique. Le problème n'est pas en général de trouver LA solution de la grille (beaucoup de programmes "bestiaux" savent le faire très bien), mais de trouver une voie "logique" évitant dans toute la mesure du possible de faire des choix "au hasard". Ceci étant, le sudoku est un jeu, et l'essentiel est d'y trouver son plaisir. papyg

Admin
Admin

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

Grilles Extra n°05-06 Empty

Sujet: Re: Grilles Extra n°05-06 Grilles Extra n°05-06 Empty

Dim Juin 28 2009, 15:29

PhB
Sudoka Expert

Inscrit le: 14 Déc 2005
Messages: 369

Posté le: Sam 31/12/2005 0:47 Sujet du message:

Jaurais du etre plus clair sur mes intentions. Lobjectif etait de reduire une quadruplette (serie de 4 chiffres non encore places dans 4 cases), si cest possible. Dans un stade devolution du jeu, chaque case peut accepter plusieurs chiffres et, selon le cas, on pourra reduire (ou non) la position. Si la position est reductible, alors on peut mettre en evidence une doublette (au moins) et 2 doublettes (au plus). On peut avoir : 1. 1 seule doublette et 2 chiffres places 2. 2 doublettes Une position non reductible aura : 1. aucune doublette (indetermination) 2. plus de 2 doublettes (trop complique) il faut se tourner alors vers une autre technique. Donc, oui, il peut y avoir des impasses. Par contre, je ne comprends pas votre conclusion. Le procede de reduction est parfaitement logique (et explique). Prenez-moi en defaut la-dessus si vous y trouvez a redire. Cela dit, ce nest pas le fil a couper le beurre, jen conviens. A mon niveau, cest la seule facon que jaie trouve pour men sortir. Je vous souhaite de bonnes fetes et rendez-vous en 2006. _________________ PhB

Admin
Admin

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

Grilles Extra n°05-06 Empty

Sujet: Re: Grilles Extra n°05-06 Grilles Extra n°05-06 Empty

Dim Juin 28 2009, 15:29

Elise
Sudoka Initié

Inscrit le: 13 Juil 2006
Messages: 37

Posté le: Lun 17/07/2006 13:40 Sujet du message:

Concernant la grille 05 : Je me suis trouvée bloquée au stade qu'indique Papyg. Je n'ai pas trouvé de "XWing", ni "XYWing", pas de coloriage possible (du moins je n'ai pas trouvé). Ne connaissant pas d'autres techniques, j'ai appliqué ma petite cuisine réservée aux cas difficiles. Voici comment j'ai procédé : Je considère la case D5, où les seuls candidats restant sont 1 ou 5. Qu'on choisisse l'un ou l'autre, le candidat 9 est éliminé des cases E2 et F5, ce qui permet de terminer la grille facilement. Je ne sais pas si cette méthode est orthodoxe ou pas, mais elle est souvent efficace. Elise

Admin
Admin

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

Grilles Extra n°05-06 Empty

Sujet: Re: Grilles Extra n°05-06 Grilles Extra n°05-06 Empty

Dim Juin 28 2009, 15:30

didier90
Sudoka Expert

Grilles Extra n°05-06 19245133384744aaa7d6461

Inscrit le: 22 Mar 2006
Messages: 622
Localisation: belfort (90) et bubry(56)

Posté le: Lun 17/07/2006 14:17 Sujet du message:

bonjour a elise j'ai regardé cette grille que je ne connaissait pas la méthode que tu utilise est bien sur non critiquable mais pour moi doit être employée que quand on est au pied du mur est que toutes les autres techniques ne sont pas utilisables. pour cette grille en utilisant les techniques du RI xy chain (en plusieurs exemplaires) et le bug ou l'huître perlière on arrivera aussi au résultat didier

Admin
Admin

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

Grilles Extra n°05-06 Empty

Sujet: Re: Grilles Extra n°05-06 Grilles Extra n°05-06 Empty

Dim Juin 28 2009, 15:30

Elise
Sudoka Initié

Inscrit le: 13 Juil 2006
Messages: 37

Posté le: Lun 17/07/2006 14:54 Sujet du message:

Merci ! J'étais au pied du mur ! En effet, ce n'est pas tout à fait satisfaisant pour l'esprit... Je ne connais pas ces techniques du RI et xy chain, je vais tâcher de comprendre comment ça marche. C'est d'ailleurs dans ce but que je me suis inscrite sur le forum. Elise

Contenu sponsorisé

Sujet: Re: Grilles Extra n°05-06