Devoirs Hebdomadaire N°9
CDL...DH9

Prolog III --- CryptArithmétique

 
M. Joseph DASSE BRIKA
 

Résolution d'un puzzle de cryptarithmétique

Principe : les chiffres [0,1,2,3,4,5,6,7,8,9] sont codés par des lettres. Deux lettres différentes représentent deux chiffres différents. Le puzzle consiste à découvrir le codage à partir d'une opération arithmétique. Exemple : soit résoudre l'addition

    S E N D
+   M O R E
  M O N E Y

Remarques :

  1. il s'agit d'une addition de deux nombres donc le chiffre de gauche doit être différent de 0.
  2. pour vérifier l'addition on procède comme appris à l'école de la droite vers la gauche, colonne par colonne.
  3. Si le résultat de la somme de deux chiffres est supérieur à 9, il y a une retenue de 1 à propager.
  4. on propage en fait toujours une retenue qui vaut 0 ou 1 selon le résultat de l'addition élémentaire précédente.

Donc on peut représenter l'addition par :

  R4 R3 R2 R1  
    S E N D
+   M O R E
  M O N E Y

et on a à réaliser successivement les additions élémentaires : D+E=10*R1+Y ; R1+N+R=10*R2+E ; R2+E+O=10*R3+N ; R3+S+M=10*R4+O et enfin  on a R4=M .

Pour réaliser ces additions élémentaires on a écrit le prédicat somCOL/5 :

somCOL(RETENUE, ARG1, ARG2, ChiffreRESULTATaPOSER, RETENUEaPROPAGER) :-
      SOMMECOLONNE is RETENUE + ARG1 + ARG1,   % somme ordinaire de 3 chiffres
      resRet(XX, ChiffreRESULTATaPOSER, RETENUEaPROPAGER). %Calcul de la retenue à propager et du chiffre résultat "à poser"
%---
resRet(N, N, 0) :- N< 10.
resRet(N, UNITE, 1) :- N >= 10, UNITE is N -10.

Remarques :

  1. on peut utiliser somCOL pour la première addition élémentaire D+E=10*R1+Y  en ajoutant une retenue fictive de 0 : somCOL(0, D, E, Y, R1)
  2. M=R4 et MONEY un "vrai" nombre implique que M=1
  3. SEND un "vrai" nombre implique que S>0

Utilisation du prédéfini Prolog select/3 pour donner une valeur différente à chaque lettre : 

?- help(select).
select(?List1, ?Elem, ?List2)
    Select  an  element of  List1 that  unifies  with Elem.    List2  is
    unified  with  the  list remaining  from  List1 after  deleting  the
    selected  element.   Normally  used with  the instantiation  pattern
    +List1, -Elem, -List2,  but can also be used to insert an element in
    a list using -List1, +Elem, +List2.

Yes 
?- select( [1,2,3, 4, 5, 6] , X ,L).

X = 1
L = [2, 3, 4, 5, 6] ;
X = 2
L = [1, 3, 4, 5, 6] ;
X = 3
L = [1, 2, 4, 5, 6] ;
X = 4
L = [1, 2, 3, 5, 6] ;
X = 5
L = [1, 2, 3, 4, 6] ;
X = 6
L = [1, 2, 3, 4, 5] ;
No
?- Donc au backtrack on récupère une valeur différente...

Première approche brutale : On donne une valeur différente à chacune des lettres et on vérifie l'addition. Si l'addition est correcte on montre la solution, si elle est incorrecte on affecte une autre valeur aux lettres. 

sendMoreMoney(S, E, N, D, M, O, R, Y) :-
      M is 1 , % Rappel on sait que M sera égal à 1
      select([0,2,3,4,5,6,7,8,9], D, LC1), %[0,2,3,4,5,6,7,8,9] parcequ'on sait que M=1
      select(LC1, E, LC2),
      select(LC2, Y, LC3), 
      select(LC3, N, LC4), 
      select(LC4, R, LC5),
      select(LC5, O, LC6), 
      select(LC6, S, _), 
      somCOL(0, D, E, Ret1, Y), %pour la col 1 la retenue "d'avant" est 0
      somCOL(Ret1, N, R, Ret2, E),
      somCOL(Ret2, E, O, Ret3, N),
      somCOL(Ret3, S, M, M, O).
?- X is cputime , sendMoreMoney1(S, E, N, D, M, O, R, Y) , Z is cputime - X.

X = 2.1531
S = 9
E = 5
N = 6
D = 7
M = 1
O = 0
R = 8
Y = 2
Z = 0.881267 

Yes

