######################################################################
##GILAD: Save this file as  GILAD                                    #
## To use it, stay in the                                            #
##same directory, get into Maple (by typing: maple <Enter> )         #
##and then type:  read GILAD<Enter>                                  #
##Then follow the instructions given there                           #
##                                                                   #
##Written by Doron Zeilberger, Rutgers University ,                  #
#zeilberg at math dot rutgers dot edu                                #
######################################################################
 
#Created: 
 
print(`Created:  June 14,  2015`):
print(`This version: Jan. 1, 2016: to enter as example for SolveP, SolvePP, and SolvePPP the Jan. 1, 2016 puzzle`):
print(` This is GILAD `):
print(`A Maple package for posing and solving Multiplication problems with X's `):
print(`that sometimes appear on Fridays in the Israeli newspaper Yediot aharanot and`):
print(`some puzzle magazines, where one has to resconstruct a long multiplaction problem`):
print(`where all the occurrences of the same one digit (that has to be determined) is`):
print(`indicated by X, and the remaining slots by a blank`):
print(`written by Doron Zeilberger`):
print(``):
print(`Please report bugs to zeilberg at math dot rutgers dot edu`):
print(``):
 print(`The most current version of this  package and paper`):
 print(` are  available from`):
 print(`http://www.math.rutgers.edu/~zeilberg/  .`):

print(`---------------------------------------`):
 print(`For a list of the Supporting procedures type ezra1();, for help with`):
 print(`a specific procedure, type ezra(procedure_name);   .`):
 print(``):
print(`---------------------------------------`):

print(`---------------------------------------`):
 print(`For a list of the MAIN procedures type ezra();, for help with`):
 print(`a specific procedure, type ezra(procedure_name);   .`):
 print(``):
print(`---------------------------------------`):

with(combinat):
with(numtheory):

ezra1:=proc()

if args=NULL then
 print(` The supporting procedures are: CarP, FillIn, FillIn1, GoodFactors, HayStack, HayStack1 `):
 print(` HayStack1a, LtoN, Matim1, Matim, Mumadim, Mumadim1, NtoL `):
 print(``):

else
ezra(args):
fi:

end:

ezra:=proc()

if args=NULL then
 print(`The main procedures are: DrP, DrS, LongM, MakePuzzle, PtorP, SolveP, SolvePP, SolvePPP `):
 print(` `):


elif nops([args])=1 and op(1,[args])=CarP then
print(`CarP(L): the Cartesian product of the list of sets in L. Try:`):
print(`CarP([{1,2},{2,4},{4}]);`):

elif nops([args])=1 and op(1,[args])=DrP then
print(`DrP(P,B): inputs, P, a puzzle of 3-digit by 3-digit puzzles in base 10, draws it nicely. Try`):
print(`DrP([[B,B,B],[B,B,B],[B,B,X],[B,B,B],[X,B,X],[B,B,B,B,X]],B);`):


elif nops([args])=1 and op(1,[args])=DrS then
print(`DrS(S): inputs a solution of a puzzle of 3-digit by 3-digit puzzles in base 10, draws it nicely. Try`):
print(`DrS([246,675,5]);`):


elif nops([args])=1 and op(1,[args])=FillIn then
print(`FillIn(L,B,X,d): inputs a list L of B's and  X's and outputs  the set of pairs [FillInL,i] where`):
print(`i is the value of X. Try:`):
print(`FillIn([B,B,X],B,X,10);`):

elif nops([args])=1 and op(1,[args])=FillIn1 then
print(`FillIn1(L,B,i,d): inputs a list L of i's (i aan integer from 0 to d-1)`):
print(`and base d, the set of pairs [FillInL] where Bcan be anything except i`):
print(` Try: `):
print(` FillIn1([B,B,5],B,5,10); `):


elif nops([args])=1 and op(1,[args])=HayStack then
print(`HayStack(P,B,X,d): inputs a puzzle P phrased in terms of B (blank) and X, in base d`):
print(`outputs the set of candidates for the top and bottm and for the X.`):
print(` Try: `):
print(`HayStack([[B,B,B],[B,B,B],[B,B,X],[B,B,B],[X,B,X],[B,B,B,B,X]],B,X,10);`):

