Editing Verbal arithmetic

{{short description|Puzzle of reconstructing equations that have been enciphered into words}}
'''Verbal arithmetic''', also known as '''alphametics''',  '''cryptarithmetic''', '''cryptarithm''' or '''word addition''', is a type of [[mathematical game]] consisting of a mathematical [[equation]] among unknown [[number]]s, whose [[numerical digit|digit]]s are represented by [[Letter (alphabet)|letter]]s of the alphabet.  The goal is to identify the value of each letter.  The name can be extended to puzzles that use non-alphabetic symbols instead of letters.

The equation is typically a basic operation of [[arithmetic]], such as [[addition]], [[multiplication]], or [[division (mathematics)|division]].  The classic example, published in the July 1924 issue of ''[[The Strand Magazine]]'' by [[Henry Dudeney]],<ref>[[Henry Dudeney|H. E. Dudeney]], in ''[[Strand Magazine]]'' vol. 68 (July 1924), pp. 97 and 214. https://babel.hathitrust.org/cgi/pt?id=mdp.39015055410669&seq=109</ref> is:

<math>\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}</math>

The solution to this puzzle is O = 0, M = 1, Y = 2, E = 5, N = 6, D = 7, R = 8, and S = 9.

Traditionally, each letter should represent a different digit, and (as an ordinary arithmetic notation) the leading digit of a multi-digit number must not be zero.  A good puzzle should have one unique solution, and the letters should make up a phrase (as in the example above).

Verbal arithmetic can be useful as a motivation and source of exercises in the [[education|teaching]] of [[elementary algebra]].

