Solving $8$ variables with $2$ equations

Question

Lets say we have $8$ variables (each variable can have a value from $1$ to $10$ only) with $2$ equations -

$A + B + C + D + E + F + G + H = {\text{SUM}}\\ A - B - C - D - E - F - G - H = {\text{DIFF}}$

What is the fastest algorithm which can find out the values of variables, given the sum and difference values.

For example,

$A = 8\\ B = 7\\ C = 10\\ D = 5\\ E = 10\\ F = 3\\ G = 9\\ H = 1$

$A + B + C + D + E + F + G + H = 53\\ A - B - C - D - E - F - G - H = -37$

So, given the values $53$ and $-37,$ how can we find values of all $8$ variables?

There is a brute force approach by substituting each variable with values from $1$ to $10$ and checking the sum and difference, but it will take a long time.

How can we achieve it in a faster way?

Thanks.

Answer 1

Adding the two equations, we see $A = \frac{\{SUM\}+\{DIFF\}}{2}$. Consequently, if two does not divide $\{SUM\}+\{DIFF\}$, there is no solution. Also, we require $2 \leq \{SUM\}+\{DIFF\} \leq 20$, or no solution is possible.

Subtracting the second equation from the first, $B +C +D+E+F+G+H= \frac{\{SUM\}-\{DIFF\}}{2}$. The requirement that two divides $\{SUM\}+\{DIFF\}$ automatically causes two to divide $\{SUM\}-\{DIFF\}$, so we do not have a new condition to check for the existence of a solution. However, we must have $14 \leq \{SUM\}-\{DIFF\} \leq 140$, or no solution is possible.

Assuming a solution exists, for each composition of $\frac{\{SUM\}-\{DIFF\}}{2}$ into seven parts of size in $[1,10]$, emit a solution. There can be a lot of these. When $\frac{\{SUM\}-\{DIFF\}}{2} = 39$, there are $512\,365$ solutions. (Found using the generating function $(x+x^2+\cdots+x^{10})^7$.)

Note that since $B$, $C$, $D$, $E$, $F$, $G$, and $H$ are all at least $1$, we might as well generate compositions of $\frac{\{SUM\}-\{DIFF\}}{2} - 7$ having seven parts of size in $[0,9]$, then add $1$ to each part to get the value to assign to its variable.

Optimal time generation of compositions is still an area of ongoing research. (example) Since the ranges of these variables are so narrow, I would probably use the non-tricky "six nested for loops" method.

(* do the various checks described above to see if there are any solutions before proceeding *)
A := ({SUM}+{DIFF})/2
tot := ({SUM}-{DIFF})/2
for B = max(1,tot-6*10) to min(10,tot)
  for C = max(1,tot-B-5*10) to min(10, tot-B)
    for D = max(1,tot-B-C-4*10) to min(10, tot-B-C)
      for E = max(1,tot-B-C-D-3*10) to min(10, tot-B-C-D)
        for F = max(1,tot-B-C-D-E-2*10) to min(10, tot-B-C-D-E)
          for G = max(1,tot-B-C-D-E-F-10) to min(10, tot-B-C-D-E-F)
            H = tot-B-C-D-E-F-G
            if 1 <= H <= 10
              emit the solution (A,B,C,D,E,F,G,H)

The principle effect of the max(1,tot-...) lower bounds is to force variables to start at the least value that will reach tot assuming all subsequent variables are maxed out.

(It's late/early here and I haven't tested this code, so it likely contains typos and bugs. Corrections in comments are welcome.)