On peut obtenir un peu plus rapide en faisant les additions élémentaires dès que cela est possible et aussi on peut améliorer la présentation de la solution :

SEND + MORE = MONEY
sendMoreMoney([S,E,N,D] + [M,O,R,E] = [M,O,N,E,Y] ) :-
      select([0,2,3,4,5,6,7,8,9], D, C1), select(E, C1, C2),
      somCOL(0, D, E, Y, R1), select(Y, C2, C3),
      select(C3, N, C4), select(C4, R, C5),
      somCOL(R1, N, R, E, R2), select(C5, O, C6),
      somCOL(R2, E, O, N, R3),
      select(C6, S, _), S>0 ,
      M is 1 , %select(M, C7, C8), % on sait que M = 1
      somCOL(R3, S, M, O, M).
      %---
somCOL(RAvant, UN, DEUX, RES, Rsuiv) :-
      XX is RAvant + UN + DEUX, resRet(XX, RES, Rsuiv).
%---
resRet(XX, XX, 0) :- XX < 10.
resRet(XX, RES, 1) :- XX >= 10, RES is XX -10.
%--- 
?-Xis cputime,SMM=([S,E,N,D]+[M,O,R,E]=[M,O,N,E,Y]),sendMoreMoney6(SMM),Z is cputime-X.

X = 0.100144
SMM = [9, 5, 6, 7]+[1, 0, 8, 5]=[1, 0, 6, 5, 2]
S = 9
E = 5
N = 6
D = 7
M = 1
O = 0
R = 8
Y = 2
Z = 0.0100144 ;

No
?-

Rappels : les nombres cherchés sont de vrais nombres i.e. le premier chiffre à gauche correspond à un chiffre supérieur à 0

% Pour passer d'une liste de chiffres à l'entier correspondant on a écrit list2int/2 :

lst2nt(L,V) :- lst2nt(L , 0 , V).

lst2nt([] , R,R).
lst2nt([C|L] , V , R) :- chiffre(C) , W is V*10+C , lst2nt(L , W , R).

chiffre(C) :- member(C , [0,1,2,3,4,5,6,7,8,9]).

puzzle de cryptarithmétique : NEED + MORE = CASH

Il s'agit toujours du babacool qui pendant son voyage initatique en Inde envoie tous les mois  un message de détresse à ses parents professeurs de mathématiques. Cette semaine il a donc envoyer NEED + MORE = CASH en demandant au parent qui lit la lettre de lui envoyer en EUROs la valeur de CASH , solution du problème. Il connait en effet une solution :

6449+1754=8203.

Hélas, il y a d'autres solutions au puzzle et si c'est le Papa qui ouvre la lettre le babacool aura le minimum et si c'est la maman le babacool aura le maximum.

QUESTION 1 : sur le modèle de sendMoreMoney([S,E,N,D] + [M,O,R,E] = [M,O,N,E,Y] ) :- ... spécifier le prédicat résoud ce puzzle mais retournant des nombres et non des listes de chiffres (utilisation de list2int ci dessus). needMoreCASH(NEED + MORE = CASH) :- ...  /* à compléter */. Donner une solution.

QUESTION 2 : la solution du babacool est-elle effectivement une solution du puzzle (donnez la question posée pour cette vérification) ?

Après étude des prédicats prédéfinis bagof/3  et setof/3 de Prolog : 

?- help(bagof/3).
bagof(+Var, +Goal, -Bag)
    Unify  Bag with the alternatives of Var, if Goal has  free variables
    besides  the one  sharing  with Var  bagof will  backtrack over  the
    alternatives  of  these  free  variables,   unifying  Bag  with  the
    corresponding  alternatives of Var.   The construct +Var^Goal  tells
    bagof  not to  bind  Var in  Goal.   bagof/3  fails if  Goal has  no
    solutions.

    The  example below  illustrates bagof/3  and the  ^ operator.    The
    variable bindings are printed together on one line to save paper.

         2 ?- listing(foo).

         foo(a, b, c).
         foo(a, b, d).
         foo(b, c, e).
         foo(b, c, f).
         foo(c, c, g).

         Yes
         3 ?- bagof(C, foo(A, B, C), Cs).

         A = a, B = b, C = G308, Cs = [c, d] ;
         A = b, B = c, C = G308, Cs = [e, f] ;
         A = c, B = c, C = G308, Cs = [g] ;

         No
         4 ?- bagof(C, A^foo(A, B, C), Cs).

         A = G324, B = b, C = G326, Cs = [c, d] ;
         A = G324, B = c, C = G326, Cs = [e, f, g] ;

         No
         5 ?-
 
