# Cryptarithme

Un cryptarithme, aussi connu sous les noms d'arithmétique verbale, d'alphamétique et de cryptarithmétique, est un casse-tête numérique et logique qui consiste en une équation mathématique où les lettres représentent des chiffres à trouver.

## Description

L'équation comporte habituellement des opérations mathématiques de base, telles l'addition et la multiplication. L'exemple le plus connu, publié en juillet 1924 dans The Strand Magazine, est dû à Henry Dudeney :
${\begin{matrix}&&{\text{S}}&{\text{E}}&{\text{N}}&{\text{D}}\\+&&{\text{M}}&{\text{O}}&{\text{R}}&{\text{E}}\\\hline =&{\text{M}}&{\text{O}}&{\text{N}}&{\text{E}}&{\text{Y}}\\\end{matrix}}$
Chaque lettre correspond à un chiffre différent et le premier chiffre de chaque nombre est différent de zéro. Idéalement, le casse-tête doit avoir une solution unique.
La solution est O = 0, M = 1, Y = 2, E = 5, N = 6, D = 7, R = 8 et S = 9. Une méthode de résolution détaillée est décrite plus bas.

## Historique

Ce casse-tête est relativement ancien et son inventeur est inconnu. Par exemple, le magazine The American Agriculturalist de 1864 démontre que ce n'est pas Sam Loyd, un spécialiste américain de casse-têtes mathématiques, qui a développé ce casse-tête. Le nom crypt-arithmétique est dû au Belge Minos qui en fait le premier usage en mai 1931 dans Sphinx, un magazine belge de mathématiques ludiques. En 1955, James Alston Hope Hunter introduit le mot « alphametic » pour identifier des cryptarithmes dont les lettres forment des mots ou des phrases intelligibles.

## Résolution

Pour résoudre à la main un cryptarithme, il faut faire des déductions astucieuses et une recherche extensive parmi les possibilités. Par exemple, dans l'exemple fourni au début de l'article, le M du résultat est 1, puisqu'il s'agit de la retenue de la somme de deux chiffres. Il est donc logique d'estimer que S=9 ou S=8, puisque ce sont les deux seuls nombres qui peuvent donner une retenue lorsqu'additionnés à M=1 ou M=2 (de M O R E).
Un cryptarithme est une chaîne d'opérations où chaque lettre différente désigne un chiffre différent. Par exemple, supposons que nous ayons
Après quelques tâtonnements, on obtiendra A=1, B=2 et C=3. Par contre, pour des cryptarithmes plus complexes, il faut utiliser une démarche plus rigoureuse qui fait appel à la logique. La démarche suivante pour trouver une solution est donnée à titre didactique. Elle offre un modèle de résolution sur lequel s'appuyer pour résoudre des problèmes semblables.

### Trouver une solution

