Hello all. I am working on a USACO problem for practice. The question asks:
The following cryptarithm is a multiplication 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.
1 2 3 4 5 6 7 8 9 10

/***
* * *
x * *

* * * < partial product 1
* * * < partial product 2

* * * *
***/
 
Digits can appear only in places marked by `*'. Of course, leading zeroes are not allowed.
Note that the 'partial products' are as taught in USA schools. The first partial product is the product of the final digit of the second number and the top number. The second partial product is the product of the first digit of the second number and the top number.
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}.
My code passes for 3 tests but fails on the fourth:
7
4 1 2 5 6 7 3
 our output  (correct answer vs incorrect)
384
 your output 
270

An example of one that passes:
5
2 3 4 6 8
Output: 1
By looking at this:
1 2 3 4 5 6 7 8 9 10

/***
5 4 2
x 3 1

* * * < partial product 1
* * * < partial product 2 4*3 1*4 1*4+4*3

* x y z
***/
 
My approach is to loop through the values 15 in the
diagram above, getting all permutations and testing if they pass the necessary conditions along the way. Only continuing if the elements we've plugged in so far make no contradictions and increment a counter if we pass the final conditional. The conditionals just check to see if the number is in our vector of given numbers to work with. I made sure to carry over any values that had to be carried over. Is there a flaw in this approach? I feel there is some gap in my approach that I am missing. If anyone could help it would be very appreciated! It mentions PRIME Cryparithm, perhaps this is a special case? Hmm , the fail case isnt a prime cryparithm either way.
In the most simple sense I am going through the grade school multiplication algorithm with partial products, and testing at each loop.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdlib.h>
using std::vector; using std::cin;
using std::cout; using std::endl;
int main()
{
vector<int> numbers;
int counter = 0;
int s_one, s_two, s_three, s_four, s_five;
int data_size;
cin >> data_size;
for (int i = 0; i < data_size; i++){
int x;
cin >> x;
numbers.push_back(x);
}
sort (numbers.begin(), numbers.end());
for (vector<int>::const_iterator iter = numbers.begin(); iter != numbers.end(); ++iter){
cout << *iter << ' ';
}
cout << endl;
// Start search. 5 Loops for each element as labeled in comment (1 through 5).
for (int i = 0; i < numbers.size(); i++){
s_one = numbers[i];
cout << "Current count: " << counter << endl;
for (int j = 0; j < numbers.size(); j++){
s_two = numbers[j];
int carry1 = 0; // Value to carry over.
int mult1 = s_one * s_two;
if (mult1 > 9){ // Calculate carry value if needed...
carry1 = mult1/10;
mult1 = mult1 % 10;
}
if (find(numbers.begin(),numbers.end(), mult1) != numbers.end()){
for (int k = 0; k < numbers.size(); k++){
s_three = numbers[k];
int carry2 = 0;
int mult2 = s_three * s_two;
if (mult2 > 9){ // Calculate carry value if needed...
carry2 = mult2/10;
mult2 = mult2 % 10;
}
if (find(numbers.begin(),numbers.end(), mult2) != numbers.end()){
for (int l = 0; l < numbers.size(); l++){
s_four = numbers[l];
int mult3 = s_three * s_four + carry2;
int mult4 = s_one * s_four + carry1;
int carry3 = 0, carry4 = 0;
if (mult3 > 9){
carry3 = mult3/10;
mult3 = mult3 % 10;
}
if (mult4 > 9){
carry4 = mult4/10;
mult4 = mult4 % 10;
}
int sum1 = mult2 + mult4;
int sum_carry1 = 0;
if (sum1 > 9){
sum_carry1 = sum1/10;
sum1 = sum1 % 10;
}
if (find(numbers.begin(),numbers.end(), mult3) != numbers.end() &&
find(numbers.begin(),numbers.end(), mult4) != numbers.end() &&
find(numbers.begin(),numbers.end(), sum1) != numbers.end()){
for (int m = 0; m < numbers.size(); m++){
s_five = numbers[m];
int mult5 = s_three * s_five + carry3;
int mult6 = s_one * s_five + carry4;
if (mult5 > 9  mult6 > 9){
continue; // Condition breaks our template.
}
int sum2 = mult6 + mult3 + sum_carry1;
if (sum2 > 9){
continue;
}
int status = 1;
if (find(numbers.begin(),numbers.end(), mult5) != numbers.end() &&
find(numbers.begin(),numbers.end(), mult6) != numbers.end() &&
find(numbers.begin(),numbers.end(), sum2) != numbers.end()){
counter++;
cout << "SOLUTION FOUND!" << endl;
status = 0;
}
if (status == 1){
cout << endl;
cout << "__Current values__ " << endl;
cout << "Numbers at i: " << numbers[i] << endl;
cout << mult1 << ' ' << mult2 << ' ' << mult3 << ' ' << mult4 << ' ' << mult5 << ' ' << mult6 << endl;
cout << sum1 << ' ' << sum2 << endl;
cout << "********" << endl;
system("pause");
}
} // End loop 5
}
} // End loop 4
}
} // End loop 3
}
} // End loop 2
} // End loop 1
cout << counter << endl;
}
 