Backtracking | Set 8 (Solving Cryptarithmetic Puzzles) | GeeksforGeeks

Newspapers and magazines often have crypt-arithmetic puzzles of the form:

  SEND  + MORE  --------   MONEY  -------- 

The goal here is to assign each letter a digit from 0 to 9 so that the arithmetic works out correctly. The rules are that all occurrences of a letter must be assigned the same digit, and no digit can be assigned to more than one letter.

• First, create a list of all the characters that need assigning to pass to Solve
• If all characters are assigned, return true if puzzle is solved, false otherwise
• Otherwise, consider the first unassigned character
• for (every possible choice among the digits not in use)
make that choice and then recursively try to assign the rest of the characters
if recursion sucessful, return true
if !successful, unmake assignment and try another digit

• If all digits have been tried and nothing worked, return false to trigger backtracking

bool ExhaustiveSolve(puzzleT puzzle, string lettersToAssign)

{

    if (lettersToAssign.empty()) // no more choices to make

        return PuzzleSolved(puzzle); // checks arithmetic to see if works

    for (int digit = 0; digit <= 9; digit++)   // try all digits

    {

        if (AssignLetterToDigit(lettersToAssign[0], digit))

        {

            if (ExhaustiveSolve(puzzle, lettersToAssign.substr(1)))

                return true;

            UnassignLetterFromDigit(lettersToAssign[0], digit);

        }

    }

    return false;  // nothing worked, need to backtrack

}

Pruning
A smarter algorithm could take into account the structure of the puzzle and avoid going down dead-end paths. For example, if we assign the characters starting from the ones place and moving to the left, at each stage, we can verify the correctness of what we have so far before we continue onwards.
http://ideone.com/Ev6ptM
http://ideone.com/jvZq3i

Solving Cryptarithmetic Problems Using Parallel Genetic Algorithm
http://blog.csdn.net/taoqick/article/details/20478575?utm_source=jiancool
Cryptarithmetic - CodeProject

Extension
http://www.quora.com/Mathematical-Puzzles/How-would-you-solve-this-cryptarithmetic-multiplication

×OOOUNOYHEWNOPAPHUNYOYTPP
Read full article from Backtracking | Set 8 (Solving Cryptarithmetic Puzzles) | GeeksforGeeks