?- help(setof/3).
setof(+Var, +Goal, -Set)
    Equivalent to bagof/3, but sorts the result using sort/2 to get a
    sorted list of alternatives without duplicates.

QUESTION 3 : analyser les résultats des buts : (décrire le résultat par une phrase aussi précise que possible)

?-  setof(NEED+MORE=CASH , needMoreCASH(NEED+MORE=CASH) , L).

et

?- setof(CASH , NEED^MORE^needMoreCASH(NEED+MORE=CASH) , L).

QUESTION 4 : Combien y a-t-il de solutions au puzzle NEED + MORE = CASH ?  
                        Combien recevra le babacool si son père ouvre la lettre ?
                        Combien recevra le babacool si sa mère ouvre la lettre ?

  L'exemple de l'énnoncé a plusieurs erreur et a été remplacé ici par :
 
sendMoreMoney([S,E,N,D] + [M,O,R,E] = [M,O,N,E,Y] ) :- 
 select([0,2,3,4,5,6,7,8,9], D, C1), select(C1, E, C2), 
 somCOL(0, D, E, Y, R1), select(C2, Y, C3), 
 select(C3, N, C4), select(C4, R, C5), 
 somCOL(R1, N, R, E, R2), select(C5, O, C6), 
 somCOL(R2, E, O, N, R3), 
 select(C6, S, _), S>0 ,
 M is 1 , somCOL(R3, S, M, O, M). 
somCOL(RAvant, UN, DEUX, RES, Rsuiv) :- XX is RAvant + UN + DEUX, resRet(XX, RES, Rsuiv). 
resRet(XX, XX, 0) :- XX < 10. 
resRet(XX, RES, 1) :- XX >= 10, RES is XX -10.
Question 1:
  Même chose avec NEED + MORE = CASH :
Attention: pour tout le dh je considère N>0 et M>0 pour que NEED et MORE soient de "vrais" nombres
(précision importante, car cela réduit le nombre de solutions possibles) 
needMoreCash( A1 + A2 = A3 ) :- 
      select([0,1,2,3,4,5,6,7,8,9], D, C1), select(C1, E, C2), 
      somCOL(0, D, E, H, R1), select(C2, H, C3), 
      select(C3, R, C4),somCOL(R1, E, R, S, R2),
      select(C4, S, C5), select(C5, O, C6), 
      somCOL(R2, E, O, A, R3), select(C6, A, C7),
      select(C7, N, C8), N > 0 , select(C8, M, C9) , M > 0,
      somCOL(R3, N, M, C, 0), select(C9, C, _),
    	lst2nt( [N,E,E,D], A1),
        lst2nt( [M,O,R,E], A2),
        lst2nt( [C,A,S,H], A3).
Question 2:
  Vérifions que 6449+1754=8203 est bien solution:
?- needMoreCash( 6449+1754=8203 ).

Yes
Question 3:
  setof(NEED+MORE=CASH , needMoreCASH(NEED+MORE=CASH) , L).

A pour résultat une liste de toutes les combinaisons de NEED,MORE et CASH,
solutions de NEED+MORE=CASH et classées par ordre croissant de NEED.
?- setof(NEED+MORE=CASH , needMoreCash(NEED+MORE=CASH) , L).

