@x @s item int @y \let\maybe=\iffalse @s item int @z @x @ After this program finds all solutions, it normally prints their total @y @ This version of the program keeps removing options at the bottom, thereby finding all solutions that have minimax option number. (And it usually also finds a few more, before it has found the best cutoff point.) Furthermore, a very special feature is added: Whenever we backtrack from a choice at level~0, we also cover the secondary item at the very end of its option! (Perhaps someday I will think of a suitable generalization for which this action sounds sensible.) Here's why: Several applications of {\mc DLX2} have equivalence relations between their solutions. For example, if I'm generating word squares, the transpose of every solution is a solution. Suppose I put secondary item \.{foo} at the end of the options for placing \.{foo} in option~1 and item~1. Then the word chosen for item~1 will always come later than the word chosen for option~1. We assume that the items contain options in their original order; the |up| and |down| links actually point upwards and downwards. Therefore we disable the ``randomizing'' feature by which items could be linked randomly. (Randomization still does apply, however, when choosing an item for branching.) After this program finds all the desired solutions, it normally prints their total @z @x @d show_details 4 /* |vbose| code for further commentary */ @y @d show_details 4 /* |vbose| code for further commentary */ @d show_cutoffs 8 /* |vbose| code to report improvements in the cutoff point */ @z @x int last_itm; /* the first item in |cl| that's not yet used */ @y int last_itm; /* the first item in |cl| that's not yet used */ int cutoff=max_nodes; /* nodes after this point have essentially disappeared */ @z @x @d sanity_checking 0 /* set this to 1 if you suspect a bug */ @y @d sanity_checking 0 /* set this to 1 if you suspect a bug */ @z @x here's where the kludge happens recover: @; @y recover: @; if (level==0) { for (p=cur_node-1;o,nd[p].itm>0;p--) ; oo,p=nd[p].down,cc=nd[p].itm; /* fetch the last item of the option */ if (cc>=second && !nd[p].color) cover(cc); /* cover it, if secondary and uncolored */ } @z @x @ I used to think that it was important to uncover an item by processing its options from bottom to top, since covering was done from top to bottom. But while writing this program I realized that, amazingly, no harm is done if the options are processed again in the same order. So I'll go downward again, just to prove the point. Whether we go up or down, the pointers execute an exquisitely choreo\-graphed dance that returns them almost magically to their former state. @y @ A subtle point should be noted: As we uncover item $c$, and run across an option `$c$~$x$~\dots' that should be restored to item~$x$, the original successors `$x$~$a$~\dots', `$x$~$b$~\dots', etc., of that option in item~$x$ may now be cut off. In such a case we can be sure that those successor options have disappeared from item~$x$, and they have {\it not\/} been restored. The reason is that each of those options must have a primary item; and every primary item was covered before we changed the cutoff. The options were therefore not restored to item~$x$ when we uncovered those primary items. @z @x void uncover(int c) { register int cc,l,r,rr,nn,uu,dd,t; for (o,rr=nd[c].down;rr>=last_itm;o,rr=nd[rr].down) for (nn=rr+1;nn!=rr;) { if (o,nd[nn].color>=0) { o,uu=nd[nn].up,dd=nd[nn].down; cc=nd[nn].itm; if (cc<=0) { nn=uu;@+continue; } @y void uncover(int c) { register int cc,l,r,rr,nn,uu,dd,t; for (o,t=0,rr=nd[c].up;rr>=cutoff;o,rr=nd[rr].up) t++; if (t) { /* |t| options that we covered have been cut off */ oo,nd[c].len-=t; if (c>=second) lmems+=2; oo,nd[c].up=rr,nd[rr].down=c; } for (;rr>=last_itm;o,rr=nd[rr].up) for (nn=rr+1;nn!=rr;) { if (o,nd[nn].color>=0) { o,uu=nd[nn].up,dd=nd[nn].down; cc=nd[nn].itm; if (cc<=0) { nn=uu; continue; } if (dd>=cutoff) o,nd[nn].down=dd=cc; /* see the ``subtle point'' above */ @z @x void unpurify(int p) { register int cc,rr,nn,uu,dd,t,x; o,cc=nd[p].itm,x=nd[p].color; /* there's no need to clear |nd[cc].color| */ for (o,rr=nd[cc].up;rr>=last_itm;o,rr=nd[rr].up) { if (o,nd[rr].color<0) o,nd[rr].color=x; else if (rr!=p) { for (nn=rr-1;nn!=rr;) { if (o,nd[nn].color>=0) { o,uu=nd[nn].up,dd=nd[nn].down; cc=nd[nn].itm; if (cc<=0) { nn=dd;@+continue; } @y void unpurify(int p) { register int cc,rr,nn,uu,dd,t,x; o,cc=nd[p].itm,x=nd[p].color; /* there's no need to clear |nd[cc].color| */ for (o,t=0,rr=nd[cc].up;rr>=cutoff;o,rr=nd[rr].up) t++; if (t) { /* |t| options that we covered have been cut off */ oo,nd[cc].len-=t; lmems+=2; oo,nd[cc].up=rr,nd[rr].down=cc; } for (;rr>=last_itm;o,rr=nd[rr].up) { if (o,nd[rr].color<0) o,nd[rr].color=x; else if (rr!=p) { for (nn=rr-1;nn!=rr;) { if (o,nd[nn].color>=0) { o,uu=nd[nn].up,dd=nd[nn].down; cc=nd[nn].itm; if (cc<=0) { nn=dd;@+continue; } if (dd>=cutoff) o,nd[nn].down=dd=cc; /* see the ``subtle point'' above */ @z @x count++; @y count++; for (k=0,pp=0;k<=level;k++) if (choice[k]>pp) pp=choice[k]; for (pp++;o,nd[pp].itm>0;pp++); /* move to end of largest chosen option */ if (pp!=cutoff) { cutoff=pp; if (vbose&show_cutoffs) { fprintf(stderr," new cutoff after option "O"d:\n",-nd[pp].itm); prow(nd[pp].up); } for (k=0;k<=level;k++) { o,cc=nd[choice[k]].itm; /* |cc| will stay covered until we backtrack */ for (o,t=0,pp=nd[cc].up;pp>=cutoff;o,pp=nd[pp].up) t++; if (t) { /* need to prune unneeded options from item |cc| */ oo,nd[pp].down=cc,nd[cc].up=pp; oo,nd[cc].len-=t; } } } @z