\datethis

@*Intro. 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 16 /* |m| and |n| mustn't exceed this (4-bit limit for |row|) */
@d maxq 255 /* $mn$ mustn't exceed this (8-bit |val| in |mv| codes) */
@d board(i,j) brd[(i)+m*(j)]

@c
#include <stdio.h>
#include <stdlib.h>
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? */
int 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 */
@<Subroutines@>@;
main (int argc,char*argv[]) {
  register int a,b,i,j,k,l,t,v,aa,bb,ii,row,col,ccol,val,mv,trouble;
  @<Process the command line@>;
  @<Initialize the data structures@>;
  @<Backtrack through all solutions@>;
  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);
}

@ @<Process the command line@>=
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<<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.


@<Initialize the data structures@>=
rankl=rankr=0;
for (l=0;l<=q;l++) labeled[l]=-1;
l=0;

@ @<Sub...@>=
void print_board(void) {
  register int i,j;
  for (i=0;i<rankl;i++) fprintf(stderr,""O"3d",board(i,0));
  fprintf(stderr,"  | ");
  for (j=0;j<rankr;j++) fprintf(stderr,""O"3d",board(j,1));
  fprintf(stderr,"\n");
}

@ @<Sub...@>=
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 */

@<Sub...@>=
void sanity(void) {
  register int i,j,l,t,v;
  @<Check the ranks@>;
  @<Check the labels@>;
  @<Check the placements@>;
}

@ @<Check the ranks@>=
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);

@ @<Check the labels@>=
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;i<rankl;i++) {
  if (board(i,0)>q) 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;j<rankr;j++) {
  if (board(j,1)>q) fprintf(stderr,"board("O"d,"O"d) out of range!\n",j,1);
  if (labeled[board(j,1)]!=(1<<4)+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);

@<Check the placements@>=
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<rankl;i++) for (j=0;j<rankr;j++)
  testedge(i,j);

@ At level |l| of the backtrack procedure I try to place the edge
whose difference is |q-l|, if that edge hasn't already been placed.

Initially there are two or four symmetries in addition to the $m!\,n!$
permutations of the two parts of the board:
We can complement each label, replacing |l| by |q-l|.
We can also interchange the left and right parts, if $m=n$;
that's called reflection. 

I've set up the levels near the root so that the label~0 always goes
into the right part. If $m\ne n$, that avoids complementation.
If $m=n$, it avoids reflection; and complementation is avoided
by also forcing~1 into the right part when $m=n$.

@<Backtrack through all solutions@>=
enter: nodes++;
  if (mems>=thresh) {
    thresh+=delta;
    print_progress(l);
  }
  if (sanity_checking) sanity();
  if (l<=1) @<Make special moves near the root@>;
  if (l==q) @<Report a solution and |goto backup|@>;
  if (o,placed[q-l]) @<Record the null move and |goto ready|@>;
  for (t=a=0,b=q-l;b<=q;a++,b++)
    @<Record all possible $(a,b)$ moves in the array |move[l]|@>;
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];
  @<Make |mv|@>;
  if (trouble) goto unmake;
  l++;
  goto enter;
backup:@+if (--l>=0) {
  o,t=x[l];
unmake: o,mv=move[l][t];
  @<Unmake |mv|@>;
  goto tryit;
}

@ @<Report a solution and |goto backup|@>=
{
  count++;
  printf(""O"d: ",count);
  @<Analyze and print the solution@>;
  goto backup;
}

@ @<Sub...@>=
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<level;l++) {
    d=deg[l],k=d-x[l];
    fd*=d,f+=(k-1)/fd; /* choice |l| is |k| of |d| */
    fprintf(stderr," "O"c"O"c",
      k<10? '0'+k: k<36? 'a'+k-10: k<62? 'A'+k-36: '*',
      d<10? '0'+d: d<36? 'a'+d-10: d<62? 'A'+d-36: '*');
  }
  fprintf(stderr," "O".5f\n",f+0.5/fd);
}

@ A ``move'' consists of labeling 0, 1, or 2 vertices and updating
the data structures. A 16-bit packed entry, consisting of
column number (4~bits), row number (4~bits), and label value
(8~bits), specifies what labeling should be done. If two 16-bit
entries are present, the rightmost one is done first.

It turns out that |(row,col,val)| will never be simultaneously zero.
Hence an all-zero move means ``do nothing.''

@d pack(row,col,val) (((col)<<12)+((row)<<8)+(val))

@<Record the null move and |goto ready|@>=
{
  o,move[l][0]=0,t=1;
  goto ready;
}

@ @<Sub...@>=
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");
  }
}

@ @<Sub...@>=
void print_state(int levels) {
  register int l;
  for (l=0;l<levels;l++) {
    print_move(move[l][x[l]]);
    fprintf(stderr," ("O"d of "O"d)\n",deg[l]-x[l],deg[l]);
  }
}

@ The edge labeled |q| must have endpoints labeled 0 and~|q|.

