How to do it quickly?

Question

C++ / C#

It is necessary to make sure that the numbers assigned to the letters are all different, I think if you see the code, you will understand what I am asking. This can be done by brute-force, but I'm wondering if it can be done somehow faster.

#include <iostream>
using namespace std;
int main()
{
    int dedka, babka, repka;
    long int skazka;
    cout << "s" << endl;
    for (int d = 0; d < 10; d++) {
        for (int e = 0; e < 10; e++) {
            for (int k = 0; k < 10; k++) {
                for (int a = 0; a < 10; a++) {
                    for (int b = 0; b < 10; b++) {
                        for (int r = 0; r < 10; r++) {
                            for (int p = 0; p < 10; p++) {
                                for (int s = 0; s < 10; s++) {
                                    for (int k = 0; k < 10; k++) {
                                        for (int z = 0; z < 10; z++) {
                                            dedka = d * 10000 + e * 1000 + d * 100 + k * 10 + a;
                                            babka = b * 10000 + a * 1000 + b * 100 + k * 10 + a;
                                            repka = r * 10000 + e * 1000 + p * 100 + k * 10 + a;
                                            skazka = s * 100000 + k * 10000 + a * 1000 + z * 100 + k * 10 + a;
                                            if ((dedka + babka + repka == skazka) && ((dedka > babka) && (babka > repka)) && ((dedka > 9999)&& (babka > 9999)&& (repka > 9999)&& (skazka > 99999))) {
                                                cout << dedka << " + " << babka << " + " << repka << " = " << skazka << endl;
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    return 0;
}

Answer 1

It is necessary to solve as much as possible analytically.
a + a + a = ...a
This is possible only if a = 0 or a = 5.
k + k + k = ...k if a = 0 or k + k + k + 1 = ...k if a = 5
This system only has a solution for a = 0 and k = 5.
s is a carry from the least significant bit. Hence s ∈ {1, 2}.
e + 0 + e = ...0 or e + 0 + e + 1 = ...0 or e + 0 + e + 2 = ...0
This is only possible for e ∈ {0, 4, 5, 9 }. But 0 and 5 are already taken. Hence e ∈ {4, 9}.
We get

int a = 0;
int k = 5;
for (int s = 1; s <= 2; s++) {
  for (int e = 4; e <= 9; e += 5) {
    ...Тут все остальные буквы.

Such an analysis will reduce the exhaustive search by a factor of 2500.
Then, we can say that d > b > r, respectively write the cycles as

...
    for (int d = 3; d <= 9; d++) {
      for (int b = 2; b < d; b++) {
        for (int r = 1; r < b; r++) {
          ...

This will reduce the enumeration by almost 12 times more (from 1000 cycles to 84)
For p, taking into account that 1 is transferred from the low order, and 2 should go to the high order, we can write the condition
d + b + p + 1 >= 20 => p >= 19 - d - b
So we get a cycle

...
          for (int p = 19 - d - b; p <= 9; p++) {
            ...

z can not be wrapped in a loop at all, but calculated as z = (d + b + p + 1) % 10.
This will reduce the enumeration by another 10 times.
Well, as a rule, in such problems there is a condition that different letters correspond to different numbers. It is worth adding a check where necessary.
In total, the enumeration will be reduced by more than 300,000 times.

Solution in PHP

<?php
$a = 0;
$k = 5;
$count = 0;
for ($s = 1; $s <= 2; $s++) {
  for ($e = 4; $e <= 9; $e += 5) {
    for ($d = 3; $d <= 9; $d++) {
      if ($d == 5 || $d == $e) {
        continue;
      }
      for ($b = 2; $b < $d; $b++) {
        if ($b == 5 || $b == $s || $b == $e) {
          continue;
        }
        for ($r = 1; $r < $b; $r++) {
          if ($r == 5 || $r == $s || $r == $e) {
            continue;
          }
          for ($p = 19 - $d - $b; $p <= 9; $p++) {
            if ($p == 5 || $p == $s || $p == $e || 
                $p == $d || $p == $b || $p == $r) {
              continue;
            }
            $z = ($d + $b + $p + 1) % 10;
            if ($z == 0 || $z == 5 || $z == $s || 
                $z == $e || $z == $d || $z == $b || 
                $z == $r || $z == $p) {
              continue;
            }
            $count += 1;
            $dedka = $d * 10100 + $e * 1000 + 50;
            $babka = $b * 10100 + 50;
            $repka = $r * 10000 + $e * 1000 + $p * 100 + 50;
            $skazka = $s * 100000 + $z * 100 + 50050;
            if ($dedka + $babka + $repka == $skazka) {
              print " {$dedka}\n+{$babka}\n+{$repka}\n======\n{$skazka}\n";
            }
          }
        }
      }
    }
  }
}
print "count = {$count}\n";
/*
 94950
+80850
+74350
======
250150
count = 17
*/

In fact, the main condition check only ran 17 times instead of 1000000000 in your case.
PS Yes, and s can also not be sorted out, but calculated. Then it will be even faster, the main check will be performed 11 times.

Answer 2

Sort letters from low to high: a, k, d, b, z, e...
Check the correctness of the sum numerically from right to left as early as possible.
Those. after iterating over a, we can already check that (a+a+a) % 10 = a. Then, after k, you need to check (ka + ka + ka)% 100 = ka, after dbz, you can check the third digit.
You can optimize a little if you don’t count (ka + ka + ka)% 100, but remember what the carry from the lowest digit is and check only (k + k + k + carry1)% 10 = k, carry2 = (k + k +k+carry1)/10; Then check that (d+b+p + carry2)%10 = z and so on.
In this case, you will not sort out frankly superfluous, so the solution will be much faster.
The next improvement is not to iterate over the letters s, z, e and r, but immediately calculate what they should be in order for the sum to converge. With s and z everything is trivial, but for e and r you need a little bit of mathematics.
It is necessary to carefully write out the equations of the form (e+a+e+carry2)%10=a.
Here you need to apply the module properties: 2e %10=-carry2 % 10, There are 2 solutions for e, if carry2 is even: (10-carry2)/2, (20-carry2) / 2
But this improvement will not speed up much.