@s mod and \let\Xmod=\bmod % this is CWEB magic for using "mod" instead of "%" \datethis @*Intro. This program is an experimental {\mc XCC} solver, which often looks ahead considerably further than {\mc DLX2} does. More precisely, it maintains ``domain consistency'': An option $O$ is eliminated when its use would cause some primary item $I\notin O$ to have no options remaining. In a sense, I'm performing the work of {\mc DLX-PRE} repeatedly as the search proceeds. With luck, the total time will decrease, although the time per node is potentially much larger. Furthermore, I'm continuing to experiment with sparse-set data structures, as I did in the similar program {\mc SSXCC}, which was inspired by Christine Solnon's {\mc XCC-WITH-DANCING-CELLS}. This program was in fact derived directly from {\mc SSXCC}, by adding further data structures and algorithms. I confess in advance that the concepts below might not be easy to grasp, because some of them are rather subtle, and they're just beginning to make sense to me as I put the pieces together. Hopefully all will become clear by the time I finish! I've retained the documentation of {\mc SSXCC}'s features, but they too are admittedly intricate. So let's take a deep breath together. We can handle this. The {\mc DLX} input format used in previous solvers is adopted here, without change, so that fair comparisons can be made. (See the program {\mc DLX2} for definitions. Much of the code from that program is used to parse the input for this one.) @ After this program finds all solutions, it normally prints their total number on |stderr|, together with statistics about how many nodes were in the search tree, and how many ``updates'' were made. The running time in ``mems'' is also reported, together with the approximate number of bytes needed for data storage. (An ``update'' is the removal of an option from its item list, or the removal of a satisfied color constraint from its option. One ``mem'' essentially means a memory access to a 64-bit word. The reported totals don't include the time or space needed to parse the input or to format the output.) Empirical tests show that this program takes more elapsed time per mem than most other programs that I've written. I don't know why. Perhaps it's because the number of ``global registers'' is unusually large. Here is the overall structure: @d o mems++ /* count one mem */ @d oo mems+=2 /* count two mems */ @d ooo mems+=3 /* count three mems */ @d subroutine_overhead mems+=4 @d O "%" /* used for percent signs in format strings */ @d mod % /* used for percent signs denoting remainder in \CEE/ */ @d max_stage 500 /* at most this many options in a solution */ @d max_level 50000 /* at most this many levels in the search tree */ @d max_cols 10000 /* at most this many items */ @d max_nodes 50000000 /* at most this many nonzero elements in the matrix */ @d poolsize 100000000 /* at most this many entries in |pool| */ @d savesize 1000000 /* at most this many entries on |savestack| */ @d bufsize (9*max_cols+3) /* a buffer big enough to hold all item names */ @c #include #include #include #include typedef unsigned int uint; /* a convenient abbreviation */ typedef unsigned long long ullng; /* ditto */ @; @; @; int main (int argc, char *argv[]) { register int c,cc,i,j,k,p,pp,q,r,s,t,cur_choice,best_itm; @; @; @; if (vbose&show_basics) @; if (vbose&show_tots) @; imems=mems, mems=0; if (baditem) @@; else @; done:@+@; } @ You can control the amount of output, as well as certain properties of the algorithm, by specifying options on the command line: \smallskip\item{$\bullet$} `\.v$\langle\,$integer$\,\rangle$' enables or disables various kinds of verbose output on |stderr|, given by binary codes such as |show_choices|; \item{$\bullet$} `\.m$\langle\,$integer$\,\rangle$' causes every $m$th solution to be output (the default is \.{m0}, which merely counts them); \item{$\bullet$} `\.d$\langle\,$integer$\,\rangle$' sets |delta|, which causes periodic state reports on |stderr| after the algorithm has performed approximately |delta| mems since the previous report (default 10000000000); \item{$\bullet$} `\.c$\langle\,$positive integer$\,\rangle$' limits the levels on which choices are shown during verbose tracing; \item{$\bullet$} `\.C$\langle\,$positive integer$\,\rangle$' limits the levels on which choices are shown in the periodic state reports; \item{$\bullet$} `\.l$\langle\,$nonnegative integer$\,\rangle$' gives a {\it lower\/} limit, relative to the maximum level so far achieved, to the levels on which choices are shown during verbose tracing; \item{$\bullet$} `\.t$\langle\,$positive integer$\,\rangle$' causes the program to stop after this many solutions have been found; \item{$\bullet$} `\.T$\langle\,$integer$\,\rangle$' sets |timeout| (which causes abrupt termination if |mems>timeout| at the beginning of a level); \item{$\bullet$} `\.S$\langle\,$filename$\,\rangle$' to output a ``shape file'' that encodes the search tree; \item{$\bullet$} `\.x$\langle\,$positive integer$\,\rangle$' causes partial solutions of this many stages to be written to files, not actually explored; \item{$\bullet$} `\.X$\langle\,$filename$\,\rangle$' to input and resume a partial solution. @d show_basics 1 /* |vbose| code for basic stats; this is the default */ @d show_choices 2 /* |vbose| code for backtrack logging */ @d show_details 4 /* |vbose| code for stats about choices */ @d show_purges 8 /* |vbose| code to show inconsistent options deleted */ @d show_supports 16 /* |vbose| code to show new supports */ @d show_option_counts 32 /* |vbose| code to count active options */ @d show_mstats 64 /* |vbose| code to show memory usage in key arrays */ @d show_profile 128 /* |vbose| code to show the search tree profile */ @d show_full_state 256 /* |vbose| code for complete state reports */ @d show_tots 512 /* |vbose| code for reporting item totals at start */ @d show_warnings 1024 /* |vbose| code for reporting options without primaries */ @d show_max_deg 2048 /* |vbose| code for reporting maximum branching degree */ @ @= int vbose=show_basics+show_warnings; /* level of verbosity */ int spacing; /* solution $k$ is output if $k$ is a multiple of |spacing| */ int show_choices_max=1000000; /* above this level, |show_choices| is ignored */ int show_choices_gap=1000000; /* below level |maxl-show_choices_gap|, |show_details| is ignored */ int show_levels_max=1000000; /* above this level, state reports stop */ int maxl,maxs; /* maximum level and stage actually reached */ int xcutoff=-1,xcount; /* stage when partial solutions output, and their number */ int maxsaveptr; /* maximum size of |savestack| */ char buf[bufsize]; /* input buffer */ ullng count; /* solutions found so far */ ullng options; /* options seen so far */ ullng imems,mems,bmems,nmems,pmems,tmems; /* mem counts */ ullng updates; /* update counts */ ullng bytes; /* memory used by main data structures */ ullng nodes; /* total number of branch nodes initiated */ ullng thresh=10000000000; /* report when |mems| exceeds this, if |delta!=0| */ ullng delta=10000000000; /* report every |delta| or so mems */ ullng maxcount=0xffffffffffffffff; /* stop after finding this many solutions */ ullng timeout=0x1fffffffffffffff; /* give up after this many mems */ FILE *shape_file; /* file for optional output of search tree shape */ char *shape_name; /* its name */ int maxdeg; /* the largest branching degree seen so far */ @ If an option appears more than once on the command line, the first appearance takes precedence. @= for (j=argc-1,k=0;j;j--) switch (argv[j][0]) { case 'v': k|=(sscanf(argv[j]+1,""O"d",&vbose)-1);@+break; case 'm': k|=(sscanf(argv[j]+1,""O"d",&spacing)-1);@+break; case 'd': k|=(sscanf(argv[j]+1,""O"lld",&delta)-1),thresh=delta;@+break; case 'c': k|=(sscanf(argv[j]+1,""O"d",&show_choices_max)-1);@+break; case 'C': k|=(sscanf(argv[j]+1,""O"d",&show_levels_max)-1);@+break; case 'l': k|=(sscanf(argv[j]+1,""O"d",&show_choices_gap)-1);@+break; case 't': k|=(sscanf(argv[j]+1,""O"lld",&maxcount)-1);@+break; case 'T': k|=(sscanf(argv[j]+1,""O"lld",&timeout)-1);@+break; case 'S': shape_name=argv[j]+1, shape_file=fopen(shape_name,"w"); if (!shape_file) fprintf(stderr,"Sorry, I can't open file `"O"s' for writing!\n", shape_name); break; case 'x': k|=(sscanf(argv[j]+1,""O"d",&xcutoff)-1);@+break; case 'X': @; default: k=1; /* unrecognized command-line option */ } if (k) { fprintf(stderr, "Usage: "O"s [v] [m] [d] [c] [C] "@/ "[l] [t] [T] [S] [x] [X] < foo.dlx\n", argv[0]); exit(-1); } @ I don't report the memory used for |deg|, |stagelevel|, and |profile|, because they are only for documentation, not part of the search process. @= if (vbose&show_profile) @; if (vbose&show_max_deg) fprintf(stderr,"The maximum branching degree was "O"d.\n",maxdeg); if (vbose&show_basics) { fprintf(stderr,"Altogether "O"llu solution"O"s, "O"llu+"O"llu mems,", count,count==1?"":"s",imems,mems); bytes=(itemlength+setlength)*sizeof(int)+last_node*sizeof(node) +(4*maxs+maxl)*sizeof(int)+maxsaveptr*sizeof(twoints) +poolptr*sizeof(twoints); fprintf(stderr," "O"llu updates, "O"llu bytes, "O"llu nodes,", updates,bytes,nodes); fprintf(stderr," acost "O"lld%%, bcost "O"lld%%, ccost "O"lld%%.\n", mems? (200*nmems+mems)/(2*mems):0, mems? (200*pmems+mems)/(2*mems):0, mems? (200*bmems+mems)/(2*mems):0); } if (vbose&show_mstats) { fprintf(stderr," itemlength="O"d, setlength="O"d, last_node="O"d;\n", itemlength,setlength,last_node); fprintf(stderr, " maxsaveptr="O"d, poolptr="O"d, maxstage="O"d, maxlevel="O"d.\n", maxsaveptr,poolptr,maxs,maxl); } if (sanity_checking) fprintf(stderr,"sanity_checking was on!\n"); if (leak_checking) fprintf(stderr,"leak_checking was on!\n"); if (shape_file) fclose(shape_file); if (xcount) @; @ Here's a subroutine for use in debugging, but I hope it's never invoked. @= void confusion(char *id) { /* an assertion has failed */ fprintf(stderr,"trouble after "O"lld mems, "O"lld nodes: %s!\n", mems,nodes,id); } @*Data structures. Sparse-set data structures were introduced by Preston Briggs and Linda Torczon [{\sl ACM Letters on Programming Languages and Systems\/ \bf2} (1993), 59--69], who realized that exercise 2.12 in Aho, Hopcroft, and Ullman's classic text {\sl The Design and Analysis of Computer Algorithms\/} (Addison--Wesley, 1974) was much more than just a slick trick to avoid initializing an array. (Indeed, {\sl TAOCP\/} exercise 2.2.6--24 calls it the ``sparse array trick.'') The basic idea is amazingly simple, when specialized to the situations that we need to deal with: We can represent a subset~$S$ of the universe $U=\{x_0,x_1,\ldots,x_{n-1}\}$ by maintaining two $n$-element arrays $p$ and $q$, each of which is a permutation of~$\{0,1,\ldots,n-1\}$, together with an integer $s$ in the range $0\le s\le n$. In fact, $p$ is the {\it inverse\/} of~$q$; and $s$ is the number of elements of~$S$. The current value of the set $S$ is then simply $\{x_{p_0},\ldots,x_{p_{s-1}}\}$. (Notice that every $s$-element subset can be represented in $s!\,(n-s)!$ ways.) It's easy to test if $x_k\in S$, because that's true if and only if $q_k= typedef struct node_struct { int itm; /* the item |x| corresponding to this node */ int loc; /* where this node resides in |x|'s active set */ int clr; /* color associated with item |x| in this option, if any */ int xtra; /* used for special purposes (see below) */ } node; @ @= node nd[max_nodes]; /* the master list of nodes */ int last_node; /* the first node in |nd| that's not yet used */ int item[max_cols]; /* the master list of items */ int second=max_cols; /* boundary between primary and secondary items */ int last_itm; /* items seen so far during input, plus 1 */ int set[max_nodes+6*max_cols]; /* sets of active options for active items */ int itemlength; /* number of elements used in |item| */ int setlength; /* number of elements used in |set| */ int active; /* current number of active items */ int oactive; /* value of active before swapping out current-choice items */ int totopts; /* current number of active options */ int baditem; /* an item with no options, plus 1 */ int osecond; /* setting of |second| just after initial input */ @ We're going to store string data (an item's name) in the midst of the integer array |set|. So we've got to do some type coercion using low-level \CEE/-ness. @= typedef struct { int l,r; } twoints; typedef union { unsigned char str[8]; /* eight one-byte characters */ twoints lr; /* two four-byte integers */ } stringbuf; stringbuf namebuf; @ @= void print_item_name(int k,FILE *stream) { namebuf.lr.l=lname(k),namebuf.lr.r=rname(k); fprintf(stream," "O".8s",namebuf.str); } @ An option is identified not by name but by the names of the items it contains. Here is a routine that prints an option, given a pointer to any of its nodes. If |showid=1|, it also prints the value of |opt-1|, which should be the location of the spacer just preceding |opt|. Otherwise it optionally prints the position of the option in its item list. @= void print_option(int opt,FILE *stream,int showpos,int showid) { register int k,q,x; x=nd[opt].itm; if (opt>=last_node || x<=0) { fprintf(stderr,"Illegal option "O"d!\n",opt); return; } if (showid) fprintf(stream,""O"d `",opt-1); for (q=opt;;) { print_item_name(x,stream); if (nd[q].clr) fprintf(stream,":"O"c",nd[q].clr); q++; x=nd[q].itm; if (x<0) q+=x,x=nd[q].itm; if (q==opt) break; } k=nd[q].loc; if (showid) fprintf(stream," '"); if (showpos>0) fprintf(stream," ("O"d of "O"d)\n",k-x+1,size(x)); else if (showpos==0) fprintf(stream,"\n"); } @# void prow(int p) { print_option(p,stderr,1,0); } @# void propt(int opt) { /* |opt| should be the spacer just before an option */ if (nd[opt].itm>=0) fprintf(stderr,""O"d isn't an option id!\n", opt); else print_option(opt+1,stderr,0,1); } @ The |print_option| routine has a sort of inverse, which reads from |buf| what purports to be the description of an option and verifies it. @= int read_option(void) { register int k,q,x,j,opt; for (opt=0,k=1;o,buf[k]>='0' && buf[k]<='9';k++) opt=10*opt+buf[k]-'0'; if ((o,buf[k]!=' ')||(o,buf[k+1]!='`')||(o,buf[k+2]!=' ')) return -1; for (k+=3,q=opt+1;o,(x=nd[q].itm)>0;q++) { oo,namebuf.lr.l=lname(x),namebuf.lr.r=rname(x); for (j=0;j<8;j++) { if (!namebuf.str[j]) break; if (o,namebuf.str[j]!=buf[k+j]) return -1; } k+=j; /* we've verified the item name */ if (o,nd[q].clr) { if ((o,buf[k]!=':')||(o,(unsigned char)buf[k+1]!=nd[q].clr)) return -1; k+=2; } if (o,buf[k++]!=' ') return -1; } if (buf[k]!='\'') return -1; return opt+1; } @ When I'm debugging, I might want to look at one of the current item lists. @= void print_itm(int c) { register int p; if (c=setlength || pos(c)<0 || pos(c)>=itemlength || item[pos(c)]!=c) { fprintf(stderr,"Illegal item "O"d!\n",c); return; } fprintf(stderr,"Item"); print_item_name(c,stderr); if (c=active) fprintf(stderr," (secondary "O"d, purified), length "O"d:\n", pos(c)+1,size(c)); else fprintf(stderr," (secondary "O"d), length "O"d:\n", pos(c)+1,size(c)); for (p=c;p= void sanity(void) { register int k,x,i,l,r,q,qq; for (k=0;kr) fprintf(stderr,"itm>loc in node "O"d!\n",i); else { if (set[r]!=i) { fprintf(stderr,"Bad loc field for option "O"d of item",r-l+1); print_item_name(l,stderr); fprintf(stderr," in node "O"d!\n",i); } if (pos(l)= twoints pool[poolsize]; /* where the linked lists live */ int poolptr=1; /* the first unused cell of |pool| */ int qfront,qrear; /* the front and rear of $Q$ */ unsigned int curstamp; /* the current ``time stamp'' */ unsigned int biggeststamp; /* the largest time stamp used so far */ unsigned int compatstamp; /* another stamp, used for compatibility tests */ @ A few basic primitive routines undergird all of our list processing. (When counting mems here, we consider |avail| and |poolptr| to be in global registers. The compiler could inline this code, so I don't count any overhead for these subroutine calls.) @d avail pool[0].r /* head of the stack of available cells */ @= int getavail(void) { /* return a pointer to an unused cell */ register int p; p=avail; if (p) { o,avail=link(p); return p; /* |info(p)| might be anything */ } if (poolptr++>=poolsize) { fprintf(stderr,"Pool overflow (poolsize="O"d)!\n",poolsize); exit(-7); } return poolptr-1; } @# void putavail(int p) { /* free the single cell |p| */ o,link(p)=avail; avail=p; } @ Entries of a trigger list are pairs $(o,p)$, with the cell that mentions option $o$ linking to the cell that mentions primary item~$p$. @= void print_trigger(int opt) { register int p,q; fprintf(stderr,"trigger stack for option "); print_option(opt+1,stderr,0,1); for (p=trigger(opt);p;p=link(q)) { q=link(p); fprintf(stderr," "); if (info(p)>=0) { print_option(info(p)+1,stderr,-1,1); fprintf(stderr,","); p=link(p); print_item_name(info(p),stderr); }@+else @; fprintf(stderr,"\n"); } } @ @= void print_triggers(int all) { register int opt,jj,optp; for (opt=0;opt=jj+size(jj)) continue; /* is |opt| in |jj|'s set? */ } print_trigger(opt); } } @ Entries of a fixit list are pairs $(o,p)$, with the cell that mentions option $o$ linking to the cell that mentions primary item~$p$. @= void print_fixit(int opt) { register int p,q; fprintf(stderr,"fixit stack for option "); print_option(opt+1,stderr,-1,1); fprintf(stderr,":"); for (p=fixit(opt);p;p=link(q)) { q=link(p); fprintf(stderr," "); print_item_name(info(q),stderr); fprintf(stderr,"["O"d]",info(p)); } fprintf(stderr,"\n"); } @ @= void print_queue(void) { register int p; for (p=qfront;p!=qrear;p=link(p)) print_option(info(p)+1,stderr,0,1); } @ Linked lists are wonderful; but a single weak link can cause a catastrophic error. Therefore, when debugging, I want to be extra sure that this program doesn't make any silly errors when it uses pool pointers. Furthermore, since I'm doing my own garbage collection, I want to avoid any ``memory leaks'' that would occur when I've forgotten to recycle a no-longer-used entry of the |pool|. The |list_check| routine laboriously goes through everything and makes sure that every cell less than |poolptr| currently has one and only one use. Warning: Do not call |list_check| at a busy time during which lists are being manipulated. Wait for a quiet time when all of the lists are supposedly stable and well-formed. @d leak_checking 0 /* set this nonzero if you suspect linked-list bugs */ @d signbit 0x8000000 @d vet_and_set(l) {@+if ((l)<=0 || (l)>=poolptr) { fprintf(stderr,"Bad link "O"d!\n",l); return; } if (link(l)&signbit) { fprintf(stderr,"Double link "O"d, "O"lld!\n",l,mems); return; } link(l)^=signbit; } @= void list_check(int count) { register int p,t,opt; for (t=0,p=avail;p;t++,p=signbit^link(p)) vet_and_set(p); if (count) fprintf(stderr,"avail size "O"d\n",t); for (opt=0;opt= if (++compatstamp==badstamp) { for (ii=0;ii= @; for (nn=opt+1;o,(ii=nd[nn].itm)>0;nn++) { o,mark(ii)=compatstamp; if (ii>=second) { if (o,nd[nn].clr) o,match(ii)=nd[nn].clr; else o,match(ii)=-1; /* this won't match any color */ } } @ At the beginning of this section, |nd[optp].itm| is an item |ii| in the middle of some option~$O'$. If $O'$ is compatible with |opt|, we want to reset |optp| so that |nd[optp]| is the spacer preceding~$O'$. We use the fact that |ii| isn't present in~|opt|. @= for (qq=optp,nn=qq+1;nn!=qq;nn++) { if (o,(jj=nd[nn].itm)<=0) optp=nn+jj-1,nn=optp; /* |nn| is a spacer */ else if (o,mark(jj)==compatstamp) { /* watch out, |jj| is in |opt| */ if (jj= while (1) { if (!fgets(buf,bufsize,stdin)) break; if (o,buf[p=strlen(buf)-1]!='\n') panic("Input line way too long"); for (p=0;o,isspace(buf[p]);p++) ; if (buf[p]=='|' || !buf[p]) continue; /* bypass comment or blank line */ last_itm=1; break; } if (!last_itm) panic("No items"); for (;o,buf[p];) { o,namebuf.lr.l=namebuf.lr.r=0; for (j=0;j<8 && (o,!isspace(buf[p+j]));j++) { if (buf[p+j]==':' || buf[p+j]=='|') panic("Illegal character in item name"); o,namebuf.str[j]=buf[p+j]; } if (j==8 && !isspace(buf[p+j])) panic("Item name too long"); oo,lname(last_itm<<2)=namebuf.lr.l,rname(last_itm<<2)=namebuf.lr.r; @; last_itm++; if (last_itm>max_cols) panic("Too many items"); for (p+=j+1;o,isspace(buf[p]);p++) ; if (buf[p]=='|') { if (second!=max_cols) panic("Item name line contains | twice"); second=last_itm; for (p++;o,isspace(buf[p]);p++) ; } } if (second==last_itm) second=max_cols; /* no secondaries actually named */ @ @= for (k=last_itm-1;k;k--) { if (o,lname(k<<2)!=namebuf.lr.l) continue; if (rname(k<<2)==namebuf.lr.r) break; } if (k) panic("Duplicate item name"); @ @= while (1) { if (!fgets(buf,bufsize,stdin)) break; if (o,buf[p=strlen(buf)-1]!='\n') panic("Option line too long"); for (p=0;o,isspace(buf[p]);p++) ; if (buf[p]=='|' || !buf[p]) continue; /* bypass comment or blank line */ i=last_node; /* remember the spacer at the left of this option */ for (pp=0;buf[p];) { o,namebuf.lr.l=namebuf.lr.r=0; for (j=0;j<8 && (o,!isspace(buf[p+j])) && buf[p+j]!=':';j++) o,namebuf.str[j]=buf[p+j]; if (!j) panic("Empty item name"); if (j==8 && !isspace(buf[p+j]) && buf[p+j]!=':') panic("Item name too long"); @; if (buf[p+j]==':') { if (k>=second) { if ((o,isspace(buf[p+j+1])) || (o,!isspace(buf[p+j+2]))) panic("Color must be a single character"); o,nd[last_node+(pp?0:1)].clr=(unsigned char)buf[p+j+1]; p+=2; }@+else panic("Primary item must be uncolored"); } for (p+=j+1;o,isspace(buf[p]);p++) ; } if (!pp) { if (vbose&show_warnings) fprintf(stderr,"Option ignored (no primary items): "O"s",buf); while (last_node>i) { @; last_node--; } }@+else { o,nd[i].loc=last_node-i; /* complete the previous spacer */ last_node++; /* create the next spacer */ if (last_node==max_nodes) panic("Too many nodes"); options++; o,nd[last_node].itm=i+1-last_node; } } @; @; @; @ We temporarily use |pos| to recognize duplicate items in an option. This program shifts the items of an option, if necessary, so that the very first item is always primary. In other words, secondary items that precede the first primary item are actually stored in |nd[last_node+1]|. @= for (k=(last_itm-1)<<2;k;k-=4) { if (o,lname(k)!=namebuf.lr.l) continue; if (rname(k)==namebuf.lr.r) break; } if (!k) panic("Unknown item name"); if (o,pos(k)>i) panic("Duplicate item name in this option"); last_node++; if (last_node+1>=max_nodes) panic("Too many nodes"); o,t=size(k); /* how many previous options have used this item? */ if (!pp) { /* no primary items seen yet */ if ((k>>2)>2,nd[i+1].loc=t,nd[i+1].clr=0; else oo,nd[last_node+1].itm=k>>2,nd[last_node+1].loc=t,nd[last_node+1].clr=0; }@+else oo,nd[last_node].itm=k>>2,nd[last_node].loc=t,nd[last_node].clr=0; o,size(k)=t+1, pos(k)=last_node; @ @= o,k=nd[last_node+1].itm<<2; oo,size(k)--,pos(k)=i-1; @ @= active=itemlength=last_itm-1; for (k=0,j=primextra;k= for (;k;k--) { o,j=item[k-1]; if (k==second) second=j; /* |second| is now an index into |set| */ oo,size(j)=size(k<<2); if (size(j)==0 && k<=osecond) baditem=k; o,pos(j)=k-1; oo,rname(j)=rname(k<<2),lname(j)=lname(k<<2); o,mark(j)=0; } @ @= for (k=1;k= { if (vbose&show_choices) { fprintf(stderr,"Item"); print_item_name(item[baditem-1],stderr); fprintf(stderr," has no options!\n"); } } @ The ``number of entries'' includes spacers (because {\mc DLX2} includes spacers in its reports). If you want to know the sum of the option lengths, just subtract the number of options. @= fprintf(stderr, "("O"lld options, "O"d+"O"d items, "O"d entries successfully read)\n", options,osecond,itemlength-osecond,last_node); @ The item lengths after input are shown (on request). But there's little use trying to show them after the process is done, since they are restored somewhat blindly. (Failures of the linked-list implementation in {\mc DLX2} could sometimes be detected by showing the final lengths; but that reasoning no longer applies.) @= { fprintf(stderr,"Item totals:"); for (k=0;k= int opt_out(int opt,int act,char*typ) { register int ii,jj,nn,nnp,p,q,qq,pp,ss,t,optp,cutoff,tmin=infinite_age; subroutine_overhead; if (vbose&show_purges) { fprintf(stderr," "O"d "O"s option ",cur_age,typ); print_option(opt+1,stderr,0,1); } @; o,age(opt)=cur_age; for (o,p=trigger(opt),pp=0; p;p=pp) { o,optp=info(p),q=link(p); o,ii=info(q),pp=link(q); if (optp<0) @; @; @; ooo,info(p)=opt,link(q)=fixit(optp); /* change trigger to fixit */ if (!fixit(optp)) { /* we should enqueue |optp| */ o,link(qrear)=getavail(),info(qrear)=optp,qrear=link(qrear); o,age(optp)=infinite_age; } o,fixit(optp)=p; continue; inactive:@+if (t<0) @; if (o,trig_head[t]==0) o,trig_tail[t]=q; oo,link(q)=trig_head[t],trig_head[t]=p; /* move trigger to temp list |t| */ if (t; totopts--; return 1; } @ @= int purge_the_option(register int opt,int act,char*typ) { /* |opt| isn't at the left spacer */ for (opt--;o,nd[opt].itm>0;opt--) ; return opt_out(opt,act,typ); } @ After a secondary item has been purified, we mustn't mess with its set. Secondary items that lie between |active| and the parameter |act| are in the process of being purified. @= for (nn=opt+1;o,(ii=nd[nn].itm)>0;nn++) { p=nd[nn].loc; if (p>=second && (o,pos(ii)>=act)) continue; /* |ii| already purified */ o,ss=size(ii)-1; if (ss==0 && p=maxl-show_choices_gap) { fprintf(stderr," can't cover"); print_item_name(ii,stderr); fprintf(stderr,"\n"); } @; } o,nnp=set[ii+ss]; o,size(ii)=ss; oo,set[ii+ss]=nn,set[p]=nnp; oo,nd[nn].loc=ii+ss,nd[nnp].loc=p; updates++; } @ We can't complete the current options to a viable set that's domain consistent. So all of the fixit lists remaining in the queue must go back into the trigger lists that triggered them. @= while (qfront!=qrear) { o,p=qfront,opt=info(p),qfront=link(p),putavail(p); @; } return 0; @ @= { for (o,p=fixit(opt); p; p=pp) { oo,optp=info(p), q=link(p), info(p)=opt; o,pp=link(q); /* |info(q)| is the same for triggers and fixits */ oo,link(q)=trigger(optp), trigger(optp)=p; } o,fixit(opt)=0; } @ An option with negative age will never be used, so we needn't trigger it. (I realized later that, in fact, an inactive option with age~0 will also remain inactive. So I could also have discarded a few more entries, and used $-c$ instead of $-c-1$ in hints. I've decided not to make this optimization, for fear of breaking something.) @= { putavail(p),putavail(q); continue; } @ The queue contains options where we've left holes in the support matrix. The fixit lists of those options tell us where those holes are. @= int empty_the_queue(void) { register int p,q,pp,qq,s,ss,ii,jj,nn,opt,optp; subroutine_overhead; while (qfront!=qrear) { o,p=qfront,opt=info(p),qfront=link(p),putavail(p); if (fixit(opt)==0) confusion("queue"); if (leak_checking) list_check(0); @; @; for (o,p=fixit(opt); p; p=pp) { o,q=link(p); /* ignore |info(p)|, which is irrelevant for now */ o,ii=info(q),pp=link(q); /* |ii| is a primary item, not in |opt| */ for (o,s=ii,ss=s+size(ii);s; } if (s==ss) { /* |opt| is inconsistent */ if (vbose&show_supports) { print_option(opt+1,stderr,-1,1); fprintf(stderr,","); print_item_name(ii,stderr); fprintf(stderr," not supported\n"); } fixit(opt)=p; @; if (!opt_out(opt,active,"purging")) return 0; break; /* move to another |opt| */ }@+else @; } o,fixit(opt)=0; } return 1; } @ Here's how we get the ball rolling by making every domain consistent in the first place. At the beginning, all |mark| fields are zero. @= int establish_dc(void) { register int k,ii,jj,nn,opt,optp,p,q,qq,s,ss; cur_age=-1; qfront=qrear=getavail(); for (opt=0;opt; for (k=0;k; } if (s==ss) { /* |opt| is inconsistent */ if (vbose&show_supports) { print_option(opt+1,stderr,-1,1); fprintf(stderr,","); print_item_name(ii,stderr); fprintf(stderr," not supported\n"); } if (!opt_out(opt,active,"purging")) return 0; break; /* move to the next |opt| */ }@+else { p=getavail(),q=getavail(); o,link(p)=q; o,info(q)=ii; @; } } } } return empty_the_queue(); } @ @= { totopts=options; if (!establish_dc()) { if (vbose&show_choices) fprintf(stderr,"Inconsistent options!\n"); goto done; } @; if (vbose&show_choices) fprintf(stderr,"Initial consistency after "O"lld mems.\n",mems); @; } @ The purged options that appear in trigger lists are useless baggage. @= { register int opt,optp,p,q,pp,qq; for (opt=0;opt=0) { for (o,p=trigger(opt),qq=-1;p;p=pp) { oo,optp=info(p),q=link(p),pp=link(q); if (o,age(optp)<0) { putavail(p),putavail(q); if (qq<0) o,trigger(opt)=pp; else o,link(qq)=pp; }@+else qq=q; } } } @ @= { if (vbose&show_supports) { print_option(opt+1,stderr,-1,1); fprintf(stderr,","); print_item_name(ii,stderr); fprintf(stderr," supported by "); print_option(optp+1,stderr,0,1); } o,info(p)=opt; oo,link(q)=trigger(optp); o,trigger(optp)=p; } @*A view from the top. Our strategy for generating all exact covers will be to repeatedly choose an item that appears to be hardest to cover, namely an item whose set is currently smallest, among all items that still need to be covered. And we explore all possibilities via depth-first search, in the following way: First we try using the first option in that item's set; then we explore the consequences of {\it forbidding\/} that item. The neat part of this algorithm is the way the sets are maintained. Depth-first search means last-in-first-out maintenance of data structures; and the sparse-set representations make it particularly easy to undo what we've done at less-deep levels. The basic operation is ``covering'' each item of a chosen option. Covering means to make an item inactive. If it is primary, we remove it from the set of items needing to be covered, and we block all other options that contain it. If the item is secondary and still active (not yet purified), we block all options in which it has the wrong color. The branching discipline that we follow is quite different from what we did in {\mc DLX2} or {\mc SSXCC}, however, because we're now maintaining domain consistency throughout the search. The old way was to choose a ``best item''~$p$, having say~$d$ options, and then to try option 1 of the $d$~possibilities for~$p$, then option 2 of those~$d$, \dots, option $d$ of those~$d$, before backtracking to the previous level. The new way, given consistent domains, starts out the same as before. We choose a best item~$p_1$, having $d_1$ options, and we try its first option. But after returning from that branch, we remove that option and restore domain consistency; then we choose a new best item~$p_2$, having $d_2$ options, and try the first of those. Eventually, after trying and removing the first remaining options of $p_1$ through~$p_k$, we'll reach a point where we can't make the remaining domains both consistent and nonempty. That's when we back up. In this scenario, all of the subproblems for $p_1$, \dots, $p_k$ are trying to extend the same partial solution with $s$ choices to a partial solution that has $s+1$ choices. We call this ``stage $s$'' of the search. Stage $s$ actually involves $k$ different nodes of the (binary) search tree, each of which is on its own ``level.'' (The level is the distance from the root; the stage is the number of options that have been chosen in the current partial solution.) We might think of the search as a tree that makes a $k$-way branch at stage~$s$, instead of as a tree that makes binary branches at each level. Such an interpretation is equivalent to the ``natural correspondence'' between ordinary trees and binary trees, discussed in {\sl TAOCP\/} Section 2.3.2. @ As search proceeds, the current subproblem gets easier and easier as the number of active items and options gets smaller and smaller. Let $I_s$ be the set of all items that are active when $s$ options $c_1$, \dots,~$c_s$ have been chosen to be in the partial solution-so-far. Thus $I_0$ is the set of all items initially given; and $I_s$ for $s>0$ is obtained from $I_{s-1}$ by removing the primary items and the previously unpurified secondary items of~$c_s$. We denote the primary items of~$I_s$ by $P_s$; these are the primary items not in $c_1$, \dots,~$c_s$. Let $O_{-1}$ be the set of all options actually given. Just before entering stage~0, we reduce $O_{-1}$ to \def\init{^{\rm init}}% $O_0\init$, the largest subset of $O_{-1}$ that is domain consistent, by purging options that have no support. In general, stage~$s$ begins with a domain-consistent set of options $O_s\init$, which is the largest such set that's compatible with $c_1$, \dots,~$c_s$. Later on in stage~$s$ we usually work with a smaller set of active options $O_s$, which is the largest domain-consistent set that's contained in $O_s\init$ after we've removed the options whose consequences as potential choices were previously examined in this stage. If every item in $P_s$ still belongs to at least one option of~$O_s$, we're ready to make a new~$c_{s+1}$ from among those remaining options. We get $O_{s+1}\init$ from $O_s$ by choosing $c_{s+1}$ and blocking every option incompatible with it, and then by purging options that aren't domain-consistent. Thus when we're in stage~$s$, there's a sequence of sets of options $$O_{-1}\supseteq O_0\init \supseteq O_0 \supset O_1\init \supseteq O_1\supset\cdots\supset O_s\init \supseteq O_s,$$ all of which are domain consistent except possibly $O_{-1}$. Notice that $$\hbox{if $o\in O_s\init$ and $p\in o$ then $p\in P_s$.}$$ And there's good news: The support array $S[o,p]$ follows the nested structure of our search in a useful way. Recall that $S[o,p]=\#$ if $p\in o$; otherwise $S[o,p]=o'$, where $p\in o'$ and $o'$ is compatible with~$o$. This array is defined for all options $o\in O_0\init$, and for all primary items $p\in P_0$. However, when we enter stage~$s$, we're interested only in the much smaller subarray that contains supports when $o\in O_s\init$ and $p\in P_s$. And when we're transitioning from stage~$s$ to stage~$s+1$, we care only about a still-smaller subarray, for $o\in O_s$ and $p\in P_s$. In particular, domain consistency implies that we have $$\eqalign{ &\hbox{if $o\in O_s\init$ and $p\notin o$ and $p\in P_s$ then } S[o,p]\in O_s\init;\cr &\hbox{if $o\in O_s$ and $p\notin o$ and $p\in P_s$ then } S[o,p]\in O_s.\cr}$$ @ Eventually a choice will fail, of course. Backtracking becomes necessary in two distinct ways: \ (1)~If we've settled on a new~$c_s$ among the options of $O_s$, but we're unable to reduce the remaining compatible options to a domain-consistent $O_{s+1}\init$ without emptying some domain, we ``backtrack in stage~$s$'' and reject that choice. (Thus, we stay in stage~$s$ but move to a new level; the active items remain the same.) \ (2)~If we've finished exploring a choice from $O_s$ and are unable to reduce the other options to a smaller domain-consistent~$O_s$, we ``backtrack to stage~$s-1$'' and reject~$c_{s-1}$. (Thus, we resume where we left off at the previous stage's deepest level; the active items revert back from $P_s$ to the larger set~$P_{s-1}$.) I wish I could say that it was easy for me to discover the programming logic just described. I~guess it was my baptism into what researchers have called ``fine-grained'' versus ``coarse-grained'' algorithms. Notice that when we backtrack, we need not change the $S$ array in any way. A support is always a support. Thus there's no point in trying to undo any of the changes we've made to the current support structure. @*The triggering. Suppose there are 1000 options and 100 items. Then the $S$ array has 100,000 entries, most of which are supports (that is, not~\#). Every support is an entry in a trigger list; hence the trigger lists are necessarily long. The task of maintaining domain consistency might therefore seem hopelessly inefficient. On the other hand, after we've made some choices, there may be only 100 options left, and perhaps 30 items not yet covered. Then at most 3000 supports are relevant, and most of the information in trigger lists is of no interest to us. An efficient scheme might therefore still be possible, if we can figure out a way to avoid looking at useless triggers. Ideally we'd like options from $O_s$ to appear at the top of each trigger stack, with options from $O_s\init$ just below them, and with $O_{s-1}$, $O_{s-1}\init$, \dots, $O_0$, $O_0\init$ furthest down. The pairs $(o,p)$ of interest would then appear only near the top. Unfortunately such an arrangement cannot be guaranteed. Indeed, that's obvious: The trigger-list entries occur in essentially arbitrary order when we first form $O_0\init$. If they happen to be supports that work for every subsequent stage, no changes to the trigger lists will be needed, and we won't even want to look at those lists. We can, however, come sort of close to an ideal arrangement, by exploiting the fact that every option not in the current $O_s$ has been deactivated at least once. We look at \\{trigger}$(o)$ only after $o$~has become inactive; and at that time we can reorder its entries. Therefore this program inserts markers into the trigger lists, saying that ``all further entries of this list are young'' (meaning deactivated early, hence uninteresting until we've backtracked to an early stage). Every such marker is accompanied by a time stamp, so that we can recognize later when its message is no longer~true. @ When deactivating an option from $O_s\init$ that won't be in~$O_s$, the ``current age'' |cur_age| is $2s$. And when deactivating an option from $O_s$ that won't be in~$O_{s+1}\init$ it is $2s+1$. Thus an inactive option is in $O_s\init$ if and only if its age is $\ge2s$; and it's in $O_s$ if and only if its age is $\ge2s+1$. Incidentally, I've tried to avoid making bad puns based on |cur_age| versus courage, or \\{age} versus~\\{stage}. @ A negative entry |optp=-c| in a trigger list is a hint that all future entries will have age less than~$c$. The search tree may have changed since this hint was put into the list; so we must look at the relevant stage stamp, to ensure that the hint is still valid. Suppose $o$ has age $2s$. Then $o$ is in $O_s\init$ but not in $O_s$. As computation proceeds, without backtracking to stage~$s-1$, the set $O_s$ might get smaller and smaller, but $o$ will still not be in~$O_s$. Therefore a trigger hint saying that $o$ is inactive will be valid until |stagestamp[s]| changes. (More precisely: If we backtrack to stage~$s-1$, |stagestamp[s]| won't change until we progress again to stage~$s$; before that time, we won't be looking at the hint.) Suppose $o$ has age $2s+1$. Then $o$ is in $O_s$ but not in $O_{s+1}\init$. As computation proceeds, without backtracking in or to stage~$s$, the set $O_{s+1}\init$ won't change. Therefore a trigger hint saying that $o$ is inactive will be valid until |stagestamp[s+1]| changes. That's why the following code says `|(cutoff+1)>>1|' when selecting the relevant stage stamp. @= { cutoff=-optp-1; if (cutoff>1])) { pp=p; break; } putavail(p),putavail(q); /* discard an obsolete hint */ continue; /* and ignore it */ } @ If |optp| is inactive, it has been purged and its recorded age is |cur_age| or less. Thus we can conclude that |optp| is active whenever |age(optp)>cur_age|. In general, of course, that age test won't be conclusive and a slightly more expensive test needs to be made by looking further into the data structures. Option |optp| is active if and only if it appears in the current set of its first item. (This is where we use the fact that the first item of |optp| is primary.) @= o,t=age(optp); if (t<=cur_age) { o,jj=nd[optp+1].itm; /* |jj| is |optp|'s first item */ if (o,nd[optp+1].loc>=jj+size(jj)) goto inactive; } /* branch if |optp| was removed from |jj|'s set */ @ When the trigger list for |opt| refers to an item |ii|, that item is in |opt|. Suppose |ii| is currently inactive; then we wouldn't be purging |opt| unless |ii| has just become inactive (and we're calling |opt_out| from within |include_option|). @= if (o,pos(ii)>=active) { if (pos(ii)>=act) confusion("active"); t=cur_age; goto inactive; } @ When we get here, |pp| is either zero or the cell where we found |cutoff|. In the latter case, |pp=p| and |link(p)=q|; thus the cutoff hint is in |p| and~|q|. All of the unused trigger entries have been redirected to the |trig_head| lists, sorted by their age. @= if (pp==0) cutoff=-1; if (tmin<=cutoff) { if (tmin>1],link(q)=trig_head[t]; o,trig_head[t]=0; pp=p; } if (trig_head[cur_age]) { oo,link(trig_tail[cur_age])=pp; /* give no hint for inactive options of the current age */ o,pp=trig_head[cur_age],trig_head[cur_age]=0; } o,trigger(opt)=pp; @ @= { fprintf(stderr,"cutoff for age "O"d",-info(p)-1); if (info(q)!=stagestamp[(-info(p))>>1]) fprintf(stderr," (obsolete)"); } @ At this point we want |curstamp| to have a value that's larger than anything found in a trigger list~hint. Moreover, the values of |stagestamp[0]|, \dots, |stagestamp[stage-1]| should all be distinct and less than |curstamp|, because they might be used in future hints. We may not be able to satisfy those conditions when |badstamp| is a small positive constant! But we will have checked out the following code at least once before failing. @= if (++biggeststamp==badstamp) { if (badstamp>0 && stage>=badstamp) { fprintf(stderr,"Timestamp overflow (badstamp="O"d)!\n",badstamp); exit(-11); } @; for (k=0;k= for (k=0;k= if (o,age(opt)!=infinite_age) { @; continue; } @*The dancing. @= level=stage=-1; newstage:@+@; newlevel: nodes++; @; if (vbose&show_profile) profile[stage]++; if (sanity_checking) sanity(); if (leak_checking) list_check(0); @; if (stage; tmems=mems; if (vbose&show_option_counts) fprintf(stderr,"Level "O"d, stage "O"d, "O"d options, "O"d items\n", level,stage,totopts,active); @; bmems+=mems-tmems; if (stage==xcutoff) @; if (t==infty) @; oo,choice[level]=cur_choice=set[best_itm]; got_choice:@+o,deg[level]=t; if (t==1) o,saved[stage]=saveptr; else @; cur_age=stage+stage+1; tmems=mems; if (!include_option(cur_choice)) { nmems+=mems-tmems; goto tryagain; } if (!empty_the_queue()) { nmems+=mems-tmems; goto tryagain; } goto newstage; tryagain:@+if (t==1) goto backup; if (vbose&show_choices) fprintf(stderr,"Backtracking in stage "O"d\n",stage); goto purgeit; backup:@+if (--stage; new_age: cur_age=stage+stage; tmems=mems; if (!(o,purge_the_option(choice[level],active,"removing"))) { pmems+=mems-tmems; goto backup; } if (!empty_the_queue()) { pmems+=mems-tmems; goto backup; } goto newlevel; @ We save the sizes of active items on |savestack|, whose entries have two fields |l| and |r|, for an item and its size. This stack makes it easy to undo all deletions, by simply restoring the former sizes. @= int stage; /* number of choices in current partial solution */ int level; /* current depth in the search tree (which is binary) */ int cur_age; /* current |stage| or |stage+1/2| (times 2) */ int choice[max_level]; /* the option and item chosen on each level */ int deg[max_level]; /* the number of options that item had at the time */ int saved[max_stage]; /* size of |savestack| at each stage */ int levelstage[max_stage]; /* the most recent level at each stage */ int stagelevel[max_level]; /* the stage that corresponds to each level */ int levelopts[max_level]; /* options remaining at each level */ int stagestamp[max_stage]; /* timestamp that's current at each stage */ ullng profile[max_stage]={1}; /* number of search tree nodes on each stage */ twoints savestack[savesize]; int saveptr; /* current size of |savestack| */ int trig_head[infinite_age],trig_tail[infinite_age]; /* in |opt_out| */ @ @= if (++stage>maxs) { if (stage>=max_stage) { fprintf(stderr,"Too many stages!\n"); exit(-40); } maxs=stage; } @; o,stagestamp[stage]=curstamp; @ @= if (++level>maxl) { if (level>=max_level) { fprintf(stderr,"Too many levels!\n"); exit(-4); } maxl=level; } oo,stagelevel[level]=stage,levelstage[stage]=level; if (vbose&show_option_counts) levelopts[level]=totopts; @ @= if (delta && (mems>=thresh)) { thresh+=delta; if (vbose&show_full_state) print_state(); else print_progress(); } if (mems>=timeout) { fprintf(stderr,"TIMEOUT!\n");@+goto done; } @ This is where we extend the partial solution. Notice a tricky point: We must go through the sets from right to left, because the options we block move right as they leave the set. @= int include_option(int opt) { register int c,cc,k,p,q,pp,s,ss,optp; subroutine_overhead; if (vbose&show_choices) { fprintf(stderr,"S"O"d:",stage); print_option(opt,stderr,1,0); } for (opt--;o,nd[opt].itm>0;opt--) ; /* move back to the spacer */ @; for (k=active;k=second && (o,c=match(s))) { /* we must purify |s| */ for (;ss>=s;ss--) { o,optp=set[ss]; if ((o,nd[optp].clr!=c) && !purge_the_option(optp,oactive,"blocking")) return 0; } }@+else for (;ss>=s;ss--) { o,optp=set[ss]-1; while (o,nd[optp].itm>0) optp--; /* move to the spacer */ if (optp!=opt && !opt_out(optp,oactive,"blocking")) return 0; } } @; return 1; } @ An item becomes inactive when it becomes part of the solution-so-far (hence it leaves the problem-that-remains). Active primary items are those that haven't yet been covered. Active secondary items are those that haven't yet been purified. The active items are the first |active| entries of the |item| list. At one time I thought it would be wise to keep primary and secondary items separate, using a sparse-set discipline independently on each sector. But I found that the time spent in maintaining and searching the active list was negligible in comparison with the overall running time; so I've kept the implementation simple. At this point in the computation, an item of |opt| will be inactive if and only if it is secondary and purified, because we are including |opt| in the partial solution. @= p=oactive=active; for (q=opt+1;o,(c=nd[q].itm)>0;q++) { o,pp=pos(c); if (pp=second) oo,match(c)=nd[q].clr; oo,pos(cc)=pp,pos(c)=p; updates++; } } active=p; @ This program differs from {\mc SSXCC} in one significant way: It makes option |opt| inactive. In particular, it makes all of |opt|'s items have size~0, except for unpurified secondaries. (Thus, we essentially say that newly assigned variables---the inactivated primary items---should have empty domains when they leave the current subproblem, while {\mc SSXCC} left them with domains of size~1.) It would be a mistake to call |opt_out(opt,oactive)|, of course, because that procedure doesn't want any primary items to become optionless. On the contrary, we have precisely the opposite goal: We {\it celebrate\/} the fact that all of the primaries in |opt| have become covered. We don't have to change |trigger(opt)|, because no active options involve inactive primary items. @= for (k=active;k=second) continue; if (size(s)!=1) confusion("include"); o,size(s)=0; } if (vbose&show_purges) { fprintf(stderr," "O"d choosing option ",cur_age); print_option(opt+1,stderr,0,1); } o,age(opt)=cur_age; totopts--; @ The ``best item'' is considered to be an item that minimizes the number of remaining choices. If there are several candidates, we choose the first one that we encounter. Each primary item should have at least one valid choice, because of domain consistency. @d infty 0x7fffffff @= t=infty; if ((vbose&show_details) && level=maxl-show_choices_gap) fprintf(stderr,"Stage "O"d,",stage); for (k=0;t>1 && k=maxl-show_choices_gap) { print_item_name(item[k],stderr); fprintf(stderr,"("O"d)",s); } if (s<=t) { if (s==0) fprintf(stderr,"I'm confused.\n"); /* |hide| missed this */ if (s=maxl-show_choices_gap) { if (t==infty) fprintf(stderr," solution\n"); else { fprintf(stderr," branching on"); print_item_name(best_itm,stderr); fprintf(stderr,"("O"d)\n",t); } } if (t>maxdeg && t= { count++; if (spacing && (count mod spacing==0)) { printf(""O"lld:\n",count); for (k=0;k=maxcount) goto done; goto backup; } @ @= { o,saved[stage]=saveptr; if (saveptr+active>maxsaveptr) { if (saveptr+active>=savesize) { fprintf(stderr,"Stack overflow (savesize="O"d)!\n",savesize); exit(-5); } maxsaveptr=saveptr+active; } for (p=0;p= o,active=saveptr-saved[stage]; saveptr=saved[stage]; for (p=0;p= void print_savestack(int start,int stop) { register int k; for (k=start;k= void print_state(void) { register int l,s; fprintf(stderr,"Current state (level "O"d, stage "O"d):\n",level,stage); for (l=0;l=show_levels_max) { fprintf(stderr," ...\n"); break; } } fprintf(stderr," "O"lld solutions, "O"lld mems, and max level "O"d so far.\n", count,mems,maxl); } @ During a long run, it's helpful to have some way to measure progress. The following routine prints a string that indicates roughly where we are in the search tree. The string consists of node degrees, preceded by `\.{\char`\~}' if the node wasn't the current node in its stage (that is, if the node represents an option that has already been fully explored --- ``we've been there done that''). Following that string, a fractional estimate of total progress is computed, based on the na{\"\i}ve assumption that the search tree has a uniform branching structure. If the tree consists of a single node, this estimate is~.5. Otherwise, if the first choice is the $k$th choice in stage~0 and has degree~$d$, the estimate is $(k-1)/(d+k-1)$ plus $1/(d+k-1)$ times the recursively evaluated estimate for the $k$th subtree. (This estimate might obviously be very misleading, in some cases, but at least it tends to grow monotonically.) Fine point: If we've just backtracked within stage |stage|, the string of node degrees with end with a `\.{\char`\~}' entry, and we haven't yet made {\it any\/} choice in the current~stage. The test `|l==level-1|' below uses the fact that |levelstage[stage]=level| to adjust the fractional estimate appropriately for the partial progress in the current stage. @= void print_progress(void) { register int l,ll,k,d,c,p,ds=0; register double f,fd; fprintf(stderr," after "O"lld mems: "O"lld sols,",mems,count); if (stage=0 && stagelevel[ll]==stagelevel[l]; k++,d++,ll--) ; fd*=d,f+=(k-1)/fd; /* choice |l| is treated like |k| of |d| */ } if (l>=show_levels_max+levelstage[groundstage] && !ds) ds=1,fprintf(stderr,"..."); } fprintf(stderr," "O".5f\n",f+0.5/fd); } } @ @= { fprintf(stderr,"Profile:\n"); for (k=0;k<=maxs;k++) fprintf(stderr,""O"3d: "O"lld\n", k,profile[k]); } @ I'm experimenting with a mechanism by which partial solutions of a large problem can be saved to temporary files and computed separately --- for example, by a cluster of computers working in parallel. Each partial solution can be completed to full solutions when this program is run with one of the files output here, using \.X$\langle\,$filename$\,\rangle$ on the command line. @= { @; fprintf(xcutoff_file,"Resume at stage "O"d\n",stage); for (k=0;k0;j--) ; putc(levelstage[stagelevel[k]]!=k? '-': '+', xcutoff_file); print_option(j,xcutoff_file,0,1); } fclose(xcutoff_file); xcount++; goto backup; } @ @d part_file_prefix "/tmp/part" /* should be at most 10 or so characters */ @d part_file_name_size 20 @= k=sprintf(xcutoff_name,part_file_prefix O"d",xcount); xcutoff_file=fopen(xcutoff_name,"w"); if (!xcutoff_file) { fprintf(stderr,"Sorry, I can't open file `"O"s' for writing!\n",xcutoff_name); exit(-1); } @ @= strncpy(xcutoff_name,argv[j]+1,part_file_name_size-1); xcutoff_file=fopen(xcutoff_name,"r"); if (!xcutoff_file) fprintf(stderr,"Sorry, I can't open file `"O"s' for reading!\n", xcutoff_name); if (fgets(buf,bufsize,xcutoff_file)) { if (strncmp(buf,"Resume at stage ",16)==0) { for (groundstage=0,i=16;o,buf[i]>='0' && buf[i]<='9';i++) groundstage=10*groundstage+buf[i]-'0'; if (vbose&show_basics) fprintf(stderr, "Resuming at stage "O"d\n",groundstage); } } break; @ @= { if (!fgets(buf,bufsize,xcutoff_file)) confusion("resuming"); o,choice[level]=cur_choice=read_option(); if (cur_choice<0) { fprintf(stderr,"Misformatted option in file `"O"s':\n",xcutoff_name); fprintf(stderr,""O"s",buf); exit(-1); } t=1; if (o,buf[0]=='+') goto got_choice; goto new_age; } @ @= fprintf(stderr, "Partial solutions saved on "part_file_prefix"0.."O"s.\n",xcutoff_name); @ @= char xcutoff_name[part_file_name_size]; FILE *xcutoff_file; int groundstage; /* the stage where calculation begins or resumes */ @*Index.