NEED = _G435
MORE = _G436
CASH = _G439
L = [1223+4872=6095, 1223+7842=9065, 1224+3872=5096, 1224+7832=9056, 1225+3682=4907,
 	 1227+3842=5069, 1227+4382=5609, 1227+4832=6059, 1228+3562=4790,1228+4732=5960,
 	 1335+2763=4098, 1335+6093=7428, 1336+2753=4089, 1339+6503=7842,1442+7094=8536,
 	 1449+6574=8023, 1449+6754=8203, 1449+7204=8653, 1558+7465=9023,1558+7645=9203,
 	 1662+3096=4758, 1662+5436=7098, 1663+5426=7089, 1668+7356=9024,1668+7536=9204,
 	 1669+3206=4875, 1772+4067=5839, 1776+4207=5983, 1882+7468=9350,1882+7648=9530,
 	 2113+5691=7804, 2113+5961=8074, 2113+6591=8704, 2114+3971=6085,2116+5931=8047,
 	 2117+3491=5608, 2117+3941=6058, 2117+4391=6508, 2119+3741=5860,2119+4731=6850,
 	 2119+5361=7480, 2119+6351=8470, 2331+5763=8094, 2331+6573=8904,2331+6753=9084,
 	 2335+1763=4098, 2335+6713=9048, 2336+1753=4089, 2336+5083=7419,2336+5713=8049,
 	 2337+6153=8490, 2338+5603=7941, 2441+7364=9805, 2446+7134=9580,2447+6584=9031,
 	 2447+6854=9301, 2661+5436=8097, 2663+5146=7809, 2663+5416=8079,2664+5316=7980,
 	 2887+6148=9035, 2887+6418=9305, 2889+3158=6047, 2889+3518=6407,3114+2971=6085,
 	 3116+5291=8407, 3117+2491=5608, 3117+2941=6058, 3119+2741=5860,3119+5621=8740,
 	 3224+1872=5096, 3225+1682=4907, 3225+6182=9407, 3227+1842=5069,3228+1562=4790,
 	 3228+6512=9740, 3661+5246=8907, 3661+5426=9087, 3662+1096=4758,3662+5416=9078,
 	 3664+5126=8790, 3669+1206=4875, 3774+5287=9061, 3774+5827=9601,3884+5178=9062,
 	 3884+5718=9602, 3889+2158=6047, 3889+2518=6407, 4117+2391=6508,4119+2731=6850,
 	 4223+1872=6095, 4227+1382=5609, 4227+1832=6059, 4228+1732=5960,4772+1067=5839,
 	 4776+1207=5983, 5113+2691=7804, 5113+2961=8074, 5116+2931=8047,5116+3291=8407,
 	 5119+2361=7480, 5119+3621=8740, 5331+2763=8094, 5336+2083=7419,5336+2713=8049,
 	 5338+2603=7941, 5661+2436=8097, 5661+3246=8907, 5661+3426=9087,5662+1436=7098,
 	 5662+3416=9078, 5663+1426=7089, 5663+2146=7809, 5663+2416=8079,5664+2316=7980,
 	 5664+3126=8790, 5774+3287=9061, 5774+3827=9601, 5884+3178=9062,5884+3718=9602,
 	 6113+2591=8704, 6119+2351=8470, 6225+3182=9407, 6228+3512=9740,6331+2573=8904,
 	 6331+2753=9084, 6335+1093=7428, 6335+2713=9048, 6337+2153=8490,6339+1503=7842,
 	 6447+2584=9031, 6447+2854=9301, 6449+1574=8023, 6449+1754=8203,6887+2148=9035,
 	 6887+2418=9305, 7223+1842=9065, 7224+1832=9056, 7441+2364=9805,7442+1094=8536,
 	 7446+2134=9580, 7449+1204=8653, 7558+1465=9023, 7558+1645=9203,7668+1356=9024,
 	 7668+1536=9204, 7882+1468=9350, 7882+1648=9530]
 
  setof(CASH , NEED^MORE^needMoreCASH(NEED+MORE=CASH) , L).

A pour résultat une liste sans répétition des valeurs que peux prendre CASH,
classées par ordre croissant et avec CASH solution de NEED+MORE=CASH
?- setof(CASH , NEED^MORE^needMoreCash(NEED+MORE=CASH) , L).
	
CASH = _G439
NEED = _G435
MORE = _G436
L = [4089, 4098, 4758, 4790,4875,4907, 5069,5096, 5608, 5609, 5839, 5860, 5960, 5983,
	 6047, 6058, 6059,6085,6095,6407,6508,6850, 7089, 7098,7419, 7428, 7480,7804,
	 7809, 7842, 7941,7980,8023,8047,8049,8074, 8079, 8094,8097, 8203, 8407,8470,
	 8490, 8536, 8653,8704,8740,8790,8904,8907, 9023, 9024,9031, 9035, 9048,9056,
	 9061, 9062, 9065,9078,9084,9087,9203,9204, 9301, 9305,9350, 9407, 9530,9580,
	 9601, 9602, 9740,9805]
Question 4:
  -Nombre de solutions au puzzle NEED+MORE=CASH: 148
?- setof(NEED+MORE=CASH , needMoreCash(NEED+MORE=CASH) , L), length(L, SOLCOUNT).

NEED = _G561
MORE = _G562
CASH = _G565
L = [1223+4872=6095, 1223+7842=9065, ... , ... ,7882+1468=9350, 7882+1648=9530]
SOLCOUNT = 148

-Si le père ouvre la lettre,le babacool recevra la somme minimum : 4089
(premier élément de la liste résultat de setof(CASH , NEED^MORE^needMoreCash(NEED+MORE=CASH) , L).)

-Si ma mère ouvre la lettre,le babacool recevra la somme minimum : 9805
(dernier élément de la liste résultat )
 

FIN_dh9
 

ACCUEIL CONTACT FAVORIS ANNALES DH1 DH2 DH3 DH4 DH5 DH6 DH7 DH8 DH9 DH10 DH11 DH12 DH13 DH14 DH15 DH16