Infernale FigMag du 25/7/09

Bonjour à tous

Pour ceux qui ne sont pas familiers du marquage, je reposte directement ma solution de la dernière "infernale" du Fig'Mag dont j'ai parlé avec soryu à la fin de mon fil précédent.

Voici la position de blocage de mots-croisés après un début classique de 26 coups (chiffres d'origine en bleu)



J'ai commencé un marquage à partir des bases
A=1c8 B=9c1 C=1h3 D=6b3 E=5g2 F=8e7 G=6g1

Pour compléter les nappes de coloriage, vous devez noter par des marques X-x tous les liens "jumos" (jumeaux en unité ou duos en case) qui sont visibles sur la grille à partir de la base X, ce qui fera apparaître des conflits de marques à l'intérieur d'une même case, ou dans une unité commune pour un même chiffre.

On remarque d'abord les conflits CE/g2, 5ce/i52 qui provoquent la fusion e=C par la chaîne >CeC (C=>e=>C)

Ceci élimine 46 de g2 et les 5 de i78. Il reste les autres conflits

aB/c1, Ac/g9, CD/b3, 5cF/g27, FG/i8, 6BG/eg1, 6dG/i38

qui se résument par la chaîne d'implications

>(F,BA)Cdg équivalente à son opposée en casse inverse > GDc(ab,f)

Comme il n'y a plus rien à en tirer directement il faut s'occuper des OU qu'elle représente aussi. En effet si on inverse la casse d'une marque dans cette chaîne elle forme un OU avec toutes celles qui la suivent, puisqu'un conflit [xy] crée les implications x>Y y>X ainsi que les OU commutatifs XY YX

En pratique il suffit donc de compléter la table des implications provenant des conflits en lui ajoutant une seconde colonne de tête avec la casse inverse de la marque de base. On lit alors en même temps les implications et les OU, qu'ils soient directs et dérivés (notés après le +)

La table complète s'écrit ainsi

> - OU________________> - OU
--------------------------------------------
A - a ! C + d g__________a - A ! b
B - b ! A g + C d_________b - B !
C - c ! d + g____________c - C ! a f + b
D - d ! c + a b f_________d - D ! g
F - f ! C g + d___________f - F !
G - g ! b D f + a c________g- G !

NB: Pour ne pas confondre les implications > et les OU, il est utile d'écrire les deux colonnes de tête dans des couleurs différentes! (pour le forum j'ai mis la base des OU en gras)

Il est alors facile de trouver les OU dans la grille, on obtient:

(aC)/c1b3 supprime 1b3
(ag)/cg8 supprime 5g8 (même résultat avec (cg)/g28)

C'est suffisant pour faire tomber la grille:

Fusion D=c (b3) et F=A (e8)
jumeaux 1/bc1 supprime 1g1 => 6G4g
OU(cg) s'applique maintenant à 8g9-4g1 pour supprimer 4A en g9
a est vrai ainsi que G et f

The END

Une infernale finalement bien sympathique!

Maurice

mgrf a écrit:

Pour ceux qui ne sont pas familiers du marquage,[...]
Maurice

Bonjour mgrf,
.
Permettez-moi un petit "topo" résumant pourquoi votre technique est à la fois simple et efficace.
.
On commence donc par transformer tous les conflits en implications, puis écrire toutes les "chaines d'implications" de lettres (les plus longues possibles) : c'est de l'écriture automatique puisqu'il suffit de les...concaténer.
Avec un peu de chance, ce travail, d'un seul coup d'oeil, sans RIEN faire d'autre, est récompensé.
.
============================================
-1- Effets INTERNES d'une chaine de lettres.
============================================
.
REGLE : Dès qu'on voit 2 FOIS UNE MEME LETTRE à l'intérieur d'une chaine, on a une propriété :
.
## 1er cas ##(meme casse) : aCbHJa : 2 fois a : FUSION DE NAPPES (a=C=b=H=J). C'était une "nice loop".
De même la chaine "EFragDrm" contient la sous-chaine ragDr : fusion (r=a=g=D).
.
## 2ème cas ##(casses opposées) : aCbHJA : a est fausse.
De même "EFragDRm" contient r suivi de R : donc r est fausse (donc F et E aussi ; et R est vraie, donc m aussi)
.
=================================
-2- Effets EXTERNES d'une chaine.
=================================
Il faut revenir aux "OU" pour repérer des "tenailles" qui pourraient éliminer des candidats extérieurs.
.
REGLE : si on voit A puis B (dans cet ordre) dans une chaine, alors {a,B} est un lien "OU" [on change la casse de la 1ère lettre].
.
Par exemple la chaine "EFragDSm" donne automatiquement 28 liens, comme {e,m}, {e,g}, {R,m}, {f,D} etc.etc.
.
Cordialement,
.
soryu.
.
POST SCRIPTUM : la modestie de mgrf dût-elle en souffrir, il faut rappeler qu'il fut, avec gpenet, l'un des pionniers (francophones) du coloriage 3D Medusa.

soryu a écrit:

## 2ème cas ##(casses opposées) : aCbHJA : a est fausse.
De même "EFragDRm" contient r suivi de R : donc r est fausse (donc F et E aussi ; et R est vraie, donc m aussi)

Merci pour votre commentaire et ce complément utile (en gras) que je n'avais pas réalisé!

On peut le traduire ainsi: La marque qui dit: "si je suis vraie, telle autre l'est aussi" alors que cette dernière est réellement fausse, n'est pas dans le vrai... donc elle-même est fausse!
La logique de Mr Boole (Implication x => y s'écrit NON x OU y) est décidément implacable.

soryu a écrit:

Permettez-moi un petit "topo" résumant pourquoi votre technique est à la fois simple et efficace.
.
.

Bonjour soryu,

permettez moi d'en rajouter une couche.

Ce que vous décrivez est presque exactement ce que fait mon solveur.
Simplement, il se contente, dans un premeir temps, de composer les implications. C'est seulement s'il trouve un interdit ou une Nice boucle qu'il charche la chaîne.

Voici d'ailleurs, dans un programme qui contient des milliers de lignes, le code qui tire toutes les chaînes en parallèle à partir de l'inventaire des conflits.


void TDB::InitD(int np)
{ TDB ww=*this; int pas;
int i; for( i=2;i<col;i++)
{if (t[i].Nul())continue;
int n=1;pas=0;
while(n && pas<np)
{ n=0;pas++;for(int j=2;j<col;j++)
{if((j==i)|| (j==(i^1)))continue; if(t[i].off(j)) continue;
CB1024 y=(t[i]&ww.t[j]),x=ww.t[j]^y;
if(x.NonNul()) {t[i]=t[i]|x;n++;
}
} // end j
} // end while
}

gpenet

gpenet a écrit:

Bonjour soryu,

permettez moi d'en rajouter une couche.

Ce que vous décrivez est presque exactement ce que fait mon solveur.
gpenet

Bonjour gpenet,
.
Je me doute bien que c'est ce que fait votre solveur, non seulement parceque c'est le "top" des chaines-lettres, mais aussi parceque...nous en avions déjà parlé (en 2006 je crois), et nous étions (évidemment) d'accord à 100%. La seule nuance (que vous évoquez) est que moi j'écris "en force brute" toutes les chaines (je fais ça à la main), et je regarde après.
.
Cordialement,
.
soryu.