\datethis @*Intro. Given the specification of a filomino puzzle in |stdin|, this program outputs {\mc DLX} data for the problem of finding all solutions. The specification consists of $m$ lines of $n$ entries each. An entry is either \..' or a digit from \.1 to~\.9 or \.a to~\.f. A solution means that all \..' entries are replaced by digits. Every maximal rookwise connected set of cells labeled $d$ must be a $d$-omino. The maximum digit in the solution will be the maximum digit specified. (For example, the program will make no attempt to fit pentominoes into the blank cells, if all of the specified digits are less than~\.5.) The main interest in this program is its method for finding all feasible $d$-ominoes that cover a given entry~$d$: They must not be adjacent to a $d$ that's not included. The algorithm used here is an instructive generalization of Algorithm~R in exercise 7.2.2--75 of {\sl The Art of Computer Programming}. @d maxn 16 /* at most 16 (or I'll have to go beyond hex) */ @d maxd 16 /* digits of the solution must be less than this */ @d bufsize 80 @d pack(i,j) ((((i)+1)<<8)+(j)+1) @d unpack(ij) icoord=((ij)>>8)-1,jcoord=((ij)&0xff)-1 @d board(i,j) brd[pack(i,j)] @d panic(message) {@+fprintf(stderr,"%s: %s",message,buf);@+exit(-1);@+} @c #include #include char buf[bufsize]; int brd[pack(maxn,maxn)]; /* the given pattern */ int dmax; /* the maximum digit seen */ @; @; main() { register int a,d,i,j,k,l,m,n,p,q,s,t,u,v,di,dj,icoord,jcoord; @; @; for (d=1;d<=dmax;d++) @; } @ @= printf("| filomino-dlx:\n"); for (i=n=t=0;i<=maxn;i++) { if (!fgets(buf,bufsize,stdin)) break; printf("| %s", buf); for (j=k=0;;j++,k++) { if (buf[k]=='\n') break; if (buf[k]=='.') continue; if (buf[k]>='1' && buf[k]<='9') board(i,j)=buf[k]-'0',t++; else if (buf[k]>='a' && buf[k]<='f') board(i,j)=buf[k]-'a'+10,t++; else panic("illegal entry"); if (board(i,j)>dmax) dmax=board(i,j); } if (j>n) n=j; /* short rows are extended with \..'s */ } if (i>maxn) panic("too many rows"); m=i; for (i=0;i= for (i=0;i= { for (di=0;di; } @ Now comes the interesting part. I assume the reader is familiar with Algorithm R in the solution to exercise 7.2.2--75. But we add a new twist: A {\it forced move\/} is made to a $d$-cell if we've chosen a vertex adjacent to~it. The first vertex ($v_0$) is also considered to be forced. Since I'm not operating with a general graph, the \.{ARCS} and \.{NEXT} aspects of Algorithm~R are replaced with a simple scheme: Codes 1, 2, 3, 4 are used respectively for north, west, east, and south. In other words, the operation $a\gets\.{ARCS($v$)}$' is changed to to $a\gets1'$; $a\gets\.{NEXT($a$)}$' is changed to $a\gets a+1$'; $a=\Lambda$?' becomes `$a=5$?'. The vertex \.{TIP($a$)} is the cell north, west, east, or south of~$v$, depending on~$a$. A forced move at level $l$ is indicated by $a_l=0$. If cell $(di,dj)$ is not already filled, we fill it with a $d$-mino that uses only unfilled cells and doesn't come next to a $d$-cell. @= { u=pack(di,dj); if (!board(di,dj)) { for (q=1;q<=4;q++) if (brd[u+dir[q]]==d) break; /* next to $d$ */ if (q<=4) continue; forcing=0; }@+else if (board(di,dj)!=d) continue; else forcing=1; @; @; @; @; @; @; @; done: checktags(); } @ @= r1: /* initialize */ for (i=0;i1|, it's a vertex adjacent to |v=vv[i]| in direction~|a|, where |i=ii[l-1]| and |a=aa[l-1]|. @= r2: /* enter level $l$ */ if (forcing) @; if (l==d) { @; @; } @ Ye olde depth-first search. If forcing, we backtrack if the |d|-omino gets too big, or if we're forced to choose a |d|-cell whose options have already been considered. If not forcing, we backtrack if we're next to a |d|-cell, or if solutions for this cell have already been considered. @= for (stack[0]=u,s=1;s;) { u=stack[--s]; for (q=1;q<=4;q++) { t=u+dir[q]; if (brd[t]!=d) continue; /* not a |d|-cell */ if (tag[t]) continue; /* we've already chosen this |d|-cell */ if (t= { curstamp++; for (p=0;p= for (l--;aa[l]==0;l--) { if (l==0) goto done; tag[vv[l]]=0; } @ @= r3: /* advance |a| */ a++; @ @= r4: /* done with level? */ if (a!=5) goto r5; if (i==l-1) goto r6; v=vv[++i],a=1; @ @= r5: /* try |a| */ u=v+dir[a]; if (brd[u]) goto r3; /* not really a neighbor of |v| */ tag[u]++; if (tag[u]>1) goto r3; /* already chosen */ if (!forcing) @; ii[l]=i,aa[l]=a,vv[l]=u,l++; goto r2; @ @= { if (u= r6: /* backtrack */ @; for (i=ii[l],k=i+1;k<=l;k++) { t=vv[k]; for (q=1;q<=4;q++) if (brd[t+dir[q]]==0) tag[t+dir[q]]--; /* untag the neighbors of |vv[k]| */ } for (a=aa[l]+1,v=vv[i];a<=4;a++) if (brd[v+dir[a]]==0) tag[v+dir[a]]--; /* untag late neighbors of |vv[i]| */ a=aa[l]; goto r3; @ @= for (l--;aa[l]==0;l--) { if (l==0) goto done; t=vv[l]; for (q=1;q<=4;q++) if (brd[t+dir[q]]==0) tag[t+dir[q]]--; /* untag the neighbors of |vv[l| */ tag[t]=0; } @ @= r7: /* recover from bad forcing */ @; i=ii[l],v=vv[i],a=aa[l]; goto r3; @ @= int forcing; int dir[5]={0,-(1<<8),-1,1,1<<8}; int tag[pack(maxn,maxn)]; int vv[maxd],aa[maxd],ii[maxd],stack[maxd]; /* state variables */ int curstamp; int stamp[pack(maxn,maxn)]; int mm,nn; @ @= void debug(char*message) { fprintf(stderr,"%s!\n", message); } @ Here's a handy routine for debugging the tricky parts. @= void showtags(void) { register int i,j; for (i=0;i= void checktags(void) { register int i,j,q; for (i=0;i