On the NP-completeness of cryptarithms
Dror Epstein · ACM SIGACT News · 1987
Cryptarithm puzzles, also known as alphametics, appear widely in recreational mathematics publications , and have also been used as an example of the efficiency of constraint propagation search techniques [5] .Her e we show that solving such puzzles is an NP-complete problem .Many cryptarithms are given by Madachy [4], including the following well-known example :The puzzle is to find a one-to-one correspondence between letters in the puzzle and decimal digits (not.all of which must appear) that will make the sum correct .There is usually also a rule that numbers ar e expressed without leading zeros .The above example has a unique solution : 956 7