elif nops([args])=1 and op(1,[args])=HayStack1 then
print(`HayStack1(P,B,X,d): inputs a puzzle P phrased in terms of B (blank) and X, in base d`):
print(`outputs the set of candidates for the top and for the X.`):
print(`Try: `):
print(`HayStack1([[B,B,B],[B,B,B],[B,B,X],[B,B,B],[X,B,X],[B,B,B,B,X]],B,X,10); `):

elif nops([args])=1 and op(1,[args])=HayStack1a then
print(`HayStack1a(L1,L2,B,X,d): inputs a lists  L1 and L2 of B's and X's such that L2 is a multiple of L1`):
print(`finds all the possibilities in base d The outputs is the set of pairs [m,q,i] where L1 is the base-d`):
print(`representation of m, q is the quotient L2/L1 and X=i. Try:`):
print(`HayStack1a([B,B,X],[B,X,B,B],B,X,10);`):


elif nops([args])=1 and op(1,[args])=GoodFactors then
print(`GoodFactors(N,d,k1,k2): inputs a positive integer N and outputs all pairs`):
print(`[a,b] such that N=a*b and a and b are k1-digit and k2-digits integers in base d`):
print(`Try:`):
print(`GoodFactors(345*842,10,3,3);`):

elif nops([args])=1 and op(1,[args])=LongM then
print(`LongM(m,n,d): inputs positive integers m and n, an integer d>=2, presents the long-multiplication of m by n. Try:`):
print(`LongM(243,357,10);`):

elif nops([args])=1 and op(1,[args])=LtoN then
print(`LtoN(L,d): inputs a list in base d to an integer. Try:`):
print(`LtoN([1,0,1],10);`):


elif nops([args])=1 and op(1,[args])=MakePuzzle then
print(`MakePuzzle(m,n,i,B,X,d): inputs positive integers m and n, an integer d>=2, letters B and X, and a digit i (between 0 and d-1)`):
print(`makes a multiplication puzzle where the digit i is replaced by an X and all the other digits are replaced by B. Try:`):
print(`MakePuzzle(243,357,4,B,X,10);`):

elif nops([args])=1 and op(1,[args])=Matim then
print(`Matim(L,B,X,i,L1): inputs a puzzle L phrased in terms of B and X, and a proposed solved one, decides`):
print(`whether L1 is indeed a solution where X is i. Try:`):
print(` Matim(MakePuzzle(23,35,3,B,X,10),B,X,3,LongM(23,35,10)); `):

elif nops([args])=1 and op(1,[args])=Matim1 then
print(`Matim1(L1,L2,B,X,i): Is the list L1 of B's and X's  compatible with the list of integers L2`):
print(`such that when there is an X it is i`):
print(`and when there is a B it is not i?, Try: `):
print(`Matim1([B,X,B,X],[3,2,3,2],B,X,2); `):



elif nops([args])=1 and op(1,[args])=Mumadim then
print(`Mumadim(n,i,P,B,X,d): inputs an integer n that is a candidate for the top`):
print(`and a candidate for i (the value of X), and a puzzle P`):
print(`phrased in terms of B,X, outputs the list of length nops(P)-3 (alias nops(P[2]))`):
print(`for the feasible values of the second row.`):
print(`make it compatible with L2 such that n times 1 is L2 and X is i. Try:`):
print(`Mumadim(337,5,MakePuzzle(337,564,5,B,X,10),B,X,10);`):

elif nops([args])=1 and op(1,[args])=Mumadim1 then
print(`Mumadim1(n,i,L2,B,X,d): inputs an integer n that is a candidate for the top`):
print(`and a candidate i, and a list L2 in B,X, outputs the list of q's that would`):
print(`make it compatible with L2 such that n times 1 is L2 and X is i. Try:`):
print(`Mumadim1(335,5,[B,X,B,B],B,X,10);`):

elif nops([args])=1 and op(1,[args])=NtoL then
print(`NtoL(n,d): inputs a positive integer n, and outputs it as a list in base d. Try:`):
print(`NtoL(101,10);`):


