Discussion :

[Gilbert Geyer]

Bonjour,

La logique utilisée par l'appli ci-jointe pour résoudre des grilles du type AI Escargot est dérivée de celle des "Candidats forcés en chaîne de cases à Paires nues" qui considère que si, quel que soit le choix de départ, le résultat d'une case de la chaîne est toujours faux ce candidat peut être éliminé.
Et cette logique dérivée, au lieu de s'appuyer sur des cases à Paires nues, s’appuie sur les candidats situés en Emplacements Jumeaux et considère que si, quel que soit le choix de départ, ce choix provoque l'apparition, soit d'un doublon parmi les résultats, soit d'une case vidée de tous ses candidats alors ce candidat peut être éliminé ... mais avec un énorme avantage résultant du fait que les candidats jumeaux sont nettement plus fréquents que les Paires nues et que les Paires nues formant de surcroît une chaîne sont encore plus rares. (AI Escargot ne comporte que 2 paires nues mais 26 cases formant 13 emplacements jumeaux donc 13 à résoudre sur ses 58 cases à résoudre, et le reste se résout par effet domino + la logique des candidats situés en emplacement unique)

Pour plus de détails sur cette logique voir §A de l'Aide n°2 dans Zip ci-joint.

Mais comme l'utilisation d'un logiciel qui donne presque instantanément la solution d'une grille c'est vite ennuyeux celui-ci est utilisable pour une résolution manuelle plus ou moins assistée par ordinateur ... y compris à n'utiliser l'ordi que pour s'imprimer sa grille avec tous ses candidats et se la résoudre loin de l'ordi.

Autre curiosité : On peut également constater que pour résoudre la Grille_AIEscargot on peut la déverrouiller en plaçant un 5 en L1C5, un 4 en L3C5 et un 7 en L7C5 et le reste se résout alors entièrement par effet domino et la règle du "Candidat en Emplacement Unique".

A+.

EDIT du 14/11/2013 11h : Le Zip qui se trouvait ici est remplacé par celui joint à mon message du 14/11/2013.

[Gilbert Geyer]

Bonjour,

Suite à une modif de dernière minute l'appli de mon Zip précédent ne permettait plus de saisir directement des grilles dans le TMemo de la Grille 8 : j'avais oublié le Chr(VK_RETURN) dans la routine de filtrage des saisies !!!
Ce problème est réglé avec le nouveau Zip ci-joint.

J'en ai profité pour permettre de récupérer via le presse-papier également des grilles où le '0' se trouve remplacé par des tirets-bas : 1__3__8__326___1___9___6________4_6__1__52___734____2_2_85____7_____8_4______9_5_ : qu'elles soient sur 1 seule ou 9 lignes, les points, les tirets '_' ou '-' ou les espaces sont convertis en des 0.

A+.

[Gilbert Geyer]

Bonjour,

En ouvrant la présente discussion je pensais que la résolution par la logique de grilles du type AI Escargot intéresserait encore un peu la curiosité de quelques uns des anciens combattants qui ont participé à la discussion du Défi n°5
.... mais on dirait bien que cela n'intéresse plus personne ???

A+.

[Rekin85]

Bon alors, bien que n'étant pas sudokiste effréné, mais néanmoins féru d'informatique, j'ai essayé très sérieusement ce logiciel. Je n'ai qu'un mot : EXHAUSTIF !

J'ai tout compris des finesses du sudoku de haut niveau et j'ai enfin admis que la résolution de grilles telles AI Escargot ne relève pas du "j'y vais au petit bonheur la chance (alors brute force ?)", mais bien d'un raisonnement logique : départ les jumeaux (d'autres sur le Net appellent ça la méthode des pistes) c'est imparable : et au maximum 2 essais et la résolution s'enchaîne impitoyablement. Bien sûr c'est à la limite de la méthode essais-erreurs, mais avec une limitation logique des erreurs (1 seule admise...)

Alors un autre mot me vient à l'esprit : PEDAGOGIQUE !

Le logiciel et la notice : un très bel ensemble sur le sudoku. Alors BRAVO GILBERT !

Un seul petit, tout petit, regret : oeuvre d'informaticien chevronné mais un peu trop dense d'aspect en première approche... Mais ce n'est rien, l'essai est beau !

[Gilbert Geyer]

Bonjour,