Plusieurs cryptarithmes n'ont qu'une seule solution, d'autres en présentent plusieurs.
Avant de résoudre ce problème, il faut identifier le plus de contraintes possibles (plus il y en a, plus rapidement la solution apparaîtra) :
* Les chiffres possibles sont {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
* Tous les chiffres complètement à gauche de chaque nombre n'égalent jamais zéro. Donc, S doit être différent de zéro, tout comme M.
* Lorsque l'on additionne deux chiffres, il peut y avoir une retenue. Par exemple, 5 + 7 = 12, le 1 sera mis en retenue dans la colonne suivante.
* On additionne au plus deux chiffres à la fois. Il est donc impossible que la retenue soit plus grande que 1 (ex. : 8 + 9 = 17)
* Pour faciliter le travail, on indiquera les retenues par des lettres minuscules : a, b et c.
* Finalement, la lettre E revient le plus souvent. Cela servira probablement à accélérer la recherche vers la solution.
Nous sommes prêts à commencer.
M est le dernier chiffre à la gauche de MONEY. Il est tentant de poser M=1 ou M=2, car la somme maximale est donnée par (8 + 9), qui égale 17. Pour qu'elle fasse au moins 20, il faudrait que a=3, ce qui est impossible ici. Donc, M=1. Nous avons maintenant
Le 1 de MONEY provient de la retenue calculée à partir de (a + S + 1), ce qui amène trois additions possibles :
* Si a=0, nous avons (0 + 9 + 1)
* Si a=1,
** nous avons (1 + 8 + 1)
** nous avons aussi (1 + 9 + 1)
Supposons que a=0, nous avons alors
Cette hypothèse semble raisonnable, car (0 + 9 + 1) = 10 et (E+0) donne probablement un nombre plus petit que 10. Puisque E est différent de N, il faut donc que b=1.
En inspectant rapidement la solution partielle, on voit que E se répète trois fois. C'est cette lettre qui, probablement, nous amènera le plus rapidement vers la solution, car si nous posons une valeur fausse pour elle, cela aura une incidence sur les trois nombres. En se basant sur cette solution partielle, il faut que E soit différent de 0, 1 et 9 (car ils sont déjà pris). Avec b=1, il faut que E soit différent de 8 car (1 + E + 0) = N, mais 9 est déjà pris. Donc, E vaut 2, 3, 4, 5, 6 ou 7. Posons E=2, on a donc
Par cette nouvelle addition, nous savons que N=3
Est-il possible que (c + 3 + R) égale 12? Le chiffre 9 est déjà pris, ce qui exclut c=0. R=7 ne fonctionne pas, car (1 + 3 + 7) = 11 (le chiffre 1 est déjà pris). Dans ce cas de figure, il faut donc que R=8 et c=1.
L'hypothèse E=2 amène une contradiction, car (D + 2) doit valoir au moins 10, alors que 8 et 9 sont déjà pris. Posons E=3, on a donc
Par cette nouvelle addition, nous savons que N=4.
Est-il possible que (c + 4 + R) égale 13? Il y a deux possibilités :
* (1 + 4 + 8) = 13, ce qui oblige à poser D=9, mais il est déjà pris.
* (0 + 4 + 9) = 12, mais 9 est déjà pris.
L'hypothèse E=3 amène une contradiction. Posons E=4, on a donc
Par cette nouvelle addition, nous savons que N=5.
Est-il possible que (c + 5 + R) égale 14? Il y a deux possibilités :
* (1 + 5 + 8) = 14,
** ce qui oblige à poser D=6 et amène Y=0, ce qui est impossible.
** ce qui oblige à poser D=7 et amène Y=1, ce qui est impossible.
L'hypothèse E=4 amène une contradiction. Posons E=5, on a donc
Par cette nouvelle addition, nous savons que N=6.
Est-il possible que (c + 6 + R) égale 15? Il y a une seule possibilité :
* (1 + 6 + 8) = 15, ce qui oblige à poser D=7 et amène Y=2.
Le cryptarithme est résolu.

### D'autres solutions ?

Y a-t-il d'autres solutions à ce cryptarithme? Posons E=6, on a donc
Par cette nouvelle addition, nous savons que N=7.
Est-il possible que (c + 7 + R) égale 16? Il y a une seule possibilité :
* (1 + 7 + 8) = 16, ce qui oblige à poser D=5 et amène Y=1, ce qui est impossible.
Posons E=7, on a donc
Par cette nouvelle addition, nous savons que N=8.
Est-il possible que (c + 8 + R) égale 17? Les deux possibilités sont impossibles :
* (0 + 8 + 9) = 17, mais 9 est déjà pris.
* (1 + 8 + 8) = 17, mais 8 est déjà pris.
L'utilisation de l'arithmétique modulaire peut aider à résoudre. En particulier, la réduction par 9 est souvent utile. Toujours dans l'exemple, ce principe affirme que S+E+N+D + M+O+R+E doit égaler M+O+N+E+Y modulo 9, donc S+E+D+R-Y est exactement divisible par 9.
En informatique, les cryptarithmes sont facilement résolubles à l'aide du retour sur trace. Ils servent aussi en tant qu'application pédagogique pour analyser les performances des algorithmes qui génèrent les permutations de n objets.

## Exemples

Voici les plus beaux exemples en français (compilés par Naoyuki Tamura) et complétés au moyen d'une recherche exhaustive avec tous les nombres :
HUIT + HUIT = SEIZE (8253 + 8253 = 16506 et 9254 + 9254 = 18508)
UN + UN + NEUF = ONZE (81 + 81 + 1987 = 2149)
CINQ + CINQ + VINGT = TRENTE (6483 + 6483 + 94851 = 107817)
ZERO + NEUF + NEUF + DOUZE = TRENTE (9206 + 3257 + 3257 + 86592 = 102312)
ZERO + ZERO + ZERO + UN + DOUZE = TREIZE (9506 + 9506 + 9506 + 82 + 76895 = 105495)
ZERO + ZERO + SEPT + SEPT + SEIZE = TRENTE (6904 + 6904 + 7921 + 7921 + 79869 = 109519)
ZERO + UN + TROIS + ONZE + QUINZE = TRENTE (7139 + 68 + 53902 + 9871 + 460871 = 531851)
ZERO + TROIS + TROIS + TROIS + SEPT = SEIZE (4273 + 17356 + 17356 + 17356 + 6201 = 62542)
ZERO + TROIS + TROIS + DOUZE + DOUZE = TRENTE (3496 + 19625 + 19625 + 76034 + 76034 = 194814)
ZERO + QUATRE + QUATRE + ONZE + ONZE = TRENTE (4876 + 130278 + 130278 + 6548 + 6548 = 278528)
UN + UN + QUATRE + DOUZE + DOUZE = TRENTE (59 + 59 + 652801 + 74531 + 74531 = 801981)
UN + DEUX + DEUX + DEUX + DEUX = NEUF (25 + 1326 + 1326 + 1326 + 1326 = 5329)
UN + QUATRE + CINQ + CINQ + QUINZE = TRENTE (50 + 356724 + 8103 + 8103 + 351094 = 724074)
TROIS + TROIS + TROIS + CINQ + SEIZE = TRENTE (14509 + 14509 + 14509 + 7063 + 98028 = 148618)
QUATRE + QUATRE + QUATRE + NEUF + NEUF = TRENTE (172536 + 172536 + 172536 + 9674 + 9674 = 536956)
3 × MOT = TOM - 1.