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

typedef struct pc PC;
typedef struct form FORM;
typedef struct getfn GETFN;
typedef struct cell CELL;

struct pc {
  int x;
  int y;
  char key;
  char bitmap[3][5];
  int inx;
  int nforms;
  FORM *forms;
  unsigned int placed : 1;
  int place_x;
  int place_y;
  int place_form;
  } ;

struct form {
  int finx;
  PC *pc;
  int inx;
  const GETFN *get;
  } ;

struct getfn {
  const char *tag;
  int (*cell)(const PC *, int, int);
  int (*xsize)(const PC *);
  int (*ysize)(const PC *);
  } ;

struct cell {
  char key;
  char colour;
  } ;

#define BOARDSZ 19

static CELL board[BOARDSZ][BOARDSZ];
static int unplaced;

static PC pcs[]
 = { /* one square */
     { 1, 1, '1',
       { { 1 } } },
     /* two squares */
     { 1, 2, '2',
       { { 1, 1 } } },
     /* three squares */
     { 1, 3, '3',
       { { 1, 1, 1 } } },
     { 2, 2, 'v',
       { { 1, 1 },
	 { 1, 0 } } },
     /* four squares */
     { 1, 4, '4',
       { { 1, 1, 1, 1 } } },
     { 2, 3, 'l',
       { { 1, 1, 1 },
	 { 1, 0, 0 } } },
     { 2, 3, 't',
       { { 1, 1, 1 },
	 { 0, 1, 0 } } },
     { 2, 3, 'n',
       { { 1, 1, 0 },
	 { 0, 1, 1 } } },
     { 2, 2, 'o',
       { { 1, 1 },
	 { 1, 1 } } },
     /* five squares */
     { 3, 3, 'T',
       { { 1, 1, 1 },
	 { 0, 1, 0 },
	 { 0, 1, 0 } } },
     { 2, 3, 'U',
       { { 1, 0, 1 },
	 { 1, 1, 1 } } },
     { 3, 3, 'V',
       { { 0, 0, 1 },
	 { 0, 0, 1 },
	 { 1, 1, 1 } } },
     { 3, 3, 'W',
       { { 0, 0, 1 },
	 { 0, 1, 1 },
	 { 1, 1, 0 } } },
     { 3, 3, 'X',
       { { 0, 1, 0 },
	 { 1, 1, 1 },
	 { 0, 1, 0 } } },
     { 2, 4, 'Y',
       { { 0, 0, 1, 0 },
	 { 1, 1, 1, 1 } } },
     { 3, 3, 'Z',
       { { 1, 1, 0 },
	 { 0, 1, 0 },
	 { 0, 1, 1 } } },
     { 3, 3, 'F',
       { { 0, 1, 1 },
	 { 1, 1, 0 },
	 { 0, 1, 0 } } },
     { 1, 5, 'I',
       { { 1, 1, 1, 1, 1 } } },
     { 2, 4, 'L',
       { { 0, 0, 0, 1 },
	 { 1, 1, 1, 1 } } },
     { 2, 3, 'P',
       { { 1, 1, 1 },
	 { 0, 1, 1 } } },
     { 2, 4, 'N',
       { { 1, 1, 1, 0 },
	 { 0, 0, 1, 1 } } } };
#define NPCS (sizeof(pcs)/sizeof(pcs[0]))

static char (*self_overlap)[BOARDSZ][BOARDSZ];

#define FNS() FN(none) FN(cw) FN(180) FN(ccw)\
	FN(flip_lr) FN(flip_ud) FN(flip_slash) FN(flip_back)

#define FN(x) \
	static int get_cell_##x(const PC *, int, int);	\
	static int get_xsize_##x(const PC *);		\
	static int get_ysize_##x(const PC *);
FNS()
#undef FN

#define FN(x) { #x, &get_cell_##x, &get_xsize_##x, &get_ysize_##x },
static const GETFN getfns[]
 = { FNS() };
#undef FN

#define MAXFORMS (sizeof(getfns)/sizeof(getfns[0]))

#define DEFS(tag,bitx,bity,xsz,ysz) \
	static int get_cell_##tag(const PC *pc, int x, int y)		\
	{ return(pc->bitmap[bitx][bity]); }				\
	static int get_xsize_##tag(const PC *pc)			\
	{ return(pc->xsz); }						\
	static int get_ysize_##tag(const PC *pc)			\
	{ return(pc->ysz); }