Rekin85 : Bon alors, bien que n'étant pas sudokiste effréné, mais néanmoins féru d'informatique, j'ai essayé très sérieusement ce logiciel. Je n'ai qu'un mot : EXHAUSTIF ! ... Alors BRAVO GILBERT !

Merci René pour ce bouquet de fleurs constellé de compliments.
Par contre je n'ai pas la prétention d'avoir été "EXHAUSTIF", loin de là car on trouve sur le Net des techniques de résolution manuelle que je n'ai pas codés comme par exemple les suivantes : Empty_Rectangles, Unique Rectangles, Extended Rectangles, Finned X-Wing, Finned Swordfish qui permettent parfois d'éliminer quelques candidats.

A propos de la logique des candidats situés en emplacements jumeaux je tiens également à signaler que si elle est très efficace pour résoudre des grilles à solution(s) unique ou multiples elle ne peut en aucun cas fonctionner avec des grilles dévoyées, les pires étant des "grilles dévoyées par conception" :
J'entends par grille dévoyée par conception une grille créée à partir d'une grille-source à solution unique dans laquelle on a ajouté, au moins dans une case, une N+Unième valeur-révélée différente de la valeur-résultat-unique de la grille-source ... et dans ce cas comme l'"erreur" est logée dans le camp des valeurs-révélées ce type de grille n'a plus aucune solution ni par la logique ni par un brute-force puisque la case en question est occupée par un "coucou" qui a pris la place d'un autre.
... Et pour pimenter les choses, le nombre possible de telles grilles est nettement plus grand que celui des grilles à solution unique vu que chacune de ces dernières peut donner naissance à plusieurs grilles diversement dévoyées. Mais bon pour ce type de grilles il y a la touche-clavier Echap ou Fin.

Mais dans la logique des candidats en emplacements jumeaux j'aurais bien aimé qu'elle soit aussi praticable en résolution manuelle car comme actuellement j'utilise une grille-clone pour pouvoir revenir en arrière en cas d'erreur, je vois mal un joueur de sudoku se photocopier sa grille-papier à chaque étape de sa résolution pour revenir en arrière en cas de besoin.
... Mais bon, dans ce cas on peut au moins se l'imprimer.

A+.

[tourlourou]

Fort beau travail, que j'ai à peine effleuré...

A noter que :
1) mon D5 Pro ne reconnaissait pas le uses StrUtils, vite pallié en utilisant StringReplace au lieu de AnsiReplaceStr et en codant un ReverseString ;
2) l'affichage de la charte couleur n'est pas conforme (Win7) aux libellés, cf. image jointe, les possibilités apparaissant en noir (couleur des révélés), et les révélés de 2 couleurs...

[Gilbert Geyer]

Bonjour Yves,

2) l'affichage de la charte couleur n'est pas conforme (Win7) aux libellés, cf. image jointe, les possibilités apparaissant en noir (couleur des révélés)

... Je me suis simplifié la vie en mettant en noir les candidats possibles comme les révélés puisqu'on les distingue par leur taille, par contre je vais modifier le Hint de la charte couleur.

A+.

[tourlourou]

Bonjour Gilbert,

Tu as raison pour la taille, qui ne prête pas à confusion.
Sur mon exemple, le 8 et le 2 en grand format sont tous deux révélés, mais apparaissent dans les 2 couleurs de droite de la charte (effet du fond ?)

Y a-t-il possibilité de ne disposer que de la grille sans aucune aide ? (c'est pê écrit dans l'aide, mais tu connais les utilisateurs... )

[Gilbert Geyer]

Bonjour Yves,

1) Sur mon exemple, le 8 et le 2 en grand format sont tous deux révélés, mais apparaissent dans les 2 couleurs de droite de la charte (effet du fond ?)

Pour ma part je nomme "révélés" les chiffes qui figurent sur la grille à résoudre, par opposition à ceux qui sont "résolus" par la suite.
Les 2 couleurs de droite de la charte servent à distinguer les chiffres qui ont été "résolus" :
- soit directement par la logique pilote : le Vert,
- soit par effet domino : la couleur Olive.
Exemple : si je trouve un candidat en emplacement unique sur une ligne la routine CandiToRes le transforme en valeur résolue affichée en vert, ensuite cette même routine élimine les homologues de ce même candidat dans les unités partagées (ligne, colonne, bloc) et si lors de ces éliminations il ne reste plus qu'un candidat unique dans une case la routine s'appelle récursivement et transforme ce candidat en valeur résolue (effet domino) affichée en couleur Olive.

