Retour
Solutionner Démineur


1) Un cas simple pour commencer.

Conventions de cette page :
 
 
 
 
 
 
1 2 1
 
a b c d e

Définissons les conditions logiques susceptibles de produire les cases 1, 2 et 1:

  • Pour la case '1' de gauche, il y a une seule case à 1 parmis les cases a, b et c, donc :
    a./b./c+/a.b./c+/a./b.c = 1
  • Pour la case '2', il y a deux cases à 1 parmis les cases b, c et d, donc :
    b.c./d+b./c.d+/b.c.d = 1
  • Pour la case '1' de droite, il y a une seule case à 1 parmis les cases c, d et e, donc :
    c./d./e+/c.d./e+/c./d.e = 1
  • La solution globale est donc donnée par :
    (a./b./c+/a.b./c+/a./b.c).(b.c./d+b./c.d+/b.c.d).(c./d./e+/c.d./e+/c./d.e) = 1
    Après calcul, on obtient ;
    /a.b./c.d./e = 1
    Ce qui correspond à une seule solution avec mines en b et en d.

    2) Utilisation des fonctions pour simplifier l'écriture.Liste de toutes les fonctions

    Codification des fonctions, exemple de fonction : On a donc :
    fd13(a,b,c):=a./b./c+/a.b./c+/a./b.c
    et
    fd23(a,b,c):=a.b./c+a./b.c+/a.b.c

    La solution est donc donnée par le calcul de :
    fd13(a,b,c).fd23(b,c,d).fd13(c,d,e)=1
    Qui donne après calcul :
    /a.b./c.d./e=1


    3) Quelques cas un peu plus compliqués.

    Exemple N1
    a 2
     
     
    2 j
    b 3 1 1 2 i
    c d e f g h


    La solution est donnée par le calcul de :
    fd22(a,b).fd35(a,b,c,d,e).fd13(d,e,f).fd13(e,f,g).fd25(f,g,h,i,j).fd22(i,j)=1
    Qui donne après calcul :
    a.b./c./d.e./f./g./h.i.j=1


    Exemple N2
    a 1
     
     
    1 j
    b 2 1 2 3 i
    c d e f g h
    La solution est donnée par le calcul de :
    fd12(a,b).fd25(a,b,c,d,e).fd13(d,e,f).fd23(e,f,g).fd35(f,g,h,i,j).fd12(i,j)=
    Qui donne après calcul :
    /a.b./c./d.e./f.g.h./i.j + /a.b./c./d.e./f.g.h.i./j + /a.b.c./d./e.f.g./h./i.j + /a.b.c./d./e.f.g./h.i./j +
    a./b./c./d.e./f.g.h./i.j + a./b./c./d.e./f.g.h.i./j + a./b.c./d./e.f.g./h./i.j + a./b.c./d./e.f.g./h.i./j = 1

    Il y a 8 solutions. Alignons les 8 termes de l'équation les uns en dessous des autres :
    /a.b./c./d.e./f.g.h./i.j
    /a.b./c./d.e./f.g.h.i./j
    /a.b.c./d./e.f.g./h./i.j
    /a.b.c./d./e.f.g./h.i./j
    a./b./c./d.e./f.g.h./i.j
    a./b./c./d.e./f.g.h.i./j
    a./b.c./d./e.f.g./h./i.j
    a./b.c./d./e.f.g./h.i./j
    Il apparait :
    (/a.b+a./b).(/c.e./f.h+c./e.f./h).(/i.j+i./j)./d.g
    On retrouve des solutions partielles par :
    fd12(a,b)=(/a.b+a./b)
    fd12(i,j)=(/i.j+i./j)
    De plus on a les tautologies suivantes :
    fd12(a,b).fd25(a,b,c,d,e)=>fd12(a,b).fd13(c,d,e)=1
    fd35(f,g,h,i,j).fd12(i,j)=>fd23(f,g,h).fd12(i,j)=1
    Ce qui donne :
    fd12(a,b).fd25(a,b,c,d,e).fd35(f,g,h,i,j).fd12(i,j)=>fd12(a,b).fd13(c,d,e).fd23(f,g,h).fd12(i,j)=1
    Attention, ceci n'est vrai que pour des tautologies. La raison en est :
    (((a=>b)<=>1).((c=>d)<=>1))=>(((a.c)=>(b.d))<=>1)=1
    On peut donc décomposer le problème en deux sous-problèmes :
    a 1
     
     
    1 j
    b 2 1 2 3 i
    c d e f g h
    Equivalent à :
    a 1
     
     
    1 j
    b
     
     
     
     
    i
     
     
     
     
     
     
    Et
     
     
     
     
     
     
     
    1 1 2 2
     
    c d e f g h
    L'équation pour ci-dessus est :
    fd13(c,d,e).fd13(d,e,f).fd23(e,f,g).fd23(f,g,h)=1
    soit :
    /c./d.e./f.g.h+c./d./e.f.g./h=1
    Ce qui se factorise en :
    /d.g.(/c.e./f.h+c./e.f./h)=1
    On retrouve bien le résultat donné par la méthode globale, et cela montre que la méthode que l'on utilise intuitivement pour résoudre un tel problème est justifiée.

    Exemple N3
    a 1
     
     
    1 j
    b 2 1 1 2 i
    c d e f g h
    La solution est donnée par le calcul de :
    fd12(a,b).fd25(a,b,c,d,e).fd13(d,e,f).fd13(e,f,g).fd25(f,g,h,i,j).fd12(i,j)=1
    Qui donne après calcul 12 solutions :
    /a.b./c./d.e./f./g.h./i.j + /a.b./c./d.e./f./g.h.i./j + /a.b./c.d./e./f.g./h./i.j + /a.b./c.d./e./f.g./h.i./j + /a.b.c./d./e.f./g./h./i.j + /a.b.c./d./e.f./g./h.i./j + a./b./c./d.e./f./g.h./i.j + a./b./c./d.e./f./g.h.i./j + a./b./c.d./e./f.g./h./i.j + a./b./c.d./e./f.g./h.i./j + a./b.c./d./e.f./g./h./i.j + a./b.c./d./e.f./g./h.i./j = 1
    En raisonnant comme ci-dessus nous obtenons :
    fd12(a,b)=(/a.b+a./b)
    fd12(i,j)=(/i.j+i./j)
    fd13(c,d,e).fd13(d,e,f).fd13(e,f,g).fd13(f,g,h)= /c./d.e./f./g.h+/c.d./e./f.g./h+c./d./e.f./g./h

    3) Conclusion.

    Ceci montre : Calculons l'inverse de la solution, par exemple pour l'exemple n2 :
    /(fd12(a,b).fd25(a,b,c,d,e).fd13(d,e,f).fd23(e,f,g).fd35(f,g,h,i,j).fd12(i,j))=0
    a.b+/a./b+c.e+c./f+c.h+d+/c./e+/e./f+/e.h+/c.f+e.f+f.h+/g+/c./h+e./h+/f./h+i.j+/i./j=0
    Chaque terme doit valoir 0.
    Ceci montre la dépendance des variables logiques. On a : L'analyse du regroupement des variables des termes de cette fonction est un problème de sous-graphes (complets), problème qui a sa solution par la logique. Donc, il ne faut pas désespérer...


    Liste de toutes les fonctions Retour