S'identifier           S'inscrire

assistant-sudoku.com

Grille Sudoku résolue

La grille -664
Grille de niveau 12 conventionnel à solution unique.



Afficher les commentaires


Commentaires sur cette grille

De Paolo
(Publié le 16/03/2020)

Bonjour 1)10 placements par les TB initiales. P(7L5C1)=>couvre la grille 2)P(7L5C9).P(3L3C8)=>contradiction 3)P(7L5C9).P(6L3C8)=>contradiction=>solution. ou 1)10 placements par les TB initiales. P(3L3C7)=>couvre la grille 2)P(3L3C8)=>contradiction 3)P(3L3C3)=>contradiction=>solution.

De Francis Labetoulle
(Publié le 17/03/2020)

Bonjour à tous En essayant d'exploiter les présences élevées de liens forts dans B1,L3 et C1 j'obtiens : P(3L3C3) invalide. P(3L1C1).P (4L1C2) invalide et P(3L1C1).P(4 L1C9) couvre la grille, avec nécessité d'utiliser un triplet caché dans C9 et une interaction bloc bloc des 9 libérant 8L4C7. Taille 2 en attendant mieux? Merci à Robert de nous proposer ces grilles en cette période difficile.

De François C.
(Publié le 17/03/2020)

Bonsoir, 10 candidats uniques puis un abattement de la grille à petits coups de canif: P(6L1C1) => (48)B1 , 7L2C1 => L5C1 vide => -6L1C1 P(6L9C8) => 3L3C8, 3L1C1, 1L9C9 => 3L9 vide => -6L9C8 P(6L8C1) => 6L5C9 => 6L9 vide => -6L8C1 P(6L2C9) => 6L1C2, 6L5C1 => 6L9 vide => -6L2C9 P(8L1C1) => 3L3C3, 6L3C8, 4L7C3, 6L2C3 => 6L1 vide => -8L1C1 P(3L1C8) => 4L1C1, 6L1C9 => L3C8 vide => -3L1C8 P(6L2C1) => 4L2C5, 8L2C3, 8L1C8, 6L1C9 => 6L5 vide => -6L2C1 P(6L1C8) => 3L3C8, 3L1C1, (189)B6, 3L9C9 => 1C9 vide => -6L1C8 => L1C8 = 8 P(6L6C2) => 6L1C9 => 6L5 vide => -6L6C2 P(6L8C9) => 6L1C2, 6L5C1 => 6L9 vide => -6L8C9 P(6L6C9) => 6L1C2, 6L5C1 => 6L9 vide => -6L6C9 P(6L6C1) => 6L5C9, 6L1C2 => 6L9 vide => -6L6C1 P(4L7C2) => 3L7C3, 9L7C7, 4L8C9, 4L1C1 => 3C1 vide => -4L7C2 =>L7C2 = 9 P(6L3C2) => 6L1C9, 6L5C1 => 6L9 vide => -6L3C2 P(6L2C7) => 3L3C8, 4L1C9, 9L8C9 => 9L2 vide => -6L2C7 P(4L3C2) => 6L1C2, 6L3C5 => 6L2 vide => -4L3C2 P(8L9C5) => 6L9C2, 4L1C2, 3L1C1 => L9C1 vide => -8L9C5 => L9C5 = 9, L8C5 = 8 => Tous les 9 de C8 se trouvent dans B6 => - 9L46C7 -9L6C9 => L4C7 = 8 P(6L2C3) => 8L2C1, 8L9C2 => 6C2 vide => -6L2C3 => L2C5 = 6, L3C5 = 4 P(6L1C9) => 4L1C2, 1L4C2, 1L3C3 => 6L3 vide => -6L1C9 => L1C2 = 6, L9C2 = 8, L4C2 = 4 P(1L4C3) => 3L3C3, 4L1C1, 2L8C1 => 2L4 vide => -1L4C3 => candidats uniques dans 30 cases => solution

De Robert Mauriès
(Publié le 18/03/2020)