DEFS(none,x,y,x,y)
DEFS(cw,pc->x-1-y,x,y,x)
DEFS(180,pc->x-1-x,pc->y-1-y,x,y)
DEFS(ccw,y,pc->y-1-x,y,x)
DEFS(flip_lr,pc->x-1-x,y,x,y)
DEFS(flip_ud,x,pc->y-1-y,x,y)
DEFS(flip_slash,y,x,y,x)
DEFS(flip_back,pc->x-1-y,pc->y-1-x,y,x)
#undef DEFS

static int sameform(FORM *a, FORM *b)
{
 int sx;
 int sy;
 int x;
 int y;

 sx = (*a->get->xsize)(a->pc);
 if (sx != (*b->get->xsize)(b->pc)) return(0);
 sy = (*a->get->ysize)(a->pc);
 if (sy != (*b->get->ysize)(b->pc)) return(0);
 for (y=sy-1;y>=0;y--)
  { for (x=sx-1;x>=0;x--)
     { if ((*a->get->cell)(a->pc,x,y) != (*b->get->cell)(b->pc,x,y)) return(0);
     }
  }
 return(1);
}

static void setup_forms(void)
{
 int i;
 int j;
 int k;
 int nforms;
 FORM forms[MAXFORMS];
 FORM *f;
 int finx;
 char b[BOARDSZ][BOARDSZ];

 finx = 0;
 for (i=NPCS-1;i>=0;i--)
  { nforms = 0;
    for (j=MAXFORMS-1;j>=0;j--)
     { f = &forms[nforms];
       f->pc = &pcs[i];
       f->get = &getfns[j];
       do <"found">
	{ for (k=nforms-1;k>=0;k--)
	   { if (sameform(f,&forms[k]))
	      { forms[k] = *f;
		break <"found">;
	      }
	   }
	  nforms ++;
	} while (0);
     }
    pcs[i].inx = i;
    pcs[i].nforms = nforms;
    pcs[i].forms = malloc(nforms*sizeof(FORM));
    bcopy(&forms[0],pcs[i].forms,nforms*sizeof(FORM));
    for (j=nforms-1;j>=0;j--)
     { pcs[i].forms[j].inx = j;
       pcs[i].forms[j].finx = finx ++;
     }
  }
 self_overlap = malloc(finx*sizeof(*self_overlap));
 for (i=NPCS-1;i>=0;i--)
  { for (j=pcs[i].nforms-1;j>=0;j--)
     { int x;
       int y;
       int xs;
       int ys;
       int cx;
       int cy;
       int bx;
       int by;
       int r;
       int tmp;
       f = &pcs[i].forms[j];
       bzero(&self_overlap[f->finx],sizeof(self_overlap[0]));
       xs = (*f->get->xsize)(f->pc);
       ys = (*f->get->ysize)(f->pc);
       for (x=BOARDSZ-xs;x>=0;x--)
	{ for (y=BOARDSZ-ys;y>=0;y--)
	   { bzero(&b,sizeof(b));
	     do <"nextloc">
	      { for (cx=xs-1;cx>=0;cx--)
		 { for (cy=ys-1;cy>=0;cy--)
		    { if (! (*f->get->cell)(f->pc,cx,cy)) continue;
		      bx = x + cx;
		      by = y + cy;
		      for (r=3;r>=0;r--)
		       { if (b[bx][by])
			  { self_overlap[f->finx][x][y] = 1;
			    break <"nextloc">;
			  }
			 b[bx][by] = 1;
			 tmp = bx;
			 bx = by;
			 by = BOARDSZ-1 - tmp;
		       }
		    }
		 }
	      } while (0);
	   }
	}
#if 0
       printf("%c %s:\n",f->pc->key,f->get->tag);
       for (x=0;x<xs;x++)
	{ printf("\t");
	  for (y=0;y<ys;y++)
	   { printf(" %c",(*f->get->cell)(f->pc,x,y)?'*':'·');
	   }
	  printf("\n");
	}
       for (x=0;x<BOARDSZ;x++)
	{ for (y=0;y<BOARDSZ;y++)
	   { char c;
	     c = ' ';
	     switch (x)
	      { case 9:
		   switch (y)
		    { case 9: c = '/'; break;
		      case 11: c = '\\'; break;
		    }
		   break;
		case 10:
		   switch (y)
		    { case 9: c = '\\'; break;
		      case 11: c = '/'; break;
		    }
		   break;
	      }
	     printf("%c%c",c,self_overlap[f->finx][x][y]?'X':'·');
	   }
	  printf("\n");
	}
#endif
     }
  }
}

