S'identifier           S'inscrire

assistant-sudoku.com

Grille Sudoku résolue

La grille -503


Afficher les commentaires


Commentaires sur cette grille

De Robert Mauriès
(Publié le 26/05/2018)

Pas de commentaire pour l'instant.

De François C.
(Publié le 26/05/2018)

Bonjour, les techniques de base donnent 4 placements et quelques suppressions grâce à un alignement, une paire et 2 paires cachées. Ensuite je considère la paire 9L56C7. La piste P(9L5C7) donne 7 placements et conduit à 2 contradictions par bifurcation sur les 9 de la ligne 6. La piste P(9L6C7) ne donne aucun placement mais permet de conclure grâce à une bifurcation sur la case L5C5: P(9L6C7).P(3L5C5) => solution P(9L6C7).P(4L5C5) => contradiction P(9L6C7).P(5L5C5) => contradiction Donc solution unique prouvée et taille de résolution = 4

De Richard
(Publié le 26/05/2018)

Bonjour, 4 placements par les TB initiales. Bravo à François pour sa solution de taille 4 car cette grille est plus propice aux solutions de taille 5. Etudions les 6 du bloc 8 : (1) 6L7C6 => piste comportant 3 candidats virtuels. (2) 6L9C4 => piste comportant 6 candidats virtuels. Bifurcation de (1) avec les 5 du bloc 2 : (3) 6L7C6 + 5L1C5 => résolution de la grille. (4) 6L7C6 + 5L2C4 => piste comportant un seul candidat virtuel. Bifurcation de (4) en utilisant les 3 candidats de L6C6 : (5) 6L7C6 + 5L2C4 + 4L6C6 => contradiction. (6) 6L7C6 + 5L2C4 + 5L6C6 => contradiction. (7) 6L7C6 + 5L2C4 + 9L6C6 => contradiction via une réduction bloc/ligne : à un moment dans la ligne 1, les 7 sont cantonnés dans le bloc 3 ce qui force 1L2C7 à faire partie de la piste. Bifurcation de (2) avec les 9 de la ligne 6 : (8) 6L9C4 + 9L6C4 => contradiction via une paire (45) dans le bloc 9 qui force 3L8C7 et 1L7C9 à faire partie de la piste. (9) 6L9C4 + 9L6C7 => contradiction.

De Clément
(Publié le 28/05/2018)

Bonjour je viens de réussir a démonter l'existence et l’unicité de la grille 183 .C,'était mon dernier objectif avant de faire al escargot... Du coup je tente de faire le fameux monstre et là stupeur! je me rend compte que la 183 est une grille équivalente à AI escargot à qui on a rajouté le 1 évident!(permutation (64981)(7352) + permutation de ligne et colonne) Du coup vu que j'ai réussi a trouver ce fameux 1 j'ai réussi IA escargot! Comment cela est t'il possible? Comment le niveau sans le 1 peut être de 25 et avec le 1 de 31? En tout cas je suis super content, j'ai réussi a résoudre AI escargot sans le savoir!

De Clément
(Publié le 28/05/2018)

@ Clément : En fait cette grille c'est AI escargot à qui on a rajouter le 1 donc l'unicité de la grille à été prouvé.

De Robert Mauriès
(Publié le 29/05/2018)

@ Clément : Ravi de vous lire sur ce forum Clément ! Ceci dit, je suis étonné par l'association que vous faîtes entre la grille N°183 qui est Easter Monster et la grille AI Escargot (N°23), étant donné que leurs nombres de dévoilés sont différents. Pouvez-vous préciser les tranformations qui selon vous font passer de l'une à l'autre ? Quand au niveau TDP d'AI Escargot, 31 est son niveau maximum, il n'est pas exclu qu'on puisse trouver une résolution de taille plus faible, ce que vous avez sans doute fait et dans ce cas bravo à vous !

De Paolo
(Publié le 29/05/2018)

@ Clément : @ Robert Mauriès : Bonjour, Si la " SK-loop" est utilisée comme technique initiale pour la résolution du Easter Monster,voir http://www.sudokusnake.com/nakeddoubleloop.php vous obtenez 13 suppressions qui sont produites avec une seule étape logique. Combien de contradictions peuvent être associées aux 13 éliminations produites par le "SK-Loop" si vous associez la technique des pistes pour résoudre le puzzle? Je pense qu'avec l'association de la technique de pistes, vous obtenez un TDP plus bas.

