GN09 XSUDO1

Bonjour,

J'ouvre cette page qui serait mieux dans les outils, mais elle concerne les discussions du moment.

Nous parlons beaucoup de l'approche globale par les ensembles femés de rang 0 ou voisin de 0.
Allan Barker a développé un outil puissant qui permet de faire ce travail directement sur la grille.

Je viens de le charger et je commence à le découvrir.
Pour ceux qui s'interessent au sujet, voici le point de chargement.


http://sudokuone.com/xsudo1/xsudo1.htm


J'ai chargé la dernière version et suis en train de tester le système, avec l'aide d'Allan Barker.

C'est un très bon complément à ce que sait faire mon programme, j'y ferai donc sans doute souvent référence.

Si d'autres veulent tenter l'aventure, nous pourrons partager nos expérience (et difficultés).

gpenet

bonjour Gpenet,

Par curiosité, j' ai essayé le programme de A.Barker en particulier le TUTORIAL1.
Impressionnant. Il descend 13 candidats d'un seul coup. On ne sait pas très bien comment? Intéressant quand même quand on ne trouve pas de sortie avec les outils classiques.
En tous les cas, très bel outil informatique.

André
N.B.J'ai essayé de trouver la traduction du mot "TRUTH" que je ne comprends pas très bien dans le contexte.
Je n' ai trouvé que "Vérité".?

COLLIN a écrit:

bonjour Gpenet,

Par curiosité, j' ai essayé le programme de A.Barker en particulier le TUTORIAL1.
Impressionnant. Il descend 13 candidats d'un seul coup. On ne sait pas très bien comment? Intéressant quand même quand on ne trouve pas de sortie avec les outils classiques.
En tous les cas, très bel outil informatique.

André
N.B.J'ai essayé de trouver la traduction du mot "TRUTH" que je ne comprends pas très bien dans le contexte.
Je n' ai trouvé que "Vérité".?

Bonjour Collin,

1) Je sais comment cà marche, mais je considère qu'il n'est utilisable sans réserve que si on trouve des ensembles de rang 0 ou "quasi 0".

J'ai d'ailleurs une espèce de démonstration par l'absurde. Si on entre par exemple toutes les cases en "set" et toutes les lignes, colonnes, boites en "linkset", on obtient en une seule fois tous les valides et tous les invalides. Ce serait absude de pésenter une telle solution.

Le "raisonnable" se situe donc quelquepart entre une structure totalement de rang 0, qui est un peu la même chose que les matrices carrées de soryu, et ce monstre.

Je ne sais pas bien placer la frontière, mais je vais essayer d'illustrer mon propos sur la résolution complète de col0805 1622 en jouant sur les deux tableaux.

J'avais déja trouvé un peu complexe la structure qui permet de démarrer Fata Morgana et j'avais été très content de trouver une échappatoire par les Exocets.

C'est à nous de trouver progressivement la place qu'il peut utilement trouve dans l'arsenal des moyens de résolution.





Concernant "truth", c'est un changement de vocabulaire récent :

Set ou "cover set" est devenu "Truth"

"Link Set" est devenu "False".

Ceci nous rapproche du vocabulaire de Soryu

"Lien" -> un de vrai au moins
"Conflit" -> pas deux de vrai

et du rôle joué par ces deux ensembles dans le raisonnement.

amicalement

gpenet

PS1: c'est en tous cas un outil précieux pour la recherche des structures de rang 0 dans les grilles du type de celles que j'ai présentées.

PS2: il me semble de mémoire que le tutorial 1 est un "fish complexe". Je vais vérifier et dire pourquoi il élimine. De toutes façons, si on ne sait pas pourquoi une structure élimine, on ne doit pas à mon sens la produire.

Re bonjour André,

Je reviens sur le tutorial 1 limité au premier groupe d'éliminations.
En voici le résumé.

TUTO 26 Candidates, Raw Rank = 0 (linksets - sets)
8 Sets = {4569N5 4569N6}
8 Links = {678c5 128c6 59b5}
9 Eliminations --> r127c5<>8, r278c6<>8, r5c4<>59, r7c5<>7,

Code:

+------------------+-------------------------+-------------------+
| 458 1 9 | 258 45-8 6 | 3 2478 247 |
| 458 7 2 | 589 3459-8 3459-8 | 168 14689 469 |
| 348 348 6 | 289 1 7 | 28 2489 5 |
+------------------+-------------------------+-------------------+
| 1 245 457 | 3 (5678) (258) | 9 2467 2467 |
| 2347 23459 457 | 167-59 (5679) (1259) | 2567 23467 8 |
| 6 2359 8 | 4 (579) (259) | 257 237 1 |
+------------------+-------------------------+-------------------+
| 2478 6 457 | 5789 3459-78 3459-8 | 1278 12789 2379 |
| 478 458 1 | 56789 2 3459-8 | 678 6789 3679 |
| 9 28 3 | 1678 (678) (18) | 4 5 267 |
+------------------+-------------------------+-------------------+

Cette structure est de rang 0, celui que l'on peut utiliser sans réserve. Soryu le transformera aisément en tableau carré.
Dans une structure de rang 0, tous les "linksets" sont assignés sur des sommets appartenant aux "sets". Soryu le dit différemment, mais il a le même théorème. Donc tous les points des linksets qui n'appartiennent pas aux sets sont éliminés. (soryu dirait toute le colonnes sont des liens).

C'est une généralisation, si je puis dire, des XWings, Swordfishes ...

La structure suivante est plus compliquée à décoder. Je réserverais pour plus tard.

amicalement
gpenet


EDIT Je termine l'exeercice.

Une fois que tu as fait les éliminations du premier temps, tu te trouves avec un XWing des 8 qui te donne la fin.

Si tu combines les deux groupes, tu contruis un SLG qui te donne l'ensemble, celui de l'exemple. Je préfère nettement opérer en deux temps.

gpenet a écrit:

Bonjour,

Allan Barker a développé un outil puissant qui permet de faire ce travail directement sur la grille.
gpenet

Bonjour gpenet,
.
Sur un grille au hasard (il s'agit de SE09) j'ai fait ce que vous dites : toutes les cases sont regardées comme "liens" (sets).
Les conflits (linksets) sont les liens-chiffres. Je m'attendais que les lignes et les colonnes suffiraient, mais c'est faux. Dans cet exemple, le linkset des 9 en boite 1 ne peut pas etre enlevé, etc.
Ceci dit je ne sais pas "comment ça marche". J'ai réessayé de faire marcher brutalement la méthode des liens dérivés (qui est exactement adaptée à ces concepts de liens et de conflits), mais je me heurte toujours à des débordements de mémoire...
Cordialement,
.
soryu.

soryu a écrit:

.
Sur un grille au hasard (il s'agit de SE09) j'ai fait ce que vous dites : toutes les cases sont regardées comme "liens" (sets).
Les conflits (linksets) sont les liens-chiffres. Je m'attendais que les lignes et les colonnes suffiraient, mais c'est faux. Dans cet exemple, le linkset des 9 en boite 1 ne peut pas etre enlevé, etc.
Ceci dit je ne sais pas "comment ça marche". J'ai réessayé de faire marcher brutalement la méthode des liens dérivés (qui est exactement adaptée à ces concepts de liens et de conflits), mais je me heurte toujours à des débordements de mémoire...
Cordialement,
.
soryu.

Bonjour soryu,

Je me reconnecte après une semaine sans internet et je essaye de répondre à quelques unes de vos interrogations.

1) Comment ça marche.

Oublions un instant le découpage en sets et link sets. Le modèle d'Allan Barker applique la règle de base du sudoku (Un seul chiffre par ligne, colonne, boite et neufs chiffres disponibles). C'est la seule qu'il connaisse.


1.1)

Il ne traite que des "sets" qui sont les positions possibles pour un chiffres en ligne / colonne / boite ou les chiffres encore possibles dans une case.

Il gère un sous ensemble des sets et ne peut appliquer la règle logique que sans ce sous ensemble. Il regarde alors toutes les combinaisosn possibles

On peut prendre comme exemple trois lignes qui pourraient être dans un swordfish résolu de 1:

A B C D E F G H I

