assistant-sudoku.com

Commentaires sur cette grille

De Robert Mauriès
(Publié le 12/06/2018)

Ma proposition de résolution dans "Voir la résolution" ci-dessus.

De Francis Labetoulle
(Publié le 12/06/2018)

Par exemple les pistes issues de 4L5C4 et 7L5C4. Que donnent les 6 de B7? Et une partition des candidats de la case L2C5?

De Paolo
(Publié le 12/06/2018)

Bonjour, 1)7 placements par les TB initiales. 2) P(5L1C18) => contradiction (L7C1=Ø) =>validation P(5L1C679) 3) P(5L1C679) =>solution.

De Robert Mauriès
(Publié le 12/06/2018)

@ Paolo : Choix très original de la paire d'ensembles génératrice Paolo, mais dommage tout de même que vous n'ayez pas remarqué (ou indiqué) que l'interaction des deux pistes suffisait à résoudre la grille (solution et unicité) sans avoir recours à l'invalidité. Je fais cette remarque car je constate (et Francis Labetoulle aussi) que le recours systématique à l'invalidité (contradiction) devient la règle sur le forum pour quasiment tout le monde, réduisant la TDP à du backtracking. Si l'originalité est dans le choix astucieux des ensembles générateurs comme vous l'avez fait ici (et encore bravo), elle est aussi dans l'utilisation des divers outils offerts par la TDP ( interactions des pistes et/ou des extensions, piste opposée, jeu piste-antipiste, etc...), même si c'est au détriment de la performance (taille de résolution), voire en glissant quelques techniques évoluées bien expliquées par leur équivalents TDP.

De Paolo
(Publié le 12/06/2018)

@ Robert Mauriès : Bonsoir, Oui, comme vous l'avez remarqué dans votre communication, les deux pistes se croisent et mènent directement à la solution. En effet, comme je l'ai souligné dans mon précédent post, une résolution obtenue par le croisement de deux pistes conjuguées est plus restrictive que la résolution obtenue en démontrant l'invalidité de l'une des deux (le croisement de deux pistes conjuguées implique l'invalidité de l'un des deux alors que l'invalidité de l'un des deux n'implique pas nécessairement la résolution de la grille à travers l'intersection des deux pistes conjuguées). Pour cette raison, il serait utile de différencier les deux taille de résolution en utilisant un correcteur mathématique. Je voudrais également soumettre un problème que j'essaie de résoudre lié à la résolution du Golden-Nugget .......39.....1..5..3.5.8....8.9...6.7...2...1..4.......9.8..5..2....6..4..7..... Comme on le sait, ce schéma peut être grandement simplifiée grâce à une méthode qui est une extension de « SK-loop » appelé « Almost SK loop ». Dans ce cas, la boucle obtenue est la suivante: (24 = 35) L4C12 - (35 = 17) L4C46 - (17 = 36) L56C5 - (36 = 124) L89C5 - (124 = 36) L7C46 - (36 = 17) L7C12 - (17 = 56) L89C3 - (56 = 24) R56C3 - (24) R4C12: avec inférence forte "=" et l'inférence faible "-". Dans ce cas, contrairement à la « Sk-Loop » il est introduit une absurdité, trois chiffres réels dans deux cases dans une box. Selon le metode la procédé bidirectionnel logique est toujours valide et des 15 deletions obtenus: L7C7 ≠ 3, L7C9 ≠ 3, L1C3 ≠ 5, L1C3 ≠ 6, L2C3 ≠ 6, L1C5 ≠ 6, L2C5 ≠ 3, L2C5 ≠ 6, L5C4 ≠ 1, L6C6 ≠ 7, L8C4 ≠ 1, L8C6 ≠ 4, L8C1 ≠ 7, L9C2 ≠ 1, L4C7 ≠ 5, une est faux et les autres sont vraies. Mise en place de manière cyclique chaque vrai et les autres fausses est réalisé que la seule série qui ne crée pas la contradiction est la suivante: L7C7 ≠ 3, L7C9 ≠ 3, L1C3 ≠ 5, L1C3 ≠ 6, L2C3 ≠ 6, L1C5 ≠ 6, L2C5 ≠ 3, L2C5 ≠ 6, L5C4 ≠ 1, L6C6 ≠ 7, L8C4 ≠ 1, L8C6 ≠ 4, L8C1 ≠ 7, L9C2 ≠ 1, L4C7 = 5. Il est clair que, après cette insertion, et ces deletions la résolution de la grille est considérablement simplifiée. Je voudrais comprendre pourquoi la logique bidirectionnelle est toujours valable malgré l'absurdité (je l'ai remarqué que cette méthode est utilisée avec succès dans de nombreux autres exemples) et si ces suppressions peuvent également être obtenus avec la théorie des pistes, en général, il y a toujours un lien logique entre différentes méthodes.

De Francis Labetoulle
(Publié le 13/06/2018)

