\datethis @s mod and \let\Xmod=\bmod % this is CWEB magic for using "mod" instead of "%" \def\sqprod{\setbox0=\hbox{\kern-.13em$\times$\kern-.13em} \dimen0=\ht0 \advance\dimen0 -.09em \ht0=\dimen0 \dimen0=\dp0 \advance\dimen0 -.09em \dp0=\dimen0 \mathbin{\vcenter{\hrule\kern-.4pt \hbox{\vrule\kern-.4pt\phantom{$\box0$}\kern-.4pt\vrule}\kern-.4pt \hrule}}} @*Intro. This program finds all of the nonisomorphic graceful labelings of the graph $K_m\sqprod P_3$. It was inspired by the paper of B.~M. Smith and J.-F. Puget in {\sl Constraints\/ \bf15} (2010), 64--92, where Table~5 reports a unique solution for $m=6$. I'm writing it because I want to gain experience, gracefulnesswise --- and also because Smith and Puget have unfortunately lost all records of the solution! The graph $K_m\sqprod P_3$ is hardwired'' into the logic of this program. It has $q=3{m\choose2}+2m$ edges; that's (7,~15, 26, 40, 57, 77, \dots) for $m=(2$, 3, 4, 5, 6, 7, \dots). I doubt if I'll be able to reach $m=7$; but I see no reason to exclude that case, because the algorithm needs very little memory. Please excuse me for writing this in a rush. @d m 6 /* the size of the cliques; must be at least 2 and at most 12 */ @d q ((m*(3*m+1))/2) /* number of edges */ @d o mems++ /* count one mem */ @d oo mems+=2 /* count two mems */ @d ooo mems+=3 /* count three mems */ @d delta 10000000000; /* report progress every |delta| or so mems */ @d O "%" /* used for percent signs in format strings */ @d mod % /* used for percent signs denoting remainder in \CEE/ */ @d board(i,j) brd[3*(i)+(j)] @d leftknown colknown[0] @c #include #include unsigned long long mems; /* memory accesses */ unsigned long long thresh=delta; /* time for next progress report */ unsigned long long nodes; /* nodes in the search tree */ unsigned long long nulls; /* nodes that need no new vertex placement */ unsigned long long leaves; /* nodes that have no descendants */ int count; /* number of solutions found so far */ int brd[3*m]; /* one-dimensional array accessed via the |board| macro */ int rank; /* how many rows of the board are active? */ int labeled[q+1]; /* what row and column, if any, have a particular label? */ int placed[q+1]; /* has this edge been placed? */ int colknown[3]; /* how many vertices of each clique are labeled? */ int move[q][1024]; /* feasible moves at each level */ int deg[q]; /* number of choices at each level; used in printouts only */ int x[q]; /* indexes of moves made at each level */ int maxl; /* maximum level reached */ int vbose=0; /* can set this nonzero when debugging */ @@; main () { register int a,b,i,j,k,l,t,v,aa,bb,ii,row,col,ccol,val,mv,trouble; fprintf(stderr,"--- Graceful labelings of K"O"d times P3 ---\n",m); @; @; fprintf(stderr,"Altogether "O"d solution"O"s,", count,count==1?"":"s"); fprintf(stderr," "O"lld mems, "O"lld-"O"lld nodes, "O"lld leaves;", mems, nodes, nulls, leaves); fprintf(stderr," max level "O"d.\n",maxl); if (sanity_checking) fprintf(stderr,"sanity_checking was on!\n"); } @ The current status of the vertices labeled so far appears in the |board|, which has three columns and $m$ rows. This is not a canonical representation: The rows can appear in any order. When a vertex is unlabeled, the |board| has $-1$. When the vertex in row~$i$ and column~$j$ receives label~$l$, |labeled[l]| records the value |(j<<4)+i|; but |labeled[l]| is $-1$ if that label hasn't been used. If both endpoints of an edge are labeled, and if $d$ is the difference between those labels, |placed[d]=1|; but |placed[d]=0| if no edge for difference~|d| is yet known. The first |rank| rows of the board have been labeled, at least in part. @= for (i=0;i= void print_board(int rank) { register int i,j; for (i=0;i=0) fprintf(stderr,""O"3d",board(i,j)); else fprintf(stderr," ?"); fprintf(stderr,"\n"); } } @ @= void print_placed(void) { register int k; for (k=1;k<=q;k++) { if (placed[k]) { if (!placed[k-1]) fprintf(stderr," "O"d",k); else if (k==q || !placed[k+1]) fprintf(stderr,".."O"d",k); } } fprintf(stderr,"\n"); } @ These data structures are somewhat fancy, so I'd better check that they're self-consistent. @d sanity_checking 0 /* set this to 1 if you suspect a bug */ @= void sanity(void) { register int i,j,l,t,v; @; @; @; } @ @= for (i=rank;i=0) break; if (board(i,1)>=0) break; if (board(i,2)>=0) break; } if (im) fprintf(stderr,"rank shouldn't be "O"d!\n",rank); @ @= for (l=0;l<=q;l++) { v=labeled[l]; if (v>=0 && board(v&0xf,v>>4)!=l) fprintf(stderr,"labeled["O"d] not on the board!\n",l); } for (i=0;iq) fprintf(stderr,"board("O"d,"O"d) out of range!\n",i,j); if (board(i,j)>=0 && labeled[board(i,j)]!=(j<<4)+i) fprintf(stderr,"label of board("O"d,"O"d) is wrong!\n",i,j); } @ @d testedge(i,j,ii,jj) if (board(i,j)>=0 && board(ii,jj)>=0) if (t--,!placed[abs(board(i,j)-board(ii,jj))]) fprintf(stderr,"edge from ("O"d,"O"d) to ("O"d,"O"d) not placed!\n", i,j,ii,jj); @= for (t=0,l=1;l<=q;l++) t+=placed[l]; for (i=0;i= enter: nodes++; if (mems>=thresh) { thresh+=delta; print_progress(l); } if (sanity_checking) sanity(); if (l<=1) @; if (l>=maxl) { maxl=l; if (l==q) @; } if (o,placed[q-l]) @; for (t=a=0,b=q-l;b<=q;a++,b++) @; ready: deg[l]=t; /* no |mems| counted for diagnostics */ if (!t) leaves++; tryit:@+if (t==0) goto backup; advance:@+if (vbose) { fprintf(stderr,"L"O"d: ",l); print_move(move[l][t-1]); fprintf(stderr," ("O"d of "O"d)\n",deg[l]-t+1,deg[l]); } o,x[l]=--t; o,mv=move[l][t]; @; if (trouble) { if (vbose) fprintf(stderr," -- was bad\n"); goto unmake; } l++; goto enter; backup:@+if (--l>=0) { o,t=x[l]; unmake: o,mv=move[l][t]; @; goto tryit; } @ @= { count++; printf(""O"d:\n",count); for (i=0;i= void print_progress(int level) { register int l,k,d,c,p; register double f,fd; fprintf(stderr," after "O"lld mems: "O"d sols,",mems,count); for (f=0.0,fd=1.0,l=0;l= { o,move[l][0]=0,t=1,nulls++; goto ready; } @ @= void print_move(int mv) { if (!mv) fprintf(stderr,"null"); else if (mv<0x10000) fprintf(stderr,""O"d"O"d="O"d",(mv>>8)&0xf,(mv>>12)&0xf,mv&0xff); else fprintf(stderr,""O"d"O"d="O"d,"O"d"O"d="O"d", (mv>>8)&0xf,(mv>>12)&0xf,mv&0xff,(mv>>24)&0xf,(mv>>28)&0xf,(mv>>16)&0xff); } @# void print_moves(int level) { register int i; for (i=deg[level]-1;i>=0;i--) { /* we try the moves in decreasing order */ fprintf(stderr,""O"d:",deg[level]-i); print_move(move[level][i]); fprintf(stderr,"\n"); } } @ @= void print_state(int levels) { register int l; for (l=0;l= if (l==0) { o,move[0][0]=(pack(1,1,0)<<16)+pack(0,1,q); o,move[0][1]=(pack(1,0,0)<<16)+pack(0,0,q); o,move[0][2]=(pack(0,1,0)<<16)+pack(0,0,q); t=3; goto ready; }@+else if (o,x[0]!=2) { t=(m==2? 1: 2); o,move[1][0]=pack(0,x[0],1); if (m>2) o,move[1][1]=pack(2,1-x[0],1); goto ready; } @ I set |trouble| nonzero if any edge is placed more than once. @= for (trouble=0;mv;mv>>=16) { val=mv&0xff,row=(mv>>8)&0xf,col=(mv>>12)&0xf; o,labeled[val]=(mv>>8)&0xff; o,board(row,col)=val; oo,colknown[col]++; if (col>0) { o,v=board(row,col-1); if (v>=0) oo,trouble+=placed[abs(val-v)],placed[abs(val-v)]=1; } if (col<2) { o,v=board(row,col+1); if (v>=0) oo,trouble+=placed[abs(val-v)],placed[abs(val-v)]=1; } for (i=0;i=0) oo,trouble+=placed[abs(val-v)],placed[abs(val-v)]=1; } if (row==rank) rank++; } @ @= if (mv>=0x10000) mv=(mv>>16)+((mv&0xffff)<<16); /* undo in opposite order */ for (;mv;mv>>=16) { val=mv&0xff,row=(mv>>8)&0xf,col=(mv>>12)&0xf; if (row==rank-1 && (o,board(row,(col+1)mod 3)<0) && (o,board(row,(col+2)mod 3)<0)) rank=row; o,labeled[val]=-1; o,board(row,col)=-1; oo,colknown[col]--; if (col>0) { o,v=board(row,col-1); if (v>=0) o,placed[abs(val-v)]=0; } if (col<2) { o,v=board(row,col+1); if (v>=0) o,placed[abs(val-v)]=0; } for (i=0;i=0) o,placed[abs(val-v)]=0; } } @*The nitty gritty. OK, I've put all the infrastructure into place. It remains to figure out all legal ways to place a new edge whose endpoints are labeled |a|~and~|b|. (This is where the graph $K_m\sqprod P_3$ is really hardwired.'') I do this by brute force, while trying to be careful. Sometimes I just barely avoided a bug, but I hope that I've exterminated them all. @= { oo,aa=labeled[a],bb=labeled[b]; if (aa>=0) { if (bb>=0) continue; /* |a| and |b| are already on the |board| */ row=aa&0xf, col=aa>>4; @; }@+else if (bb>=0) { row=bb&0xf, col=bb>>4; @; } else @; } @ @= switch (col) { case 0:@+if ((o,board(row,1)<0) && legal_in_col(b,1) && ((o,board(row,2)<0) || (o,!placed[abs(b-board(row,2))]))) o,move[l][t++]=pack(row,1,b); break; case 1:@+if ((o,board(row,0)<0) && legal_in_col(b,0)) o,move[l][t++]=pack(row,0,b); if ((o,leftknown) && (o,board(row,2)<0) && legal_in_col(b,2)) o,move[l][t++]=pack(row,2,b); break; case 2:@+if ((o,board(row,1)<0) && legal_in_col(b,1) && ((o,board(row,0)<0) || (o,!placed[abs(b-board(row,0))]))) o,move[l][t++]=pack(row,1,b); break; } if (legal_in_col(b,col)) { for (i=0;i0 && (o,board(i,col-1)>=0) && (o,placed[abs(b-board(i,col-1))])) continue; if (col<2 && (o,board(i,col+1)>=0) && (o,placed[abs(b-board(i,col+1))])) continue; o,move[l][t++]=pack(i,col,b); } if (rank= int legal_in_col(val,col) { register int i,v; if (o,colknown[col]==m) return 0; for (i=0;i=0 && (o,placed[abs(v-val)])) return 0; } return 1; } @ @= switch (col) { case 0:@+if ((o,board(row,1)<0) && legal_in_col(a,1) && ((o,board(row,2)<0) || (o,!placed[abs(a-board(row,2))]))) o,move[l][t++]=pack(row,1,a); break; case 1:@+if ((o,board(row,0)<0) && legal_in_col(a,0)) o,move[l][t++]=pack(row,0,a); if ((o,leftknown) && (o,board(row,2)<0) && legal_in_col(a,2)) o,move[l][t++]=pack(row,2,a); break; case 2:@+if ((o,board(row,1)<0) && legal_in_col(a,1) && ((o,board(row,0)<0) || (o,!placed[abs(a-board(row,0))]))) o,move[l][t++]=pack(row,1,a); break; } if (legal_in_col(a,col)) { for (i=0;i0 && (o,board(i,col-1)>=0) && (o,placed[abs(a-board(i,col-1))])) continue; if (col<2 && (o,board(i,col+1)>=0) && (o,placed[abs(a-board(i,col+1))])) continue; o,move[l][t++]=pack(i,col,a); } if (rank= for (o,ccol=(leftknown? 2: 1);ccol>=0;ccol--) if (legal_in_col(a,ccol)) { for (ii=0;ii0 && (o,board(ii,ccol-1)>=0) && (o,placed[abs(a-board(ii,ccol-1))])) continue; if (ccol<2 && (o,board(ii,ccol+1)>=0) && (o,placed[abs(a-board(ii,ccol+1))])) continue; aa=mv=pack(ii,ccol,a);@+@;@+mv=aa; if (!trouble) @; @; } if (rank;@+mv=aa; if (!trouble) @; @; } } @ @= { switch (col) { case 0:@+if ((o,board(row,1)<0) && legal_in_col(b,1) && ((o,board(row,2)<0) || (o,!placed[abs(b-board(row,2))]))) o,move[l][t++]=(pack(row,1,b)<<16)+mv; break; case 1:@+if ((o,board(row,0)<0) && legal_in_col(b,0)) o,move[l][t++]=(pack(row,0,b)<<16)+mv; if ((o,leftknown) && (o,board(row,2)<0) && legal_in_col(b,2)) o,move[l][t++]=(pack(row,2,b)<<16)+mv; break; case 2:@+if ((o,board(row,1)<0) && legal_in_col(b,1) && ((o,board(row,0)<0) || (o,!placed[abs(b-board(row,0))]))) o,move[l][t++]=(pack(row,1,b)<<16)+mv; break; } if (legal_in_col(b,col)) { for (i=0;i0 && (o,board(i,col-1)>=0) && (o,placed[abs(b-board(i,col-1))])) continue; if (col<2 && (o,board(i,col+1)>=0) && (o,placed[abs(b-board(i,col+1))])) continue; o,move[l][t++]=(pack(i,col,b)<<16)+mv; } if (rank