. . 1 . . 1 . 1 .
.
.
. . 1 . . 1 . 1 .
.
.
. . 1 . . 1 . 1 .


Si je prends les trois sets ligne, j'ai 81 combinaisons possibles pour le placement des 1.
Si j'ajoute les sets colonne, je n'ai plus que six combinaisons.

1.2) J'ai volontairement pris un swordfish "résolu" pour simplifier. Si j'ajoute des "1" possibles dans les colonnes pour les lignes autres que les trois lignes de base du swordfish, aucune combinaison valide ne peut être construite occupant une de ces positions.

Si j'ajoutais à mon lot de sets un set quelconque non relié (la case A1 par exemple), j'augmenterai certes le nombre de combinaisonsons, mais je constaterai toujours que les positions invalides restent invalides.


Je peux de la même manière imaginer que mon sous ensemble identifie une des valeurs de la grille. Si ma grille a une solution unique et que je prends tous les sets non résolus, l'ensemble de contraintes me conduit nécessairement à une seule combinaison valide, donc à toutes les éliminations et à toutes les assignations.

1.3) Le modèle de base ne se préoccupe donc pas du découpage en "base set" et "link sets"'. Il recherche toutes les combinaisons valides pour un sous-ensemble de sets et constate les "éliminations / assignations" qui en résultent. C'est ainsi que je procède pour détecter les groupes de chiffes ayant du potentiel.


2) Le découpage en "sets de base" et "sets de couverture" est une analyse complémentaire qui recherche des raisons simples pour ces éliminations/assignations.

Le principe en est de déterminer des régions de rang 0,1,2,3.

rang 0: tout candidat d'un link set non attaché à un sete est éliminé,
rang 1: tout candidat appartenant à deux linksets et non nattaché à un set est éliminé
rang 2: (maximum ?) id pour trois linkset

La recherche des régions de rang x devient vite un exercice inextricable. Il suffit pour s'en convaincre de parcourir le "fil" Monster loop très actif en ce moment.
Ma stratégie personnelle sera de me limiter aux structures assez simples en mode "fish", celui qui se traite mal par les chaînes. Les acteurs du "fil" précité cherchent au contraire à pousser la construction sets linksets à ses limites, ce qui est un autre exercice.

3)
Les conflits (linksets) sont les liens-chiffres. Je m'attendais que les lignes et les colonnes suffiraient, mais c'est faux. Dans cet exemple, le linkset des 9 en boite 1 ne peut pas etre enlevé, etc.


Dans l'exercice que je proposais, j'étais certain qu'en prenant tous les sets chiffres en linksets on avait dans la logique l'unicité de la solution. Il n'y a aucune raison de penser que cette propriété est encore définie en supprimant toutes les boites. Allan Barker a développé des outils performants pour rechercher une configuration minimale de linksets conservant une propriété donnée. J'ai essayé de prospecter cette voie, mais sans résultat probant, et surtout avec des temps de traitement de très loin supérieurs à ceux de la recherche de chaînes dérivées. J'avais laissé tomber, et j'y suis revenu quand Allan a constaté que les grillse qui résistaient aux chaînes, Exocets . . . avaient des structures de type "fish".

Vous pouvez, dans l'exercice que vous avez fait, utiliser l'un de ces outils optionnels pour voir le type de cure d'amaigrissement qu'il pratique.

cordialement

gpenet

Bonjour gpenet,
.

gpenet a écrit:

Le modèle de base ne se préoccupe donc pas du découpage en "base set" et "link sets"'. Il recherche toutes les combinaisons valides pour un sous-ensemble de sets et constate les "éliminations / assignations" qui en résultent. C'est ainsi que je procède pour détecter les groupes de chiffes ayant du potentiel.

J'avais cru, un peu naïvement, que les éliminations par les SLG étaient trouvées par des moyens LOGIQUES. Réflexion faite, et ce que vous dites me le confirme, il s'agit de SLG traités en force brute (méthode du Chimpanzé donc), qui cherche TOUTES les solutions et CONSTATE ce qui se passe. J'avais noté d'ailleurs que la JUSTIFICATION LOGIQUE des brillantes éliminations était curieusement absente dans la plupart des cas (le calcul du "rang" n'a rigoureusement aucun intérêt en général, sauf si c'est 0 ou 1 ou 2).
NOTE : la méthode du Chimpanzé est...parfaitement logique, n'est-ce pas ?

