@x sprintf(tet[q].aux,""O"c"O"c"O"c",encode(i+1),encode(j+1),encode(k+1)); @y optloc[i][j][k]=q; sprintf(tet[q].aux,""O"c"O"c"O"c",encode(i+1),encode(j+1),encode(k+1)); @z @x o,trail[trailptr++]=opt; @y o,trail[trailptr++]=opt; @; @z @x active+=3; /* hooray for the sparse-set technique */ @y @; active+=3; /* hooray for the sparse-set technique */ @z @x @*Miscellaneous loose ends. In a long run, it's nice to know @y @*A hoped-for speedup. We might perhaps be able to cut the running time approximately in half, if it turns out that every solution contains a $2\times2$ latin square in rows $(i,i')$ and columns $(j,j')$. The entries in that $2\times2$ square can then be swapped, and we can obtain all solutions by looking at only half of them. For example, consider the $4\times4$ problem \def\\#1/#2/#3/#4/{\vcenter{\offinterlineskip \halign{\vphantom(\tt##\cr#1\cr#2\cr#3\cr#4\cr}}\,} \\12../21../..../..../,\quad \hbox{ which has 8 solutions }\quad \\1234/2143/3412/4321/,\quad \\1234/2143/3421/4312/,\quad \\1234/2143/4312/3421/,\quad \\1234/2143/4321/3412/,\quad \\1243/2134/3412/4321/,\quad \\1243/2134/3421/4312/,\quad \\1243/2134/4312/3421/,\quad \\1243/2134/4321/3412/. Since this one has three independent $2\times2$ subsquares, we can reduce all eight solutions to a single one. The general idea is to find sets of six indices $i$, $j$, $k$, $i'$, $j'$, $k'$ such that $i= { register ii,jj,kk; if (showprunes) fprintf(stderr,"potential swaps:\n"); for (i=0;i; if (showprunes) print_swap_quad(swapptr-swapitemsize+4); } } } } } } } fprintf(stderr,"(I found "O"d potential swaps)\n",swapcount); @ Each possible swap record will occupy 17 positions of the |swap| array. The first four of these point respectively to options$ijk$,$ij'k'$,$i'jk'$, and$i'j'k$. The next is a counter, which will trigger the appropriate action when it gets large enough. Then come four entries of the form$(\\{count},\\{inc}.\\{next})\$, which are commands linked to the four options; they mean add \\{inc} to \\swap(\\count), then go to \\swap(\\next) for the next such command.'' The |down| field of an option links to the quadruples containing that option. @d swapitemsize 17 @d maxswaps 100000 @= { if (++swapcount>=maxswaps) { fprintf(stderr,"Too many swaps! (max="O"d)\n",maxswaps); exit(-668); } oo,swap[swapptr]=optloc[i][j][k]; oo,swap[swapptr+1]=optloc[i][jj][kk]; oo,swap[swapptr+2]=optloc[ii][j][kk]; oo,swap[swapptr+3]=optloc[ii][jj][k]; o,swap[swapptr+5]=swapptr+4; o,swap[swapptr+6]=0x10; oo,swap[swapptr+7]=tet[optloc[i][j][k]].down; o,tet[optloc[i][j][k]].down=swapptr+5; o,swap[swapptr+8]=swapptr+4; o,swap[swapptr+9]=0x11; oo,swap[swapptr+10]=tet[optloc[i][jj][kk]].down; o,tet[optloc[i][jj][kk]].down=swapptr+8; o,swap[swapptr+11]=swapptr+4; o,swap[swapptr+12]=0x12; oo,swap[swapptr+13]=tet[optloc[ii][j][kk]].down; o,tet[optloc[ii][j][kk]].down=swapptr+11; o,swap[swapptr+14]=swapptr+4; o,swap[swapptr+15]=0x13; oo,swap[swapptr+16]=tet[optloc[ii][jj][k]].down; o,tet[optloc[ii][jj][k]].down=swapptr+14; swapptr+=swapitemsize; } @ @= void print_swap_quad(int p) { fprintf(stderr," "O"s "O"s "O"s "O"s "O"02x\n", tet[swap[p-4]].aux,tet[swap[p-3]].aux, tet[swap[p-2]].aux,tet[swap[p-1]].aux,swap[p]); } @# void print_swap_list(int t) { register int q; fprintf(stderr,"swap quads for "O"s:\n",tet[t].aux); for (q=tet[t].down;q;q=swap[q+2]) print_swap_quad(swap[q]); } @ The mechanism for avoiding forbidden quadruples of options is similar to what we've done before: Whenever an option is forced, we add to the counter for each of the quadruples that contain it. And if that counter reaches~three, we'll hide the fourth option. (Each option is well separated from the options that participate in other parts of the forcing operation.) The |up| field of an option is set nonzero when that option has been hidden although its variables may be active. When we fetch three consecutive items in the |swap| array, the cost is only two mems. I hope the reader enjoys looking into the code in this step! @= stack=0; for (o,q=tet[opt].down;q;o,q=swap[q+2]) { oo,p=swap[q],swap[p]+=swap[q+1]; /* see the note about mems above */ if (swap[p]>=0x30) { /* we've chosen three options of a quad */ o,t=swap[p+0x32-swap[p]]; /* the unchosen option(!) */ o,tip[stack++]=t; } } while (stack) { o,t=tip[--stack]; oo,tet[t].up++; if (tet[t].up>1) continue; /* option |t| was already hidden */ ooo,pij=tet[t+1].itm,rik=tet[t+2].itm,cjk=tet[t+3].itm; if ((o,var[pij].pos>=active) || (o,var[rik].pos>=active) || (o,var[cjk].pos>=active)) continue; /* option |t| isn't active */ if (showprunes) fprintf(stderr,"swap disables "O"s\n",tet[t].aux); t++;@; t++;@; t++;@; } @ @= stack=0; for (o,q=tet[opt].down;q;o,q=swap[q+2]) { o,p=swap[q]; if (swap[p]>=0x30) { /* we've chosen three options of a quad */ o,t=swap[p+0x32-swap[p]]; /* the unchosen option(!) */ o,tip[stack++]=t; } o,swap[p]-=swap[q+1]; /* see the note about mems above */ } for (s=0;s