typedef unsigned char u8t;
typedef unsigned short u16t;
enum { NR=4, NC=4, NCELLS = NR*NC };
enum { UP, DOWN, LEFT, RIGHT, NDIRS };
enum { OK = 1<<8, XX = 1<<9, FOUND = 1<<10, zz=0x80 };
enum { MAX_INT=0x7E, MAX_NODES=(16*65536)*90};
enum { BIT_HDR=1<<0, BIT_GRID=1<<1, BIT_OTHER=1<<2 };
enum { PHASE1,PHASE2 };  

typedef struct { u16t dn; u16t hn; }HSORT_T;

typedef struct {
   u8t data[NCELLS]; unsigned id; unsigned src;
   u8t h; u8t g; u8t udlr;
}NODE_T;  

NODE_T goal44={
   {1,2,3,4, 5,6,7,8, 9,10,11,12, 13,14,15,0},0,0,0,0,0};
NODE_T work; 

NODE_T G34={ 
 {13,9,5,4, 15,6,1,8, 0,10,2,11, 14,3,7,12},0,0,0,0,0};

NODE_T G52={ 
   {15,13,9,5, 14,6,1,4,  10,12,0,8, 3,7,11,2},0,0,0,0,0};

NODE_T G99={ 
   {15,14,1,6, 9,11,4,12, 0,10,7,3, 13,8,5,2},0,0,0,0,0};

struct {
   unsigned nodes;
   unsigned gfound;
   unsigned root_visits;
   unsigned verbose;
   unsigned locks;
   unsigned phase;
}my;

u16t  HybridIDA_star(NODE_T *pNode);
u16t  make_node(NODE_T *pNode, NODE_T *pNew, u8t udlr );
u16t  search(NODE_T *pNode, u16t bound);
u16t  taxi_dist( NODE_T *pNode);
u16t  tile_home( NODE_T *p44);
void  print_node( NODE_T *pN, const char *pMsg, short force );
u16t  goal_found(NODE_T *pNode);
char  udlr_to_char( char udlr );
void  idx_to_rc( u16t idx, u16t *row, u16t *col );
void  sort_nodes(HSORT_T *p);

int main( )
{
   my.verbose = 0;		
   
   

   memcpy(&work,  &G99, sizeof(NODE_T));  
   if(1){   
      printf();
      my.phase = PHASE1;
      (void) HybridIDA_star(&work);
   }
   printf();
   my.phase = PHASE2;
   (void)HybridIDA_star(&work);
   return 0;
}


u16t HybridIDA_star(NODE_T *pN){
   my.nodes = 1;
   my.gfound = 0;
   my.root_visits = 0;
   pN->udlr = NDIRS;
   pN->g = 0;
   pN->h = taxi_dist(pN);
   pN->id = my.nodes;
   pN->src = 0;
   const char *pr = {}; 
   print_node( pN,pr,1 );
   u16t depth = pN->h;
   while(1){
      depth = search(pN,depth);
      if( depth & FOUND){
         return FOUND;  
      }
      if( depth & 0xFF00 ){
	 printf(,depth);
	 return XX;
      }
      my.root_visits++;
      printf(,my.root_visits,depth);
   }
   return 0;
}


u16t search(NODE_T *pN, u16t bound){ 
   if(bound & 0xff00){ return bound; }
   u16t f = pN->g + pN->h;
   if( f > bound){ return f; }
   if(goal_found(pN)){
      my.gfound = pN->g;
      memcpy(&work,pN,sizeof(NODE_T));
      printf(, my.nodes, my.gfound);
      const char *pr = {}; 
      print_node( &work,pr,1 );
      return FOUND;
   }
   NODE_T news;
   
   
   
   HSORT_T hlist[NDIRS];
   for( short i=0; i<NDIRS; i++ ){
      u16t rv = make_node(pN,&news, i );
      hlist[i].dn = i;
      if( rv & OK ){
	 hlist[i].hn = news.h;
	 continue;
      }
      hlist[i].hn = XX;
   }
   sort_nodes(&hlist[0]);

   u16t temp, min = MAX_INT; 
   for( short i=0; i<NDIRS; i++ ){
      if( hlist[i].hn > 0xff ) continue;
      temp = make_node(pN,&news, hlist[i].dn );
      if( temp & XX ) return XX;
      if( temp & OK ){
	 news.id = my.nodes++;
	 print_node(&news,,0 );
	 temp = search(&news, bound);
	 if(temp & 0xff00){  return temp;}
	 if(temp < min){ min = temp; }
      }
   }
   return min;
}


