Prime cryptarithm

[arun1390]

Trying to write a few programs to get practice, i decided to solve the following problem i found on http://www.inf.bme.hu/contests/tasks/usa93q.html :


PRIME CRYPTARITHM
The following cryptarithm is a multi- plication problem that can be solved by substituting digits from a specified set of N digits into the positions marked with *. If the set of prime digits {2,3,5,7} is selected, the cryptarithm is called a PRIME CRYPTARITHM.

* * *
x * *
-------
* * * *
* * * *
---------
* * * * *

Write a program that will find all solutions to the cryptarithm above for any subset of digits from the set {1,2,3,4,5,6,7,8,9}.

Test your program with the digits 23468
and the prime digits 2357.

Sample Run
ENTER A SET OF DIGITS: 23468
2 2 2
x 2 2
------
4 4 4 <-partial result 1
4 4 4 <-partial result 2
---------
4 8 8 4 <-final result

The number of unique solutions = 4


The program works well, but i get the feeling there may be simpler (more effective) ways to do it!
I want to know how you would go about it.

My approach was this:
1. Find all possible combinations of digits, from the specified subset, for the two numbers being multiplied (this has resulted in several nested loops!).
2. For each combination, find the corresponding partial and final results.
3. Check if the results contain only digits found within the set of specified digits
4. If yes increment a counter.
5. Output the numbers and the number of solutions.


I'm not posting the actual code because it's quite long. I'll do it if required by anyone.

Thanks.

[Hammurabi]

To get rid of your nested loops, you could count in the base given by the number of digits. E.g., 2357 is 4 digits, so count in base 4. That is, increment a variable in a loop and interpret it as base 4. Then assign numbers from the given list according to the (base 4) digits in the count:

Count    Assigned
00000    22222
00001    22223
00002    22225
00003    22227
00010    22232
00011    22233
 ...      ...

Here's a possible mainline. Only generateSolution needs to do any base 4 (or whatever) stuff.

const int SolutionLength = 5;
int digits[ 10 ], solution[ SolutionLength ];
int nDigits = getDigits( digits );
int stop = (int) pow( nDigits, SolutionLength );
int nSolutions = 0;
for( int i = 0; i < stop; ++i ){
    generateSolution( i, digits, nDigits, solution, SolutionLength );
    if( testSolution( digits, solution )){
        displaySolution( solution );
        ++nSolutions;
    }
}
cout << "Number of solutions: << nSolutions << '\n'; 

[jsmith]

At first glance it seems like this is a good candidate for recursion because the recursion can be used to prune out obvious non-solutions without doing any actual work. For example, given the numbers ABC and YZ (each letter represents a digit), if partial result 1 does not satisfy the constraint, then you know that for all values k, ABC and kZ yield a non-solution since k does not in any way affect partial result 1.

NB: this can also be implemented non-recursively as well.