\datethis @*Intro. This program is designed to compose multiplication-skeleton puzzles of a type pioneered by Junya Take. For example, consider his puzzle for the lettter \.O, in {\sl Journal of Recreational Mathematics\/ \bf38} (2014), 132: \vcenter{\halign{\hfil\tt#\cr .......\cr \times\hfil......\cr \noalign{\medskip\hrule\medskip} ........\cr OO.....\ \cr ..O..O..\ \ \ \cr ...O..O.\ \ \ \ \cr ...O..O\ \ \ \ \ \cr \noalign{\medskip\hrule\medskip} ....OO......\cr}} Each occurrence of \.O' should be replaced by some digit~$d$, and each \..' should be replaced by a digit $\ne d$. (And no zero should be in a most significant position.) The solution is unique: \vcenter{\halign{\hfil\tt#\cr 2208068\cr \times\hfil357029\cr \noalign{\medskip\hrule\medskip} 19872612\cr 4416136\ \cr 15456476\ \ \ \cr 11040340\ \ \ \ \cr 6624204\ \ \ \ \ \cr \noalign{\medskip\hrule\medskip} 788344309972\cr}} But the purpose of this program is not to {\it solve\/} such a puzzle! The purpose of this program is to {\it invent\/} such a puzzle, namely to find integers $x$ and $y$ whose partial products and final product have digits that match a given binary pattern. The pattern is given in |stdin| as a set of lines, with asterisks marking the position of the special digit. For example, the \.O' shape in the puzzle above would be specified thus: \vcenter{\halign{\hfill\tt#\cr .**.\cr *..*\cr *..*\cr *..*\cr .**.\cr}} @ The examples above show that zeros in the multiplier will offset'' the shape in different ways. We try all possible offsets, for a given number $m$ of nonzero multiplier digits. A second parameter, $z$, specifies the maximum number of zeros in the multiplier. Both $m$ and $z$ are specified on the command line. @d maxdigs 22 /* size of the longest numbers considered, plus 2 */ @d maxdim 8 /* maximum size of pattern */ @d bufsize maxdim+5 @d maxm 8 /* |m| must be less than this */ @d o mems++ @d oo mems+=2 @c #include #include @; int m; /* the number of nonzero digits in the multiplier */ int z; /* the maximum number of zero digits in the multiplier */ int vbose; /* level of verbosity */ char buf[bufsize]; /* buffer used when inputting the shape */ char rawpat[maxdim][maxdim]; /* pixels of the raw pattern */ char last[maxdim]; /* positions of the rightmost asterisks */ int count; /* this many solutions found */ unsigned long long nodes; /* size of the backtrack trees, times 10 */ int unresolved; /* this many cases left unresolved */ unsigned long long mems; /* memory accesses */ @; @; main(int argc,char*argv[]) { register int d,i,ii,imax,j,jj,k,kk,l,lc,lj,n,t,tt,x,pos,maxl,printed; @; @; @; @; while (1) { @; for (d=0;d<10;d++) { if (vbose) fprintf(stderr," *=%d:\n", d); @; } @; } fprintf(stderr,"Altogether %d solutions, %lld nodes, %lld mems.\n", count,nodes/10,mems); if (unresolved) fprintf(stderr,"... %d cases were unresolved!\n", unresolved); } @ @= if (argc<3 || sscanf(argv[1],"%d", &m)!=1 || sscanf(argv[2],"%d", &z)!=1) { fprintf(stderr,"Usage: %s m z [verbose] [extraverbose] < foo.dots\n", argv[0]); exit(-1); } if (m<2 || m>=maxm) { fprintf(stderr,"m should be between 2 and %d, not %d!\n", maxm-1,m); exit(-2); } if (m+z>maxdigs-2) { fprintf(stderr,"m+z should be at most %d, not %d!\n", maxdigs-2,m+z); exit(-3); } vbose=argc-3; @ @= for (n=k=0;;n++) { if (!fgets(buf,bufsize,stdin)) break; if (n>=maxdim) { fprintf(stderr,"Recompile me: I allow at most %d lines of input!\n", maxdim); exit(-3); } @; } fprintf(stderr,"OK, I've got a pattern with %d rows and %d asterisks.\n", n,k); if (m= for (j=0;buf[j] && buf[j]!='\n';j++) { if (buf[j]=='*') { if (j>=maxdim) { fprintf(stderr,"Recompile me: I allow at most %d columns per row!\n", maxdim); exit(-5); } oo,rawpat[n][j]=1, k++, last[n]=j+1; } } @*Bignums. We implement elementary decimal addition on nonnegative integers. Each integer is represented by an array of bytes, in which the first byte specifies the number of significant digits, and the remaining bytes specify the digits themselves (right to left). @= typedef char bignum[maxdigs]; @ For example, it's easy to test equality of two such bignums, or to copy one to another. @= int isequal(bignum a,bignum b) { register int la=a[0],i; if (oo,la!=b[0]) return 0; for (i=1;i<=la;i++) if (oo,a[i]!=b[i]) return 0; return 1; } @# void copy(bignum a,bignum b) { register int lb=b[0],i; for (o,i=0;i<=lb;i++) oo,a[i]=b[i]; } @ Here's the basic routine. It's OK to have |a=b| or |b=c|. (But beware of |a=c|.) @= void add(bignum a,bignum b,bignum c,int p) { /* set $a=b+10^p c$ */ register int lb=b[0],lc=c[0],i,k,d; if (oo,lc==0) { copy(a,b); return; } for (i=1;i<=p && i<=lb;i++) oo,a[i]=b[i]; for (k=0;i<=lb || i<=lc+p || k;i++) { d=k+(i<=lb? o,b[i]:0)+(i<=lc+p && i>p? o,c[i-p]:0); if (d>=10) k=1,d-=10;@+else k=0; o,a[i]=d; } o,a[0]=i-1; if (i>=maxdigs) { fprintf(stderr,"Integer overflow, more than %d digits!\n", maxdigs-1); exit(-666); } if (a[a[0]]==0) fprintf(stderr,"why?\n"); } @ @= void print_bignum(bignum a) { register int i,la=a[0]; if (!la) fprintf(stderr,"0"); else for (i=la;i;i--) fprintf(stderr,"%d", a[i]); } @ We might as well have a primitive multiplication table. @= o,cnst[0][0]=0; for (k=1;k<10;k++) oo,cnst[k][0]=1,cnst[k][1]=k; for (;k<=81;k++) oo,o,cnst[k][0]=2,cnst[k][2]=k/10,cnst[k][1]=k%10; @ @= bignum cnst[82]; @*Offsets and constraints. The $k$th partial product, for $0\le k\le m$, will be shifted left by |off[k]|. (When $k=m$ this is the entire product, the sum of the shifted partials.) It inherits the constraints of row $k-(m+1-n)$ of the $n$-row pattern in |rawpat|. The data in |rawpat| appears left to right,'' but the constraints on digits are right to left.'' I mean, column~0 in |rawpat| refers to the most significant digit that is constrained. The constraints on a partial product $({}\ldots p_2p_1p_0)_{10}$ say that $p_i=d$ for certain~$i$, while $p_i\ne d$ for the others. We represent them as a bignum, with 1 in the |d|'' positions and 0~elsewhere. For example, the opening problem in the introduction has $m=5$, $z=1$, offsets (0, 1, 3, 4, 5), and constraints (0, 1100000, 100100, 10010, 1001, 11000000). We do not constrain the length of the multiplicand or the partial products; we simply require that any digits to the left of explicitly constrained positions must differ from~|d|. This produces multiple potential puzzles, some of which won't have unique solutions. @ @= for (i=0;i= for (i=m-1;i>0;i--) if (o,off[i]= for (i=pos=0;i<=m;i++) if (oo,off[m+1-n+i]+last[i]>pos) pos=off[m+1-n+i]+last[i]; pos+=slack-1; @ Sometimes two constraints are identical, and we'll want to know that fact. So we set up a table called |id|, where |id[j]=id[k]| if and only if $c_j=c_k$. @= for (k=ids=0;k<=m;k++) { o,i=k-(m+1-n), constr[k][0]=0; if (i>=0) { for (oo,j=pos-off[k]-last[i]+1;j>=0;j--) o,constr[k][j]=0; for (o,j=last[i]-1;j>=0;j--) { if (o,rawpat[i][j]) oo,o,constr[k][pos-off[k]-j+1]=1,constr[k][0]=pos-off[k]-j+1; else oo,constr[k][pos-off[k]-j+1]=0; } } for (j=k-1;j>=0;j--) if (oo,isequal(constr[j],constr[k])) break; if (j>=0) oo,id[k]=id[j];@+else o,id[k]=ids++; } @ @= char off[maxm]; /* blanks at right of partial products */ bignum constr[maxm]; /* the constraint patterns, decimalized */ char id[maxm]; /* equivalence class number for a given constraint */ char ids; /* how many classes are there? */ @ @= { @; @; if (vbose) { fprintf(stderr,"Constraints for offsets"); for (k=0;k<=m;k++) fprintf(stderr," %d", off[k]); fprintf(stderr,":"); for (k=0;k<=m;k++) { fprintf(stderr," "); print_bignum(constr[k]); } fprintf(stderr,".\n"); } } @*Backtracking. Let the multiplicand be $(a_l\ldots a_2a_1a_0)_{10}$. We proceed by trying all possibilities $\ne d$ for $a_0$, then all possibilities consistent with $a_0$ for $a_1$, and so on. The upper limit on~$l$ is $|maxdigs|-2-s_{m-1}$, because of our limit on the size of bignums; but I~doubt if we'll often get really big solutions. (If |slack>0|, we forbid $a_0=0$, because those solutions would have been obtained with lesser |slack|.) The basic ideas will become clear if we look more closely at the constraints and offsets of our running example, supposing for convenience that $d=1$. The multiplier is $(b_5b_4b_30b_1b_0)_{10}$, because of the given offsets. The partial products $(p_0,p_1,p_2,p_3,p_4,p_5)$ apply respectively to $b_0$, $b_1$, $b_3$, $b_4$, $b_5$, and the grand total. They are supposed to satisfy the constraints (0, 1100000, 100100, 10010, 1001, 11000000), as stated earlier. Suppose $a_0=3$. Then we must have $b_5=7$; that's the only way to have $p_4$ end with~1. And $b_5=7$ implies that $b_0$, $b_1$, $b_3$, $b_4$ can't be 7: All five constraints are different in this problem, hence no two $b$'s can be equal. Moving on, if $a_0=3$ we cannot have $a_1=3$. The reason is that the candidates for multiplier digits are 2 thru~9, and the values of $33k\bmod100$ for $2\le k\le 9$ are respectively (66, 99, 32, 65, 98, 31, 64, 97); none of those is suitable for the constraint 10010. If $a_0=3$ and $a_1=4$, we must have $b_5=7$ and $b_4=5$. Furthermore, $a_2=4$ will mess up the constraint 1001, because $443\times7=3101$. The values $a_2\in\{3,8,9\}$ are also impossible, because they yield no multiplier digits for the constraint 100100. Thus $a_2$ must be 0, 2, or~6. Proceeding in this way, we're able to rule out most of the potential trailing digits of the multiplicand before exploring very far. When we're choosing suitable values of $a_l$, we check the least significant $l$ digits of each constraint $c_k$ for $0\le k= b1: o,maxl=maxdigs-2-off[m-1]; l=0; @; b2: nodes+=10; if (vbose>1) { fprintf(stderr,"Level %d,", l); @; } if (l>=maxl) @; @; x=0; b3:@+if (slack && l==0 && x==0) goto b4; if (x==d) goto b4; if (vbose>2) fprintf(stderr," testing %d\n", x); @; o,a[l]=x; if (vbose>1) fprintf(stderr,"Trying a[%d]=%d\n", l,x); @q)@> @; l=l+1;@+goto b2; b4:@+if (x==9) goto b5; x=x+1;@+goto b3; b5:l=l-1; if (l>=0) { if (vbose>1) fprintf(stderr,"Back to level %d\n", l); o,x=a[l]; @; goto b4; } @ What data structures will support this computation nicely? First, there's an array of bignums: |ja[l][j]| contains$j$times the partial multiplier$(a_l\ldots a_0)_{10}$at a given level. Clearly |ja[l][j]| is |ja[l-1][j]| plus$j\cdot10^{\mkern1mul}a_l$. These entries are computed only for values of~|j| that are necessary; |stamp[l][j]| contains the node number at which they were most recently computed (actually it contains |nodes+x|). We also maintain arrays called |choice[k]|, which list the all nonzero multiplier digits that haven't been ruled out for constraint~|k|. Their sizes at level~|l| are |csize[l][k]|. Actually |choice[k]| is a permutation of$\{0,1,\ldots,9\}$, and |where[k]| is the inverse permutation; the viable elements at level~|l| are those$j$with |where[k][j]= bignum ja[maxdigs][10]; /* multiples of the multiplicand */ unsigned long long stamp[maxdigs][10]; /* when they were computed */ char choice[maxm][10], where[maxm][10]; /* available multipliers, ranked */ char csize[maxdigs][maxm]; /* current degree of viability */ char stack[maxm]; /* constraints that have become uniquely satisfied */ char stackptr; /* current size of |stack| */ char a[maxdigs]; /* the multiplicand */ bignum total; /* grand total when checking for a solution */ @ @= if (d==0 && off[m-1]>=m) goto b5; /* forbid zeros in multiplier if |d=0| */ for (i=0,j=1;j<10;j++) if (j!=d) { for (k=0;k= for (k=0;k= for (stackptr=0,k=m-1;k>=0;k--) @; while (stackptr) { o,k=stack[--stackptr]; if (vbose>2) fprintf(stderr," b%d must be %d\n", off[k],choice[k][0]); @; } for (o,t=csize[l+1][0],k=1;k; while (stackptr) { o,k=stack[--stackptr]; if (vbose>2) fprintf(stderr," b%d has to be %d\n", off[k],choice[k][0]); @; } } @ Now we've come to the heart and soul of the program. As we test each constraint, we also store some data that will be needed on level~|l+1| if we get there. @= { o,imax=csize[l][k]; /* how many multipliers worked in the previous level? */ for (i=0;i; if (vbose>2) fprintf(stderr," c%d loses option %d\n", k,j); if (--imax==0) goto b4; /* we've lost the last option */ if (i!=imax) oo,oo,oo,choice[k][i]=choice[k][imax],where[k][choice[k][imax]]=i--, choice[k][imax]=j,where[k][j]=imax; /* swap |j| into last position (for easy backtracking) */ jok: continue; } o,csize[l+1][k]=imax; if (imax==1 && (o,csize[l][k]!=1)) o,stack[stackptr++]=k; } @ We've previously verified constraint |k| in the least significant |l| digits, and those digits don't depend on$a_l$. Thus it suffices to do an `incremental'' test, looking only at digit~|l| of the constraint. @= if (o,stamp[l][j]!=nodes+x) { /* have we already updated |ja[l]|? */ o,stamp[l][j]=nodes+x; if (l==0) oo,copy(ja[0][j],cnst[x*j]); else oo,add(ja[l][j],ja[l-1][j],cnst[x*j],l); } oo,t=(ja[l][j][0]<=l? 0: ja[l][j][l+1]); o,tt=(constr[k][0]<=l? 0: o,constr[k][l+1]); if ((tt==1 && t==d) || (tt!=1 && t!=d)) goto jok; @ @= for (o,kk=0,j=choice[k][0];kk= if (x) printed=0; @ Downdating seems to be completely unnecessary, thanks largely to the |choice| and |csize| mechanism, and the fact that other data is recomputed at each level. @= @ @= if (printed) goto nope; /* we've already printed this guy */ for (k=0;k1) goto nope; for (k=m-1;k>=0;k--) @; @; @; while (o,a[l-1]==0) l--; goto b5; nope: @ @= { oo,o,j=choice[k][0], lj=ja[l-1][j][0], lc=constr[k][0]; if (lc>lj) goto nope; /* this is correct even if |d=0| */ for (i=1;i<=lj;i++) { o,t=ja[l-1][j][i], tt=(i<=lc? o,constr[k][i]: 0); if ((t==d && tt==0) || (t!=d && tt!=0)) goto nope; } } @ @= oo,oo,add(total,ja[l-1][choice[0][0]],ja[l-1][choice[1][0]],off[1]); for (k=2;klj) goto nope; /* this is correct even if |d=0| */ for (i=1;i<=lj;i++) { o,t=total[i], tt=(i<=lc? o,constr[m][i]: 0); if ((t==d && tt==0) || (t!=d && tt!=0)) goto nope; } @ When a solution is found, I first print out the lengths of the multiplicand, multiplier, partial products, and total product. (By sorting these lines later, I can distinguish unique solutions.) Then I print the multiplicand, multiplier, |d|, and the solution number. @= count++; for (i=l-1;a[i]==0;i--) ; /* bypass leading zeros of multiplicand */ printf("%d,%d;", i+1,off[m-1]+1); for (k=0;k=0;i--) printf("%d", a[i]); printf(" x "); for (k=m-1,i=off[k];k>=0;k--,i--) { while (i>off[k]) printf("0"),i--; printf("%d", choice[k][0]); } printf(",d=%d (#%d)\n", @q)@> d,count); printed=1; @ It's conceivable that we've constructed a max-length multiplicand without finding enough obstructions to force all digits of the multiplier. In such cases constraint~|m| (the constraint on the entire product) has probably not yet been fully tested. We should therefore backtrack over all choices of multipliers, in order to be sure that no solutions have been overlooked. Pathological patterns can make this happen, but I don't think it will occur in the cases that interest me. So I am simply reporting the unusual case here. Then I can follow up later if additional investigations are called for. (If$a_{l-1}!=0\$, there might exist very long solutions that cannot be tested without exceeding our |maxdigits| precision.) @d show_unresolved 0 @= { for (k=0;k1) break; if (k=0;k--) fprintf(stderr,"%d", a[k]); fprintf(stderr,", status "); for (k=0;k= { for (k=0;k; if (o,shadow[0]==0) goto b4; /* there were no solutions */ for (k=0;k; } } @ @= bb1: k=0; bb2:@+if (k==m) @; g[k]=0; bb3:@+@; k++; goto bb2; bb4: oo,g[k]++; if (o,g[k]=0) goto bb4; @ @= oo,o,j=choice[k][g[k]], lj=ja[l][j][0]; for (i=0;o,i0? o,acc[k-1][i]+kk: kk); if (ii<=lj) o,t+=ja[l][j][ii]; if (t>=10) o,acc[k][i]=t-10,kk=1;@+else o,acc[k][i]=t,kk=0; } @ @= { for (o,i=0,lc=constr[m][0];i<=l;i++) { o,t=acc[m-1][i]; if (i2) { fprintf(stderr," ok "); for (k=m-1;k>=0;k--) fprintf(stderr,"%d", choice[k][g[k]]); fprintf(stderr,"\n"); } for (k=0;k= { o,imax=csize[l+1][k]; for (i=imax-1;i>=0;i--) if (o,(shadow[k]&(1<2) fprintf(stderr," b%d ain't %d\n", k,j); imax--; if (i!=imax) oo,oo,oo,choice[k][i]=choice[k][imax],where[k][choice[k][imax]]=i, choice[k][imax]=j,where[k][j]=imax; } o,csize[l+1][k]=imax; if (imax==1) o,stack[stackptr++]=k; } @ @= char acc[maxm][maxdigs]; /* partial sums */ char g[maxm]; /* indices for inner loop */ int shadow[maxm]; /* bits where solutions were found */ @*Index.