@s edge int @*Intro. Given the specification of a masyu puzzle in |stdin|, this program outputs {\mc DLX} data for the problem of finding all solutions. (I first hacked it from {\mc SLITHERLINK-DLX}; but a day later, I realized that a far more efficient solution was possible, because masyu clues force many of the secondary items to be identical or complementary.) No attempt is made to enforce the single loop'' condition. Solutions found by {\mc DLX2} will consist of disjoint loops. But {\mc DLX2-LOOP} will weed out any disconnected solutions; in fact it will nip most of them in the bud. The specification begins with $m$ lines of $n$ characters each; those characters should be either \.0' or \.1' or~\..', representing either a white circle, a black circle, or no clue. @d maxn 31 /* |m| and |n| must be at most this */ @d bufsize 80 @d debug 0x0 /* verbose printing? (each bit turns on a different case) */ @d panic(message) {@+fprintf(stderr,"%s: %s",message,buf);@+exit(-1);@+} @c #include #include @; char buf[bufsize]; int board[maxn][maxn]; /* the given clues */ int m,n; /* the given board dimensions */ edge ejj[((maxn+maxn)<<8)+(maxn+maxn)]; /* the union-find table */ char code[]={0xc,0xa,0x5,0x3,0x9,0x6,0x0}; int opt[4],optval[4]; int optcount; @; main() { register int i,j,k,ii,jj,v,t,e,p; @; @; @; @; for (i=0;i@; else @; } @ @= printf("| masyu-dlx:\n"); for (i=0;i'4')) panic("illegal clue"); board[i][j]=k; } if (i==0) n=j; else if (n!=j) panic("row has wrong number of clues"); } m=i; if (m<2 || n<2) panic("the board dimensions must be 2 or more"); fprintf(stderr,"OK, I've read a %dx%d array of clues.\n", m,n); @*Big reductions. The original version of this program had one secondary item for each edge of the grid. These secondary items essentially acted as boolean variables, with their colors'' \.0 and~\.1. Let the edges surrounding a clue be called $N$, $S$, $E$, and $W$. A black clue tells us, among other things, that $N=\bar S$ and $E=\bar W$. So it reduces the number of independent variables by two. A white clue does even more: It tells us, among other things, that $N=S$ and $E=W$ and $N=\bar E$. Internally, we represent the edge between cell $(i,j)$ and cell $(i',j)'$ by the packed value $256(i+i')+(j+j')$. A standard union-find algorithm is used to determine which edges are dependent, and to provide a canonical form for any edge in terms of an independent basis. Edges off the board have the constant value~\.0. We often can deduce a constant value for other edges. The constant'' edge is denoted internally by zero. @d N(v) ((v)-(1<<8)) @d S(v) ((v)+(1<<8)) @d E(v) ((v)+1) @d W(v) ((v)-1) @= typedef struct { int ldr; /* the representative of this equivalence class */ int cmp; /* are we the same as the leader, or the same as its complement? */ int nxt; /* next member of this class, in a cyclic list */ int siz; /* the size of this class (if we're the leader) */ } edge; @ @= for (ii=0;ii<=m+m-2;ii++) for (jj=0;jj<=n+n-2;jj++) if ((ii+jj)&1) { e=(ii<<8)+jj; ejj[e].ldr=ejj[e].nxt=e,ejj[e].siz=1; } @ @= int normalize(int e) { if (e<0) return 0; /* $i$ negative */ if ((e&0xff)>n+n-2) return 0; /* $j$ negative or too large */ if ((e>>8)>m+m-2) return 0; /* $i$ too large */ return e; /* this edge not obviously constant */ } @ @= int yewnion(int e,int ee,int comp) { register int p,q,pp,qq,s,t; e=normalize(e),ee=normalize(ee); if (debug&1) fprintf(stderr," %c%c is %s%c%c\n", encode(e>>8),encode(e&0xff), comp?"~":"",encode(ee>>8),encode(ee&0xff)); p=ejj[e].ldr,s=comp^ejj[e].cmp; pp=ejj[ee].ldr,s^=ejj[ee].cmp; /* now we want to set |p| to |pp^s| */ if (p==pp) @; if (p==0 || (pp!=0 && ejj[p].siz>ejj[pp].siz)) t=p,p=pp,pp=t,t=e,e=ee,ee=t; @; return 0; /* no problem'' */ } @ @= ejj[pp].siz+=ejj[p].siz; if (debug&2) fprintf(stderr," (size of %c%c now %d)\n", encode(pp>>8),encode(pp&0xff),ejj[pp].siz)@q)@>; for (q=ejj[p].nxt;;q=ejj[q].nxt) { ejj[q].ldr=pp, ejj[q].cmp^=s; if (q==p) break; } t=ejj[p].nxt,ejj[p].nxt=ejj[pp].nxt,ejj[pp].nxt=t; @ @= { if (s==0) return 0; /* the new relation is consistent (and redundant) */ fprintf(stderr,"Inconsistency found when equating %c%c to %s%c%c!\n", encode(e>>8),encode(e&0xff), comp?"~":"",encode(ee>>8),encode(ee&0xff)); return 1; /* `one problem'' */ } @ @= @; for (i=0;i= for (i=0;i1) printf("#%c%c ", encode(ii),encode(jj)); } printf("|"); for (i=0;i= void begin_opt(int ii,int jj) { if (debug&4) fprintf(stderr," beginning an option for %c%c:\n", encode(ii),encode(jj)); optcount=0; } @ @= void append_opt(int e,int val) { register int q,p,s,t; if (optcount<0) return; /* option has already been cancelled */ e=normalize(e),val=val&1; if (debug&4) fprintf(stderr," %c%c:%d\n", encode(e>>8),encode(e&0xff),val); p=ejj[e].ldr, val^=ejj[e].cmp; if (p==0) @; for (t=0;t=p) break; if (t; for (s=optcount++;s>t;s--) opt[s]=opt[s-1],optval[s]=optval[s-1]; opt[s]=p,optval[s]=val; if (debug&8) fprintf(stderr," (%c%c:%d)\n", encode(p>>8),encode(p&0xff),val);@q)@> return; } @ The constant 0 is false. @= { if (val==1) { if (debug&8) fprintf(stderr," (false)\n"); optcount=-1; }@+else if (debug&8) fprintf(stderr," (true)\n"); return; } @ @= { if (val!=optval[t]) { if (debug&8) fprintf(stderr," (%c%c:%d!)\n", encode(p>>8),encode(p&0xff),val)@q)@>; optcount=-1; } if (debug&8) fprintf(stderr," (%c%c:%d)\n", encode(p>>8),encode(p&0xff),val)@q)@>; return; } @ @= void finish_opt(int ii,int jj) { register int t; if (optcount>=0) { printf("%c%c", encode(ii),encode(jj)); for (t=0;t>8),encode(opt[t]&0xff),optval[t]); printf("\n"); } } @*Generating the special options. Just after making the item-name line, we generate a catchall option that names all tiles for which a clue has been given, as well as all edges whose boolean value is known in advance. This option will get {\mc DLX2-LOOP} off to a good start. @= for (i=0;i>8),encode(p&0xff),ejj[p].cmp); printf("\n"); @ @= for (ii=0;ii<=m+m-2;ii++) for (jj=0;jj<=n+n-2;jj++) if ((ii+jj)&1) { e=(ii<<8)+jj; if (ejj[e].ldr==e && ejj[e].siz>1) { printf("#%c%c", encode(ii),encode(jj)); for (p=ejj[e].nxt;;p=ejj[p].nxt) { printf(" %c%c:%d", encode(p>>8),encode(p&0xff),ejj[p].cmp); if (p==e) break; } printf("\n"); printf("#%c%c", encode(ii),encode(jj)); for (p=ejj[e].nxt;;p=ejj[p].nxt) { printf(" %c%c:%d", encode(p>>8),encode(p&0xff),ejj[p].cmp^1); if (p==e) break; } printf("\n"); } } @*Generating the normal options. The four constraints for a tile say that the $N$, $S$, $E$, $W$ neighbors of $(i,j)$ include exactly 0 or 2 true edges. @= { e=((i+i)<<8)+(j+j); for (k=0;k<7;k++) { begin_opt(i+i,j+j); append_opt(N(e),code[k]>>3); append_opt(W(e),code[k]>>2); append_opt(E(e),code[k]>>1); append_opt(S(e),code[k]); finish_opt(i+i,j+j); } } @ @= { e=((i+i)<<8)+(j+j); if (board[i][j]=='1') @@; else @; } @ The four constraints for circles look further, at neighbors that are two steps away. @d NN(v) ((v)-(3<<8)) @d SS(v) ((v)+(3<<8)) @d EE(v) ((v)+3) @d WW(v) ((v)-3) @= { for (k=0;k<4;k++) { begin_opt(i+i+1,j+j+1); if (code[k]&8) append_opt(N(e),1),append_opt(NN(e),1); if (code[k]&4) append_opt(W(e),1),append_opt(WW(e),1); if (code[k]&2) append_opt(E(e),1),append_opt(EE(e),1); if (code[k]&1) append_opt(S(e),1),append_opt(SS(e),1); finish_opt(i+i+1,j+j+1); } } @ @= { for (k=4;k<6;k++) for (ii=0;ii<2;ii++) for (jj=0;jj<2;jj++) if (ii*jj==0) { begin_opt(i+i+1,j+j+1); if (code[k]&8) { append_opt(N(e),1); append_opt(NN(e),ii),append_opt(SS(e),jj); }@+else { append_opt(W(e),1); append_opt(WW(e),ii),append_opt(EE(e),jj); } finish_opt(i+i+1,j+j+1); } } @*Index.