@x \S1 @ After this program finds all solutions, it normally prints their total @y This version is a special extension that adds a {\it loop constraint\/}: Certain primary items encode vertices'' and certain secondary items encode edges,'' which are pairs of vertices, using an even-odd coordinate system. The edges whose color is~1 must form a {\it single cycle\/}. (We assume that other constraints require every vertex to have degree 0~or~2.) I wrote this in order to solve puzzles like slitherlink and masyu. It incorporates some ideas of Rory Molinari, who greatly simplified the algorithm I had originally used. @ After this program finds all solutions, it normally prints their total @z @x \S6 @ Each \&{item} struct contains three fields: The |name| is the user-specified identifier; |next| and |prev| point to adjacent items, when this item is part of a doubly linked list. @y @ Each \&{item} struct contains five fields: The |name| is the user-specified identifier; |next| and |prev| point to adjacent items, when this item is part of a doubly linked list. And there are two fields |left|, |right|, for this special loop extension. If a secondary item represents an edge, its |left| and |right| fields point to the primary items for the vertices linked by this edge. The |left| and |right| field of such primary items are used for different purposes entirely; so we call them |mate| and |inner| when used in that context. Both |mate| and |inner| are initially zero. Then |mate| becomes nonzero when the vertex first becomes the endpoint of a partial path, in which case |mate| points to the vertex at the other end of that path. The |inner| field is nonzero when the vertex is internal to such a path fragment. @z @x int prev,next; /* neighbors of this item */ @y int prev,next; /* neighbors of this item in the active list */ int left,right; /* vertex references */ @z @x \S15 last_itm++; @y @; last_itm++; @z @x \S22 level=0; forward: nodes++; @y for (k=second;k0) purify(pp); @y else if (nd[pp].color>0) { if (purify(pp)<0) goto dangerous_recovery; } @z @x \S28 pp--; @y dangerous_recovery: pp--; /* yes, I jumped into the middle of this loop */ @z @x \S29 void purify(int p) { register int cc,rr,nn,uu,dd,t,x; o,cc=nd[p].itm,x=nd[p].color; @y int purify(int p) { register int cc,rr,nn,uu,dd,t,x; o,cc=nd[p].itm,x=nd[p].color; if (x=='1' && (o,cl[cc].left)) @; @z @x } @y return 0; } @z @x \S30 o,cc=nd[p].itm,x=nd[p].color; /* there's no need to clear |nd[cc].color| */ @y o,cc=nd[p].itm,x=nd[p].color; /* there's no need to clear |nd[cc].color| */ nd[cc].color=0; /* but I do it anyway for tidiness (see |print_uncolored|) */ if (x=='1' && (o,cl[cc].left)) @; @z @x \S32 count++; if (spacing && (count mod spacing==0)) { printf(""O"lld:\n",count); for (k=0;k<=level;k++) print_option(choice[k],stdout); @y count++; if (spacing && (count mod spacing==0)) { register int x,y,x0,y0,prev; k=cl[last_edge].left; x=decode(cl[k].name[0]),y=decode(cl[k].name[1]); if (x<0 || y<0) fprintf(stderr,"This can't happen!\n"); else { printf(""O"lld: "O".8s",count,cl[k].name); for (x0=x,y0=y,prev=-1;;) { if (prev!=0 && try(x-1,y)) x-=2,prev=3; else if (prev!=1 && try(x,y-1)) y-=2,prev=2; else if (prev!=2 && try(x,y+1)) y+=2,prev=1; else if (prev!=3 && try(x+1,y)) x+=2,prev=0; else { fprintf(stderr,"Lost in the cycle!\n"); break; } printf(" "O"c"O"c",encode(x),encode(y)); if (x==x0 && y==y0) break; } printf("\n"); } @z @x @*Index. @y @ @= void print_frags(void) { register int p; for (p=1;pp && cl[cl[p].mate].mate==p) { fprintf(stderr," "O".8s, mate "O".8s\n",cl[p].name, cl[cl[p].mate].name); } } @ @= void count_frags(void) { register int p,f; for (f=0,p=1;pp && cl[cl[p].mate].mate==p) f++; if (f!=frags) fprintf(stderr,"frags is wrong (%d should be %d)!\n", frags,f); } @ @= void print_verts() { register int c; for (c=1;c='0' && (c)<='9'? (c)-'0': (c)>='a' && (c)<='z'? (c)-'a'+10: (c)>='A' && (c)<='Z'? (c)-'A'+36: -1) @d encode(d) ((d)<10? (d)+'0': (d)<36? (d)-10+'a': (d)<62? (d)-36+'A': '?') @= if (cl[last_itm].name[1]!=0 && cl[last_itm].name[2]==0) { register int x,y,u,v; x=decode(cl[last_itm].name[0]),y=decode(cl[last_itm].name[1]); if (x>=0 && y>=0) { o,itmloc[x][y]=last_itm; if ((x+y)&1) { /* edge item */ if (second==max_cols) panic("Edge item isn't secondary"); if (x&1) u=itmloc[x-1][y],v=itmloc[x+1][y]; else u=itmloc[x][y-1],v=itmloc[x][y+1]; if (u==0 || v==0) panic("Edge item for nonexistent vertex"); o,cl[last_itm].left=u,cl[last_itm].right=v; }@+else if ((x&1)==0 && (y&1)==0) { /* vertex item */ if (second!=max_cols) panic("Vertex item isn't primary"); } } } @ A new edge from $u$ to $v$ introduces two new endpoints to the fragment list, if $u$ and $v$ aren't endpoints already. (We don't allow any new edges after the loop has been closed; immediate backtracking will be forced.) On the other hand, if $v$ is an existing endpoint but $u$ isn't, we replace $v$ by $u$ in the fragment list. And if both $u$ and $v$ are existing endpoints, we eliminate them both, possibly closing the loop in the process. (We refuse to close the loop unless $u$ and $v$ were the {\it only\/} endpoints present.) This part of the program is therefore the heart of the loop-checking mechanism. We are careful to do everything in such a way that it can be conveniently undone, again adopting the philosophy of dancing links for the doubly linked fragment list. A global variable |last_edge| points to the edge that has closed a cycle, if any. Another global variable, |frags|, counts the number of fragments that are formed by existing edges. Several cases arise when an edge from $u$ to~$v$ receives color~`\.1': If |last_edge| is nonzero, this edge is rejected. Otherwise, \smallskip\noindent{\it Case 0.} |mate(u)=0=mate(v)|. (The vertices were previously isolated.) We create a new fragment. \par\noindent{\it Case 1.} |mate(u)=0!=mate(v)|. Extend the fragment that ends at |v|. \par\noindent{\it Case 2.} |mate(u)!=0=mate(v)|. Extend the fragment that ends at |u|. \par\noindent{\it Case 3.} |mate(u)!=0!=mat(v)|. If |mate(u)=v| (and therefore |mate(v)=u|), we allow the new edge (and set |last_edge|) only if |frags=1|. If |mate(u)!=v|, we use the edge to join two fragments into one. Note: When I first wrote this code, I believed that |u| and |v| must necessarily be endpoints in case 3, because the options are designed to assure that no vertex can have degree~3. (Therefore I didn't think the |inner| field was needed.) Unfortunately, that reasoning led to a serious bug that was hard to track down! In rare cases a new edge {\it can\/} temporarily make a vertex have degree~3. But that vertex will then have no remaining options, and we will backtrack at the next level --- too late to recover from an improper clobbering of |mate| fields. @d mate left @d inner right @= { register int u,v,mu,mv; if (last_edge) { if (vbose&show_choices) fprintf(stderr," (not adding "O".8s to a loop)\n", cl[cc].name); return -1; } u=cl[cc].left,v=cl[cc].right; oo,mu=cl[u].mate,mv=cl[v].mate; if (mu && cl[u].inner) { if (vbose&show_choices) fprintf(stderr,"(not allowing "O".8s degree 3)\n", cl[u].name); return -1; } if (mv && cl[v].inner) { if (vbose&show_choices) fprintf(stderr,"(not allowing "O".8s degree 3)\n", cl[v].name); return -1; } if (!mu) { /* |u| not in any fragment */ if (!mv) { /* |v| not in any fragment */ oo,cl[u].mate=v,cl[v].mate=u,frags++; }@+else { /* |mv| is the endpoint opposite |v| */ ooo,cl[u].mate=mv,cl[mv].mate=u,cl[v].inner=1; } }@+else if (!mv) { /* |mu| is the endpoint opposite |u| */ ooo,cl[v].mate=mu,cl[mu].mate=v,cl[u].inner=1; }@+else { /* |u| and |v| are endpoints of fragments */ if (mu==v) { /* also |mv==u|, loop is closing */ if (frags!=1) { if (vbose&show_choices) fprintf(stderr," (not closing a short loop with "O".8s)\n", cl[cc].name); return -1; } last_edge=cc; }@+else { /* fragments are being joined */ oo,oo,cl[mu].mate=mv,cl[mv].mate=mu,cl[u].inner=cl[v].inner=1,frags--; } } } @ @= { register int u,v,mu,mv; u=cl[cc].left,v=cl[cc].right; oo,mu=cl[u].mate,mv=cl[v].mate; if (mu==mv) { if (o,cl[mu].mate==v) ooo,cl[mu].mate=u,cl[v].mate=0,cl[u].inner=0; else if (cl[mu].mate==u) ooo,cl[mu].mate=v,cl[u].mate=0,cl[v].inner=0; else fprintf(stderr,"Confusion removing edge "O".8s!\n", cl[cc].name); }@+else if (mu==v) { /* also |mv==u| */ if (last_edge==cc) last_edge=0; else oo,cl[u].mate=cl[v].mate=0, frags--; }@+else oo,oo,cl[mu].mate=u,cl[mv].mate=v,cl[u].inner=cl[v].inner=0, frags++; } @ @= int itmloc[62][62]; /* what item has a given pair of coordinates? */ int last_edge; /* the edge that completed the cycle */ int frags; /* the number of current fragments */ @ @= int try(int x,int y) { register int p; if (x<0 || x>=62 || y<0 || y>=62) return 0; p=itmloc[x][y]; if (p>=second && cl[p].left && nd[p].color=='1') return 1; return 0; } @ Here's a subroutine that I might be able to use to discover early cutoffs in new ways. It displays all the edges whose fate is not yet decided (that is, the edges that are still uncolored). @= void print_uncolored(void) { register int p; for (p=second;p