@<Make special moves near the root@>=
{
  if (l==0) o,move[0][0]=(pack(0,0,q)<<16)+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.

@<Make |mv|@>=
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;
  if (col==0) {
    if (row!=rankl) confusion("left move");
    rankl++;
    for (j=0;j<rankr;j++) {
      o,v=board(j,1);
      oo,trouble+=placed[abs(val-v)],placed[abs(val-v)]=1;
    }
  }@+else {
    if (row!=rankr) confusion("rightt move");
    rankr++;
    for (i=0;i<rankl;i++) {
      o,v=board(i,0);
      oo,trouble+=placed[abs(val-v)],placed[abs(val-v)]=1;
    }
  }
}

@ @<Sub...@>=
void confusion(char *message) {
  fprintf(stderr,""O"s!\n",message);
}

@ @<Unmake |mv|@>=
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;
  o,labeled[val]=-1;
  if (col==0) {
    rankl--;
    if (row!=rankl) confusion("left unmove");
    for (j=0;j<rankr;j++) {
      o,v=board(j,1);
      o,placed[abs(val-v)]=0;
    }
  }@+else {
    rankr--;
    if (row!=rankr) confusion("right unmove");
    for (i=0;i<rankl;i++) {
      o,v=board(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,n}$ 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.

@<Record all possible $(a,b)$ moves in the array |move[l]|@>=
{
  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;
    @<Record all legal placements of |b| adjacent to |a|@>;
  }@+else if (bb>=0) {
    row=bb&0xf, col=bb>>4;
    @<Record all legal placements of |a| adjacent to |b|@>;
  }
  else @<Record all adjacent placements of |a| and |b|@>;
}

@ @<Record all legal placements of |b| adjacent to |a|@>=
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);

@ @<Sub...@>=
int right_legal(val) {
  register int i,v;
  if (rankr==n) return 0;
  for (i=0;i<rankl;i++) {
    o,v=board(i,0);
    if (o,placed[abs(v-val)]) return 0;
  }
  return 1;
}

@ @<Sub...@>=
int left_legal(val) {
  register int j,v;
  if (rankl==m) return 0;
  for (j=0;j<rankr;j++) {
    o,v=board(j,1);
    if (o,placed[abs(v-val)]) return 0;
  }
  return 1;
}

@ @<Record all legal placements of |a| adjacent to |b|@>=
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.

@<Record all adjacent placements of |a| and |b|@>=
if (left_legal(a)) {
  aa=mv=pack(rankl,0,a);@+@<Make |mv|@>;@+mv=aa;
  if (!trouble) @<Record all double placements of |b| adjacent to |a|@>;
  @<Unmake |mv|@>;
}
if (right_legal(a)) {
  aa=mv=pack(rankr,1,a);@+@<Make |mv|@>;@+mv=aa;
  if (!trouble) @<Record all double placements of |b| adjacent to |a|@>;
  @<Unmake |mv|@>;
}

@ @<Record all double placements of |b| adjacent to |a|@>=
{
  if (col==0 && right_legal(b)) o,move[l][t++]=(pack(rankr,1,b)<<16)+mv;
  else if (col==1 && left_legal(b)) o,move[l][t++]=(pack(rankl,0,b)<<16)+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<\ldots<b_n$. It's an ``alpha solution''
if $b_n<a_m$. (Such bipartite labelings
were considered by Rosa in his original paper on graceful labelings.)
Then, if $t$ is any integer $>1$, 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}'.

@<Analyze and print the solution@>=
@<Sort the solution into |left| and |right|@>;
for (i=0;i<m;i++) printf(""O"3d",left[i]);
printf("  | ");
for (j=0;j<n;j++) printf(""O"3d",right[j]);
if (left[m-1]<right[n-1]) nonalf++,printf(" #\n");
else @<Analyze an alpha solution@>;

@ @<Sort the solution into |left| and |right|@>=
for (i=0;i<m;i++) {
  a=board(i,0);
  for (j=i;j>0;j--) {
    if (left[j-1]>a) break;  
    left[j]=left[j-1];
  }
  left[j]=a;
}
for (j=0;j<n;j++) {
  b=board(j,1);
  for (i=j;i>0;i--) {
    if (right[i-1]<b) break;
    right[i]=right[i-1];
  }
  right[i]=b;
}

@ @<Analyze an alpha solution@>=
{
  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<n;j++) if (right[j]@q)@>%t) goto irreducible;
    for (v=t;v<m;v+=t) {
      if (left[v]@q)@>%t) goto irreducible;
      for (i=1;i<t;i++) if (left[v+i]!=left[v]-i) goto irreducible;
    }
    printf(" R"O"d\n",t);
    goto done;
  }
  for (t=1;;t++) if (t==n || right[t]!=t) break;
  if (t>1) {
    if (n@q)@>%t) goto irreducible;
    for (i=0;i<m;i++) if (left[i]@q)@>%t) goto irreducible;
    for (v=t;v<n;v+=t) {
      if (right[v]@q)@>%t) goto irreducible;
      for (i=1;i<t;i++) if (right[v+i]!=right[v]+i) goto irreducible;
    }
    printf(" L"O"d\n",t);
    goto done;
  }
irreducible: printf(" XXX\n");
done:;
}

@*Index.