static void dumpboard(char emphkey)
{
 int x;
 int y;
 CELL *c;

 for (x=0;x<BOARDSZ;x++)
  { printf("|");
    for (y=0;y<BOARDSZ;y++)
     { c = &board[x][y];
       if (c->key)
	{ if ((c->key == emphkey) || (c->colour > 3))
	   { printf(" _\b%c_\b%d",c->key,c->colour);
	   }
	  else
	   { printf(" %c%d",c->key,c->colour);
	   }
	}
       else
	{ printf(" ··");
	}
     }
    printf("\n");
  }
}

static void placeit(FORM *f, int atx, int aty)
{
 int ysz;
 int xsz;
 int x;
 int y;
 CELL *c;
 int bx;
 int by;
 int bt;
 int i;

#if 0
 printf("%*splacing %c %s at %d %d\n",21-unplaced,"",f->pc->key,f->get->tag,atx,aty);
#endif
 if (f->pc->placed)
  { printf("*** %c already placed\n",f->pc->key);
    dumpboard(f->pc->key);
    abort();
  }
 f->pc->placed = 1;
 f->pc->place_x = atx;
 f->pc->place_y = aty;
 f->pc->place_form = f->inx;
 xsz = (*f->get->xsize)(f->pc);
 ysz = (*f->get->ysize)(f->pc);
 for (x=xsz-1;x>=0;x--)
  { for (y=ysz-1;y>=0;y--)
     { if (! (*f->get->cell)(f->pc,x,y)) continue;
       bx = atx + x;
       by = aty + y;
       for (i=4-1;i>=0;i--)
	{ c = &board[bx][by];
	  if (c->key)
	   { printf("*** %d %d already taken (pc %d %d, rot %d)\n",bx,by,x,y,i);
	     c->colour += 4;
	     dumpboard('\0');
	     abort();
	   }
	  c->key = f->pc->key;
	  c->colour = i;
	  bt = bx;
	  bx = by;
	  by = BOARDSZ-1 - bt;
	}
     }
  }
#if 0
 dumpboard(f->pc->key);
#endif
 unplaced --;
}

static void unplaceit(FORM *f)
{
 int ysz;
 int xsz;
 int x;
 int y;
 CELL *c;
 int bx;
 int by;
 int bt;
 int i;

#if 0
 printf("%*sremoving %c %s from %d %d\n",20-unplaced,"",f->pc->key,f->get->tag,f->pc->place_x,f->pc->place_y);
#endif
 if (! f->pc->placed)
  { printf("*** %c not placed\n",f->pc->key);
    dumpboard('\0');
    abort();
  }
 if (f->pc->place_form != f->inx)
  { printf("*** %c placed form is %s, not %s\n",
	f->pc->key,f->pc->forms[f->pc->place_form].get->tag,f->get->tag);
    dumpboard(f->pc->key);
    abort();
  }
 ysz = (*f->get->ysize)(f->pc);
 xsz = (*f->get->xsize)(f->pc);
 for (x=xsz-1;x>=0;x--)
  { for (y=ysz-1;y>=0;y--)
     { if (! (*f->get->cell)(f->pc,x,y)) continue;
       bx = f->pc->place_x + x;
       by = f->pc->place_y + y;
       for (i=4-1;i>=0;i--)
	{ c = &board[bx][by];
	  if (! c->key)
	   { printf("*** %d %d not taken (pc %d %d, rot %d)\n",bx,by,x,y,i);
	     c->colour += 4;
	     dumpboard('\0');
	     abort();
	   }
	  c->key = '\0';
	  bt = bx;
	  bx = by;
	  by = BOARDSZ-1 - bt;
	}
     }
  }
 f->pc->placed = 0;
 unplaced ++;
#if 0
 dumpboard('\0');
#endif
}