gpenet a écrit:

Oublions un instant le découpage en sets et link sets. Le modèle d'Allan Barker applique la règle de base du sudoku

Je pense que ce découpage est conservé par A.Barker (je crois avoir constaté que si on remplace un linkset par un set ce n'est plus pareil). En fait il s'agit tout simplement du traitement de mini-sudokus formels (dématérialisés comme disait joel64) : on choisit un certain nombre de sets et de linksets ; les liens sont les sets, les conflits sont dans les linksets. Autrement dit la règle de ce mini-jeu est : chaque set contient une fois vrai au moins, chaque linkset une fois vrai au plus.
.
En fait Xsudo contient 2 solveurs différents : le premier fonctionne comme ci-dessus "en force brute". Le deuxième (classique) identifie les "patterns" connus, les plus simples d'abord, pour avancer pas à pas.
.
Cordialement,
.
soryu.

soryu a écrit:

1)J'avais cru, un peu naïvement, que les éliminations par les SLG étaient trouvées par des moyens LOGIQUES. Réflexion faite, et ce que vous dites me le confirme, il s'agit de SLG traités en force brute (méthode du Chimpanzé donc), qui cherche TOUTES les solutions et CONSTATE ce qui se passe. J'avais noté d'ailleurs que la JUSTIFICATION LOGIQUE des brillantes éliminations était curieusement absente dans la plupart des cas (le calcul du "rang" n'a rigoureusement aucun intérêt en général, sauf si c'est 0 ou 1 ou 2).
NOTE : la méthode du Chimpanzé est...parfaitement logique, n'est-ce pas ?


2)

gpenet a écrit:

Oublions un instant le découpage en sets et link sets. Le modèle d'Allan Barker applique la règle de base du sudoku

Je pense que ce découpage est conservé par A.Barker (je crois avoir constaté que si on remplace un linkset par un set ce n'est plus pareil). En fait il s'agit tout simplement du traitement de mini-sudokus formels (dématérialisés comme disait joel64) : on choisit un certain nombre de sets et de linksets ; les liens sont les sets, les conflits sont dans les linksets. Autrement dit la règle de ce mini-jeu est : chaque set contient une fois vrai au moins, chaque linkset une fois vrai au plus.
.
3)
En fait Xsudo contient 2 solveurs différents : le premier fonctionne comme ci-dessus "en force brute". Le deuxième (classique) identifie les "patterns" connus, les plus simples d'abord, pour avancer pas à pas.

Re bonjour,


1) J'ai un peu simplifié, mais pour moi, la recherche est un peu en méthode du chimpanzé, d'où mon refus d'en utiliser les résultats sans discernement.

Je ne voudrais tout de même pas donner une impression réductrice du modèle d'Allan Barker. Une des possibilités, dont je connais mal le mode d'emploi, est la recherche progressive d'un sous ensemble actif, un peu comme certains semblent construire les chaînes alternées ou les "T" chaînes. Il applique alors à ce sous-ensemble une optimisation qui produit un SLG qui, dans les cas simples, se révèle très consommable.

Quant au rang, il est effectivement sans intérêt s'il dépasse 1 ( on peut en théorie aller à 3, me semble-t-il). Le rang brut peut être supérieur, la détection des "régions" de rang 0,1,2 est vite un casse-tête.

2) Quand il fonctionne en mode "manuel", le modèle d'Allan Barker conserve la classification set/linkset de l'utilisateur. Cela peut effectivement changer la logique d'élimination.
Je dois encore analyser le fonctionnement de cette partie du modèle. J'ai en particulier noté une couleur "rouge sombre" dont je n'ai pas compris, faute d'avoir lu la documentation, la signification. On la retrouve, sauf erreur de ma part dans une image que vous avez publiée récemment.

3) Oui, mais la partie classique, simple, est sans doute là pour accélérer et sécuriser les enchaînements

cofrdialement

gpenet

ps: xsudo1 reste un très bon outil pour trouver les "multi fishs"