Discussion :

[Gilbert Geyer]

Bonjour,

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

Bin non, je ne cherche rien : je me suis laisser piéger par le fait que les grilles étaient nommées selon les cas par Grid1.txt, GridX1, GridZ4.txt etc et que le contenu de la GridZ4.txt était identique à une seule case près à celui de l'AI Escargot.
Je ne me serai pas gouré si la GridX4.txt avait été nommée GridAIEScargot.txt
Mais en plus de tout ça, vu que le solveur plantait avec la GridZ4.txt j'en avais déduit hâtivement que l'AI Escargot n'avait pas été résolue autrement que par le brute force de Mick605.
Donc, encore une fois : Mille excuses pour ce problème de confusions.

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 ?

Effectivement le 1 en C3, L8 est candidat unique et en changeant son statut fait disparaître les 1 en C4,L8 + C5,L8 et C6,L8

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

En fait pour résoudre AI Escargot (58 cases à résoudre), il suffit de d'y rentrer seulement 3 résultats :
- un 5 en L1,C5
- un 4 en L3,C5
- un 7 en L7,C5
et avec ce déverrouillage les résultats des 55 cases restantes apparaissent automatiquement par l'effet domino associé à la logique du candidat unique.
Pour Easter Monster (60 cases à résoudre) on obtient le même résultat, mais le déverrouillage nécessite d'y rentrer 4 résultats (le 7, le 6, le 4 et le 9) dans des cases formant un carré.

A+.

[ShaiLeTroll]

Perso, à l'époque du Défi, j'avais regardé des articles sur la résolution de grille
je N'avais RIEN compris au formule !

La seule logique que j'ai mis dans mon programme, c'est la résolution des candidats uniques, le reste c'est aussi un Brut !
Et j'ai même appris à faire des Sudoku au moment du Défi
Tu imagines mon niveau !

Je serais très intéressé de voir un algo de résolution logique, ça me dépasse un peu !

[Gilbert Geyer]

Re-bonjour,

ShaiLeTroll : Perso, à l'époque du Défi, j'avais regardé des articles sur la résolution de grille
... Et j'ai même appris à faire des Sudoku au moment du Défi

Bin moi à l'époque du Défi je ne jouais pas au Sudoku pour la bonne raison que sur les grilles qu'on trouve dans la presse il n'y jamais de place pour y noter les candidats ...
donc j'ai suivi la discussion par curiosité.

Bien plus tard, par curiosité j'ai téléchargé les sources de compétiteurs, en pensant y découvrir lla logique de chacun : mais je n'y ai rien pigé, sauf qu'avec l'un des codes ça m'a au moins appris à utiliser le TDrawGrid.

Mais comme les logique de résolution m'interaissaient j'ai fouillé le net pour en savoir plus, et j'y ai découvert la pléthore des ruses (X-Wing, Swordfish, Jellyfish, Squirmbag) utilisées par ceux qui pratiquent la résolution manuelle et j'ai commencé à les étudier puis ça m'a pris de me mettre à coder et comme à force de galérer j'ai réussi à résoudre l'AI Escargot avec une logique plus simple que toutes ces ruses je me suis dit tiens je vais placer le ZIP sur Dev (ZIP du Sudoku version 2 de la première page).

Je serais très intéressé de voir un algo de résolution logique, ça me dépasse un peu !

