S'identifier           S'inscrire

assistant-sudoku.com

Grille Sudoku résolue

La grille -604
Grille de niveau 15 conventionnel.



Afficher les commentaires


Commentaires sur cette grille

De Paolo
(Publié le 06/04/2019)

Bonjour, 1)5 placements par les TB initiales. P(2L9C9)=>couvre la grille. 2) P(2L7C8).P(1L8C4)=> contradiction 3) P(2L7C8).P(4L8C4)=> contradiction 4) P(2L7C8).P(8L8C4)=> contradiction=>validation P(2L9C9)=> solution.

De Philippe
(Publié le 06/04/2019)

Bonjour 5 placements par TB P(9L9C5).P(8L9C4) couvre la grille Solution donnée en considérant que la grille est à solution unique donc sans vérification de l'unicité (cf commentaires grille 599)

De Francis Labetoulle
(Publié le 07/04/2019)

@ Paolo : Bonjour J'aimerais connaître votre point de vue sur une question de méthodologie. Je suis parvenu au même résultat que vous concernant cette grille, mais en étudiant d'abord la cellule L8C4, intersection de B8, à 3 dévoilés et 7 liens forts, et L8, à 5 dévoilés et 4 liens forts, et C4 n'est pas mal non plus. B2 et L3 sont également intéressants à priori mais sans une bonne cellule pivot. J'obtiens de suite P(4L8C4) et P(8L8C4) invaliides. Concernant P(1L4C8) il faut faire ensuite le bon choix des 2 de B9, mais il se trouve assez "naturellement" parmi les choix possibles. Il y a donc "commutativité" de nos cheminements. J'ai le sentiment néanmoins que la recherche préalable des backdoors est plus efficace en général, mais celà nécessite d'y passer un temps non négligeable, ou d'utiliser un logiciel type hodoku, qui, de toute façon ne dispense pas de traiter le cas des sous-ensembles d'entités... Qu'en pensez-vous? Bon week-end

De Paolo
(Publié le 07/04/2019)

@ Francis Labetoulle : Bonsoir À mon avis, il est un peu difficile de comprendre quelle est la meilleure approche pour résoudre une grille de sudoku. Je pense que si l'objectif est de parvenir à une solution, votre façon de travailler est celle qui offre le plus de chances de réussite, alors que si l'objectif est de minimiser la taille, je pense que la stratégie inverse est plus puissante. Pour cette raison, dans un premier temps, j'essaie d'identifier une backdoor(si elle existe) en utilisant également les tentatives, puis en partant de la connaissance de la solution, en identifiant s'il existe d'autres backdoors et en commençant par les plus performants (plus isolées, avec un voisinage avec moins de candidats à invalider). à la recherche d’extensions menant à la démonstration d’unicité. Dans les cas plus complexes où cette route ne mène pas au succès avec peu de contradictions, je cherche des backdoors de taille 2 à partir de certaines pistes (non parce qu’elles sont prouvées, mais parce qu’elles sont construites à partir d’éléments appartenant à une solution trouvée par une backdoor de taille 1). qui se développent en profondeur et cela pourrait être prouvé par une ou deux contradictions au plus. À ce stade, je travaille à l'envers sur une grille simplifiée qui pourrait être résolue avec une ou deux contradictions au maximum. Certes, il n’ya aucune certitude d’obtenir la solution avec une taille minimale. Pour résoudre les problèmes les plus difficiles avec une taille supérieure, le travail est clairement beaucoup plus long car les backdoors sont de taille supérieure à 2. Dans la grille de studio des 5 backdoors (P2L2C5, P2L3C8, P2L7C4, P1L7C8 et P2L9C9), P (2L9C9) est certainement le plus performant, sur B9, il n’ya que deux 2. Le travail final consistait à identifier le nombre minimal d'extensions démontrant l'invalidité de P (2L7C8). Je n'ai pas pu trouver de solution avec deux extensions. Le seul que j'ai trouvé est celui avec trois extensions dans la case L8C4. Bon week-end

De Francis Labetoulle
(Publié le 08/04/2019)

@ Paolo : Merci pour votre réponse très complète. Je partage votre analyse; mon seul problème, mais il est de taille, est l'aspect chronophage de votre approche sans l'outil informatique. François C a montré la voie à suivre. Peut-être que pour les grilles très difficiles (niveau TDP > 5) un mixage des méthodes est envisageable ?

De Paolo
(Publié le 08/04/2019)