De Robert Mauriès
(Publié le 29/05/2018)

@ Paolo : La taille d'une résolution est définie avec les TB, c'est une définition et comme toute définition elle ne peut pas être "ajustable". Les doubles boucles ne peuvent pas être considérées comme basiques, elles sont même très complexes. Les 13 éliminations dont vous faîtes état en sont la preuve comme vous pouvez le voir dans la résolution que je propose de Easter Monster qui montre que ces éliminations résultent de nombreuses applications de la TDP.

De Paolo
(Publié le 29/05/2018)

@ Robert Mauriès : Ce que vous dites est vrai, mais je me raccrocherai à ce qui a été dit dans de nombreuses discussions que l'utilisation d'autres techniques de résolution comme la x-wind être utilisée et comptée comme une piste invalide (contradiction) et non comme un TB. Clairement, dans ce cas, la technique utilisée serait très efficace et je me demandais exactement comment cela pouvait être compté en termes de contradictions .Généralement toutes les éliminations obtenues avec les techniques avancées jusqu'aux chaînes forcées peuvent être remplacées par la contradiction de la piste formée par l'élément qui sera éliminé mais dans le cas du SK -loop ce n'est pas valide en fait aucune des pistes formées par l'un des 13 candidats éliminé dans le Monstre de Pâques génère une piste invalide.

De Robert Mauriès
(Publié le 29/05/2018)

@ Paolo : L'application de ces doubles boucles qui produit 13 éliminations compte pour 26 dans le décompte de la taille puisque l'on obtient le même résultat en utilisant 13 pistes issues de ces 13 candidats qui conduisent à des contradictions via deux branches de bifurcation pour chaque piste. Il est peut-être possible de réduire ce nombre avec des pistes issues d'ensembles, mais je n'ai pas essayé.

De Paolo
(Publié le 29/05/2018)

@ Robert Mauriès : Oui, j'ai compris après une lecture attentive de votre résolution sur le site.

De Clément
(Publié le 30/05/2018)

Bonjour ça me fait également très plaisir de pouvoir discuter avec des personnes qui s'y connaissent vraiment en sudoku. Je crois que je viens de trouver une preuve d'un résultat que j'avais remarqué depuis longtemps: toute grille qui admet une solution et qui posséde au plus deux candidats par case et résoluble par les techniques de bases. J'étais très content de démontrer ce résultat mais dans mon entourage personne ne comprend ne serait que le sens de cette propriété qui est fausse dans un tectonic par exemple. Ce théorème c'est celui que vous appelez Bug non ? Je me suis trompé c'est la 184 qui est AI escargot En partant de AI escargot voila les transformations que l'on peut faire pour obtenir la grille 184 Tout d'abord on fait la permutation des chiffres suivante (64981)(7352) Puis On se débrouille pour avoir le bloc vide en R8 en R6 pour cela on fait L123 -> L789 -> L456 -> L123 Puis C456 <-> C789 ensuite on permute les lignes au sein d'un même "trois lignes" C4 <-> C5 C5<-> C6 L8 <-> L9 L1 -> L2 -> L3 -> L1 C7 <-> C8 ensuite on a qu'a rajouter le 6 en E3 qui s'obtient grâce au techniques de bases et on tombe sur la grille 184 Du coup je pense que le niveau 25 c'est pour juste trouver le backdoor. Je me suis lancé à la recherches de blonde platine, je l'ai pas vu su le site, elle a pas l'air facile non plus mais je compte bien avoir le dernier mot et montrer l'unicité de la solution.

De Paolo
(Publié le 30/05/2018)

@ Clément : Bonjour, Ce n'est pas clair pour moi ce que cela signifie d'échanger 5 chiffres avec quatre chiffres (64981)(7352). L'un d'eux doit nécessairement être exclu. Une autre chose qui n'est pas claire pour moi. les deux grilles ont toutes deux 24 chiffres initiaux donc il n'est pas possible d'obtenir la grille 184 à partir de l'escargot en insérant aussi le 6 en E3 car il atteindrait 25 chiffres initiaux.