@ François C : Bonjour François. Intéressante résolution à la mode "Berthier" avec des "fouets (whips)" courts ne dépassant par 4 placements (on ne compte pas la cible à éliminer) pour constater la contradiction. Ainsi toutes les éliminations peuvent se faire de mémoire, sans tracer effectivement les pistes, sauf peut-être celle du 6L1C8 qui classe la résolution dans S3-whips (S3 pour le triplet). Reste que la recherche des candidats dont l'élimination peut se faire par des pistes courtes est un travail d'observation fastidieux. Berthier ne m'a pas donné de réponse satisfaisante à ce sujet, et pour cause, c'est son logiciel qui le fait ! Vous, l'avez-vous fait à la main seulement ? Robert

De Francis Labetoulle
(Publié le 18/03/2020)

@ Robert Mauriès et François Bonjour J'ai lu avec grand intérêt la solution proposée par Francois et le commentaire associé de Robert. Puis-je en conclure que les techniques proposées par Denis Berthier peuvent se résumer à la recherche visuelle (à la manière d'un joueur d'échecs anticipant les coups à venir...) des candidats à éliminer car associés à des invalidités décelables? Mais alors cette notion a-t-elle une signification intrinsèque, ou dépend-elle du nombre de "pas" ou "longueur de piste" nécessaire à la mise en évidence de l'invalidité associée au candidat ? Que faut-il en conclure alors concernant un cheminement comme ceux proposés par Paolo et moi pour la résolution de la grille, avec deux invalidités qui suffisent pour trouver la solution, mais avec de grandes "longueurs de pistes"? Où est le problème logique associé?

De Robert Mauriès
(Publié le 18/03/2020)

@ Francis Labetoulle : Bonjour Francis. Je vous suggère de lire les échanges que j'ai eu avec Berthier dans le fil de commentaires suivant : http://forum.enjoysudoku.com/tdp-versus-forcing-braids-t37379.html . Je pourrais résumer cela en disant que Berthier considère que la technique des pistes est une DFS (Depth First Search) qui permet de résoudre tous les puzzles. Une T&E reposant sur les paires et les bifurcations. Son approche est différente en ce sens qu'elle repose sur des modèles (patterns) répondant à des définitions précises (whip, braids, etc..) sur la base desquels son logiciel recherche la solution en procédant par étapes progressives : recherche de toutes des cibles associées à des whips de longueur 1 (les alignements pour nous), puis recherche des cibles associées à des whips de longueur 2, et ainsi de suite. Si les whips ne suffisent pas, il passe aux braids avec le même principe de recherche. Cela lui permet de quantifier la difficulté du puzzle par la longueur maximum utilisée des whips ou des braids, leur nombre ne comptant pas. Oui, selon moi, on pourrait dire une procédure de partie d'échec? Pour moi, cela revient à rechercher les candidats dont la piste ou l'antipiste conduit à contradiction, mais pour Berthier une piste n'est pas un modèle au sens qui est le sien. J'avoue que la nuance m'échappe ! A mi-chemin entre essayer tous les candidats qui conduiront à contradiction, comme François l'a fait, et rechercher la résolution la plus courte comme vous l'avez fait, on peut aussi envisager une résolution reposant sur des enchaînements relativement courts et en nombre limité en exploitant toutes les paires, ce qui reste à la portée d'une résolution à la main. Un aspect intéressant aussi tiré du livre de Berthier et adapté à la TDP, est celui de "candidats compatibles avec une cible", par exemple sur cette grille avec une anti-piste issue du 8L4C7 et comme cible le 8L2C7* qui exclue tous les 8 qui voient la cible : P'(8L4c7) : -8L4c7->(9L4C7->9L2C9)->46L8C79->3L7C7->(3L3C3->4L7C3)*->6L2C3->6L3C5 => L3C8 vide => -8L2C7. Ce qui évidemment revient à tester 8L2C7 pour l'éliminer, à part que quand on développe P' on se laisse à tout moment du développement de P' la possibilité de choisir une autre cible parmi les 8 qui voient 8L4c7. La TDP c'est tout cela.

De François C.
(Publié le 18/03/2020)