elif nops([args])=1 and op(1,[args])=PtorP then
print(`PtorP(P,B,X,d): inputs a puzzle P phrased in terms of B and X, and in base d outputs all solutions`):
print(`using the factorization method. Try:`):
print(`PtorP([[B,X,B],[B,B,B],[B,B,B,B],[B,B,B,B],[B,B,B,B],[X,B,X,B,X,B]],B,X,10);`):

print(``):
print(`For Gilad Harshoshanim's Yediot puzzle #2357 (Jan. 1, 2016) try`):
print(` PtorP([[B,B,B],[B,B,X],[B,B,B,B],[B,X,B,B],[B,B,B,B],[X,B,B,B,X,B]],B,X,10); `):

elif nops([args])=1 and op(1,[args])=SolveP then
print(`SolveP(P,B,X,d): inputs a puzzle P phrased in terms of B and X, and in base d outputs all solutions. Try:`):
print(`SolveP(MakePuzzle(34,57,4,B,X,10),B,X,10);`):
print(``):

print(`For Gilad Harshoshanim's Yediot puzzle #2323 try`):
print(`SolveP([[B,B,X],[B,B,B],[B,B,B,B],[B,B,B,B],[B,X,B,B],[B,X,B,B,B,B]],B,X,10);`):
print(``):
print(`For Gilad Harshoshanim's Yediot puzzle #2328 try`):
print(`SolveP([[B,B,B],[B,B,B],[B,B,X],[B,B,B],[X,B,X],[B,B,B,B,X]],B,X,10);`):

print(``):
print(`For Gilad Harshoshanim's Yediot puzzle #2613 try`):
print(`SolveP([[B,X,B],[B,B,B],[B,B,B,B],[B,B,B,B],[B,B,B,B],[X,B,X,B,X,B]],B,X,10);`):


print(``):
print(`For Gilad Harshoshanim's Yediot puzzle #2450 try`):
print(`SolveP([[B,B,X],[B,B,B],[B,X,B,B],[B,B,X,B],[B,B,B,X],[B,B,B,B,B,B]],B,X,10);`):


print(``):
print(`For Gilad Harshoshanim's Yediot puzzle #2357 (Jan. 1, 2016) try`):
print(` SolveP([[B,B,B],[B,B,X],[B,B,B,B],[B,X,B,B],[B,B,B,B],[X,B,B,B,X,B]],B,X,10); `):




elif nops([args])=1 and op(1,[args])=SolvePP then
print(`SolvePP(P,B,X,d): Like  SolveP(P,B,X,d) but also returns digits that do not participate`):

print(`For Gilad Harshoshanim's Yediot puzzle #2323 try`):
print(`SolvePP([[B,B,X],[B,B,B],[B,B,B,B],[B,B,B,B],[B,X,B,B],[B,X,B,B,B,B]],B,X,10);`):
print(``):
print(`For Gilad Harshoshanim's Yediot puzzle #2328 try`):
print(`SolvePP([[B,B,B],[B,B,B],[B,B,X],[B,B,B],[X,B,X],[B,B,B,B,X]],B,X,10);`):

print(``):
print(`For Gilad Harshoshanim's Yediot puzzle #2613 try`):
print(`SolvePP([[B,X,B],[B,B,B],[B,B,B,B],[B,B,B,B],[B,B,B,B],[X,B,X,B,X,B]],B,X,10);`):


print(``):
print(`For Gilad Harshoshanim's Yediot puzzle #2450 try`):
print(`SolvePP([[B,B,X],[B,B,B],[B,X,B,B],[B,B,X,B],[B,B,B,X],[B,B,B,B,B,B]],B,X,10);`):

print(``):
print(`For Gilad Harshoshanim's Yediot puzzle #2357 (Jan. 1, 2016) try`):
print(` SolvePP([[B,B,B],[B,B,X],[B,B,B,B],[B,X,B,B],[B,B,B,B],[X,B,B,B,X,B]],B,X,10); `):