De Clément
(Publié le 30/05/2018)

Bonjour (64981)(7352) est une notation utilisé pour désigner les permutations d'un ensembles Cela veut dire 6 -> 4 -> 9 -> 8 -> 1-> 6 7 -> 3 -> 5 -> 2 -> 7 AI escargot a 23 chiffres initiaux et non 24 mais je je viens de me rendre comte que sur ce site le 1 trivial est déjà mis donc effectivement cela fait 24. Donc pas besoin de rajouter le 6 en L5 C3 il y sera déja. de plus on remarque que AI escargot contient une fois le 1 mis 1 bloc avec 0 initial 1 bloc avec 2 initiaux 5 blocs avec 3 initiaux 1 bloc avec 4 initiaux Exactement comme la grille 184 De plus on peut supprimer dans la grille 184, 4 candidats 8 dans le blocs 6 en partant de piste de la paire de 8 du bloc 1. Puis en remarquant des X wings Exactement comme dans la résolution proposé sur ce site de AI escargot on enlève 4 candidats 9 du bloc 8

De Paolo
(Publié le 30/05/2018)

@ Clément : Bonsoir, Oui, effectivement, la grille 184 est une version de l'escargot. La même résolution que l'escargot peut être utilisée

De Robert Mauriès
(Publié le 31/05/2018)

@ Clément : Ce serait intéressant que vous expliquiez sur ce forum comment vous montrez qu'une grille ne présentant que deux candidats par cases non-résolues peut se résoudre avec les seules TB. Je ne vous cache pas que je suis étonné par ce résultat.

De Paolo
(Publié le 31/05/2018)

@ Robert Mauriès: @ Clément : Probablement Clément quand il parle de la résolution d'une grille avec seulement les techniques de base, comprend également des bifurcations ou des "extensions". En fait, toute la technique des pistes n'utilise que les TB.

De Clément
(Publié le 31/05/2018)

