{ 
  This is an old arithmetic problem given in the book of puzzles by
                      Professor F. Schuh

  The problem is solved by asking the query

                  all Schuh()     

  Replace the 20 dots by digits (each digit is used exactly twice)
  so the following holds:

                ...                            a
              x ...                          x b
                ---                            -
                ...                           r3
               ...                           r2
              ...                           r1
              -----                         ----
              .....                            c

  The variables on the right refer to the names used in the solution.

  It would seem that the problem should be solved by using the long integer
  (L) constraints but because of the multiplication the problem involves
  non-linear constraints. Another difficulty is how to express the fact
  that each digit should occur exactly twice.

  As it happens the straightforward backtracking gives the simplest
  solution. The input/output variable "dig:.Digits" is used to keep
  the track of how many times each digit has been used sofar. The
  predicate "Dig(digs,d)" checks whether the digit d was used at most
  twice. Note the use of Dig in the body of Schuh1 where it is used to
  generate the digits into implicitly declared output variables ah,at,au.

  Incidentally, the solution is:

        179
      x 224
        ---
        716
       358
      358
      -----
      40096     

}
  
local Nl :<S = '\n'
local Digit = [0..9]
local Digits = Digit->I                     // for counting used digits

local Num3 = h:Digit,t:Digit,u:Digit        // 3 digit number htu

pred Schuh() iff
    Schuh1(a,b,r3,r2,r1,c) &                // solve the problem
    Print('        ',a,Nl) &                // print it nicely
    Print('      x ',b,Nl) &
    Print('        ','---',Nl) &
    Print('        ',r3,Nl) &
    Print('       ',r2,Nl) &
    Print('      ',r1,Nl) &
    Print('      ','-----',Nl) &
    Print('      ',c)                           
 
// a * b = c        with r3, r2, r1 as the intermediate results
local pred Schuh1(aa:>I,bb:>I,rr3:>I,rr2:>I,rr1:>I,c:>I) iff
    digs:.Digits & digs := [0,0,0,0,0,0,0,0,0,0] &     // used digit counter
    Dig(digs,ah) & Dig(digs,at) & Dig(digs,au) & 
    a = (ah,at,au):Num3 &                   // generate a
    Mult(digs,a,bu,r3) &                    // a * bu = r3 
    Mult(digs,a,bt,r2) &                    // a * bt = r2
    Mult(digs,a,bh,r1) &                    // a * bh = r1
    Add(digs,r3,r2,r1,c) &                  // r3+10*r2+100*r1 = c 
    aa = 100*a.h + 10*a.t + a.u &
    bb = 100*bh + 10*bt + bu &
    rr1 = 100*r1.h + 10*r1.t + r1.u &
    rr2 = 100*r2.h + 10*r2.t + r2.u &
    rr3 = 100*r3.h + 10*r3.t + r3.u

// d used at most twice in digs 
local pred Dig(digs:.Digits,d:<Digit) iff      
    digs(d) < 2 & digs(d) := digs(d) + 1

// a * d = r  
local pred Mult(digs:.Digits,a:<Num3,d:>Digit,r:>Num3) iff 
    Dig(digs,d) &   
    ku = a.u * d &         ru = ku mod 10 & Dig(digs,ru) &
    kt = a.t * d + ku/10 & rt = kt mod 10 & Dig(digs,rt) &  
    rh = a.h * d + kt/10 &                  Dig(digs,rh) & 
    r = rh,rt,ru

// r3+10*r2+100*r3 = s 
local pred Add(digs:.Digits,r3:<Num3,r2:<Num3,r1:<Num3,s:>I) iff 
    s5 = r3.u &                                        Dig(digs,s5) &
    k4 = r3.t + r2.u &                s4 = k4 mod 10 & Dig(digs,s4) &
    k3 = r3.h + r2.t + r1.u + k4/10 & s3 = k3 mod 10 & Dig(digs,s3) &
    k2 = r2.h + r1.t + k3/10 &        s2 = k2 mod 10 & Dig(digs,s2) &
    s1 = r1.h + k2/10 &                                Dig(digs,s1) &
    s = 10000*s1 + 1000*s2 + 100*s3 + 10*s4 + s5    
                                                

This page was created by F1toHTML