#define CP_NO     1
#define CP_YES    2
#define CP_FUTURE 3
static int can_place(FORM *f, int atx, int aty)
{
 int ysz;
 int xsz;
 int x;
 int y;
 CELL *c;
 int bx;
 int by;
 int ok;

 if (self_overlap[f->finx][atx][aty]) return(CP_NO);
 ysz = (*f->get->ysize)(f->pc) - 1;
 xsz = (*f->get->xsize)(f->pc) - 1;
 ok = 0;
 for (y=ysz;y>=0;y--)
  { for (x=xsz;x>=0;x--)
     { if (! (*f->get->cell)(f->pc,x,y)) continue;
       bx = atx + x;
       by = aty + y;
       if (board[bx][by].key) return(CP_NO);
       if (bx > 0)
	{ c = &board[bx-1][by];
	  if (c->key && (c->colour == 3)) return(CP_NO);
	}
       if (by > 0)
	{ c = &board[bx][by-1];
	  if (c->key && (c->colour == 3)) return(CP_NO);
	}
       if (bx < BOARDSZ-1)
	{ c = &board[bx+1][by];
	  if (c->key && (c->colour == 3)) return(CP_NO);
	}
       if (by < BOARDSZ-1)
	{ c = &board[bx][by+1];
	  if (c->key && (c->colour == 3)) return(CP_NO);
	}
       if (! ok)
	{ do <"done">
	   { do <"ok">
	      { if ((bx > 0) && (by > 0))
		 { c = &board[bx-1][by-1];
		   if (c->key && (c->colour == 3)) break <"ok">;
		 }
		if ((bx > 0) && (by < BOARDSZ-1))
		 { c = &board[bx-1][by+1];
		   if (c->key && (c->colour == 3)) break <"ok">;
		 }
		if ((bx < BOARDSZ-1) && (by > 0))
		 { c = &board[bx+1][by-1];
		   if (c->key && (c->colour == 3)) break <"ok">;
		 }
		if ((bx < BOARDSZ-1) && (by < BOARDSZ-1))
		 { c = &board[bx+1][by+1];
		   if (c->key && (c->colour == 3)) break <"ok">;
		 }
		break <"done">;
	      } while (0);
	     ok = 1;
	   } while (0);
	}
     }
  }
 return(ok?CP_YES:CP_FUTURE);
}

static void havesoln(void)
{
 int x;
 int y;
 CELL *c;

 for (x=0;x<BOARDSZ;x++)
  { if (x) printf(" ");
    printf("(");
    for (y=0;y<BOARDSZ;y++)
     { c = &board[x][y];
       printf("%c",c->key?:'.');
     }
    printf(")");
  }
 printf("\n");
 fflush(stdout);
}

static void search(void)
{
 int x;
 int y;
 int px;
 PC *p;
 int fx;
 FORM *f;
 int xsz;
 int ysz;

 if (unplaced < 1)
  { havesoln();
    return;
  }
 for <"nextpc"> (px=NPCS-1;px>=0;px--)
  { p = &pcs[px];
    if (p->placed) continue;
    for (fx=p->nforms-1;fx>=0;fx--)
     { f = &p->forms[fx];
       xsz = (*f->get->xsize)(f->pc);
       ysz = (*f->get->ysize)(f->pc);
       for (x=BOARDSZ-xsz;x>=0;x--)
	{ for (y=BOARDSZ-ysz;y>=0;y--)
	   { switch (can_place(f,x,y))
	      { case CP_YES:
		case CP_FUTURE:
		   continue <"nextpc">;
	      }
	   }
	}
     }
#if 0
    printf("%*sno place for %c\n",21-unplaced,"",p->key);
#endif
    return;
  }
 for <"nextpc"> (px=NPCS-1;px>=0;px--)
  { p = &pcs[px];
    if (p->placed) continue;
    for (fx=p->nforms-1;fx>=0;fx--)
     { f = &p->forms[fx];
       xsz = (*f->get->xsize)(f->pc);
       ysz = (*f->get->ysize)(f->pc);
       for (x=BOARDSZ-xsz;x>=0;x--)
	{ for (y=BOARDSZ-ysz;y>=0;y--)
	   { switch (can_place(f,x,y))
	      { case CP_YES:
		   placeit(f,x,y);
		   search();
		   unplaceit(f);
		   break;
	      }
	   }
	}
     }
  }
}

static void solve(void)
{
 int i;
 int j;
 FORM *f;

 for (i=BOARDSZ-1;i>=0;i--)
  { for (j=BOARDSZ-1;j>=0;j--)
     { board[i][j].key = '\0';
     }
  }
 for (i=NPCS-1;i>=0;i--) pcs[i].placed = 0;
 unplaced = NPCS;
 for (i=NPCS-1;i>=0;i--)
  { for (j=pcs[i].nforms-1;j>=0;j--)
     { f = &pcs[i].forms[j];
       if ((*f->get->cell)(f->pc,0,0))
	{ placeit(f,0,0);
	  search();
	  unplaceit(f);
	}
     }
  }
}

int main(void);
int main(void)
{
 setup_forms();
 solve();
 return(0);
}