elif nops([args])=1 and op(1,[args])=SolvePPP then
print(`SolvePPP(P,B,X,d): Like  SolvePP(P,B,X,d) but with the extra condition that exacly d-1 digits participate`):
print(`it also returns the digit that does not participate.`):


print(``):
print(`For Gilad Harshoshanim's Yediot puzzle #2576 (Jan. 1, 2016) try`):
print(` SolvePPP([[B,B,B],[B,B,X],[B,B,B,B],[B,X,B,B],[B,B,B,B],[X,B,B,B,X,B]],B,X,10); `):


print(`For Gilad Harshoshanim's Yediot puzzle #2323 try`):
print(`SolvePPP([[B,B,X],[B,B,B],[B,B,B,B],[B,B,B,B],[B,X,B,B],[B,X,B,B,B,B]],B,X,10);`):
print(``):
print(`For Gilad Harshoshanim's Yediot puzzle #2328 try`):
print(`SolvePPP([[B,B,B],[B,B,B],[B,B,X],[B,B,B],[X,B,X],[B,B,B,B,X]],B,X,10);`):

print(``):
print(`For Gilad Harshoshanim's Yediot puzzle #2613 try`):
print(`SolvePPP([[B,X,B],[B,B,B],[B,B,B,B],[B,B,B,B],[B,B,B,B],[X,B,X,B,X,B]],B,X,10);`):


print(``):
print(`For Gilad Harshoshanim's Yediot puzzle #2450 try`):
print(`SolvePPP([[B,B,X],[B,B,B],[B,X,B,B],[B,B,X,B],[B,B,B,X],[B,B,B,B,B,B]],B,X,10);`):

print(``):
print(`For Gilad Harshoshanim's Yediot puzzle #2357 (Jan. 1, 2016) try`):
print(` SolvePPP([[B,B,B],[B,B,X],[B,B,B,B],[B,X,B,B],[B,B,B,B],[X,B,B,B,X,B]],B,X,10); `):


else
print(`There is no ezra for`,args):
fi:
 
end:


#NtoL(n,d): inputs a positive integer n, and outputs it as a list in base d. Try:
#NtoL(101,10);
NtoL:=proc(n,d) local L,n1,i1:
option remember:
if (n<0 or d<2) then
 RETURN(FAIL):
fi:

if n=0 then
   RETURN([]):
fi:

i1:=n mod d:

n1:=(n-i1)/d:
L:=NtoL(n1,d):
[op(L),i1]:
end:

#LtoN(L,d): converts the list of integers L in base d to an integer
LtoN:=proc(L,d) local i,k:
k:=nops(L)-1:
add(L[nops(L)-i]*d^i,i=0..k):
end:



#LongM(m,n,d): inputs positive integers m and n, an integer d>=2, presents the long-multiplication of m by n. Try:
#LongM(243,357,10,B,X,4);
LongM:=proc(m,n,d) local L,L1,L2,j,L3:
if not (type(m,integer) and  type(n,integer) and type(d,integer) and m>0 and n>0 and d>1) then
 RETURN(FAIL):
fi:

L1:=NtoL(m,d):
L2:=NtoL(n,d):

L:=[L1,L2]:

for j from nops(L2) by -1 to 1 do
 L3:=NtoL(m*L2[j],d):
 L:=[op(L),L3]:
od:
L3:=NtoL(m*n,d):
[op(L),L3]:
end:


#MakePuzzle(m,n,i,B,X,d): inputs positive integers m and n, an integer d>=2, letters B and X, and a digit i (between 0 and d-1)
#makes a multiplication puzzle where the digit i is replaced by an X and all the other digits are replaced by B. Try:
#MakePuzzle(243,357,4,B,X,10);
MakePuzzle:=proc(m,n,i,B,X,d) local L,i1,i2,L1,L1a:
if not (type(m,integer) and  type(n,integer) and type(d,integer) and m>0 and n>0 and d>1 and type(i,integer) and i>=0 and i<d) then
 RETURN(FAIL):
fi:

L:=LongM(m,n,d):

L1:=[]:

for i1 from 1 to nops(L) do
L1a:=[]:
for i2 from 1 to nops(L[i1]) do
 if L[i1][i2]=i then
  L1a:=[op(L1a),X]:
 else
   L1a:=[op(L1a),B]:
 fi:
od:
L1:=[op(L1),L1a]:
od:
L1:
end:




#Matim(L,B,X,i,L1): inputs a puzzle L phrased in terms of B and X, and a proposed solved one, decides
#whether L1 is indeed a solution where X is i. Try:
#Matim(MakePuzzle(23,35,3,B,X,10),B,X,3,LongM(23,35,10));
Matim:=proc(L,B,X,i,L1) local i1,i2:

if nops(L)<>nops(L1) then
 RETURN(false):
fi:

if {seq(nops(L[i1])-nops(L1[i1]),i1=1..nops(L))}<>{0} then
  RETURN(false):
fi:

for i1 from 1 to nops(L) do
 for i2 from 1 to nops(L[i1]) do

   if L[i1][i2]=X  then

      if L1[i1][i2]<>i then
       RETURN(false):
      fi:

  elif L[i1][i2]=B  then
     if L1[i1][i2]=i  then
      RETURN(false):
     fi:

   else
     RETURN(FAIL):
  fi:
od:
od:
true:
end:




#SolvePslow(P,B,X,d): inputs a puzzle P phrased in terms of B and X, and in base d outputs all solutions. Try:
#SolveP(MakePuzzle(34,57,4,B,X,10),B,X,10);
SolvePslow:=proc(L,B,X,d) local gu,m,n,L1,i:

gu:={}:

for m from d^(nops(L[1])-1) to d^nops(L[1])-1 do


 for n from d^(nops(L[2])-1) to d^nops(L[2])-1 do



    L1:=LongM(m,n,d):
 


      for i from 0 to d-1 do



      if Matim(L,B,X,i,L1) then
       gu:=gu union {[m,n,i]}:
      fi:

     od:

 od:
od:

gu:

end:




#FillIn1(L,B,i,d): inputs a list L of i's (i aan integer from 0 to d-1)
#and base d, the set of pairs [FillInL] where Bcan be anything except i
#Try:
#FillIn1([B,B,5],5,10);
FillIn1:=proc(L,B,i,d) local mu,j,k:

if L=[] then
   RETURN({[]}):
fi:

if not member(B,{op(L)}) then
    RETURN({L}):
fi:

mu:={seq(j,j=0..d-1)} minus {i}:



for j from 1 to nops(L) while L[j]<>B do od:

{seq(op(FillIn1([op(1..j-1,L),k,op(j+1..nops(L),L)],B,i,d)),k in mu)}:

end:





#FillIn(L,B,X,d): inputs a list L of B's and  X's and outputs  the set of pairs [FillInL,i] where
#i is the value of X. Try:
#FillIn([B,B,X],B,X,10);
FillIn:=proc(L,B,X,d) local L1,gu,gu1,gu11,i:

gu:={}:

for i from 0 to d-1 do
L1:=subs(X=i,L):
gu1:=FillIn1(L1,B,i,d):
gu:=gu union {seq([gu11,i],gu11 in gu1)}:
od:
gu:


end:

#Matim1(L1,L2,B,X,i): Is the list L1 of B's and X's  compatible with the list of integers L2
#such that when there is an X it is i
#and when there is a B it is not i?, Try:
#Matim1([B,X,B,X],[3,2,3,2],B,X,2);
Matim1:=proc(L1,L2,B,X,i) local j:

if nops(L1)<>nops(L2) then
   RETURN(false):
fi:

for j from 1 to nops(L1) do
 if L1[j]=B then
     if L2[j]=i then
          RETURN(false):
     fi:
 elif L1[j]=X then
     if L2[j]<>i then
          RETURN(false):
     fi:
 else
   RETURN(FAIL):
 fi:
od:
true:
end:

#HayStack1a(L1,L2,B,X,d): inputs a lists  L1 and L2 of B's and X's such that L2 is a multiple of L1
#finds all the possibilities in base d The outputs is the set of pairs [m,q,i] where L1 is the base-d
#representation of m, q is the quotient L2/L1 and X=i. Try:
#HayStack1a([B,B,X],[B,X,B,B],B,X,10);