@ Robert Mauriès : Alors La preuve est assez longue car elle demande beaucoup de pré requis Mais voila ceux qu’elle donne, si vous avez des questions pour la démonstrations des résultats intermédiaire n’hésitez pas. J’ai essayer de m’adapter au maximum au notation de votre site mais j’ia eu un peu de mal par moment. Tout d’abord voila ce que j’appelle exactement les techniques de bases. Définition Technique d’insertion 1 (ti1) Si dans une zone une seul case contient le chiffres a alors le a de cette case est valide Technique d’insertion 2 (ti2) Si dans une case, un seul chiffres est présent, alors ce candidat est valide Technique d’élimination 1 (te1) Si dans une zone un candidat a est valide dans une case , alors tous les candidats a des autres cases de la zone sont invalides Technique d’élimination 2 (te2) Si dans une case , un candidat a est valide alors tous les autres chiffres de cette case sont invalides Théorème : Une grille de sudoku qui possède au plus deux candidats par case et possédant une unique solution est résoluble par les techniques de base à savoir te1 te2 ti1 et ti2 Dans toute la preuve on appellera binaire une grille possédant deux candidats au plus par case Et simple une grille résolvable par Te1 te2 ti1 et ti2 Une preuve possible de ce théorème passe par la notion de partie isolée Définition. Une partie isolée(Pi) P est un ensemble de cases tel que si on prend une case A appartenant à P et une case B de la grille si A et B ont un candidat de même valeur alors B appartient à P Autrement dit si dans une zone on a une case qui appartient à P et une case qui appartient pas à P alors ces deux cases n’ont aucun candidats de même valeurs Exemple Après avoir utilisé Te1, un chiffre inscrit est une partie isolée Le vide, une case vide, et la grille toute entière sont des parties isolées Le rectangle interdit est aussi une partie isolée si on a utilisé la technique des paires. Pour la démonstration du théorème on aura seulement besoin de démontrer que la grille est une Pi Définition : une partie est isolée est dite simple (PIS) si elle contient exactement deux sous partie isolée. A savoir elle-même et le vide. Ainsi le vide n’est pas une PIS La première propriété importante à démontrer est la suivante Propriété 1 Une partie isolée est décomposable de manière unique en une union disjointe de Partie isolée simple La démonstration de cette propriété ressemble beaucoup a l’existence et l’unicité de la décomposition en facteur premier d’un enter naturel Définition Soit P un ensemble de case, P est dit connexe par candidat si pour toutes case X et Y appartenant à P Il est possible de trouver des cases W1 W2 ….Wn Tel que X et W1 soient dans la même région et contienne un candidat de la même valeur. De même pour Wk et Wk+1 et Wn et Y Propriété 2 Une partie isolée simple est connexe par candidat. Remarque On a aussi une PI non vide connexe par candidat est simple mais on a pas besoin de ce résultat dans la preuve. Ensuite on a besoin de définir ce qu’est une solution d’un ensemble de case E Soit S un ensemble de case, on dit que S est une solution de l’ensemble E si - S contient toutes les cases de E et seulement celles ci - toutes les cases de S contiennent exactement un candidat par case -Tous les candidats de S sont des candidats de E -Dans une zone il ya jamais deux candidats de même valeur Remarque si S est une solution d’une grille G alors toutes les zones contiennent une seules fois chaque chiffres, on donc bien S est une solution de la grille au sens usuel. Propriété 3. le nombre de solution de l’union de deux partie isolée disjointe est égal au produit du nombre de solutions des deux PI Corollaire Une partie isolée(et donc la grille) admet une unique solution si et seulement toutes ces sous parties isolées simples admettent une unique solution. Ce corollaire est vraiment important , c’est une généralisation du principe des rectangles interdits. On a en effet dans un sudoku à solution unique si une piste amène a séparer la grille en plusieurs parties isolées et que au moins l’une d’entre elle admet plusieurs solutions. Cette piste est invalide On a fini avec les pré requis concernant les PI Pour démontrer qu’une grille binaire est résoluble il suffit de montrer qu’elle est simplifiable c'est-à-dire qu’on peut supprimer ou valider un candidat. En effet une grille binaire simplifiée reste binaire. Remarque Si une grille n’est pas simple si dans une zone un chiffre n’est pas inscrit alors il ya au moins deux candidat qui ont pour valeur ce chiffre dans cette zone sinon on pour appliquer Ti1 . Si de plus la grille est binaire , il apparait donc exactement deux fois. Propriété4 Soit G une grille binaire non simple , Soit A et B deux insertions du type Supposer qu’un candidat est vrai ou Supposer qu’un candidat est faux ;Si on a A Implique B par l’utilisation des techniques te1 te2 ti1 ti2 alors on a Non A implique Non B Cette propriété est une conséquence de la remarque juste avant. Propriété 5. Soit G une grille binaire non simple. Soit P une PIS de G alors toutes pistes issu d’un candidat de P peut amener a faire en sorte qu’il reste exactement un candidat dans toutes les cases de P seulement en utilisant Ti1 Ti2 Te1 et Te3 Cela est du a fait qu’une Pi est connexe par candidat Enfin on peut démontrer le théorème Par l’absurde Soit G une grille binaire non simple avec une unique solution. Soit X une case qui contient deux chiffres candidats A et B On a X qui appartient a une PIS que je note P Comme G admet une unique solution on a P qui admet une unique solution d’après le corollaire Donc on a soit A soit B qui est faux. Supposons que c’est A On a d’après la propriété 5 que supposer A permet de faire en sorte que dans chaque case on est un seul candidat. Mais vu que A est faux , on tombe pas sur une solution de P donc il existe une zone Z qui contient deux cases appartenant à P avec deux candidats ayant la valeur c Oui mais si on suppose B on suppose Non A donc d’après la propriété 4 dans ces deux cases on aura pas de candidats ayant la valeur c. Mais on a vu que dans chaque Zone un candidat qui a pas été déterminer apparait exactement deux fois donc Z n’aura plus de candidat de valeur c donc B est faux donc G n’admet aucune solution absurde. Remarque on a montré que le candidat B était faux car il implique qu’une zone n’admet pas de chiffre c mais dans ce cas il y aura un chiffre présent au moins deux fois dans Z.


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 : +7z-z3=y=C

Commentaire



La solution




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