/*
 * Program to brute-force a Rush Hour puzzle.  See puzzle-fmt.txt for
 *  the puzzle file format.
 *
 * The puzzle is taken from stdin.  The output consists of some trace
 *  data (from the "Live nodes..." printf in search()) followed by the
 *  solution.  For example, if the input is the very simple puzzle
 *
 *	6
 *	......
 *	....b.
 *	.aa.b.
 *	....b.
 *	..ccc.
 *	......
 *
 *  then the output is
 *
 *	Live nodes = 1, hash table load = 1
 *	Live nodes = 6, hash table load = 7
 *	Live nodes = 15, hash table load = 22
 *	c to 1
 *	b to 3
 *	finish
 *
 *  The solution description is of the form "LETTER to PLACE", where
 *  LETTER is one of the piece letters and PLACE is the destination
 *  offset from the left (for horizontal pieces) or top (for vertical
 *  pieces) of the diagram, with "finish" indicating moving piece a out
 *  the exit gate.  Thus, the solution above corresponds to three
 *  moves, thus:
 *
 *	(start)       c to 1        b to 3        finish
 *
 *	......        ......        ......        ......
 *	....b.        ....b.        ......        ......
 *	.aa.b.        .aa.b.        .aa...        ......aa
 *	....b.        ....b.        ....b.        ....b.
 *	..ccc.        .ccc..        .cccb.        .cccb.
 *	......        ......        ....b.        ....b.
 */

#include <stdio.h>
#include <errno.h>
#include <stdarg.h>
#include <stdlib.h>
#include <unistd.h>
#include <strings.h>
#include <sys/mman.h>

#define SIZE 6
#define MAXPCS 16
#define HTSIZE 1048583

extern const char *__progname;

typedef enum {
	  O_H = 1,
	  O_V,
	  } ORIENT;

typedef struct piece PIECE;
typedef struct xy XY;
typedef struct node NODE;

struct xy {
  int x;
  int y;
  } ;

struct piece {
  ORIENT o;
  int size;
  int loc;
  char letter;
  } ;

struct node {
  int depth;
  NODE *up;
  NODE *sib;
  NODE *kids;
  NODE *livelink;
  int *state;
  unsigned int hash;
  } ;

static int npcs;
static PIECE pcs[MAXPCS];
static int apx;
static NODE *root;
static NODE *live;
static int nlive;
static int alloc_chunk = 0;
static int nodesize;
static int stateoffset;
static int nfnodes;
static char *fnodes;
static unsigned int crctbl[256];
static NODE *nodeht[HTSIZE];
static int nodehtload;
static int *newstate;

static void init_hash(void)
{
 int i;
 int j;
 unsigned int h;

 for (i=255;i>=0;i--)
  { h = i;
    for (j=8;j>0;j--) h = (h >> 1) ^ ((h&1) ? 0xedb88320 : 0);
    crctbl[i] = h;
  }
 for (i=HTSIZE-1;i>=0;i--) nodeht[i] = 0;
}

static unsigned int hash(const void *data, int len)
{
 const unsigned char *dp;
 unsigned int h;

 h = 0x12345678;
 for (dp=data;len>0;len--,dp++) h = (h >> 8) ^ crctbl[(h^*dp)&0xff];
 return(h);
}

static void init_alloc(void)
{
 int ps;
 int i;

 nodesize = ((sizeof(NODE)/sizeof(int)) + ((sizeof(NODE)%sizeof(int))?1:0) + npcs) * sizeof(int);
 ps = getpagesize();
 i = (ps < 1048576) ? 1048576 : ps;
 if (i % nodesize) i = ((i / nodesize) + 1) * nodesize;
 if (i % ps) i = ((i / ps) + 1) * ps;
 alloc_chunk = i;
 stateoffset = nodesize - (npcs * sizeof(int));
 nfnodes = 0;
 fnodes = 0;
}

static NODE *newnode(void)
{
 NODE *n;

 if (alloc_chunk == 0) init_alloc();
 if (nfnodes < 1)
  { void *mmrv;
    mmrv = mmap(0,alloc_chunk,PROT_READ|PROT_WRITE,MAP_ANON|MAP_PRIVATE,-1,0);
    if (mmrv == MAP_FAILED)
     { fprintf(stderr,"%s: mmap: %s\n",__progname,strerror(errno));
       exit(1);
     }
    fnodes = mmrv;
    nfnodes = alloc_chunk / nodesize;
  }
 nfnodes --;
 n = (void *)fnodes;
 fnodes += nodesize;
 n->depth = -1;
 n->up = 0;
 n->sib = 0;
 n->kids = 0;
 n->state = (int *)(((char *)n) + stateoffset);
 return(n);
}

static void read_puzzle(void)
{
 int fsz;
 int x;
 int y;
 int c;
 char data[SIZE][SIZE];
 char chs[MAXPCS];
 char *chp;
 XY min[MAXPCS];
 XY max[MAXPCS];
 int cx;
 int n;

 auto void badpiece(char, const char *, ...)
		__attribute__((__format__(__printf__,2,3)));
 void badpiece(char ch, const char *fmt, ...)
  { va_list ap;
    fprintf(stderr,"%s: bad piece %c in puzzle (",__progname,ch);
    va_start(ap,fmt);
    vfprintf(stderr,fmt,ap);
    va_end(ap);
    fprintf(stderr,")\n");
    exit(1);
  }

 if (scanf("%d",&fsz) != 1)
  { fprintf(stderr,"%s: can't read puzzle size\n",__progname);
    exit(1);
  }
 if (fsz != SIZE)
  { fprintf(stderr,"%s: wrong size puzzle for this build (file has %d, want %d)\n",__progname,fsz,SIZE);
    exit(1);
  }
 npcs = 0;
 for (y=0;y<SIZE;y++) for (x=0;x<SIZE;x++)
  { while <"skip"> (1)
     { c = getchar();
       if (c == EOF)
	{ fprintf(stderr,"%s: EOF while reading puzzle\n",__progname);
	  exit(1);
	}
       switch (c)
	{ case '.':
	  case 'a': case 'b': case 'c': case 'd':
	  case 'e': case 'f': case 'g': case 'h':
	  case 'i': case 'j': case 'k': case 'l':
	  case 'm': case 'n': case 'o': case 'p':
	  case 'q': case 'r': case 's': case 't':
	  case 'u': case 'v': case 'w': case 'x':
	  case 'y': case 'z':
	  case 'A': case 'B': case 'C': case 'D':
	  case 'E': case 'F': case 'G': case 'H':
	  case 'I': case 'J': case 'K': case 'L':
	  case 'M': case 'N': case 'O': case 'P':
	  case 'Q': case 'R': case 'S': case 'T':
	  case 'U': case 'V': case 'W': case 'X':
	  case 'Y': case 'Z':
	     break <"skip">;
	  default:
	     continue;
	     break;
	}
     }
    data[x][y] = c;
    if (c != '.')
     { if ((npcs < 1) || !(chp=memchr(&chs[0],c,npcs)))
	{ cx = npcs ++;
	  if (cx >= MAXPCS)
	   { fprintf(stderr,"%s: too many pieces in puzzle\n",__progname);
	     exit(1);
	   }
	  chs[cx] = c;
	  min[cx].x = x;
	  min[cx].y = y;
	  max[cx] = min[cx];
	}
       else
	{ cx = chp - &chs[0];
	  if (x < min[cx].x) min[cx].x = x;
	  if (x > max[cx].x) max[cx].x = x;
	  if (y < min[cx].y) min[cx].y = y;
	  if (y > max[cx].y) max[cx].y = y;
	}
     }
  }
 chp = memchr(&chs[0],'a',npcs);
 if (! chp)
  { fprintf(stderr,"%s: no piece `a' in puzzle\n",__progname);
    exit(1);
  }
 apx = chp - &chs[0];
 root = newnode();
 for (cx=npcs-1;cx>=0;cx--)
  { if (min[cx].x == max[cx].x)
     { n = 1 + max[cx].y - min[cx].y;
       if ((n < 2) || (n > 3)) badpiece(chs[cx],"V, n=%d",n);
       if ((n == 3) && (data[min[cx].x][min[cx].y+1] != chs[cx])) badpiece(chs[cx],"V, hole");
       pcs[cx].o = O_V;
       pcs[cx].size = n;
       pcs[cx].loc = min[cx].x;
       root->state[cx] = min[cx].y;
     }
    else if (min[cx].y == max[cx].y)
     { n = 1 + max[cx].x - min[cx].x;
       if ((n < 2) || (n > 3)) badpiece(chs[cx],"H, n=%d",n);
       if ((n == 3) && (data[min[cx].x+1][min[cx].y] != chs[cx])) badpiece(chs[cx],"H, hole");
       pcs[cx].o = O_H;
       pcs[cx].size = n;
       pcs[cx].loc= min[cx].y;
       root->state[cx] = min[cx].x;
     }
    else
     { badpiece(chs[cx],"dx=%d dy=%d",max[cx].x-min[cx].x,max[cx].y-min[cx].y);
     }
    pcs[cx].letter = chs[cx];
  }
 if ((pcs[apx].o != O_H) || (pcs[apx].size != 2))
  { fprintf(stderr,"%s: piece `a' is not horizontal 2-cell piece\n",__progname);
    exit(1);
  }
 for (cx=npcs-1;cx>=0;cx--)
  { PIECE *p;
    p = &pcs[cx];
    for (c=npcs-1;c>=0;c--)
     { PIECE *p2;
       if (c == cx) continue;
       p2 = &pcs[c];
       if (p2->o == p->o)
	{ if (p2->loc != p->loc) continue;
	  if ( (root->state[cx]+p->size <= root->state[c]) ||
	       (root->state[c]+p2->size <= root->state[cx]) ) continue;
	  fprintf(stderr,"%s: parallel pieces %c and %c overlap somehow (%d+%d,%d+%d)\n",
		__progname,p->letter,p2->letter,root->state[cx],p->size,root->state[c],p2->size);
	  exit(1);
	}
       else
	{ if ( (p2->loc < root->state[cx]) || (p2->loc >= root->state[cx]+p->size) ||
	       (p->loc < root->state[c]) || (p->loc >= root->state[c]+p2->size) ) continue;
	  fprintf(stderr,"%s: perpendicular pieces %c and %c overlap somehow (%d+%d,%d+%d)\n",
		__progname,p->letter,p2->letter,root->state[cx],p->size,root->state[c],p2->size);
	  exit(1);
	}
     }
  }
 root->depth = 0;
 root->up = 0;
 root->livelink = 0;
 live = root;
 root->hash = hash(root->state,npcs*sizeof(int));
 nodeht[root->hash%HTSIZE] = root;
 nodehtload = 1;
 nlive = 1;
}

/* unused, not ifdef VERBOSE, so it's debugger-callable */
static void dumpstate(int, int *) __attribute__((__unused__));
static void dumpstate(int depth, int *sv)
{
 int i;

 printf("[%d]",depth);
 for (i=0;i<npcs;i++)
  { printf(" %c%d%d",pcs[i].letter,pcs[i].size,pcs[i].loc);
    switch (pcs[i].o)
     { case O_H: putchar('-'); break;
       case O_V: putchar('|'); break;
       default: printf("(%d)",(int)pcs[i].o); break;
     }
    printf("%d",sv[i]);
  }
}

static int can_move_to(int *state, int mover, int to)
{
 PIECE *p;
 int c;
 PIECE *p2;

 p = &pcs[mover];
 for (c=npcs-1;c>=0;c--)
  { if (c == mover) continue;
    p2 = &pcs[c];
    if (p2->o == p->o)
     { if (p2->loc != p->loc) continue;
       if ( (to+p->size <= state[c]) ||
	    (state[c]+p2->size <= to) ) continue;
       return(0);
     }
    else
     { if ( (p2->loc < to) || (p2->loc >= to+p->size) ||
	    (p->loc < state[c]) || (p->loc >= state[c]+p2->size) ) continue;
       return(0);
     }
  }
 return(1);
}

static void printsoln(NODE *n)
{
 int i;
 int j;

 if (! n->up) return;
 printsoln(n->up);
 j = -1;
 for (i=npcs-1;i>=0;i--)
  { if (n->state[i] != n->up->state[i])
     { if (j >= 0) abort();
       j = i;
     }
  }
 printf("%c to %d\n",pcs[j].letter,n->state[j]);
}

static void maybe_queue(int *newstate, NODE *up, int newdepth)
{
 unsigned int h;
 int hx;
 NODE *n;

 if (newstate[apx] == SIZE-2)
  { printsoln(up);
    printf("finish\n");
    exit(0);
  }
#ifdef VERBOSE
 printf("maybe queueing ");
 dumpstate(newdepth,newstate);
 printf("\n");
#endif
 h = hash(newstate,npcs*sizeof(int));
 for (hx=h%HTSIZE;(n=nodeht[hx]);hx=(hx+1)%HTSIZE)
  { if (n->hash != h) continue;
    if (bcmp(n->state,newstate,npcs*sizeof(int))) continue;
    if (newdepth < n->depth) abort();
#ifdef VERBOSE
    printf("not queueing, already present\n");
#endif
    return;
  }
#ifdef VERBOSE
 printf("queueing\n");
#endif
 n = newnode();
 n->depth = newdepth;
 n->up = up;
 n->sib = up->kids;
 up->kids = n;
 n->livelink = live;
 live = n;
 nlive ++;
 bcopy(newstate,n->state,npcs*sizeof(int));
 n->hash = h;
 nodeht[hx] = n;
 nodehtload ++;
 if (nodehtload > HTSIZE/2)
  { fprintf(stderr,"%s: hash table overflow\n",__progname);
    exit(1);
  }
}

static void movefrom(NODE *n, int newdepth)
{
 int i;
 int j;
 PIECE *p;

 bcopy(n->state,newstate,npcs*sizeof(int));
 for (i=npcs-1;i>=0;i--)
  { p = &pcs[i];
    for (j=n->state[i]-1;j>=0;j--)
     { if (! can_move_to(newstate,i,j)) break;
       newstate[i] = j;
       maybe_queue(newstate,n,newdepth);
     }
    for (j=n->state[i]+1;j+p->size<=SIZE;j++)
     { if (! can_move_to(newstate,i,j)) break;
       newstate[i] = j;
       maybe_queue(newstate,n,newdepth);
     }
    newstate[i] = n->state[i];
  }
}

static void search(void)
{
 NODE *oldlive;
 NODE *n;

 newstate = malloc(npcs*sizeof(int));
#ifdef VERBOSE
 printf("root: ");
 dumpstate(root->depth,root->state);
 printf("\n");
#endif
 while (1)
  { if (! live)
     { printf("No solution found\n");
       return;
     }
    printf("Live nodes = %d, hash table load = %d\n",nlive,nodehtload);
    oldlive = live;
    live = 0;
    nlive = 0;
    while (oldlive)
     { n = oldlive;
       oldlive = n->livelink;
#ifdef VERBOSE
       printf("moving from ");
       dumpstate(n->depth,n->state);
       printf("\n");
#endif
       movefrom(n,n->depth+1);
     }
  }
}

int main(void);
int main(void)
{
 init_hash();
 read_puzzle();
 search();
 return(0);
}