#\datethis # #@*Intro. This is a modified version of Donald Knuth's program, #to calculate for values of m,n larger than 16. # #This program finds all of the nonisomorphic graceful labelings #of the graph $K_{m,n}$. I based it on #{\mc BACK-GRACEFUL-KMP2}, which handles a more difficult problem. # #The graph $K_{m,n}$ is ``hardwired'' into the logic of this program. #It has $q=mn$ edges. #Although I won't be able to let $m$ and $n$ get extremely large, #I'm hoping to see a pattern from which some conjectures will follow. #(Even some theorems, if I'm lucky.) # #Please excuse me for writing this in a rush. A lot of the code has inherited #awkwardness from its history. # #@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 maxmn 32 /* |m| and |n| mustn't exceed this (5-bit limit for |row|) */ #@d maxq 512 /* $mn$ mustn't exceed this (9-bit |val| in |mv| codes) */ #@d board(i,j) brd[(i)+m*(j)] # #@c ##include ##include #int m,n; /* command-line parameters */ #int q; /* the number of edges ($mn$) */ #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 leaves; /* nodes that have no descendants */ #int count; /* number of solutions found so far */ #int nonalf; /* number of non-alpha solutions found so far */ #int brd[maxmn+maxmn]; /* one-dimensional array accessed via the |board| macro */ #int rankl,rankr; /* how many rows of each part are active? */ #int labeled[maxq+1]; /* what row and column, if any, have a particular label? */ #int placed[maxq+1]; /* has this edge been placed? */ #unsigned long long move[maxq][1024]; /* feasible moves at each level */ #int deg[maxq]; /* number of choices at each level; used in printouts only */ #int x[maxq]; /* indexes of moves made at each level */ #int vbose=0; /* can set this nonzero when debugging */ #int left[maxmn],right[maxmn]; /* sorted solution */ #@@; #main (int argc,char*argv[]) { # register int a,b,i,j,k,l,t,v,aa,bb,ii,row,col,ccol,val,trouble; # unsigned long long mv; # @; # @; # @; # fprintf(stderr, # "Altogether "O"d solution"O"s ("O"d alpha),", # count,count==1?"":"s",count-nonalf); # fprintf(stderr," "O"lld mems, "O"lld nodes, "O"lld leaves.\n", # mems, nodes, leaves); #} # #@ @= #if (argc!=3 || sscanf(argv[1],""O"d",&m)!=1 || # sscanf(argv[2],""O"d",&n)!=1) { # fprintf(stderr,"Usage: "O"s m n\n",argv[0]); # exit(-1); #} #if (m>maxmn || n>maxmn) { # fprintf(stderr,"Sorry, m and n mustn't exceed "O"d!\n",maxmn); # exit(-2); #} #if (m<2 || n<2) { # fprintf(stderr,"Sorry, m and n should be 2 or more!\n"); # exit(-4); #} #q=m*n; #if (q>maxq) { # fprintf(stderr,"Sorry, mn mustn't exceed "O"d!\n",maxq); # exit(-3); #} #printf("--- Graceful labelings of K_{"O"d,"O"d} ---\n",m,n); # #@ The current status of the vertices labeled so far appears in #the |board|, which has two columns, one for each part. This is not a #canonical representation: The entries of each column can appear in any order. #The first |rankl| rows of the first column, and the first #|rankr| rows of the second column, have been labeled. #When the vertex #in row~$i$ and column~$j$ receives label~$l$, |labeled[l]| records #the value |(j<<5)+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. # # #@= #rankl=rankr=0; #for (l=0;l<=q;l++) labeled[l]=-1; #l=0; # #@ @= #void print_board(void) { # register int i,j; # for (i=0;i= #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 a bit fancy, so I'd better check that #they're self-consistent. # #@d sanity_checking 1 /* set this to 1 if you suspect a bug */ # #@= #void sanity(void) { # register int i,j,l,t,v; # @; # @; # @; #} # #@ @= #if (rankl>m) fprintf(stderr,"rankl shouldn't be "O"d!\n",rankl); #if (rankr>n) fprintf(stderr,"rankr shouldn't be "O"d!\n",rankr); # #@ @= #for (l=0;l<=q;l++) { # v=labeled[l]; # if (v>=0 && board(v&0x1f,v>>5)!=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,0); # if (labeled[board(i,0)]!=i) # fprintf(stderr,"label of board("O"d,"O"d) is wrong!\n",i,0); #} #for (j=0;jq) fprintf(stderr,"board("O"d,"O"d) out of range!\n",j,1); # if (labeled[board(j,1)]!=(1<<5)+j) # fprintf(stderr,"label of board("O"d,"O"d) is wrong!\n",j,1); #} # #@ @d testedge(i,j) if (!placed[abs(board(i,0)-board(j,1))]) # fprintf(stderr,"edge from "O"d to "O"d not placed!\n", # i,j); # #@= #for (t=0,l=1;l<=q;l++) t+=placed[l]; #if (t!=rankl*rankr) # fprintf(stderr,"placement count is off ("O"d not "O"d)",t,rankl*rankr); #for (i=0;i= #enter: nodes++; # if (mems>=thresh) { # thresh+=delta; # print_progress(l); # } # if (sanity_checking) sanity(); # if (l<=1) @; # 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) 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: ",count); # @; # goto backup; #} # #@ @= #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; # goto ready; #} # #@ @= #void print_move(unsigned long long mv) { # if (!mv) # fprintf(stderr,"null"); # else if (mv<0x80000) # fprintf(stderr,""O"d"O"d="O"d",(mv>>9)&0x1f,(mv>>14)&0x1f,mv&0x1ff); # else fprintf(stderr,""O"d"O"d="O"d,"O"d"O"d="O"d", # (mv>>9)&0x1f,(mv>>14)&0x1f,mv&0x1ff,(mv>>28)&0x1f,(mv>>33)&0x1f,(mv>>19)&0x1ff); #} #@# #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(0,0,q)<<19)+pack(0,1,0),t=1; # else if (m==n) o,move[1][0]=pack(1,1,1),t=1; # else { # o,move[1][0]=pack(1,1,1); # o,move[1][1]=pack(1,0,q-1); # t=2; # } # goto ready; #} # #@ I set |trouble| nonzero if any edge is placed more than once. # #@= #for (trouble=0;mv;mv>>=19) { # val=mv&0x1ff,row=(mv>>9)&0x1f,col=(mv>>14)&0x1f; # o,labeled[val]=(mv>>9)&0x3ff; # o,board(row,col)=val; # if (col==0) { # if (row!=rankl) confusion("left move"); # rankl++; # for (j=0;j= #void confusion(char *message) { # fprintf(stderr,""O"s!\n",message); #} # #@ @= #if (mv>=0x80000) #{ # mv=(mv>>19)+((mv&0x7ffff)<<19); /* undo in opposite order */ #} #for (;mv;mv>>=19) { # val=mv&0x1ff,row=(mv>>9)&0x1f,col=(mv>>14)&0x1f; # o,labeled[val]=-1; # if (col==0) { # rankl--; # if (row!=rankl) confusion("left unmove"); # for (j=0;j= #{ # oo,aa=labeled[a],bb=labeled[b]; # if (aa>=0) { # if (bb>=0) continue; /* |a| and |b| are already on the |board| */ # row=aa&0x1f, col=aa>>5; # @; # }@+else if (bb>=0) { # row=bb&0x1f, col=bb>>5; # @; # } # else @; #} # #@ @= #if (col==0 && right_legal(b)) o,move[l][t++]=pack(rankr,1,b); #else if (col==1 && left_legal(b)) o,move[l][t++]=pack(rankl,0,b); # #@ @= #int right_legal(val) { # register int i,v; # if (rankr==n) return 0; # for (i=0;i= #int left_legal(val) { # register int j,v; # if (rankl==m) return 0; # for (j=0;j= #if (col==0 && right_legal(a)) o,move[l][t++]=pack(rankr,1,a); #else if (col==1 && left_legal(a)) o,move[l][t++]=pack(rankl,0,a); # #@ Finally, the hard case is when a double move is needed. #First I tentatively try all placements of~|a|, actually changing the board. #Then I record the double moves for |b| adjacent to every such placement. #Of course the board has to be restored again. # #@= #if (left_legal(a)) { # aa=mv=pack(rankl,0,a);@+@;@+mv=aa; # if (!trouble) @; # @; #} #if (right_legal(a)) { # aa=mv=pack(rankr,1,a);@+@;@+mv=aa; # if (!trouble) @; # @; #} # #@ @= #{ # if (col==0 && right_legal(b)) o,move[l][t++]=((unsigned long long)(pack(rankr,1,b))<<19)+mv; # else if (col==1 && left_legal(b)) o,move[l][t++]=((unsigned long long)(pack(rankl,0,b))<<19)+mv; #} # #@*Looking for patterns. Most of the solutions seem to be derivable in #a simple way from smaller solutions. # #Namely, suppose the left part contains $mn=a_1>\ldots>a_m>0$ #and the right part contains $0=b_1<\ldots1$, we can obtain two larger solutions: # #\item{1)} Replace each $a_i$ by $ta_i$ and each $b_j$ by #$tb_j$, $tb_j+1$, \dots, $tb_j+t-1$. This is a graceful alpha solution #for $K_{m,tn}$. # #\item{2)} Replace each $b_j$ by $tb_j$ and each #$a_i$ by $ta_i$, $ta_i-1$, \dots, $ta_i-t+1$. This is graceful alpha #solution for $K_{tm,n}$. # #I conjecture that all alpha solutions are obtained in this way. #Equivalently, all alpha solutions can be reduced to a smaller #alpha solution by inverting (1) or~(2). # #The following program marks a non-alpha solution with `\.\#'. #An alpha solution obtained from a smaller one by~(1) or~(1) is marked #`\.{L$t$}' or `\.{R$t$}', respectively. An alpha solution not obtained #by either (1) or~(2) is marked `\.{XXX}'. # #@= #@; #for (i=0;i; # #@ @= #for (i=0;i0;j--) { # if (left[j-1]>a) break; # left[j]=left[j-1]; # } # left[j]=a; #} #for (j=0;j0;i--) { # if (right[i-1]= #{ # for (t=1;;t++) if (t==m || left[t]!=q-t) break; # if (t>1) { # if (m@q)@>%t) goto irreducible; # for (j=0;j%t) goto irreducible; # for (v=t;v%t) goto irreducible; # for (i=1;i1) { # if (n@q)@>%t) goto irreducible; # for (i=0;i%t) goto irreducible; # for (v=t;v%t) goto irreducible; # for (i=1;i