assistant-sudoku.com

Commentaires sur cette grille

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

Après simplification de la grille par les TB (22 placements), on utilise par exemple le jeu de pistes issues de la paire 8B3 pour construire la solution et confirmer son unicité, par simple croisement des pistes.

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

J'ai pris la paire de 6B1 qui amène toutes les deux à un 8 en L1 C3

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

@ Clément : Très bon choix de pistes Clément ! Je détaille votre résolution dans "Résolutions guidées".

De Claude Renault
(Publié le 31/05/2018)

22 placements par TB (b1-j3)L9C4 : b invalide, j valide couvre la grille

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

Bonsoir, 1)21 placements par les TB iniiiales. Fin x-Wind (3L1 et 3L8 fin L1C3=3)=>-3L2C1=>solution.

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

@ Paolo : 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 chiffre 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 ses 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 y a au moins deux candidats qui ont pour valeur ce chiffre dans cette zone sinon on pourrait 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 Te2 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 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.

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

@ Clément : Bonsoir, Il est très intéressant ce que vous dites, Léger attentivement ce que vous avez écrit. Une première question que je voudrais poser: Puisque le théorème que vous décrivez ne concerne que les grilles de solution unique. Comprenez-vous également la démonstration de l'unicité dans la résolution? Si la réponse est négative, comme je pense, est-ce que des «backdoors» sont une résolution pour vous? J'écris ceci parce que la grille d'escargot, qui a une solution unique et qui a la case L5C3 avec seulement deux candidats, n'a pas de backdoors même après les seules éliminations possibles avec TB: P(9L7C4)=>contradiction=>-9L7C4 P(9L7C6)=>contradiction=>-9L7C6 P(9L8C6)=>contradiction=>-9L8C6 P(9L9C4)=>contradiction=>-9L9C4 P(9L9C6)=>contradiction=>-9L9C6 P(1L2C6)=>contradiction=>-1L2C6 P(2L8C6)=>contradiction=>-2L8C6. Après ces éliminations les seules possibles peuvent être obtenues avec des extensions comme par exemple: P(2L1C2).P(7L3C1).P(1L2C4)=>contradiction P(2L1C2).P(7L3C1).P(4L2C4)=>contradiction P(2L1C2).P(7L3C2).P(4L3C1)=>contradiction P(2L1C2).P(7L3C2).P(8L3C1)=>contradiction=>-2L1C2 Clairement après une tentative comme L1C2 = 6 d'autres élminations peuvent être obtenues en utilisant seulement le TB comme: P(3L1C5)=>contradiction=>-3L1C5 P(2L1C7)=>contradiction=>-2L1C7 P(6L2C8)=>contradiction=>-6L2C8 P(8L3C1) =>contradiction=>-8L3C1 P(2L4C1) =>contradiction=>-2L4C1 Ce qui conduit directement à la solution avec le seul TB.

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

@ Paolo : Bonsoir Lles seules techniques utilisées sont inductives du coup elle démontre aussi l'unicité. Je n'utilise aucune piste c'est pas du tout une techniques que j'appelle de base , même les paires je les considéres pas comme de bases dans le théorème. Seulement celles que j'appelle Ti1 ti2 te1 et te2. Sinon personnellement quelque soit la grille je tient démontrer aussi l’unicité du coup je n'utilise pas de backdoor.

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

@ Clément : Bonsoir, Ce que vous dites est surprenant parce que moi aussi je n'utilise généralement que les techniques que vous dites. Mais par exemple dans la grillel'escargot, qui a les caractéristiques du théorème que vous décrivez, après avoir inséré 1 dans L8C3 il n'est pas possible d'éliminer un élément des 216 candidats présents dans la grille en utilisant les techniques que vous avez répertoriées. Il est possible de prouver faux seulement L7C4 = 9, L7C6 = 9, L8C6 = 9, L9C4 = 9, L9C6 = 9, L2C6 = 1 et L8C6 = 2 associant la technique trial and errors aux techniques en question, mais pour les autres 209 canditates restants aucun résultat n'est obtenu. Clairement avec des extensions, en utilisant toujours les mêmes techniques de base, vous pouvez éliminer d'autres candidats et arriver à la solution et la démonstration de l'unicité, mais c'est la technique des pistes.

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

@ Paolo : @ Paolo : Pour que le théorème fonctionne il faut que toutes les cases admettent au plus deux candidats, sinon bien sûr le sudoku ne se résolue pas avec juste les techniques de bases, même blonde platine admet une case avec deux candidats et pourtant elle est loin d’être facile.

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

@ Clément : Désolé, je n'ai pas compris, c'est la démonstration d'une extension du Binary Universal Grave (BUG) http://hodoku.sourceforge.net/en/tech_ur.php#un3 http://www.sudoku9981.com/sudoku-solving/bivalue-universal-grave.php

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

@ Paolo : Oui c'est bien ce que je pensais je l'avais vu dans un problème de ce site , ce fameux bug. Je trouvais ça bizarre que vous connaissiez pas ce résultat du coup. par contre sur le lien; Je suis pas vraiment anglophone du coup j'ai pas trop compris ce qu'il disait exactement ce bug et je n'ai pas trouvé de preuve.

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

@ Clément : Je n'utilise jamais de méthodes qui commencent dans la résolution des grilles comme une supposition initiale que la solution est unique. Dans ce site, nous essayons toujours de démontrer l'unicité d'une solution. Pour moi, c'est la chose la plus difficile à réaliser. Sinon, toute backdoor serait une résolution satisfaisante.

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

@ Paolo : je fais de même en revanche ce qui peut être intéressant C'est des grilles a solutions multiple mais tel qu'il y a ait un seul chiffre qu'on puisse rajouter pour faire en sorte qu'il y ait unique solution. Il y a des exemples de tel grilles dans ce site

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

@ Clément : Bonsoir, Bien sûr, cela peut être utile mais c'est un problème différent. Il ne s'agit pas de trouver toutes les solutions d'une grille comme la 495 mais de la transformer en une solution unique. Sur ce site j'ai trouvé une démonstration du BUG. http://www.sudoku9981.com/sudoku-solving/bivalue-universal-grave.php

De Claude Renault
(Publié le 01/06/2018)

@ Paolo : n'ayant jamais consulté la littérature américaine, je suis peut-être à côté de la plaque concernant ce problème . J'ai été un peu désorienté quand Robert m'a dit un jour que toute grille résolue par les procédures de base est unique Après réflexion, j'aboutis à un raisonnement que je vous soumets : Considérons la grille obtenue après PB : il est possible d'aboutir à un rectangle interdit (doublet, 2 solutions) ; dans ce cas particulier, la technique des pistes appliquée à l'une des paires dévoile les 2 solutions ; en extrapolant, on pourrait dire (et c'est là où je m'aventure un peu) qu'une grille à n solutions se traduit par une "disposition interdite" sous la forme de ntuplets ; la technique des pistes permet de décomposer ces ntuplets et mettre en évidence les différentes solutions ; tant que des croisements n'aboutissent pas à la couverture de la grille, on poursuit l'investigation ; en cas contraire, il est évident que l'élimination par la tdp de toutes les possibilité aboutit forcément à une solution unique

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

@ Claude Renault : Je suis d'accord avec ce que vous dites. Dans la résolution de la grille 495 j'ai utilisé exactement cette méthode de résolution. Je suis parti de la case L4C6 à la recherche de toutes les solutions ou contradictions qui partent des 4 candidats présents en utilisant les TB et les extensions pour obtenir toutes les solutions. De cette manière, clairement, chaque solution est différente, en pratique, tous les backdoors de taille différente.

De Richard
(Publié le 01/06/2018)

Bonsoir, Voici une solution de taille 1 qui ne passe pas par le RG géant (coloriage virtuel) présent sur cette grille. On étudie la case L5C8 : (1) (15)L5C8 => résolution de la grille. (2) (27)L5C8 => contradiction via la paire (27) de L5C78 qui force 7L3C9 à faire partie de la piste. Evidemment il n'est pas nécessaire d'aller au bout des 2 pistes pour trouver la solution de la grille. En effet rapidement 6L2C1 peut être placé et la grille tombe.

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

@ Paolo : Pouvez vous éviter les doubles et triples retours de chariots qui mettent beaucoup de lignes blanches. Cela faciliterait l'affichage et diminuerait la taille des pages web. Merci à vous. Robert

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

@ Clément : A la lecture des explications que vous donnez sur le théorème qui dit qu'une grille binaire à solution unique peut se résoudre avec uniquement les ti et te (c-a-d les TB sans les multiplets), je comprend qu'il y a un problème de vocabulaire. Sur ce site et dans la technique des pistes, nous disons qu'une grille peut se résoudre uniquement par les TB lorsqu'il n'est pas nécessaire, à aucun moment du processus de résolution, de devoir en plus des TB utiliser une alternative vrai ou faux pour un candidat A d'une case binaire (paire). Le théorème que vous évoquez utilise cette alternative pour être démontré, même si ensuite seules les techniques ti et te sont utilisées pour chaque alternative. Dans le vocabulaire qui prévaut sur ce site et dans la technique des pistes, pour être démontré ce théorème utilise en fait un jeu de pistes issues d'une paire, ce n'est pas ce qu'on appelle résoudre avec les seules techniques de base. De la même manière un X-wing n'est pas une technique de base car pour l'établir on doit utiliser une alternative vrai ou faux, c'est à dire un jeu de pistes.

De Clément
(Publié le 03/06/2018)

@ Robert Mauriès : Bonsoir Je pense que vous avez mal lu la preuve. En effet c'est quand je suppose qu'il n'est pas résolu par des tbs que je fais une piste qui démontre ensuite que dans une case si un chiffre est faux l'autre aussi. En effet je suppose par l'absurde que les tbs ne permettent pas de résoudre une grille binaire a une solution. Ainsi si elle a une solution unique, dans chaque case un et un seul chiffre est faux donc il doit bien amener a une contradiction quelque part.(mais ce chiffre ne se supprime par les tbs par hypothèse) Et je démontre que si l'un amène a une contradiction alors l'autre aussi.

Ajouter un commentaire