2) Y a-t-il possibilité de ne disposer que de la grille sans aucune aide ?

Pour l'instant je me suis dit que le mode d'assistance minimal consistait à n'utiliser la machine que pour s'imprimer une grille avec tous ses candidats et se la résoudre loin de la machine (il n'y a jamais de la place pour noter tous les candidats sur une grille qu'on trouve dans un journal).
Ensuite j'ai prévu pour une résolution manuelle le "Mode 1 : Assistance réduite : Modif de la grille suivie par l'Actualisation des candidats + Effet Domino et Message d'erreur le cas échéant" ... donc pour l'instant il y a toujours une aide plus ou moins réduite.
Comme ta question équivaut à "utiliser un logiciel sans aucune aide" et qu'un logiciel apporte toujours un minimum d'aide ta question m'intrigue.
... mais peut-être qu'en la précisant un peu mieux on devrait s'en sortir.

A+.

[AlainGTK]

Bonjour,
Je progresse dans la résolution de grilles Sudoku.
Avant tout, merci de vos contributions. Très didactiques (fichier .zip), elles me sont une aide précieuse.
J'ai programmé (C++ API Windows) la résolution de grilles. Cà marche parfaitement pour des grilles réfutées "difficiles" (???).
Je me suis attaqué à l'Escargot qui évidemment pose problème pour un non expert.
J'ai suivi les logiques que vous décrivez : A1 à A3 et je m'attaque aux emplacements jumeaux.
Je retrouve bien pour les emplacements jumeaux les 26 cases à tester.
L'idéal serait d'arriver à une erreur et donc valider l'autre jumeau. Mais cela n'arrive jamais si on suit les logiques A1 A2 A3.
Faut-il faire simultanément 2 hypothèses sur deux couples de jumeaux ?
Merci d'avance.

[Gilbert Geyer]

Bonjour,

AlainGTK : Je me suis attaqué à l'Escargot qui évidemment pose problème pour un non expert.
J'ai suivi les logiques que vous décrivez : A1 à A3 et je m'attaque aux emplacements jumeaux.
Je retrouve bien pour les emplacements jumeaux les 26 cases à tester.
L'idéal serait d'arriver à une erreur et donc valider l'autre jumeau. Mais cela n'arrive jamais si on suit les logiques A1 A2 A3.
Faut-il faire simultanément 2 hypothèses sur deux couples de jumeaux ?

Vérification faite la grille AIEscargot est entièrement résolue par la routine TSudoku.ResolEmplaJumeaux qui travaille avec des grilles-Clones qui mémorisent l'avancement
et dans lesquelles se mémorisent donc les deux seuls types d'erreurs susceptibles de se produire :
- ErrCaseVideNonResolue = Eliminations ayant vidé une case de touts ses candidats;
- et ErrValResDoublon = Apparition d'un Résultat-Doublon dans une ligne, colonne, ou bloc.
et en cas d'erreur on récupère la grillle-clone d'avant puis on permute les indices pour injecter le candidat-résultat dans la 2ième case de l'emplacement de jumeaux
(donc on ne fait pas simultanément 2 hypothèses sur deux couples de jumeaux, mais toujours l'une après l'autre)
et bien entendu chaque fois que l'on recommence on fait appel à la résolution par la logique des Emplacements ou Candidats Uniques.
Et les deux logiques associées à cette gestion d'erreurs causent ensemble l'effet domino qui n'est qu'une heureuse conséquence.
Cette manière de résoudre l'Escargot n'est pas envisageable manuellement car il faudrait manipuler plein de grille-clones en papier.

A+

[ShaiLeTroll]

@AlainGTK : Tu trouveras d'autres versions de Solver dans la page dédié à ce Défi : Les Défis DELPHI - Le Sudoku Solver et l'explication détaillée de Franck Soriano

Tu noteras même que lors du défi et des échanges sur le forum, la fameuse "AI Escargot" n'a pas été la plus lente à résoudre, d'autres étaient bien pire comme "Easter monster"

[Gilbert Geyer]

Bonjour,

Info supplémentaire à propos de :

J'ai suivi les logiques que vous décrivez : A1 à A3 et je m'attaque aux emplacements jumeaux.