@ Francis Labetoulle: Bonjour, Ce que vous dites est correct. Généralement, lorsque la grille est très difficile, il est pratiquement impossible de comprendre quel est le chemin le plus court menant à la solution avec une taille minimale. Clairement, si je fais un contrôle systématique avec un support informatique de toutes les combinaisons possibles d’extensions de piste, j’ai plus de chance de trouver parmi les nombreuses résolutions celle avec une taille minimale. Cependant, il s’agit d’un travail qui nécessite beaucoup de temps de calcul sur computer et il n’existe aucun travail de synthèse de la part de la personne qui recherche la résolution. La seule chose certaine d'une résolution, c'est qu'elle doit se terminer par une backdoor et qu'il existe une certaine proportionnalité entre la taille de la résolution et la taille de la backdoor de la résolution elle-même. Pour cette raison, j'estime que la recherche d'une backdoor minimale est une bonne approche pour obtenir une résolution de taille minimale. Le temps requis pour trouver une solution (backdoor) est nettement inférieur à celui nécessaire pour démontrer son unicité.

De François C.
(Publié le 09/04/2019)

@ Francis Labetoulle : Bonjour, Petites remarques sur la méthodologie : personnellement j’examine les entités, des plus petites aux plus grandes (en nombre de candidats), je vais donc commencer forcément par des paires de candidats en lien fort. Mais je ne regarde pas si les 2 candidats d’une paire font partie d’un réseau de liens forts plus important (C’est ce que B. Borrelly appelle un réseau générique et qui à mon avis est inutile. Il a reconnu lui-même que les réseaux génériques les plus importants ne donnaient pas forcément les réseaux virtuels (= les pistes) les plus intéressants, et j’ai pu le constater). D’autre part la recherche de backdoors est évidemment intéressante mais plus le niveau de la grille augmente et plus les anti-backdoors (qui mènent, eux, à une contradiction) prennent de l’importance. Ceci évidemment quand on cherche à prouver l’unicité de la solution ce qui est notre cas. Concernant cette grille, effectivement, il est difficile d’éviter la case L8C4 ou les 2B9 tout en cherchant à minimiser la taille.

De Francis Labetoulle
(Publié le 09/04/2019)

@ François C : Bonjour et merci pour votre point de vue, qui envisage une approche plus globale permettant d'espérer l'obtention de la talle minimale. Le mien est plus celui d'un compromis donnant un arbre de résolution de taille souvent plus élevée, mais réalisable "presqu'à la main" en un temps pas trop long (en général). Petite question subsidiaire pour personnes intéressées : que faut-il penser des tailles comparées de vos résolutions des grilles du samedi 6 avril ( niveau annoncé 12) et du dimanche 7 avril (niveau annoncé 19) du site coloriage virtuel, mentionné ci-contre?

De François C.
(Publié le 09/04/2019)

@ Francis Labetoulle : J’obtiens une taille minimale de 3 pour ces deux grilles avec beaucoup de possibilités dans les 2 cas. C’est un peu étonnant car nous sommes habitués en moyenne à un niveau conventionnel de 15 pour un niveau TDP de 3 (remarquez que, en moyenne, ça marche puisque (12+19)/2 = 15,5 ). Ceci dit, en résolvant les 30 premières grilles du site en question, j’ai obtenu une taille 1 pour la grille du 28/07/13 de niveau conventionnel 15 et une taille 2 pour celle du 11/08/13 de niveau conventionnel 18. Il ne me reste plus que 700 grilles à voir et je ne serais pas étonné de rencontrer d’autres cas du même genre. Je serais bien incapable d’expliquer ces curiosités : il faudrait être expert en méthodes de résolution conventionnelles et connaître exactement l’algorithme utilisé pour le calcul du niveau conventionnel : non seulement savoir le barème correspondant à chaque règle, mais aussi le niveau d’optimisation de la résolution car il y a toujours 36 façons de résoudre une même grille et il n’est pas dit que chacune d’elles donne le même niveau (càd le même total de points). En fait on retrouve le même problème qu’avec le niveau TDP, sauf que là ça m’a l’air d’être beaucoup plus compliqué pour optimiser, vu la quantité de règles applicables. Et pour finir, il y a plusieurs niveaux dits conventionnels ! (le niveau affiché par B. Borrelly est une pondération entre le niveau « Hodoku » et celui de « sudoku explainer » (dixit lui-même le 24 Mars).

De Francis Labetoulle
(Publié le 09/04/2019)

@ François C : Bonsoir et bravo. Pour information mon approche "simplifiée" me donne effectivement une taille 3 pour le (19) et une taille 4, en fait 3+ XW ( ou cimetière binaire à cycle impair ) pour le (12). Je pense qu'en fait le niveau 19 est surévalué, le " vieux" logiciel SudoCue que j'utilise pour gérer les candidats donnant un temps de résolution bien trop faible pour un tel niveau. PS : dans mon approche simplifiée j'aurais dû partir de la case L3C3, pour obtenir un taille 3...


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 : C3+=y=xzz#

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.