HayStack1a:=proc(L1,L2,B,X,d) local gu,q,lu,mu,mu1:
mu:=FillIn(L1,B,X,d):

gu:={}:

for mu1 in mu do
 for q from 0 to d-1 do
   lu:=NtoL(LtoN(mu1[1],d)*q,d):
    if Matim1(L2,lu,B,X,mu1[2]) then
      gu:=gu union {[LtoN(mu1[1],d),q,mu1[2]]}:
    fi:
 od:
od:
gu:

end:



#Mumadim1(n,i,L2,B,X,d): inputs an integer n that is a candidate for the top
#and a candidate i, and a list L2 in B,X, outputs the list of q's that would
#make it compatible with L2 such that n times 1 is L2 and X is i. Try:
#Mumadim1(335,5,[B,X,B,B],B,X,10);
Mumadim1:=proc(n,i,L2,B,X,d) local gu,q,lu:

gu:={}:

 for q from 0 to d-1 do
   lu:=NtoL(n*q,d):
    if Matim1(L2,lu,B,X,i) then
      gu:=gu union {q}:
    fi:
 od:

gu:

end:



#HayStack1(P,B,X,d): inputs a puzzle P phrased in terms of B (blank) and X, in base d
#outputs the set of candidates for the top and for the X.
#Try:
#HayStack1([[B,B,B],[B,B,B],[B,B,X],[B,B,B],[X,B,X],[B,B,B,B,X],B,X,10);
HayStack1:=proc(P,B,X,d) local k,mu,mu1,lu,lu1,i,K:

mu:={seq(k,k=d^(nops(P[1])-1)+1..d^nops(P[1])-1)}:
mu:={seq(seq([mu1,k],k=0..d-1),mu1 in mu)}:

K:={}:
for i from 3 to nops(P)-1 do
 if member(X,{op(P[1])}) or member(X,{op(P[i])}) then
   K:=K union {i}:
  lu:=HayStack1a(P[1],P[i],B,X,d):
  lu:={seq([lu1[1],lu1[3]],lu1 in lu)}:
  mu:=mu intersect lu:
 fi:
od:

mu:


end:



#Mumadim(n,i,P,B,X,d): inputs an integer n that is a candidate for the top
#and a candidate for i (the value of X), and a puzzle P
#phrased in terms of B,X, outputs the list of length nops(P)-3 (alias nops(P[2]))
#for the feasible values of the second row.
#make it compatible with L2 such that n times 1 is L2 and X is i. Try:
#Mumadim(337,5,MakePuzzle(337,564,5,B,X,10),B,X,10);
Mumadim:=proc(n,i,P,B,X,d) local j:
#[seq(Mumadim1(n,i,P[j],B,X,d),j=3..nops(P)-1)]:
[seq(Mumadim1(n,i,P[nops(P)-j],B,X,d),j=1..nops(P[2]))]:
end:


#CarP(L): the Cartesian product of the list of sets in L. Try:
#CarP([{1,2},{2,4},{4}]);
CarP:=proc(L) local i, L1,gu,gu1,a:

if L=[] then
 RETURN({[]}):
fi:

if nops(L)=1 then
 RETURN({seq([L[1][i]],i=1..nops(L[1]))}):
fi:

L1:=[op(1..nops(L)-1,L)]:

gu:=CarP(L1):

{seq(seq([op(gu1),a],a in L[nops(L)]),gu1 in gu)}:

end:



#HayStack1(P,B,X,d): inputs a puzzle P phrased in terms of B (blank) and X, in base d
#outputs the set of candidates for the top and for the X.
#Try:
#HayStack1([[B,B,B],[B,B,B],[B,B,X],[B,B,B],[X,B,X],[B,B,B,B,X],B,X,10);
HayStack1:=proc(P,B,X,d) local k,mu,mu1,lu,lu1,i,K:

mu:={seq(k,k=d^(nops(P[1])-1)+1..d^nops(P[1])-1)}:
mu:={seq(seq([mu1,k],k=0..d-1),mu1 in mu)}:

K:={}:
for i from 3 to nops(P)-1 do
 if member(X,{op(P[1])}) or member(X,{op(P[i])}) then
   K:=K union {i}:
  lu:=HayStack1a(P[1],P[i],B,X,d):
  lu:={seq([lu1[1],lu1[3]],lu1 in lu)}:
  mu:=mu intersect lu:
 fi:
od:

mu:


end:


#HayStack(P,B,X,d): inputs a puzzle P phrased in terms of B (blank) and X, in base d
#outputs the set of candidates for the top and bottm and for the X.
#Try:
#HayStack([[B,B,B],[B,B,B],[B,B,X],[B,B,B],[X,B,X],[B,B,B,B,X]],B,X,10);
HayStack:=proc(P,B,X,d) local k,mu,mu1,lu,lu1,i,K,gu:

mu:={seq(k,k=d^(nops(P[1])-1)+1..d^nops(P[1])-1)}:
mu:={seq(seq([mu1,k],k=0..d-1),mu1 in mu)}:

K:={}:
for i from 3 to nops(P)-1 do
 if member(X,{op(P[1])}) or member(X,{op(P[i])}) then
   K:=K union {i}:
  lu:=HayStack1a(P[1],P[i],B,X,d):
  lu:={seq([lu1[1],lu1[3]],lu1 in lu)}:
  mu:=mu intersect lu:
 fi:
od:

gu:={}:

for mu1 in mu do

 lu:=CarP(Mumadim(op(mu1),P,B,X,d)):

    for lu1 in lu do

     if Matim1(P[2],lu1,B,X,mu1[2]) then
    gu:=gu union {[mu1[1],LtoN(lu1,d),mu1[2]]}:
   fi:
  od:
od:    


gu:

end:




#SolveP(P,B,X,d): inputs a puzzle P phrased in terms of B and X, and in base d outputs all solutions. Try:
#SolveP(MakePuzzle(34,57,10,B,X,4),B,X,10);
SolveP:=proc(L,B,X,d) local i1,lu,lu1,gu,L1,z,Lsof:
option remember:
Lsof:=L[nops(L)]:

if d^coeff(add(z[Lsof[i1]],i1=1..nops(Lsof)),B,1)<=10^4 then
 RETURN(PtorP(L,B,X,d)):
fi:


lu:=HayStack(L,B,X,d):


gu:={}:

 for lu1 in lu do


    L1:=LongM(lu1[1],lu1[2],d):

      if Matim(L,B,X,lu1[3],L1) then
       gu:=gu union {lu1}:
      fi:

  od:
gu:

end:





#SolvePP(P,B,X,d): inputs a puzzle P phrased in terms of B and X, and in base d outputs all solutions. 
#It also returns the set of digits that
#do not participate.
#Try:
#SolvePP(MakePuzzle(134,447,10,B,X,4),B,X,10);
SolvePP:=proc(L,B,X,d) local lu,lu1,mu1, gu, i1:
option remember:
lu:=SolveP(L,B,X,d):

gu:={}:


for lu1 in lu do
 mu1:={seq(i1,i1=0..d-1)} minus convert(ListTools[Flatten](LongM(lu1[1],lu1[2],d)),set):
 gu:=gu union {[lu1,mu1]}:
od:

gu:

end:


#SolvePPP(P,B,X,d): inputs a puzzle P phrased in terms of B and X, with the extra condition that
#exactly d-1 digits participate,
#and in base d outputs all solutions. 
#It also returns the digit that
#does not participate.
#Try:
#SolvePPP(MakePuzzle(134,447,10,B,X,4),B,X,10);
SolvePPP:=proc(L,B,X,d) local lu,lu1, gu:
option remember:
lu:=SolvePP(L,B,X,d):

gu:={}:


for lu1 in lu do
 if nops(lu1[2])=1 then
   gu:=gu union {[lu1[1],lu1[2]]}:
 fi:
od:

gu:


end:



#GoodFactors(N,d,k1,k2): inputs a positive integer N and outputs all pairs
#[a,b] such that N=a*b and a and b are k1-digit and k2-digits integers in base d
#Try:
#GoodFactors(345*842,10,3,3);
GoodFactors:=proc(N,d,k1,k2) local gu,a,b,lu:
gu:=divisors(N):

lu:={}:

for a in gu do

 if a>=d^(k1-1) and a<d^k1 then
    b:=N/a:
  if b>=d^(k2-1) and b<d^k2 then
    lu:=lu union {[a,b]}:
  fi:
 fi:

od:

lu:

end:



#PtorP(P,B,X,d): inputs a puzzle P phrased in terms of B and X, and in base d outputs all solutions
#using the factorization method. Try:
#PtorP([[B,X,B],[B,B,B],[B,B,B,B],[B,B,B,B],[B,B,B,B],[X,B,X,B,X,B]],B,X,10);`):
PtorP:=proc(L,B,X,d) local lu,lu1,gu,gu1,gu11,L1,k1,k2:

k1:=nops(L[1]):
k2:=nops(L[2]):

lu:=FillIn(L[nops(L)],B,X,d):

gu:={}:



gu:={}:

 for lu1 in lu do


 gu1:=GoodFactors(LtoN(lu1[1],d),d,k1,k2):

  for gu11 in gu1 do

    L1:=LongM(gu11[1],gu11[2],d):

      if Matim(L,B,X,lu1[2],L1) then
       gu:=gu union {[gu11[1],gu11[2],lu1[2]]}:
      fi:

  od:
od:

gu:

end:









SO1:=proc(L,B) local i,gu:

if L[1]=B then
 gu:=`_ `:
else
 gu:=cat(L[1],` `):
fi:

for i from 2 to nops(L) do
if L[i]=B then
 gu:=cat(gu,`_ `):
else
 gu:=cat(gu,L[i],` `):
fi:
od:
gu:

end:


#MulToList(S): multiplying a by b in base 10 outputs the lines of the long multiplcation.
#Try:
#MulToList([345,563,3]);
MulToList:=proc(S) local a,b,b1,gu,i:
a:=S[1]:
b:=S[2]:
b1:=NtoL(b,10):

gu:=[a,b]:

for i from  nops(b1) by -1 to 1 do
gu:=[op(gu),a*b1[i]]:
od:

[op(gu),a*b]:

end:

DrS:=proc(S) local P,gu,i:
P:=MulToList(S):
print(``):
printf("%10d",P[1]):
print(``):
printf("%10d",P[2]):
print(``):
printf("%10s",`________`):
print(``):
printf("%10d",P[3]):
print(``):
printf("%9d",P[4]):
print(``):
printf("%8d",P[5]):
print(``):
printf("%10s",`________`):
print(``):
printf("%10d",P[6]):
print(``):
print(``):

printf("%5s %1d",`X = `, S[3]):
print(``):
gu:=LongM(S[1],S[2],10):

gu:={seq(i,i=0..9)} minus  {seq(op(gu[i]),i=1..nops(gu))}:

if nops(gu)<>1 then
 RETURN(FAIL):
fi:

print(``):
printf("%20s %1d", `Missing digit : `, gu[1]):
print(``):
end:


DrPold:=proc(P)
printf("%10s",P[1]):
print(``):
printf("%10s",P[2]):
print(``):
printf("%10s",`________`):
print(``):
printf("%10s",P[3]):
print(``):
printf("%9s",P[4]):
print(``):
printf("%8s",P[5]):
print(``):
printf("%10s",`________`):
print(``):
printf("%10s",P[6]):


end:







DrP:=proc(P,B)
print(``):
printf("%20s",SO1(P[1],B)):
print(``):
printf("%20s",SO1(P[2],B)):
print(``):
printf("%20s",`________`):
print(``):
printf("%20s",SO1(P[3],B)):
print(``):
printf("%18s",SO1(P[4],B)):
print(``):
printf("%16s",SO1(P[5],B)):
print(``):
printf("%20s",`______________`):
print(``):
printf("%20s",SO1(P[6],B)):
print(``):
print(``):

end: