Subject: Re: Diophantic Equation System
Date: 24 Feb 2000 19:53:57 GMT
From: israel@math.ubc.ca (Robert Israel)

"Thomas Lichtenberg" <lichtenberg.thomas@t-online.de> writes:

> I worry about a numerical problem like:

>   ABCD  +  EFGH  =  KLBK
>     :        -        +
>     LL  +  EFFC  =  EFDL
>     =        =        =
>    EGA  x    AH  =  DGFG

> Where every letter represents a single number.

You mean each letter is a digit 0 to 9?  A single equation of this
type is called an alphametic, so I guess this would be a system of
alphametics.  Since there are only 10! = 3628800 possible assignments of
letters to digits, even a brute-force search would be a feasible
method, and it's easy to write programs that do a somewhat more
intelligent search.  I have an alphametic solver applet on the Web at
http://www.geocities.com:80/CapeCanaveral/Campus/7705/metic/metic.html.
You could make a system into a single equation by e.g. looking at the
sum of the squares of the differences of the two sides of the equations:
(ABCD+EFGH-KLBK)^2+(LL+EFFC-EFDL)^2+(EGA*AH-DGFG)^2=0.
However, a complicated equation such as this might take the applet a
long time.  Here's a Maple program that will handle a system of
alphametics (presented as a set or list of equations):

-----------------------
alphametics:= proc(L)
       `metic/solve`([seq(op(`metic/parse`(expr)),expr=L)],{},
             {0,1,2,3,4,5,6,7,8,9});
       end;
`metic/parse`:= proc(expr)
   local base,e,n,j;
   global `metic/forbid`;
   `metic/forbid`:= {};
   e:=collect(`metic/expand`(expr,base),base);
   n:= degree(e,base);
   [seq(coeff(e,base,j), j=0..n)]
   end;
`metic/expand`:= proc(expr,b)
  local L,n,j;
  global `metic/forbid`;
  if type(expr,{`+`,`*`,`^`}) then map(`metic/expand`,expr,b)
  elif type(expr,equation) then
    map(`metic/expand`,lhs(expr)-rhs(expr),b)
  elif type(expr,name) then
    `metic/forbid`:= `metic/forbid` union {substring(expr,1..1)};
    n:= length(expr);
    add(b^(n-j)*substring(expr,j..j),j=1..n);
  else expr
  fi
  end;
`metic/solve`:= proc(L,sofar,freedigs)
   local first,vars,n,nl,p,z,sub,v;
   global `metic/forbid`;
    first:= L[1];
    nl:= nops(L);
    vars:= convert(indets(first),list);
    n:= nops(vars);
    for p in combinat[permute](freedigs,n) do
      if not(member(0,p,'z') and
           member(vars[z],`metic/forbid`)) then
        sub:= zip((x,y)->(x=y),vars,p);
        v:= subs(sub,first);
        if v mod 10 = 0 then
          if nl=1 then
            if v = 0 then
             print([op(sub),op(sofar)])
            fi
          else
          `metic/solve`(subs(sub,L[2..nl])+[v/10,0$nl-2],
             [op(sub),op(sofar)],
             freedigs minus convert(p,set));
          fi
        fi
      fi
   od
   end;
-------------------------
For your system:

> alphametics([ABCD+EFGH = KLBK, LL+EFFC=EFDL, EGA*AH=DGFG]);

[E = 1, A = 3, L = 2, F = 4, G = 7, C = 0, B = 8, D = 6, H = 9, K = 5]

Robert Israel                                israel@math.ubc.ca
Department of Mathematics        http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2