Bonjour à tous, Non je ne l’ai pas fait à la main, j’ai effectivement écrit un programme ces derniers jours, mais qui ne sort pas directement le résultat que j’ai donné ci-dessus. J’ai quand même passé en plus une bonne heure pour choisir, à la main, l’ordre des anti-backdoors à traiter (j’appelle anti-backdoor un candidat A tel que P(A) => contradiction). J’aurais été absolument incapable de tout faire à la main. Le seul intérêt d’une telle résolution est un autre étalonnage des grilles qui est inspiré de celui de Denis Berthier, mais pour des grilles pas trop difficiles (niveau TDP 1 ou 2, peut-être 3) car au-delà le nombre de possibilités à traiter est trop grand. Les résolutions plus habituelles données par Paolo et Francis sont évidemment plus adaptées à un joueur manuel et plus faciles aussi à synthétiser. En fait, cela était surtout pour moi un prétexte pour replonger dans l’informatique et oublier un peu la perspective du confinement. Et ce n’est pas fini, car il y a moyen d’optimiser, comme toujours…

De Francis Labetoulle
(Publié le 18/03/2020)

@ Robert Mauriès : Bonsoir J'ai suivi votre conseil en parcourant votre correspondance avec Denis Berthier. Il me faudrait lire son livre pour espérer appréhender les propriétés d'existence et de convergence de sa théorie. Si j'ai compris quelque chose, grâce aux whips, puis aux braids on peut, apparement pour toute grille, parvenir à la résolution, en y mettant le temps qu'il faut en l'absence d'outil informatique. Ne faudrait-il pas démontrer, en TDP, la justification de l'existence d'au moins un arbre de résolution permettant d'obtenir une solution complète dans le cas d'une grille quelconque ? J'avoue que celà ne me perturbe absolument pas.

De Robert Mauriès
(Publié le 18/03/2020)

@ Francis Labetoulle : Bonsoir Francis. Tout arbre de résolution réalisé, par définition, avec des pistes conjuguées et des extensions successives conduit à une solution obligatoirement. Cela tient à la définition d'un arbre de résolution et au fait que la grille ayant un nombre fini de candidats, un arbre de résolution compte un nombre fini de branches. Donc pour toute grille il est toujours possible de construire un arbre de résolution qui conduit à une solution. Evidemment, en pratique, un tel procédé peut être fastidieux avec un arbre qui compte un très grand nombre de branches. Mais la présence de paires oriente les choix des extensions et réduit considérablement le nombre de branches, c'est bien ce que nous faisons dans nos résolutions.

De Robert Mauriès
(Publié le 19/03/2020)

@ Francis Labetoulle et François : Bonjour, comme je l'écrivais dans un précédent commentaire, il est possible de trouver des résolutions intermédiaires (entre celle de François et celle de Francis) à la main avec des pistes successives de longueurs modérées en s'appuyant sur les paires. En voici une avec des anti-pistes de longueurs inférieures à 10 : 1) P'(8L4C7) : -8L4C7->9L4C7->9L2C9->46L8C79->3L7C7->[(3L3C3->4L7C3)->6L3C8->6L2C5]->8L2C3 => -8L2C7, -8L4C3. 2) P'(9L7C2) : -9L7C2->[{9L7C7,4L7C2}->{6L1C2,3L7C3}->{3L1C1,4L1C9}]->6L8C9->7L5C9->6L5C1 => 6B7 vide => L7C2=9 3) P'(9L9C5) : -9L9C5->(8L9C5->6L9C2)->{3L9C1, 4L1C2}->6L1C1->7L5C1->7L3C2->1L3C3 => 3B1 vide => L9C5=9 et deux placements par TB. 4) P'(8L2C3) : -8L2C3->([{3L1C1,8L2C1}->6L9C1->6L5C9]->4L1C9->6L1C2)->6L6C3 => 8C3 vide => L2C3=8. 5) P'(3L1C1) : -3L1C1->{3L3C3,3L7C7,3L1C9}->3L6C8->9L4C8->9L6C1->8L6C2->8L9C1 => 3C1 vide => L1C1=3, deux autres placements et quelques éliminations par les TB. 6) P'(7L5C1) : -7L5C1->6L5C1->6L9C2->8L6C2 => -7L6C2 => L3C2=7 et fin de la grille par les TB.

De François C.
(Publié le 21/03/2020)