@ Paolo (et autres participants du forum) Bonjour Puisque Robert me cite dans son précédent commentaire je voudrais ici préciser l'idée que je lui ai proposée. Il s'agit, à partir de l'arbre de résolution complet d'une grille de sudoku, de calculer un niveau, disons R (réseau ou résolution ou tout autre nom...) en attribuant 5 points à toute branche se terminant par un constat d'invalidité, et seulement 1 point pour 2 branches en parallèle, 2 pour 3 branches en parallèle, etc. On pourrait ainsi utiliser, en utilisant des pistes annexes, des techniques plus élaborées sans être trop sanctionné, ce qui permettrait probablement de trouver des solutions plus diverses et originales, l'un des buts du jeu étant d'obtenir un niveau R le plus bas possible. D'aucun pourra trouver cette idée fortement incongrue...tant pis. Concernant les grilles réputées très difficiles, une méthode "bourrin" qui semble convenir très souvent consiste à trouver le bloc ou l'unité à grand nombre de liens forts et partir de 3 jeux de pistes conjuguées différents (8 cas de figure, donc niveau R au moins égal à 35, à moins que...). Dans le cas de "Golden Nugget" cette méthode convient avec le B4 mais c'est trop long. J'ai trouvé sur le net la référence : Solving The Golden Nugget | Systematic Sudoku, mais je ne comprends pas comment l'auteur a pu simplifier certains candidats de la grille, avant d'appliquer "le sk-loop", technique que je ne connais pas encore. Peut-être pouvez-vous m'éclairer sur ces points? A bientôt sur le forum. Francis

De Paolo
(Publié le 13/06/2018)

@ Francis Labetoulle (et autres participants du forum) Bonjour, En ce qui concerne le premier sujet, le niveau de difficulté, je crois que l'attribution de 1 point à chaque contradiction trouvée est correcte mais je suis convaincu qu'un passage obtenu par croisement de 2 pistes conjuguées devrait être évalué de 0,5. En ce qui concerne "Sk-loop" ou " naked double loop " j'ai trouvé que l'explication de la méthode la plus claire se trouve sur le site http://www.sudokusnake.com/nakeddoubleloop.php où elle est appliquée dans la solution de la " Easter Monster ». C'est une extension de l'AIC circulaire (Alternating Inference Chains) dans laquelle les inférences fortes et faibles alternent en une boucle à partir de paires de candidats. La particularité est que le premier et le dernier couple de candidats sont les mêmes. Pour cette raison, il peut être démontré que toutes les inférences deviennent fortes et que tous les candidats qui "voient" deux couples intéressés par une inférence peuvent être éliminés. Dans la " almost Sk-loop " une absurdité est introduite il y a deux inférences entre un couple et un triplet. Malgré cette absurdité, il est toujours possible d'effectuer des suppressions avec la contrainte que l'une d'entre elles est fausse, de sorte que vous pouvez effectuer n-1 suppressions avec une insertion. Pour trouver le véritable élément, nous testons toutes les n possibilités en éliminant les combinaisons n-1 qui conduisent à des contradictions.

De Francis Labetoulle
(Publié le 13/06/2018)

@ Paolo : Bonsoir et merci pour le site mentionné, que je ne connaissais pas et qui me paraît très riche en exemples d'usage de techniques dites experts. Je me suis aperçu que je connaissais "la Théorie" de ces "loops" via l'étude du livre de Khoan Vo Khac : Cinq techniques pour terminer toute grille de sudoku, qui présente un chapitre V sur la technique des chaînes. Parmi elles on trouve les cycles de quasi-figés (ALS en anglais) qui sont notre problème apparemment, avec des généralisations qui peuvent éventuellement répondre à votre recherche. Dommage que ce soit du condensé avec exemples sans candidats apparents et non liés au texte.

De Robert Mauriès
(Publié le 14/06/2018)

@ Francis Labetoulle et Paolo : Je ne pense pas que Khoan Vo Khac traite des SK-loops. Par ailleurs je n'ai rien trouvé de satisfaisant sur le sujet à savoir sur les conditions requises pour avoir des SK-loops et sur la justification des éliminations qu'elles engendreraient.

De Paolo
(Publié le 14/06/2018)

@ Robert Mauriès et Francis Labetoulle : Bonsoir, La seule référence que j'ai trouvée mais qui n'est pas satisfaisante comme explication est l'help "SK Loops" du solveur de Philip Beeby http://www.philsfolly.net.au/loops_help.htm où il y a de nombreux exemples.

De Francis Labetoulle
(Publié le 14/06/2018)

@ Robert Mauriès : Bonsoir Je ne crois pas avoir écrit que KVK traitait des sk-loops, dont j'ignore toujours la signification précise, mais, concernant la "naked double loop" dont Paolo fait mention, je confirme qu'on peut considérer, moyennant l'ajout d'une case au choix pour former un quasi-figé (ALS) dans B9, qu'il s'agit d'un cycle original de quasi-figés, original car deux quasi-figés unis possèdent en commun deux candidats exclusifs (ou connectants). Cela permet, avec l'utilisation de la propriété basique des quasi-figés (0n ne peut pas leur ôter deux candidats) de justifier aisément toutes les éliminations mentionnées dans l'exemple cité par Paolo. En outre des généralisations de propriétés des chaînes de quasi-figés énoncées par KVK peuvent éventuellement aider Paolo, mais ce n'est qu'une hypothèse...

Ajouter un commentaire