==History== 
'''Cryptarithmic''' puzzles are quite old and their inventor is unknown. An 1864 example in The American Agriculturist<ref name="agriculturist">{{Cite news|url=https://archive.org/stream/americanagricult23unse#page/349/mode/1up|title=No. 109 Mathematical puzzle|date=December 1864|newspaper=American Agriculturist|issue=12|volume=23|pages=349}}
</ref> disproves the popular notion that it was invented by [[Sam Loyd]].  The name "cryptarithm" was coined by puzzlist Minos (pseudonym of [[Simon Vatriquant]]) in the May 1931 issue of Sphinx, a Belgian magazine of recreational mathematics, and was translated as "cryptarithmetic" by [[Maurice Kraitchik]] in 1942.<ref>[[Maurice Kraitchik]], Mathematical Recreations (1953), pp. 79-80.</ref>  In 1955, J. A. H. Hunter introduced the word "alphametic" to designate cryptarithms, such as Dudeney's, whose letters form meaningful [[word]]s or phrases.<ref>J. A. H. Hunter, in the [[Toronto]] ''Globe and Mail'' (27 October 1955), p. 27.</ref>

== Types of cryptarithms ==
[[File:feynman_long_division_puzzle.svg|thumb|upright|[[Richard Feynman]]'s skeletal division puzzle &ndash; each A represents the same digit, and each dot any digit not represented by A <ref>{{Cite book|url=https://books.google.com/books?id=8m44DgAAQBAJ&pg=PT39|title = Perfectly Reasonable Deviations from the Beaten Track: The Letters of Richard P. Feynman|isbn = 9780786722426|last1 = Feynman|first1 = Richard P.|date = August 2008| publisher=Basic Books }}</ref>]]
Types of cryptarithm include the alphametic, the digimetic, and the skeletal division.  

;Alphametic
: A type of cryptarithm in which a set of words is written down in the form of a long addition sum or some other mathematical problem. The object is to replace the letters of the alphabet with decimal digits to make a valid arithmetic sum.
;Digimetic
: A cryptarithm in which digits are used to represent other digits.

;Skeletal division
: A long division in which most or all of the digits are replaced by symbols (usually asterisks) to form a cryptarithm.

==Solving cryptarithms==
Solving a cryptarithm by hand usually involves a mix of deductions and exhaustive tests of possibilities.  For instance the following sequence of deductions solves Dudeney's SEND+MORE = MONEY puzzle above (columns are numbered from right to left):

<math>\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}</math>

#From column 5, '''M = 1''' since it is the only carry-over possible from the sum of two single digit numbers in column 4.
#Since there is a carry in column 5, O must be less than or equal to M (from column 4). But O cannot be equal to M, so O is less than M. Therefore '''O = 0'''.
#Since O is 1 less than M, S is either 8 or 9 depending on whether there is a carry in column 4. But if there were a carry in column 4 (generated by the addition of column 3), N would be less than or equal to O. This is impossible since O = 0. Therefore there is no carry in column 4 and '''S = 9'''.
#If there were no carry in column 3 then E = N, which is impossible. Therefore there is a carry and N = E + 1.
#If there were no carry in column 2, then ( N + R ) mod 10 = E, and N = E + 1, so ( E + 1 + R ) mod 10 = E which means ( 1 + R ) mod 10 = 0, so R = 9. But S = 9, so there must be a carry in column 2 so '''R = 8'''.
#To produce a carry in column 2, we must have D + E = 10 + Y.
#Y is at least 2 so D + E is at least 12.
#The only two pairs of available numbers that sum to at least 12 are (5,7) and (6,7) so either E = 7 or D = 7.
#Since N = E + 1, E can't be 7 because then N = 8 = R so '''D = 7'''.
#E can't be 6 because then N = 7 = D so '''E = 5''' and '''N = 6'''.
#D + E = 12 so '''Y = 2'''.
Another example of TO+GO=OUT (source is unknown):

<math>\begin{matrix}
     &   & \text{T} & \text{O}  \\
   + &   & \text{G} & \text{O} \\
 \hline
   = & \text{O} & \text{U} & \text {T}\\
\end{matrix}</math>

# The sum of two biggest two-digit-numbers is 99+99=198. So '''O=1''' and there is a carry in column 3.
# Since column 1 is on the right of all other columns, it is impossible for it to have a carry. Therefore 1+1=T, and '''T=2'''.
# As column 1 had been calculated in the last step, it is known that there isn't a carry in column 2. But, it is also known that there is a carry in column 3 in the first step. Therefore, 2+G≥10. If G is equal to 9, U would equal 1, but this is impossible as O also equals 1. So only '''G=8''' is possible and with 2+8=10+U, '''U=0'''.

The use of [[modular arithmetic]] often helps.  For example, use of mod-10 arithmetic allows the columns of an addition problem to be treated as [[simultaneous equations]], while the use of mod-2 arithmetic allows inferences based on the [[parity (mathematics)|parity]] of the variables.

In [[computer science]], cryptarithms provide good examples to illustrate the [[brute force search|brute force]] method, and algorithms that  generate all [[permutation]]s of ''m'' choices from ''n'' possibilities. For example, the Dudeney puzzle above can be solved by testing all assignments of eight values among the digits 0 to 9 to the eight letters S,E,N,D,M,O,R,Y, giving 1,814,400 possibilities. They also provide good examples for [[backtracking]] paradigm of [[algorithm]] design.

==Other information==
When generalized to arbitrary bases, the problem of determining if a cryptarithm has a solution is [[NP-complete]].<ref>{{cite journal | author = David Eppstein | title = On the NP-completeness of cryptarithms | journal = SIGACT News | volume = 18 | issue = 3 | pages = 38–40 | year = 1987 | url = http://www.ics.uci.edu/~eppstein/pubs/Epp-SN-87.pdf | doi = 10.1145/24658.24662| s2cid = 2814715 | author-link = David Eppstein }}</ref> (The generalization is necessary for the hardness result because in base 10, there are only 10! possible assignments of digits to letters, and these can be checked against the puzzle in linear time.)

Alphametics can be combined with other number puzzles such as Sudoku and Kakuro to create cryptic [[Sudoku]] and [[Kakuro]].<!--NOT CLEAR HOW-->

== Longest alphametics ==
Anton Pavlis constructed an alphametic in 1983 with 41 addends:

:SO+MANY+MORE+MEN+SEEM+TO+SAY+THAT+
:THEY+MAY+SOON+TRY+TO+STAY+AT+HOME+
:SO+AS+TO+SEE+OR+HEAR+THE+SAME+ONE+
:MAN+TRY+TO+MEET+THE+TEAM+ON+THE+
:MOON+AS+HE+HAS+AT+THE+OTHER+TEN
:=TESTS

(The answer is that MANYOTHERS=2764195083.)<ref>{{cite web|last1=Pavlis|first1=Anton|title=Crux Mathematicorum|url=https://cms.math.ca/wp-content/uploads/crux-pdfs/Crux_v9n04_Apr.pdf|website=Canadian Mathematical Society|access-date=14 December 2016|page=115}}</ref>

==See also==
* [[Diophantine equation]]
* [[Mathematical puzzle]]s
* [[Permutation]]
* [[Puzzle]]s
* [[Sideways Arithmetic From Wayside School]] - A book whose plot revolves around these puzzles
* [[Cryptogram]]

==References==
{{Reflist}}
{{More footnotes|date=July 2010}}
* [[Martin Gardner]], ''Mathematics, Magic, and Mystery''. Dover (1956)
* [[Journal of Recreational Mathematics]], had a regular alphametics column.
* Jack van der Elsen, ''Alphametics''. Maastricht (1998)
* Kahan S., Have some sums to solve: The complete alphametics book, Baywood Publishing, (1978)
* Brooke M. One Hundred & Fifty Puzzles in Crypt-Arithmetic. New York: Dover, (1963)
* Hitesh Tikamchand Jain, ABC of Cryptarithmetic/Alphametics. India(2017)

==External links==
*[http://people.revoledu.com/kardi/tutorial/CryptArithmetic/index.html Solution using Matlab code and tutorial]
* [http://www.cut-the-knot.org/cryptarithms/st_crypto.shtml Cryptarithms] at [[cut-the-knot]]
* {{MathWorld | urlname=Alphametic| title=Alphametic}}
* {{MathWorld | urlname=Cryptarithmetic | title=Cryptarithmetic}}
* [http://www.mathematik.uni-bielefeld.de/~sillke/PUZZLES/ALPHAMETIC/ Alphametics and Cryptarithms]

=== Alphametics solvers ===

*[https://cs.stcc.edu/alphametics/ Alphametics Solver!]
*[http://www.tkcs-collins.com/truman/alphamet/alpha_solve.shtml Alphametics Puzzle Solver]
*[https://play.google.com/store/apps/details?id=com.practicetime.cryptsolver Android app to solve Crypt Arithmatic problems]
*[http://code.activestate.com/recipes/576615/ Alphametic Solver written in Python]
*[http://www.iread.it/cryptarithms.php An online tool to create and solve Alphametics and Cryptarithms]
*[http://cryptarithm.pavlis.ca An online tool to solve, create, store and retrieve alphametics - over 4000 English alphametics available with solutions]


[[Category:Logic puzzles]]
[[Category:NP-complete problems]]