@ Robert Mauriès : Bonjour Robert, J’ai relu les définitions d’un « whip » et d’un « braid » de Denis Berthier et j’ai décortiqué 2 exemples, ce qui m’a permis enfin de comprendre pourquoi vous utilisez des anti-pistes : elles permettent de coller à ces définitions. Du même coup j’ai compris aussi vos commentaires de la grille 662, que j’avais seulement survolés. Ma résolution de cette grille (664), qui consiste à chercher systématiquement des P(A) invalides courtes, reste valable mais ne correspond pas à ces définitions mais plutôt à un T&E optimisé. Moralité, un petit virus aura servi à une meilleure propagation de la théorie de Berthier et à la compréhension du sens (caché) des résolutions que vous faites depuis quelques temps !

De Robert Mauriès
(Publié le 21/03/2020)

@ François C : Bonjour François. C'est d'abord en étudiant les AIC très utilisées sur enjoysudoku.com que j'ai constaté que les anti-pistes donnaient les mêmes enchaînements et résultats. D'où l'intérêt de les utiliser de cette manière et le fait que j'ai présenté la TDP (version anglaise) en partant de la notion d'anti-piste avec quelques propriétés utiles. Ce n'est qu'après avoir étudié les chaînes (biv-chains, whips et braids) de Berthier à la faveur d'une intervention de sa part sur enjoysudoku.com où il faisait une comparaison avec la TDP, que j'ai constaté comme pour les AIC que les anti-pistes donnaient aussi les mêmes enchaînements et résultats. J'avais d'ailleurs constaté cela il y a longtemps déjà et j'avais écrit alors à Berthier pour lui en parler, sans réponse de sa part. Le fait d'utiliser des anti-pistes pas à pas est donc un mode de résolution équivalent à ceux que font les inconditionnels des AIC ou des techniques de Berthier. Mais c'est bien de la TDP classique que l'on utilise ainsi, avec un jeu de pistes conjuguées composé de l'anti-piste P'(E) et de la piste P(E) qui lui est associée réduite à son élément générateur. Il faut reconnaître aussi, mais cela nous le savons depuis bien longtemps, qu'il est plus facile, en général, de construire une anti-piste P'(E) qu'une piste P(E), voire plus naturel en raison de leurs définitions.


Ajouter un commentaire

Adresse Mail

Mot secret (Mot secret oublié)
Celui utilisé pour archiver, ou si vous n'avez jamais archivé, un mot secret de votre choix
Prénom et/ou Nom

Pour la sécurité du site,
merci de saisir les lettres et chiffres situés dans ce code : 3*x#3=15-A

Commentaire



La solution

Les techniques de base réduisent la grille avec 10 placements. Différentes résolutions ont été données ensuite dans le forum, de la plus rapide avec 2 jeux de pistes à la plus longue mais avec des longueurs de pistes ne dépassant pas 5 enchaînements. En voici une autre qui utilise les paires présentes et qui limite les longueurs de pistes à 10 enchaînements. 1) P'(8L4C7) : -8L4C7->9L4C7->9L2C9->46L8C79->3L7C7->[(3L3C3->4L7C3)->6L3C8->6L2C5]->8L2C3 => -8L2C7, -8L4C3. 2) P'(9L7C2) : -9L7C2->[{9L7C7,4L7C2}->{6L1C2,3L7C3}->{3L1C1,4L1C9}]->6L8C9->7L5C9->6L5C1 => 6B7 vide => L7C2=9 3) P'(9L9C5) : -9L9C5->(8L9C5->6L9C2)->{3L9C1, 4L1C2}->6L1C1->7L5C1->7L3C2->1L3C3 => 3B1 vide => L9C5=9 et deux placements par TB. 4) P'(8L2C3) : -8L2C3->([{3L1C1,8L2C1}->6L9C1->6L5C9]->4L1C9->6L1C2)->6L6C3 => 8C3 vide => L2C3=8. 5) P'(3L1C1) : -3L1C1->{3L3C3,3L7C7,3L1C9}->3L6C8->9L4C8->9L6C1->8L6C2->8L9C1 => 3C1 vide => L1C1=3, deux autres placements et quelques éliminations par les TB. 6) P'(7L5C1) : -7L5C1->6L5C1->6L9C2->8L6C2 => -7L6C2 => L3C2=7 et fin de la grille par les TB




assistant-sudoku.com est la propriété de Robert Mauriès (assistant.sudoku(AT)free.fr). Toute reproduction interdite sans son autorisation.