CODEWITHSUNDEEP
matlablinear-algebra
U_D
U_D

Reputation: 731

Solving 2 equations - 9 Unknowns, with constraints.

I'm trying to solve a riddle with the use of matlab. This is realy more about matlab than the riddle itself (The riddle is taken from a daily newspaper).

The riddle gives two 3 digits numbers represented by letters. I need to find the digit (0-9) the doesn't participate.

aba-dcc=efe ; aba+dcc=ghi

Now, I have 2 equations with 9 unknowns. I've managed to solve it by checking all permutations of the vector 0:9, in a while loop.

vecAns = 0:9;
P = perms(vecAns);
P = P(:,1:9);

A = [ 101 10 -100 -11 -101 -10 0 0 0 ;...
        101 10 100 11 0 0 -100 -10 -1];

resVec = [0;0];
found=false;

i=1;
h = waitbar(0,'Computing');
while found==false
        Res=A*P(i,:)';
        if (Res(1)==0)&&(Res(2)==0)
            break;
        end
        i=i+1;
        waitbar(i/length(P),h,sprintf('%d%%',i/length(P)*100));
end
close(h)

Is there a way (without adding mathematical considerations) to solve the problem. For example, I know that all the unknowns must be integers and within the range 0-9.

If there isn't a way. How can make it more efficient?

Upvotes: 1

Views: 185

Answers (1)

Markus Jarderot
Markus Jarderot

Reputation: 89171

You don't have to enumerate all the permutations. You can start with the first 4 digits (a, b, c and d), and check if they produce a difference and sum that matches efe and ghi. You also need to make sure all the digits are distinct.

I'm not very proficient in writing matlab code, so I'll demonstrate it with C# code:

//aba-dcc=efe
//aba+dcc=ghi
for (int a = 1; a <= 9; a++) // 'a' cannot be zero
for (int b = 0; b <= 9; b++)
if (a != b)
for (int c = 0; c <= 9; c++)
if (c != a && c != b)
for (int d = 1; d <= 9; d++) // 'd' cannot be zero
if (d != a && d != b && d != c)
{
    int aba = a*101 + b*10;
    int dcc = c*11 + d*100;

    int efe = aba - dcc;
    if (efe < 0) continue;

    int ghi = aba + dcc;
    if (ghi > 999) continue;

    int e = efe % 10;
    if (e == a || e == b || e == c || e == d) continue;

    int f = (efe/10)%10;
    if (f == a || f == b || f == c || f == d || f == e) continue;

    if (efe != e*101 + f*10) continue;

    int i = ghi%10;
    if (i == a || i == b || i == c || i == d || i == e || i == f) continue;

    int h = (ghi/10)%10;
    if (h == a || h == b || h == c || h == d || h == e || h == f || h == i) continue;

    int g = (ghi/100)%10;
    if (g == a || g == b || g == c || g == d || g == e || g == f || g == i || g == h) continue;

    Console.WriteLine("{0:d3}-{1:d3}={2:d3} ; {0:d3}+{1:d3}={3:d3}", aba, dcc, efe, ghi);
}

This completes in less than a millisecond on my computer.

Output:

717-233=484 ; 717+233=950

(% is modulus, and / is integer division. continue skips to the next iteration of the loops.)

Upvotes: 1

Related Questions