@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;
 @<check for swap prevention@>;
@z
@x
 active+=3; /* hooray for the sparse-set technique */
@y
 @<check for swap unprevention@>;
 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<i',ドル $j<j',ドル $k<k',ドル and to forbid all solutions that contain all four of the options $$ijk,\qquad ij'k',\qquad i'jk',\qquad i'j'k.$$ (That would rule out all but the last solution above.) The situation gets more complicated when the 2ドル\times2$ subsquares overlap. Consider the 5ドル\times5$ problem $$\def\\#1/#2/#3/#4/#5/{\vcenter{\offinterlineskip \halign{\vphantom(\tt##\cr#1\cr#2\cr#3\cr#4\cr#5\cr}},円} \\...../..453/.5.24/.35.2/.423./, \hbox{ which has 5 solutions }\quad \12345円/21453/35124/43512/54231/,\quad \21345円/12453/35124/43512/54231/,\quad \32145円/21453/15324/43512/54231/,\quad \42315円/21453/35124/13542/54231/,\quad \52341円/21453/35124/43512/14235/.$$ The first one was five swappable subsquares, but all five of them are ruled out. The other four solutions each have one swappable subsquare, and that subsquare is perfectly legal. So in this case the number of solutions goes down only from 5 to~4. On the other hand, if we change the order of the digits in that example, by complementing them with respect to 6, we get $$\def\\#1/#2/#3/#4/#5/{\vcenter{\offinterlineskip \halign{\vphantom(\tt##\cr#1\cr#2\cr#3\cr#4\cr#5\cr}},円} \\...../..213/.1.42/.31.4/.243./, \hbox{ which has 5 solutions }\quad \54321円/45213/31542/23154/12435/,\quad \45321円/54213/31542/23154/12435/,\quad \34521円/45213/51342/23154/12435/,\quad \24351円/45213/31542/53124/12435/,\quad \14325円/45213/31542/23154/52431/.$$ In this example only the first case is legal; the other four cases are omitted. @ In general, let's say that two latin squares are ``swap-equivalent'' if we can transform one to the other by some sequence of 2ドル\times2$ swaps. All five of the solutions in our 5ドル\times5$ example are swap-equivalent; in fact, the first one gives any of the other four after just one swap. If we replace an illegal 2ドル\times2$ subsquare by a legal one, we increase the entries of the overall square lexicographically. Therefore we don't paint ourselves into a corner: every swap-equivalence class is represented by at least one solution. (This idea is a special case of the general principle of reducing solutions by endomorphisms, as discussed on pages 107--111 of {\sl The Art of Computer Programming}, Volume~4, Fascicle~6.) @ To implement these ideas, we must start by discovering all of the potential places for swapping. @<init...@>=
{
 register ii,jj,kk;
 if (showprunes) fprintf(stderr,"potential swaps:\n");
 for (i=0;i<n;i++) for (j=0;j<n;j++) if (o,P[i][j]) { for (k=0;k<n;k++) if (o,optloc[i][j][k]) { for (jj=j+1;jj<n;jj++) if (o,P[i][jj]) { for (kk=k+1;kk<n;kk++) if (o,optloc[i][jj][kk]) { for (ii=i+1;ii<n;ii++) if (o,optloc[ii][j][kk]) { if (o,optloc[ii][jj][k]) { @<create the swap record for $(i,j,k,i',j',k')$@>;
 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 &#124;swap&#124; 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 &#124;down&#124; field of an option links to the quadruples containing
that option.
@d swapitemsize 17
@d maxswaps 100000
@<create the swap record for $(i,j,k,i',j',k')$@>=
{
 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;
}
 
@ @<sub...@>=
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 &#124;up&#124; 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 &#124;swap&#124; array,
the cost is only two mems.
I hope the reader enjoys looking into the code in this step!
@<check for swap prevention@>=
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 &#124;t&#124; 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) &#124;&#124;
 (o,var[rik].pos>=active) &#124;&#124;
 (o,var[cjk].pos>=active)) continue; /* option &#124;t&#124; isn't active */ 
 if (showprunes) fprintf(stderr,"swap disables "O"s\n",tet[t].aux);
 t++;@<hide the tetrad &#124;t&#124;@>;
 t++;@<hide the tetrad &#124;t&#124;@>;
 t++;@<hide the tetrad &#124;t&#124;@>;
} 
@ @<check for swap unprevention@>=
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<stack;s++) { /* unhide in the opposite order */ o,t=tip[s]; oo,tet[t].up--; if (tet[t].up) continue; /* option &#124;t&#124; had already been hidden */ ooo,pij=tet[t+1].itm,rik=tet[t+2].itm,cjk=tet[t+3].itm; if ((o,var[pij].pos>=active) &#124;&#124;
 (o,var[rik].pos>=active) &#124;&#124;
 (o,var[cjk].pos>=active)) continue; /* option &#124;t&#124; wasn't active */ 
 t+=3;@<unhide the tetrad &#124;t&#124;@>;
 t--;@<unhide the tetrad &#124;t&#124;@>;
 t--;@<unhide the tetrad &#124;t&#124;@>;
} 
@ @<glob...@>=
int optloc[maxn][maxn][maxn];
int swapcount,swapptr;
int swap[swapitemsize*maxswaps];
int tip[maxn*maxn*maxn];
@*Miscellaneous loose ends. In a long run, it's nice to know
@z
</div><div class="naked_ctrl">
<form action="/index.cgi/speech" method="get" name="gate">
<p><a href="http://altstyle.alfasado.net">AltStyle</a> によって変換されたページ <a href="https://cs.stanford.edu/~knuth/programs/partial-latin-gad-swap.ch">(-&gt;オリジナル)</a>
/ <label>アドレス: <input type="text" name="naked_post_url" value="https://cs.stanford.edu/~knuth/programs/partial-latin-gad-swap.ch" size="22" /></label> <label>モード: <select name="naked_post_mode">
<option value="default">デフォルト</option>
<option value="speech" selected="selected">音声ブラウザ</option>
<option value="ruby">ルビ付き</option>
<option value="contrast">配色反転</option>
<option value="larger-text">文字拡大</option>
<option value="mobile">モバイル</option>
</select>
<input type="submit" value="表示" />
</p>
</form>
</div>