Plutôt qu'un algo voici en bref ma logique qui fonctionne avec 4 logiques de base :
A1) Logique "Emplacement ou candidat unique" : Tout candidat unique dans une case est le résultat de cette case.
A2) Logique "Candidat-Résultat => N Candidats à éliminer" : Lorsqu'un candidat C passe dans le camp des Résultats, suite à A1, tous les candidats C de la même ligne, colonne et bloc, n'ont forcément plus aucune raison d'exister et doivent être éliminés.
A3) Logique "Effet Domino" : Toute élimination de candidats qui n'ont plus aucune raison d'exister entraine la diminution du nombre de candidats présents dans la grille : une paire nue peut se transformer en candidat unique donc A.1, un candidat en emplacements jumeaux peut se retrouver en emplacement unique donc A.1, des triplets deviennent jumeaux, etc
A4) Logique "Candidat en Emplacements jumeaux" : Si le candidat n'est pas le résultat de la première case il est le résultat de la case jumelle donc si on se trompe au premier coup on a 100% de gagner au 2ième coup.
Comment détecter qu'on s'est trompé : Il n'y a que deux possibilités, soit l'erreur commise provoque :
- soit l'apparition d'un Resultat-doublon,
- soit elle finit par vider, suite aux A2, une case de tous ses doublons, (l'erreur n'est généralement pas détectable immédiatement lorsqu'elle est commise)
Et en cas d'erreur on recommence à zéro avec une grille-clone de la grille à résoudre.
Donc la solution c'est une moulinette qui prend ces 4 logiques dans l'ordre en travaillant sur des grilles-clone avec un Random(2) pour le choix de l'une des cases jumelles dans laquelle on injecte le candidat jumeau.

Cela fonctionne car tout candidat s'il est jumeau sur une LIGNE il fait aussi 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 et en plaçant le candidat en tant que résultat dans la bonne case l'élimination du candidat dans la case jumelle transforme les jumeaux de la COLONNE en Uniques, les Triplets en Jumeaux, etc et avec ce détricotage progressif on résout n'importe quelle grille (sauf les grilles dévoyées par conception).

Grosso modo cette combinaison de logiques est dérivée de la logique 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 si le résultat est toujours vrai ce candidat en est le résultat ... mais avec l'avantage dû au fait que les candidats jumeaux sont plus fréquents que les Paires nues. La grille AI Escargot ne comporte que 2 paires nues mais 26 cases formant 13 emplacements jumeaux donc 13 fois Random(2) pour démarrer la résolution de ses 58 cases à résoudre.

(Dans le code de mon ZIP, la moulinette qui fait ça c'est la function TSudoku.ResolEmplaJumeaux: boolean : elle actionne le reste)

A+.

[ShaiLeTroll]

J'ai regardé ton source et ton doc, oui je confirme,

• très difficile de comprendre le code d'un autre, surement le même problèmes que tu as rencontré lorsque tu as récupérés nos propositions
• j'avais tenté aussi un code avec l'analyse des jumeaux, de triplés, de quadruplets, de quintuplés ... et je n'ai jamais abouti à un truc qui fonctionne

Du coup, en mode logique, la grille AI Escargot, tu la résout en combien de temps ?

[LadyWasky]

Bah j'applaudi Gilbert, parce que son approche est très forte !
Bravo !

[Gilbert Geyer]

Re-salut,

ShaiLeTroll : J'ai regardé ton source et ton doc, oui je confirme, très difficile de comprendre le code d'un autre, surement le même problèmes que tu as rencontré lorsque tu as récupérés nos propositions

Ah oui : c'est vraiment très ardu, d'autant plus que nos routines en appellent d'autres et on finit par s'égarer en cours de route.

Du coup, en mode logique, la grille AI Escargot, tu la résout en combien de temps ?

En cliquant directement sur le bouton résoudre "Avec en plus la logique Emplacements jumeaux" le résultat s'affiche presque avant d'avoir relâché le bouton, et c'est pareil pour les 8 grilles embarquées sur l'interface : du coup je n'ai pas ajouté de chronométrage. C'est tellement rapide qu'on finit par se lasser de jouer. J'ai acheté un jour chez mon buraliste une revue avec des grilles "difficiles" : il fallait beaucoup plus de temps pour recopier les données dans le DrawGrid que pour résoudre les grilles ... donc au bout d'un moment ce n'est plus rigolo. Je me contente maintenant d'avoir réussi à fignoler la logique (ce truc me chagrinait les neurones) ... mais j'avais passé pas mal de temps à éplucher les ruses de ceux qui pratiquent la résolution manuelle car certaines sont vraiment des ruses de sioux qui sont admirables : chapeau pour les personnes qui ont mis au point le Swordfish et le Jellyfish car ça ne saute pas aux yeux en regardant une grille.

A+.

[Gilbert Geyer]

Re-Bonjour,

LadyWasky : Bah j'applaudi Gilbert, parce que son approche est très forte ! Bravo !

Merci MyLady pour vos applaudissements. Si seulement je trouvais une approche aussi forte pour résoudre mon problème d'agrandissement de mon canvas d'avant-plan car là je suis nul.

A+.

[AlainGTK]

Bonjour,

Info supplémentaire à propos de :
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+.

Re bonjour Gilbert,
Etant novice, j'ai d'abord pris en main Delphi (chargé grâce à ce site. Merci).
Ensuite, en épluchant votre (SUPER !!!) programme , on voit que le chemin de résolution est aléatoire (choix du jumeau dans sa paire, et des suivants). Le nombre de coups dépend donc du hasard. Même si on arrive tôt ou tard à la solution.
Tous les programmes (y compris force brute) peuvent arriver à une solution tôt ou tard par la logique. Cela dépend de quelle logique on parle. Mais le nombre de coups peut être très élevé.
Quant à l'optimisation des microsecondes, c'est un problème de professionnels du temps réel (on peut même inclure des routines assembleur). C'est néanmoins passionnant. (Merci à F. Soriano).
Ce que je recherche : une logique déterministe qui ne soit pas de la force brute (c'est ce que j'ai déjà programmé et qui marche bien sauf pour AI Escargot et sans doute beaucoup d'autre grilles plus difficiles).
Est-ce que çà existe ?
Une idée de challenge : arriver à la solution en une nombre minimum de coups, sur une logique déterministe.
Merci de comprendre que je découvre votre blog, et donc si cette idée de challenge a déjà été retenue, pardonnez-moi.
Bien cordialement,

[Gilbert Geyer]

Bonjour,

AlainGTK : Ce que je recherche : une logique déterministe qui ne soit pas de la force brute

Tout d'abord il y a une grosse différence entre la logique "brute force" qui est abondamment (voire à 100%) basée sur le hasard alors qu'avec la combinaison
des logiques A1 à A4 et ce n'est que dans la logique A4 que le hasard n'intervient uniquement que lors du choix de la case dans laquelle on place le candidat
jumeau et tant que résultat car si on se trompe lors de ce premier choix on a la certitude absolue que ce candidat est le résultat de la case jumelle.
C'est exactement pareil si on cherche à résoudre une grille manuellement : comme le jumeau est le résultat soit de la première, soit de la deuxième, case jumelle
on se contente de déterminer si le premier choix conduit à une erreur et si oui on rectifie le tir sans possibilité d'erreur.

Mais bien entendu rien n'empêche de chercher à trouver comment se déterminer pour faire un bon choix du premier coup lorsqu'on n'a qu'une chance sur deux de se tromper : ça pourra aider dans d'autres circonstances.

A noter en plus que la combinaison des logiques A1 à A3 est à 100% déterministe car elle s'enchaîne selon les étapes suivantes :
1 - tout candidat en emplacement unique est forcément le résultat de cette case,
2 - dès que ce candidat prend le statut de résultat d'une case on sait déterminer avec certitude dans quelles cases ce candidat n'a plus aucune raison d'exister,
3 - comme ces candidats n'ont plus aucune raison d'exister on les élimine sans risquer de se tromper,
4 - tout candidat est présent sur une ligne et cette élimination provoque avec certitude sur sa colonne la diminution du nombre des ses occurrences : les "jumeaux"
se transforment systématiquement en "uniques" (donc : nouveau résultat et retour à l'étape 1), et les "triplés" se transforment en "jumeaux", les "quadruplés" en "triplés", etc.
5 - et tant que ce détricotage par éliminations transforme ces "jumeaux" en "uniques" on accumule à chaque tour de boucle par effet domino et sans risque d'erreur un nouveau résultat.

Et ce n'est que lorsque cet effet domino s'arrête par absence d'"uniques" dans la grille qu'on fait appel à la logique A4 qui :
- s'attaque aux "jumeaux" qui existaient ou qui ont été dégagés par effet domino,
- en cas de choix de la bonne case on peut avec certitude éliminer le candidat de la case jumelle (donc retour à l'étape 3 avec éventuellement un nouvel effet domino),
- en cas de mauvais choix on a la certitude de ne pas se tromper une deuxième fois donc case résolue et on élimine le candidat de la case jumelle (avec retour à l'étape
3 et éventuellement un nouvel effet domino),
- et comme toutes ces éliminations en réduisant systématiquement à chaque fois le nombre des occurrences des candidats résiduels, la grille est résolue soit par le dernier
effet domino soit par le choix de la bonne case lorsque la grille ne contient plus que la dernière paire de "jumeaux".

on voit que le chemin de résolution est aléatoire

... faire "plus déterministe" que ci-dessus : ???

arriver à la solution en un nombre minimum de coups, sur une logique déterministe.

avec ma solution "quasi-déterministe" et la grille AI Escargot, ayant ajouté 3 compteurs dans mon code (1- Erreur sur case vidée de tous ses candidats, 2 - Erreur par Résultat-Doublon, 3 - Recommencement à zéro avec la grille de départ ) j'ai eu les résultats successifs suivants :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
- jamais de ShowMessage " Erreur sur case vidée de tous ses candidats" : ce risque reste donc théorique.
- Erreurs par Résultat-Doublon   et  Recommencements à zéro
                    10                         4
                    3                           0
                    0                           0
                    15                         6
                    0                           0
                    44                         18
                    0                           0
                    3                           2
                    0                           0
                    54                          27
                    ----                       ----
Totaux             129                          57

On constate qu'avec cette logique d'abord que parfois il n'y a ni erreur ni recommencement, et ensuite que l'erreur ne provoque le recommencement à zéro qu'environ une fois sur deux.
Si ces recommencement à zéro sont nécessaires c'est que l'erreur causale n'est pas toujours détectable dans l'immédiat car elle aussi se propage par effet domino.
Et pour ce qui est du nombre de bons coups joués (en l'absence de toute erreur) l'Escargot est résolue par 21 coups de logique "Emplacements Uniques ou Jumeaux" et 37 bons coups par effet domino (les uns s'affichent chez moi en vert et les autres en couleur Olive).

Comparativement à ceci, un brute force doit s'attaquer aux 58 cases à résoudre qui contiennent au total 254 candidats : de quoi mouliner :

A+.

[Gilbert Geyer]

Bonjour,

Complément de réponse à :

AlainGTK : Ce que je recherche : une logique déterministe qui ne soit pas de la force brute ... Est-ce que çà existe ?

Oui, pour obtenir une solution déterministe à 100%, il suffit, en utilisant la combinaison des logiques A1 à A4, de virer le random(2) pour le choix de la Case-Jumelle-Résultat, et au-lieu de ceci choisir systématiquement la case jumelle située soit le plus à gauche, soit le plus haut dans la grille (ou encore, soit le plus à droite, soit le plus bas) : si cela propage par effet domino une erreur faisant apparaître un Résultat-Doublon cela déterminera que le candidat jumeau sera forcément le résultat de l'autre case jumelle ... sinon cela déterminera que le choix a été bon du premier coup.

Bien entendu tout dépend aussi de savoir de quelle logique déterministe on parle : logique qui détermine un bon choix par l'apparition ou l'absence d'erreur comme ci-dessus ? logique par un autre type de calcul ? Car pour résoudre les 58 cases totalisant 254 candidats on peut aussi s'imaginer que ça se résout avec un système de N équations à P solutions ???

A+.

[AlainGTK]

Bonjour,

Complément de réponse à :

Oui, pour obtenir une solution déterministe à 100%, il suffit, en utilisant la combinaison des logiques A1 à A4, de virer le random(2) pour le choix de la Case-Jumelle-Résultat, et au-lieu de ceci choisir systématiquement la case jumelle située soit le plus à gauche, soit le plus haut dans la grille (ou encore, soit le plus à droite, soit le plus bas) : si cela propage par effet domino une erreur faisant apparaître un Résultat-Doublon cela déterminera que le candidat jumeau sera forcément le résultat de l'autre case jumelle ... sinon cela déterminera que le choix a été bon du premier coup.

A+.

Bonjour,
Effectivement, c'est une solution (jumeaux) pour laquelle le nombre de coups ne doit plus rien au hasard.
Je l'ai essayée en commençant par le jumeau qui élimine le plus (12) de candidats sur la grille, et ainsi de suite ... en imaginant que cela accélèrerait le processus.
Toujours pour tenter de répondre à mon challenge : nombre de coups minimum.
Bien sur, une logique (nombre de candidats éliminés, case jumelle en haut à gauche, droite, bas ....) va être meilleure qu'une autre selon la grille de départ.
Il faudrait la tester sur plusieurs grilles réputées "difficiles" et faire un score général.
Mais votre idée est la bonne. Merci.
P.S Je suis débutant en Delphi / Pascal. Donc je ne rentre pas dans votre code. Mais si cela vous tente ...

[Gilbert Geyer]

Bonjour,

AlainGTK : Effectivement, c'est une solution (jumeaux) pour laquelle le nombre de coups ne doit plus rien au hasard.

Elle présente toute fois un inconvénient : En choisissant systématiquement la case jumelle située par exemple soit le plus à gauche sur ligne , soit le plus haut sur colonne dans la grille
et que vous avez affaire à une grille dont la résolution nécessiterait de choisir systématiquement la case jumelle située le plus à droite, soit le plus bas dans la grille
ça va vous générer davantage d'erreurs et nécessiter un nombre de coups à jouer plus élevé ... alors qu'avec une petite dose d'aléatoire avec Random(2) on évite (statistiquement une fois sur deux) l'inconvénient de cette systématisation.

Pour le cas où ça peut vous intéresser voici la copie d'écran faite à l'issue d'une résolution, avec Random(2), et qui s'est déroulée sans aucune erreur et aucun recommencement à zéro.

Les grands chiffres sont les résultats :
- en Noir ceux révélés sur la grille de départ,
- en Vert ceux révélés par les logiques du candidat en emplacement(s) soit "unique", soit "jumeaux",
- et en Olive ceux révélés par effet domino

Les petits nombres situé sous les grands chiffres révèlent l'ordre chronologique dans lequel chaque case a été résolue : en suivant du regard cette chronologie on se rend compte qu'on parcourt le grille en sautant dans tous les sens .

A+.