La logique des emplacements jumeaux étant la logique A4 voici les raisons pour lesquelles ces 4 logiques suffisent pour résoudre n'importe grille avec une bécane :
- Tout candidat est obligatoirement placé à la croisée d'une ligne et d'une colonne,
- Tout candidat s'il est jumeau sur une ligne fait partie, sur sa colonne, selon les cas : d'un couple de jumeaux, de triplés, de quadruplets, de quintuplés, ou de N-Uplets av N < 9 et N désignant ici (contrairement à la coutume des NUplets) le nombre d'apparitions du candidat sur la ligne ou la colonne,
- Tout jumeau est le résultat d'une seule des 2 cases jumelles, donc l'élimination du candidat dans la mauvaise case de la ligne a comme conséquence que dans sa colonne s'il y faisait partie : de jumeaux il y devient unique, de triplés il y devient jumeau, de quadruplets il y devient triplé, etc, et ceci réduit progressivement le nombre de candidats de la grille tout en amenant progressivement les N-Uplets à se transformer finalement en Jumeaux ou en Uniques, et comme chaque Unique est un bon Résultat et qu'avec chacun des 2 Jumeaux on sait que s'il n'est pas le Résultat de la première case jumelle il est forcément le bon Résultat de la seconde case jumelle on finit toujours par converger vers la résolution complète de la grille grâce à ce détricotage progressif.

A+.

[Gilbert Geyer]

Re-Bonjour,

ShaiLeTroll : Tu noteras même que lors du défi et des échanges sur le forum, la fameuse "AI Escargot" n'a pas été la plus lente à résoudre, d'autres étaient bien pire comme "Easter monster"

Vérification faite, le seul solver qui a résolu l' AI Escargot a été le Sudoku Solver de Mick605 mais seulement en mode de résolution "Brute Force" alors que tous ceux qui utilisaient uniquement une approche logique s'y cassaient les dents. (Pour AI Escargot le solver d'AndNotOr répond "I'm effraid Dave that this grid cannot be resolved" par contre son interface est hyper-chouette.

A+.

[Andnotor]

Pour AI Escargot le solver d'AndNotOr répond "I'm effraid Dave that this grid cannot be resolved"

Surprenant ! J'ai refais un essai et pas de soucis...

[Gilbert Geyer]

Re-bonjour,

Andnotor : Surprenant ! J'ai refais un essai et pas de soucis...

Bizarre, car avant de dire une bêtise j'ai moi aussi refait un essai dont voici à gauche la copie d'écran de ton appli avec l'AI Escargot et à droite une copie qui permet de vérifier qu'il s'agit bien d'AI Escargot.
Mais peut-être que tu as modifié ton code depuis l'époque où j'ai téléchargé ton application puisque tu dis "pas de soucis" ???.

A+.

[Andnotor]

Bizarre, car avant de dire une bêtise j'ai moi aussi refait un essai dont voici à gauche la copie d'écran de ton appli avec l'AI Escargot et à droite une copie qui permet de vérifier qu'il s'agit bien d'AI Escargot.

Ce "9" en bas me pique l’œil (j'en ai qu'un).

[Gilbert Geyer]

Re-Salut,

Andnotor : Ce "9" en bas me pique l’œil (j'en ai qu'un).

Effectivement tu as raison : vérification faite il s'agit de ta grille GridZ4.txt pour laquelle on a la réponse "I'm effraid Dave that this grid cannot be resolved"
alors que ton l'AI Escargot c'est la GridX4.txt pour laquelle, comme tu dis "pas de soucis".
Donc mille excuses dans la précipitation je n'avais pas remarqué ce "9" parmi tous les autres révélés qui sont en tous points identiques à ceux de l'AI Escargot.

En fait ta GridZ4.txt c'est ce que j'appelle une "grille dévoyée par conception" impossible à résoudre ni par la logique ni même pas avec un Brute Force car il s'agit
de l'AI Escargot où un malin a ajouté un "faux révélé" (le "9") dans la case où le seul révélé ne peut être que le "3" : je viens de vérifier avec le brute force de Mick605 : impossible à résoudre.

A+.

[ShaiLeTroll]

Tu cherches le vice avec une mauvaise grille en entrée, cela semble normal que si la grille est fausse en entrée qu'un solveur ne puisse la résoudre

[LadyWasky]

Marrant cette grille, là en bas à gauche, tout de suite, je peux dire par la logique des plus simples qu'il y a un 1, c'est bien les paires jumeaux, mais c'est pas mieux de simplifier la grille avant ?

Attention à la réponse, je suis redoutable en Sudoku !

J'allais parler du 9 qui pique les yeux aussi