/*
 * A program to solve Twiddle, 3x3 grid, 2x2 rotation.
 *
 * There are at most 9!=362880 possible states the puzzle can be in.
 *  We treat the eight possible moves (four locations, two directions)
 *  as inducing a graph on this set of 362880 points, and look at the
 *  points' distance from the solved state.
 *
 * We enumerate the positions in sorted order, so we can do binary
 *  search to locate a position's compact representation.
 */

#include <stdio.h>
#include <stdlib.h>
#include <strings.h>

#define NPOS (9*8*7*6*5*4*3*2)
#define NBYTES ((NPOS + 7) >> 3)
#define NMOVE 8
#define MAXLINE 256

typedef struct qent QENT;
typedef struct qv QV;

struct qv {
  int v;
  int d;
  } ;

struct qent {
  QENT *link;
  QV v;
  } ;

static int npos;
static unsigned char pos[NPOS][9];
static int arcs[NPOS][NMOVE];
static unsigned char dist[NPOS];
static unsigned char perm[NMOVE][9]
 = { { 3, 0, 2,  4, 1, 5,  6, 7, 8 },
     { 0, 4, 1,  3, 5, 2,  6, 7, 8 },
     { 0, 1, 2,  6, 3, 5,  7, 4, 8 },
     { 0, 1, 2,  3, 7, 4,  6, 8, 5 },
     { 1, 4, 2,  0, 3, 5,  6, 7, 8 },
     { 0, 2, 5,  3, 1, 4,  6, 7, 8 },
     { 0, 1, 2,  4, 7, 5,  3, 6, 8 },
     { 0, 1, 2,  3, 5, 8,  6, 4, 7 } };
static const char *movenames[NMOVE] = { "UL R", "UR R", "LL R", "LR R", "UL L", "UR L", "LL L", "LR L" };
static unsigned char inq[NBYTES];
static QENT *qh;
static QENT **qt;
static QENT *qf;

static void q_init(void)
{
 qh = 0;
 qt = &qh;
 qf = 0;
}

static void q_put(QV v)
{
 QENT *e;

 if (qf)
  { e = qf;
    qf = e->link;
  }
 else
  { e = malloc(sizeof(QENT));
  }
 e->link = 0;
 e->v = v;
 *qt = e;
 qt = &e->link;
}

static int q_nonempty(void)
{
 return(!!qh);
}

static QV q_get(void)
{
 QENT *e;
 QV v;

 e = qh;
 if (! e) abort();
 v = e->v;
 qh = e->link;
 if (! qh) qt = &qh;
 e->link = qf;
 qf = e;
 return(v);
}

static void enumerate(unsigned char *v, int fill, unsigned int taken)
{
 int i;

 if (fill == 9)
  { if (npos >= NPOS) abort();
    bcopy(v,&pos[npos][0],9);
    npos ++;
    return;
  }
 for (i=0;i<9;i++)
  { if ((taken >> i) & 1) continue;
    v[fill] = i;
    enumerate(v,fill+1,taken|(1U<<i));
  }
}

static void setup_pos(void)
{
 unsigned char pos[9];

 npos = 0;
 enumerate(&pos[0],0,0);
 if (npos != NPOS) abort();
}

static int find_pos(const unsigned char *p)
{
 int l;
 int m;
 int h;
 int i;

 l = -1;
 h = NPOS;
 while (h-l > 1)
  { m = (h + l) / 2;
    for (i=0;(i<9)&&(p[i]==pos[m][i]);i++) ;
    if (i >= 9) return(m);
    if (p[i] < pos[m][i])
     { h = m;
     }
    else
     { l = m;
     }
  }
 return(-1);
}

static void build_graph(void)
{
 int i;
 int j;
 int k;
 unsigned char p[9];

 for (i=NPOS-1;i>=0;i--)
  { for (j=NMOVE-1;j>=0;j--)
     { for (k=9-1;k>=0;k--)
	{ p[k] = pos[i][perm[j][k]];
	}
       k = find_pos(&p[0]);
       if (k < 0) abort();
       arcs[i][j] = k;
     }
  }
}

static void search(void)
{
 int i;
 int d;
 int j;
 QV q;
 int maxd;
 int *dc;

 for (i=NPOS-1;i>=0;i--) dist[i] = 0xff;
 bzero(&inq[0],sizeof(inq));
 q_init();
 i = find_pos((const void *)"\0\1\2\3\4\5\6\7\10");
 if (i < 0) abort();
 q_put((QV){.v=i,.d=0});
 while (q_nonempty())
  { q = q_get();
    d = dist[q.v];
    if (q.d < d)
     { dist[q.v] = q.d;
       for (j=NMOVE-1;j>=0;j--)
	{ q_put((QV){.v=arcs[q.v][j],.d=q.d+1});
	}
     }
  }
 maxd = 0;
 for (i=NPOS;i>=0;i--) if (dist[i] > maxd) maxd = dist[i];
 dc = malloc((maxd+1)*sizeof(int));
 for (i=maxd;i>=0;i--) dc[i] = 0;
 for (i=NPOS-1;i>=0;i--) dc[dist[i]] ++;
 printf("\n");
 for (i=0;i<=maxd;i++) printf("%s%d:%d",i?"  ":"",i,dc[i]);
 printf("\n");
}

static void ui(void)
{
 char line[MAXLINE];
 int ll;
 int c;
 int v[9];
 int n1;
 int n2;
 char p[9];
 int i;
 int j;

 while <"lines"> (1)
  { printf("> ");
    ll = 0;
    while (1)
     { c = getchar();
       if (c == EOF) return;
       if (ll >= MAXLINE-1)
	{ printf("\nInput line too long\n");
	  exit(1);
	}
       if (c == '\n') break;
       line[ll++] = c;
     }
    line[ll] = '\0';
    n1 = -1;
    n2 = -1;
    sscanf(&line[0],"%d%d%d%d%d%d%d%d%d %n%*c%n",
		&v[0], &v[1], &v[2],
		&v[3], &v[4], &v[5],
		&v[6], &v[7], &v[8],
		&n1, &n2);
    if (n1 < 0)
     { printf("Fewer than nine numbers\n");
       continue;
     }
    if (n2 >= 0)
     { printf("Junk after ninth number\n");
       continue;
     }
    for (i=9-1;i>=0;i--)
     { if ((v[i] < 0) || (v[i] > 8))
	{ printf("Number %d out of range\n",v[i]);
	  continue <"lines">;
	}
       p[i] = v[i];
     }
    i = find_pos(&p[0]);
    if (i < 0)
     { printf("Not a valid position\n");
       continue;
     }
    while <"trace"> (1)
     { printf("%d %d %d  %d %d %d  %d %d %d   %d",
		pos[i][0], pos[i][1], pos[i][2],
		pos[i][3], pos[i][4], pos[i][5],
		pos[i][6], pos[i][7], pos[i][8],
		dist[i] );
       if (dist[i] < 1)
	{ printf("\n");
	  break;
	}
       for (j=NMOVE-1;j>=0;j--)
	{ if (dist[arcs[i][j]] < dist[i])
	   { i = arcs[i][j];
	     printf("  %s\n",movenames[j]);
	     continue <"trace">;
	   }
	}
       printf("\nCan't make progress from here\n");
       break;
     }
  }
}

int main(void);
int main(void)
{
 printf("setting up positions...");
 fflush(0);
 setup_pos();
 printf("done\n");
 printf("building adjacency graph...");
 fflush(0);
 build_graph();
 printf("done\n");
 printf("searching...");
 fflush(0);
 search();
 printf("done\n");
 ui();
 return(0);
}