void sort_nodes(HSORT_T *p){
   for( short s=0; s<NDIRS-1; s++ ){
      HSORT_T tmp = p[0];
      if( p[1].hn < p[0].hn ){tmp=p[0]; p[0]=p[1]; p[1]=tmp; }
      if( p[2].hn < p[1].hn ){tmp=p[1]; p[1]=p[2]; p[2]=tmp; }
      if( p[3].hn < p[2].hn ){tmp=p[2]; p[2]=p[3]; p[3]=tmp; }
   }
}


u16t tile_home(NODE_T *pN ){
   for( short i=0; i<NCELLS; i++ ){
      if( pN->data[i] == 0 ) return i;
   }
   return XX;
}


void print_node( NODE_T *pN, const char *pMsg, short force ){
   const int tp1 = 0;
   if( my.verbose & BIT_HDR || force || tp1){
      char ch = udlr_to_char(pN->udlr);
      printf(,
	     pN->id, pN->src, pN->h, pN->g, ch, pMsg);
   }
   if(my.verbose & BIT_GRID || force || tp1){
      for(u16t i=0; i<NR; i++ ){
	 for( u16t j=0; j<NC; j++ ){
	    printf(,pN->data[i*NR+j]);
	 }
	 printf();
      }
      printf();
   }
   
}


u16t goal_found(NODE_T *pN) {
   if(my.phase==PHASE1){
      short tags = 0;
      for( short i=0; i<(NC); i++ ){
	 if( pN->data[i] == i+1 ) tags++;
      }
      if( tags==4 ) return 1;  
   }

   for( short i=0; i<(NR*NC); i++ ){
      if( pN->data[i] != goal44.data[i] ) return 0;
   }
   return 1;
}


char udlr_to_char( char udlr ){
   char ch = '?';
   switch(udlr){
   case UP:    ch = 'U'; break;
   case DOWN:  ch = 'D'; break;
   case LEFT:  ch = 'L'; break;
   case RIGHT: ch = 'R'; break;
   default: break;
   }
   return ch;
}


void idx_to_rc( u16t idx, u16t *row, u16t *col ){
   *row = idx/NR; *col = abs( idx - (*row * NR));
}



u16t make_node(NODE_T *pSrc, NODE_T *pNew, u8t udlr ){
   u16t row,col,home_idx,idx2;
   if(udlr>=NDIRS||udlr<0 ){ printf(,udlr); return XX; }
   if(my.nodes > MAX_NODES ){ printf(,my.nodes);
      return XX; }
   memcpy(pNew,pSrc,sizeof(NODE_T));
   home_idx = tile_home(pNew);
   idx_to_rc(home_idx, &row, &col );

   if( udlr == LEFT)  { if( col < 1 ) return 0; col--; }
   if( udlr == RIGHT ){ if( col >= (NC-1) ) return 0; col++; }
   if( udlr == DOWN ) { if(row >= (NR-1)) return 0; row++; }
   if( udlr == UP ){	 if(row < 1) return 0; row--; }
   idx2 = row * NR + col;
   if( idx2 < NCELLS ){
      u8t *p = &pNew->data[0];
      p[home_idx] = p[idx2];
      p[idx2]     = 0; 
      pNew->src   = pSrc->id;
      pNew->g     = pSrc->g + 1;
      pNew->h     = taxi_dist(pNew);
      pNew->udlr  = udlr; 
      return OK;
   }
   return 0;
}


u16t taxi_dist( NODE_T *pN){
   u16t tile,sum = 0, r1,c1,r2,c2;
   u8t *p44 = &pN->data[0];
   for( short i=0; i<(NR*NC); i++ ){
      tile = p44[i];
      if( tile==0 ) continue;
      idx_to_rc(i, &r2, &c2 );
      idx_to_rc(tile-1, &r1, &c1 );
      sum += abs(r1-r2) + abs(c1-c2);
   }
   }
   return sum;
}