Au début du XXe siècle, un étudiant anglais n’ayant plus que quelques shillings en poche, doit envoyer un télégramme à son père pour lui demander de l’argent. Le prix du télégramme dépendant du nombre de caractère, il cherche a être le plus concis possible. Il se limite donc au texte suivant: SEND + MORE = MONEY.
Quelle somme doit lui envoyer son père, sachant que chaque lettre représente un chiffre différent et qu’aucun nombre ne commence par 0 ?
Résolution manuelle
| a | b | c | d | ||
|---|---|---|---|---|---|
| S | E | N | D | ||
| + | M | O | R | E | |
| M | O | N | E | Y |
Où a, b, c et d sont les retenues. On observe tout d’abord que le résultat a un chiffre de plus que les deux nombres additionnés. Lorsque l’on additionne deux chiffres, la retenue maximale que l’on puisse obtenir est 1 (9+9 = 18). Même si il y a une retenue venant de l’étape précédente, celle-ci ne vaudra pas plus de 1 (9+9+1 = 19). On a donc a = 0 ou 1 et a = M. Or M ne peut pas valoir 0 donc a = M = 1.
| 1 | b | c | d | ||
|---|---|---|---|---|---|
| S | E | N | D | ||
| + | 1 | O | R | E | |
| 1 | O | N | E | Y |
La lettre S peut donc prendre 2 valeurs: soit 9, soit 8. Si elle vaut 9, il peut ou non y avoir une retenue, donnant à O les valeurs 0 ou 1. Si elle vaut 8, il y a forcément une retenue et O vaut 0. Comme M vaut 1, O ne peut valoir 1 et vaut donc 0. Donc: S ∈ {8, 9} , O = 0
| 1 | b | c | d | ||
|---|---|---|---|---|---|
| S | E | N | D | ||
| + | 1 | 0 | R | E | |
| 1 | 0 | N | E | Y |
Si S vaut 8, alors il faut une retenue et donc E + 0 + c > 9. Ce qui veut dire que E vaut 9 et qu’il y a une retenue c = 1 venant de N + R +d. Mais alors 9 + 0 + 1 = 10 et N vaut 0 ce qui ne convient pas car 0 est déjà assigné à O.
Donc S vaut 9.
| 1 | b | c | d | ||
|---|---|---|---|---|---|
| 9 | E | N | D | ||
| + | 1 | 0 | R | E | |
| 1 | 0 | N | E | Y |
On a donc E+0+c = N ce qui n’est possible que si c ne vaut pas 0. Donc c = 1 et N+R+d = 10 + E et E + 1 = N. Soit N+R+d = 10 + N – 1 = N + 9 d’où R+d = 9. R ne peut valoir 9 car ce chiffre est déjà attribué à S. On a donc R = 8 et d = 1.
| 1 | b | 1 | 1 | ||
|---|---|---|---|---|---|
| 9 | E | N | D | ||
| + | 1 | 0 | 8 | E | |
| 1 | 0 | N | E | Y |
Puisque d vaut 1 et le 0 et le 1 sont déjà affectés à d’autres lettres, D + E > 11. Le 9 et le 8 étant eux aussi déjà affectés, on ne peut former un nombre supérieur à 11 qu’avec 7+5 ou 7+6, ce qui laisse pour Y les valeurs 2 ou 3. En tenant compte du fait que E+1 = N, E ne peut pas valoir 7 (puisque N < 8, 8 et 9 étant déjà attribués). Donc E vaut 5 ou 6.
Si E valait 6, alors N vaudrait 7 (car N = E+1) et D vaudrait donc 5, ce qui ne va pas car E+D > 11. Donc E vaut 5, ce qui conduit à N = 6 et D = 7. On en déduit d’une part Y = 2 et d’autre part b = 0. On obtient donc au final:
| 1 | 0 | 1 | 1 | ||
|---|---|---|---|---|---|
| 9 | 5 | 6 | 7 | ||
| + | 1 | 0 | 8 | 5 | |
| 1 | 0 | 6 | 5 | 2 |
L’étudiant a donc besoin que son père lui envoi 10 652 £.
Additions mystères
Ce genre de problème est souvent appelé additions mystères, mais peut aussi se trouver sous les noms de cryptarithmes, d’arithmétique verbale, d’alphamétique ou de cryptarithmétique.
On peut en trouver facilement de très nombreux en cherchant sur internet. En voici quelques exemples:
- PLEIADE + POESIES + DE = RONSARD
- DU + POETE + MAROT = EPITRE
- MAUROIS + ET + MAURIAC = AUTEURS
- ALBERTO + ALBERTO = MORAVIA
- UN + UN + NEUF = ONZE
- ZERO+NEUF+NEUF+DOUZE=TRENTE
- ZERO+ZERO+ZERO+UN+DOUZE=TREIZE
- ZERO+ZERO+SEPT+SEPT+SEIZE=TRENTE
- ZERO+UN+TROIS+ONZE+QUINZE=TRENTE
- ZERO+TROIS+TROIS+TROIS+SEPT=SEIZE
- ZERO+TROIS+TROIS+DOUZE+DOUZE=TRENTE
- ZERO+QUATRE+QUATRE+ONZE+ONZE=TRENTE
- UN+UN+QUATRE+DOUZE+DOUZE=TRENTE
- UN+DEUX+DEUX+DEUX+DEUX=NEUF
- UN+QUATRE+CINQ+CINQ+QUINZE=TRENTE
- TROIS+TROIS+TROIS+CINQ+SEIZE=TRENTE
- QUATRE+QUATRE+QUATRE+NEUF+NEUF=TRENTE
- MOT+MOT+MOT+1=TOM
- SATURN+URANUS=JUPITER
- MONITOR+NETWORK=INTERNET
- OASIS+SOLEIL=MIRAGE
- MANGER+MANGER=GROSSIR
- ALCOOL+ALCOOL=IVRESSE
- MARI+FEMME+12.ENFANT = FAMILLE (fonctionne aussi avec 18 au lieu de 12)
- ROUGE+GORGE=OISEAU
- MOI+TOI+LUI+ELLE=NOUS
- LES+TESTS+D+INTELL=IGENCE
- TESTS+JEUX+SUPER=ESPRIT
- TESTS+JEUX+JEUNE=RESTER
- JEUX+JEUX+JEUX+JEUNE=ESPRIT
- TES+TESTS+ET+TES=MATHS
- 6.TESTS+QI=MENSA
- ADELE+ELLE+A+LA+BOSSE+DES=MATHS
- LES+MATHS+ELLES+AIMENT
- MARTIN+GARDNER=ADMIREZ
- ENIGME+GENIALE+MEME=SUBLIME
- SOMMES+CODEES=RBLOCH
- SOMMES+CODEES=MCRITON
Lorsque l’on voit qu’il en existe autant, on se dit qu’il serait intéressant de pouvoir les résoudre plus rapidement qu’en le faisant à la main, d’autant que ce n’est pas toujours aussi simple que pour celui de notre étudiant. On ne sait jamais, peut être qu’un jour en résoudre 10 en moins d’une minute pourrait être une question de vie ou de mort !
Backtracking
Le backtracking (en français « retour en arrière » ou « retour sur trace ») est un algorithme très générique pour résoudre une grande variété de problèmes. Ainsi, il peut être appliqué pour résoudre des sudokus, jouer au morpion, aux échecs ou aux dames, etc …
Le principe du backtracking est de parcourir en profondeur un arbre permettant de construire tous les « solutions candidates » qu’elles soient valides ou non. Afin d’accélérer la découverte de la solution, on peut « couper les branches » au plus tôt en invalidant les solutions partiellement construites dont on sait qu’elles ne peuvent mener à une solution (par exemple au sudoku, dès qu’un même chiffre est présent deux fois sur une ligne, colonne ou zone).
Dans le cas des additions mystères, nous allons associer un chiffre à chaque lettre. Une fois que toutes les lettres ont un chiffre assigné, il est facile de valider ou invalider la solution en calculant la somme et en contrôlant si l’égalité est vérifiée. Pour parcourir l’ensemble des solutions, on revient en arrière après avoir testé une solution, pour passer à la suivante. Cette opération est un peu compliquée à faire de manière itérative mais est très simple à mettre en place de manière récursive.
Prenons l’exemple d’une opération dans laquelle il y aurait seulement 3 variables a, b et c, et dont les valeurs seraient entre 1 et 3 au lieu d’être entre 0 et 9. L’algorithme va construire les solutions de la manière suivante:
- a = 1
- b = 1 => ne convient pas (a = b)
- b = 2
- c = 1 => ne convient pas (a = c)
- c = 2 => ne convient pas (b = c)
- c = 3
- Teste si l’équation est vérifiée
- b = 3
- c = 1=> ne convient pas (a = c)
- c = 2
- Teste si l’équation est vérifiée
- c = 3 =>ne convient pas (b = c)
- a = 2
- b = 1
- c = 1 => ne convient pas (b = c)
- c = 2 => ne convient pas (a = c)
- c = 3
- Teste si l’équation est vérifiée
- b = 2 => ne convient pas (a = b)
- b = 3
- c = 1
- Teste si l’équation est vérifiée
- c = 2 => ne convient pas (a = c)
- c = 3 =>ne convient pas (b = c)
- c = 1
- b = 1
- a = 3
- b = 1
- c = 1 => ne convient pas (b = c)
- c = 2
- Teste si l’équation est vérifiée
- c = 3 => ne convient pas (a = c)
- b = 2
- c = 1
- Teste si l’équation est vérifiée
- c = 2 => ne convient pas (b = c)
- c = 3 => ne convient pas (a = c)
- c = 1
- b = 3 => ne convient pas (a = b)
- b = 1
Ici, l’arbre des solutions possibles a été un peu réduit en utilisant le fait que les chiffres doivent être différents. Il serait possible de réduire encore plus l’arbre en utilisant certaines propriétés de l’addition mystère. La plus simple à utiliser de manière générique est le fait que l’égalité limitée aux chiffres de poids faible (D, E et Y dans le cas de SEND + MORE = MONEY) doit être vérifiée en arithmétique modulo 9. En effet, il n’y a pas de retenue à ajouter pour ces chiffres là et l’arithmétique modulo 9 permet d’ignorer la retenue générée par l’addition.
L’effet de cette optimisation est maximale si les chiffres de poids faible sont les premiers pour lesquels on choisit la valeur, car c’est ainsi que l’on coupera le plus tôt les branches. Avec cette approche, l’ordinateur va suivre le chemin inverse de la résolution manuelle, ou nous avons commencé par les chiffres de poids le plus fort (M et S) et plus ou moins progressé de gauche à droite.
Programme en python
Voici une première version simple, parcourant la totalité de l’arbre. Bien que le programme parvienne à résoudre le problème plus rapidement que l’être humain, on ne peut pas dire qu’il soit très rapide. Sur mon ordinateur (peu puissant), il lui faut environ 1 minute et 30 secondes:
$ time python2 AdditionMystere.py
{'e': 5, 'd': 7, 'm': 1, 'o': 0, 'n': 6, 's': 9, 'r': 8, 'y': 2}
real 1m31.051s
user 1m15.797s
sys 0m0.280s
Avec une seconde version coupant les branches de l’arbre en vérifiant simplement (d+e) mod 10 = y dès que les trois valeurs sont disponibles, mais sans avoir placé ces 3 lettres en début de liste, l’amélioration est modeste:
$ time python2 AdditionMystereMalAcceleree.py
{'e': 5, 'd': 7, 'm': 1, 'o': 0, 'n': 6, 's': 9, 'r': 8, 'y': 2}
real 0m58.000s
user 0m57.493s
sys 0m0.087s
Voici la troisième version, qui a exactement la même logique que la seconde mais ayant la liste de lettres réordonnée pour que les valeurs de e, d et y soient attribuées en premier, « coupant » les branches au plus tôt:
$ time python2 AdditionMystereAcceleree.py
{'e': 5, 'd': 7, 'm': 1, 'o': 0, 'n': 6, 's': 9, 'r': 8, 'y': 2}
real 0m5.907s
user 0m5.870s
sys 0m0.017s
On appréciera l’impact que peut avoir sur les performances un changement aussi modeste que réordonner les valeurs dans un tableau !
Il est possible de trouver d’autres critères pour couper les branches plus tôt comme nous le verrons plus tard, mais vous pouvez déjà réfléchir et voir aux quels vous pensez …
Résolution en prolog
Si il est possible d’implémenter cet algorithme en python, il existe une classe de langage dont c’est la spécialité: les langages de programmation par contrainte. Prolog en fait partie. J’utilise ici une implémentation de Prolog s’appelant GNU Prolog, ou gprolog pour les intimes.
GNU Prolog peut être utilisé de manière interactive (tout comme python) et peut interpréter des programmes. Il est aussi capable de les compiler. Les programmes compilés seront plus performants.
Voici le programme en Prolog, qui interprété, est plus rapide que notre première implémentation en Python et que la version « mal accélérée », mais moins rapide que la version « accélérée » qui coupe au plus tôt les branches de l’arbre:
$ time ./AdditionMystere.pl GNU Prolog 1.4.4 (32 bits) Compiled Apr 29 2013, 20:41:58 with gcc By Daniel Diaz Copyright (C) 1999-2013 Daniel Diaz compiling AdditionMystere.pl for byte code... AdditionMystere.pl compiled, 41 lines read - 4321 bytes written, 35 ms [S,E,N,D,M,O,R,Y] = [9,5,6,7,1,0,8,2] real 0m12.153s user 0m12.077s sys 0m0.040s
Le même programme compilé devient plus rapide que toutes les versions en python, même si l’on inclut le temps de la compilation !
$ time gplc AdditionMystere.pl real 0m0.478s user 0m0.380s sys 0m0.077s $ time ./AdditionMystere [S,E,N,D,M,O,R,Y] = [9,5,6,7,1,0,8,2] real 0m2.562s user 0m2.410s sys 0m0.010s
Généralisation
Nous sommes encore loin de pouvoir résoudre dix cryptarithmes en moins d’une minute ! Pour résoudre un nouveau problème, il nous faut modifier le programme en plusieurs endroit et sans se tromper: liste de lettres, liste de lettres non nulles, vérification de la solution, vérification des derniers chiffres …
Il nous faut un programme plus générique, dans lequel on peut simplement taper notre addition et qui nous donne le résultat. Afin d’y arriver, il faut simplement:
- Pouvoir décoder l’addition. Pour cela, on lit d’abord la partie gauche, on vérifie la présence du signe égal puis on lit la partie droite. Pour lire chaque partie (droite ou gauche), on lit un mot (suite de lettres) jusqu’à rencontrer un +, un = ou la fin de la chaîne. Pour chaque mot que l’on lit, on l’ajoute à une liste de mots (mots_droite ou mots_gauche), chaque mot étant une liste de lettres.
- Il faut ensuite construire la liste de lettres et la liste de lettres non nulles. Pour cela, on parcourt les deux listes de mots, et on ajoute la première lettre de chaque à la liste de lettres non nulles. On ajoute aussi chaque lettre de chaque mot à la liste de lettres. Enfin, on déplace les lettres « de poids faible » dans la liste de lettres pour les mettre en premier.
- Enfin, il faut rendre génériques les fonctions permettant de valider les solutions partielles ou complètes. Au final les fonctions sont plus lisibles et le risque d’erreur est moins important !
Voici le programme générique en python qui est un peu plus lent que la version non générique. La raison est que l’on fait des calculs supplémentaires, en particulier les puissances de 10 qui étaient pré-calculées auparavant.
$ time echo "send+more=money" | python2 AdditionMystereGenerique.py
Addition mystere a resoudre:
{'e': 5, 'd': 7, 'm': 1, 'o': 0, 'n': 6, 's': 9, 'r': 8, 'y': 2}
real 0m10.899s
user 0m10.737s
sys 0m0.027s
Avec un ordinateur un peu plus puissant et en lançant plusieurs programme en parallèle, on doit pouvoir résoudre dix cryptarithmes en une minute mais ce n’est pas certain …
Mais des améliorations sont encore possibles ! Essayez de couper un peu plus l’arbre en plaçant les lettres des dizaines (N, R et E) juste après les lettres des unités dans la liste et en modifiant la fonction solution_valable pour qu’elle vérifie aussi si (ND+RE) mod 100 = EY. On gagne encore beaucoup de temps. Il faut adapter un peu la fonction pour qu’elle continue à fonctionner quand un des mots a moins de 2 lettres.
Pouvez vous pousser ce raisonnement à son maximum et vérifier progressivement l’addition, de droite à gauche, au fur et à mesure que les lettres sont affectées ?
Si, après plusieurs essais, vous n’y parvenez pas, voici la version optimisée du programme générique:
$ time echo "send+more=money" | python2 AdditionMystereGeneriqueAcceleree.py Addition mystere a resoudre: {'e': 5, 'd': 7, 'm': 1, 'o': 0, 'n': 6, 's': 9, 'r': 8, 'y': 2} real 0m0.566s user 0m0.533s sys 0m0.020s
Ce programme résout la majeure partie des additions mystères en moins d’une seconde ! Pour certaines, il faut un temps plus long, par exemple MAUROIS+ET+MAURIAC=AUTEURS qui nécessite 6 à 7 secondes ou pire encore ZERO+UN+TROIS+ONZE+QUINZE=TRENTE qui prend environ 30 secondes. Sauriez-vous trouver pourquoi celle-ci sont si longue à résoudre, comparées à d’autres semblables ou d’apparence plus complexe, comme par exemple PLEIADE+POESIES+DE=RONSARD ?
Voici les temps obtenus pour les exemples ci-dessus, récupérés à l’aide d’un simple script shell (les additions sont écrites une par ligne dans un fichier tests.txt):
$ sh tests.sh 0m0.152s - MOT+MOT+MOT+A=TOM 0m0.380s - PLEIADE+POESIES+DE=RONSARD 0m1.096s - DU+POETE+MAROT=EPITRE 0m6.275s - MAUROIS+ET+MAURIAC=AUTEURS 0m0.333s - ALBERTO+ALBERTO=MORAVIA 0m0.315s - UN+UN+NEUF=ONZE 0m5.318s - ZERO+NEUF+NEUF+DOUZE=TRENTE 0m1.473s - ZERO+ZERO+ZERO+UN+DOUZE=TREIZE 0m6.398s - ZERO+ZERO+SEPT+SEPT+SEIZE=TRENTE 0m36.625s - ZERO+UN+TROIS+ONZE+QUINZE=TRENTE 0m15.420s - ZERO+TROIS+TROIS+TROIS+SEPT=SEIZE 0m9.339s - ZERO+TROIS+TROIS+DOUZE+DOUZE=TRENTE 0m0.588s - ZERO+QUATRE+QUATRE+ONZE+ONZE=TRENTE 0m2.974s - UN+UN+QUATRE+DOUZE+DOUZE=TRENTE 0m0.228s - UN+DEUX+DEUX+DEUX+DEUX=NEUF 0m5.803s - UN+QUATRE+CINQ+CINQ+QUINZE=TRENTE 0m7.667s - TROIS+TROIS+TROIS+CINQ+SEIZE=TRENTE 0m1.041s - QUATRE+QUATRE+QUATRE+NEUF+NEUF=TRENTE 0m0.831s - SATURN+URANUS=JUPITER 0m0.648s - MONITOR+NETWORK=INTERNET 0m0.518s - OASIS+SOLEIL=MIRAGE 0m0.166s - MANGER+MANGER=GROSSIR 0m0.225s - ALCOOL+ALCOOL=IVRESSE 0m13.068s - MARI+FEMME+ENFANT+ENFANT+ENFANT+ENFANT+ENFANT+ENFANT+ENFANT+ENFANT+ENFANT+ENFANT+ENFANT+ENFANT=FAMILLE 0m14.707s - MARI+FEMME+ENFANT+ENFANT+ENFANT+ENFANT+ENFANT+ENFANT+ENFANT+ENFANT+ENFANT+ENFANT+ENFANT+ENFANT+ENFANT+ENFANT+ENFANT+ENFANT+ENFANT+ENFANT=FAMILLE 0m0.226s - ROUGE+GORGE=OISEAU 0m2.585s - MOI+TOI+LUI+ELLE=NOUS 0m1.489s - LES+TESTS+D+INTELL=IGENCE 0m4.974s - TESTS+JEUX+SUPER=ESPRIT 0m4.410s - TESTS+JEUX+JEUNE=RESTER 0m2.326s - JEUX+JEUX+JEUX+JEUNE=ESPRIT 0m0.154s - TES+TESTS+ET+TES=MATHS 0m0.597s - TESTS+TESTS+TESTS+TESTS+TESTS+TESTS+QI=MENSA 0m0.613s - ADELE+ELLE+A+LA+BOSSE+DES=MATHS 0m0.479s - LES+MATHS+ELLES+AIMENT 0m0.619s - MARTIN+GARDNER=ADMIREZ 0m0.343s - ENIGME+GENIALE+MEME=SUBLIME 0m0.469s - SOMMES+CODEES=RBLOCH 0m0.484s - SOMMES+CODEES=MCRITON $ cat tests.sh cat tests.txt | while read line do temps=`(time echo $line | python2 AdditionMystereGeneriqueAcceleree.py ) 2>&1 | grep real | sed 's/real//'` echo "$temps - $line" done
Pour aller plus loin
Cryptarithmes:
http://fr.wikipedia.org/wiki/Cryptarithme
Backtracking et parcours d’arbre:
http://fr.wikipedia.org/wiki/Retour_sur_trace
http://fr.wikipedia.org/wiki/Algorithme_de_parcours_en_profondeur
http://fr.openclassrooms.com/informatique/cours/le-backtracking-par-l-exemple-resoudre-un-sudoku
http://fr.openclassrooms.com/informatique/cours/algorithmique-pour-l-apprenti-programmeur/arbres
http://www.liafa.jussieu.fr/~carton/Enseignement/Algorithmique/LicenceMathInfo/Programmation/Tree/parcours.html
Méthodes de résolution de problèmes avec contraintes:
http://www.tony-lambert.fr/these/these.html
Prolog et programmation par contrainte: http://fr.wikipedia.org/wiki/Programmation_par_contraintes http://liris.cnrs.fr/csolnon/Site-PPC/e-miage-ppc-som.htm
http://www.cril.univ-artois.fr/~sais/mastermis2.html http://prolog.developpez.com/cours/
http://www-sop.inria.fr/oasis/Marjorie.Russo/Cours/Prolog.html http://www.infop7.org/cursus/M1/Prolog#cours
Résolution du Sudoku en Prolog: http://pcaboche.developpez.com/article/prolog/clp/sudoku/
Autres problèmes sur lesquels appliquer le backtracking:
http://fr.wikipedia.org/wiki/Sudoku (mais aussi beaucoup d’autres jeux qui y ressemblent)
http://fr.wikipedia.org/wiki/Solitaire_(casse-tête) (à généraliser à toutes formes de plateau et disposition de pions)
http://fr.wikipedia.org/wiki/Problème_des_huit_dames (à généraliser pour N dames sur un échiquier NxN)
http://fr.wikipedia.org/wiki/Problème_du_cavalier (à généraliser pour un échiquier NxN)
http://fr.wikipedia.org/wiki/Perles_de_Dijkstra