/*------------------------------------------------*/
/*     Copyright(C) T.Nakamura 2001               */
/*     E-Mail: nakamura@tokyo.email.ne.jp         */
/*------------------------------------------------*/
/*  hexomino                                      */
/*                                                */
/*  usage : hex                                   */
/*                                                */
/*------------------------------------------------*/
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <conio.h>

/*------------------------*/
/*  define constant       */
/*------------------------*/
#define PIECE_NO        35
#define PIECE_CELL_NO    6
#define PIECE_DIRECTION  8
#define UNUSE            0
#define USE              1
#define INHIBIT         -1
#define VACANT           0
#define VACANT_FLAG  99999
#define MAX_X           21
#define MAX_Y           15
#define GOOD             0
#define NG               1
#define RAND_INIT          123
#define SHUFFLE_PIECE_ORDER 40
#define SHUFFLE_PIECE_DIR    5
#define REQUIRE_SOLUTION 1000000
#define DISPLAY_INTERVAL      2
#define CHANGE_APPROCH_COL    1

#define LEFT15		     1

/*------------------------*/
/*  external variable     */
/*------------------------*/
int  board[MAX_X][MAX_Y];
#if LEFT15
  int  use_piece[] = 
  { 1, 0, 0, 1, 1,  0, 1, 0, 0, 0,
    1, 0, 1, 1, 1,  1, 1, 1, 1, 0,
    0, 0, 1, 0, 0,  1, 1, 0, 1, 1,
    0, 1, 1, 1, 0 };
#else
  int  use_piece[PIECE_NO];
#endif
int  seq_no;
int  size_x;
int  size_y;
clock_t t1,t2;

/*------------------------*/
void display(void);

struct piece_s {
 int x;
 int y;
};

struct piece_org_s {
  struct piece_s piece[PIECE_CELL_NO];
};

void copy_piece(struct piece_org_s *target, struct piece_org_s *source)
{
  int i;
  for (i=0; i<PIECE_CELL_NO; i++) {
    target->piece[i].x = source->piece[i].x;
    target->piece[i].y = source->piece[i].y;
  }
}

void mirror_piece(struct piece_org_s *target, struct piece_org_s
*source)
{
  int i;
  for (i=0; i<PIECE_CELL_NO; i++) {
    target->piece[i].x = source->piece[i].x;
    target->piece[i].y = -(source->piece[i].y);
  }
}

void rotate_piece(struct piece_org_s *target)
{
  int i;
  int tmp;
  for (i=0; i<PIECE_CELL_NO; i++) {
    tmp = target->piece[i].x;
    target->piece[i].x = -(target->piece[i].y);
    target->piece[i].y = tmp;
  }
}

int sort_piece(struct piece_s *a, struct piece_s *b)
{
  if (a->x > b->x) return(1);
  else if (a->x == b->x) {
    if (a->y > b->y) return(1);
  }
  return(-1);
}

int sort_piece2(struct piece_s *a, struct piece_s *b)
{
  if (a->y > b->y) return(1);
  else if (a->y == b->y) {
    if (a->x > b->x) return(1);
  }
  return(-1);
}

void origin_piece(struct piece_org_s *target, int p)
{
  int i;
  if (p==0)
    qsort(&(target->piece[0]),PIECE_CELL_NO,sizeof(struct piece_s),
          sort_piece);
  else
    qsort(&(target->piece[0]),PIECE_CELL_NO,sizeof(struct piece_s),
          sort_piece2);
  
  for (i=PIECE_CELL_NO-1; i>=0; i--) {
    target->piece[i].x -= target->piece[0].x;
    target->piece[i].y -= target->piece[0].y;
  }
/**
  printf("%d :",i);
  for (i=0; i<PIECE_CELL_NO; i++) {
    printf("  %2d,%2d",target->piece[i].x,target->piece[i].y);
  }
  printf("\n");
**/
}

struct piece_x {
 int no;
  struct {
    int x[PIECE_CELL_NO-1];
    int y[PIECE_CELL_NO-1];
  } type[PIECE_DIRECTION];
} piece[2][PIECE_NO];

void entry_piece(int piece_no,struct piece_org_s *target)
{
  int p;
  int i;
  int same;
  int no;

  for (p=0; p<2; p++) {
  origin_piece(target,p);

/*** DEBUG
  printf("%d :",i);
  for (i=0; i<PIECE_CELL_NO; i++) {
    printf("  %2d,%2d",target->piece[i].x,target->piece[i].y);
  }
  printf("\n");
 ***/

  same = 0;
  for (i=0; i<piece[p][piece_no].no; i++) {
    if (piece[p][piece_no].type[i].x[0] == target->piece[1].x &&
        piece[p][piece_no].type[i].y[0] == target->piece[1].y &&
        piece[p][piece_no].type[i].x[1] == target->piece[2].x &&
        piece[p][piece_no].type[i].y[1] == target->piece[2].y &&
        piece[p][piece_no].type[i].x[2] == target->piece[3].x &&
        piece[p][piece_no].type[i].y[2] == target->piece[3].y &&
        piece[p][piece_no].type[i].x[3] == target->piece[4].x &&
        piece[p][piece_no].type[i].y[3] == target->piece[4].y &&
        piece[p][piece_no].type[i].x[4] == target->piece[5].x &&
        piece[p][piece_no].type[i].y[4] == target->piece[5].y) {
       same = 1;
       break;
     }
  }

  if (same == 0) {
    no = piece[p][piece_no].no++;
    for (i=0; i<PIECE_CELL_NO-1; i++) {
      piece[p][piece_no].type[no].x[i] = target->piece[1+i].x;
      piece[p][piece_no].type[no].y[i] = target->piece[1+i].y;
    }
  }

  }
}

void dump_piece()
{

  int i,j,k,m,p;
  int posx,posy;
  size_x = 9;
  size_y = 12;

  /*** init board ***/
  for (i=0; i<MAX_X; i++)
    for (j=0; j<MAX_Y; j++)
      board[i][j] = INHIBIT;

  for (p=0; p<2 ;p++) {
  for (i=0; i<PIECE_NO; i++) {
      for (j=0; j<piece[p][i].no; j++) {
          for (k=1; k<size_x; k++)
            for (m=1; m<size_y; m++)
              board[k][m] = VACANT;

          seq_no = (i+1)*100+(j+1);
          posx = 2;
          posy = 5;
          board[posx][posy] =
          board[piece[p][i].type[j].x[0]+posx]
               [piece[p][i].type[j].y[0]+posy] =
          board[piece[p][i].type[j].x[1]+posx]
               [piece[p][i].type[j].y[1]+posy] =
          board[piece[p][i].type[j].x[2]+posx]
               [piece[p][i].type[j].y[2]+posy] =
          board[piece[p][i].type[j].x[3]+posx]
               [piece[p][i].type[j].y[3]+posy] =
          board[piece[p][i].type[j].x[4]+posx]
               [piece[p][i].type[j].y[4]+posy] = seq_no;

          display();
       }
     }
  }
}

void change_piece_order(void)
{
  int i,j,k,m;
  int piece_no,type_no;
  int no,x,y;
  static int 
  random[] = {
    16838,5758,10113,17515,31051,5627,23010,7419,16212,4086,
    2749,12767,9084,12060,32225,17543,25089,21183,25137,25566,
    26966,4978,20495,10311,11367,30054,17031,13145,19882,25736,
    30524,28505,28394,22102,24851,19067,12754,11653,6561,27096,
    13628,15188,32085,4143,6967,31406,24165,13403,25562,24834,
    31353,920,10444,24803,7962,19318,1422,31327,10457,1945,
    14479,29983,18751,3894,18670,8259,16248,7757,15629,13306,
    28606,13990,11738,12516,1414,5262,17116,22825,3181,13134,
    25343,8022,11233,7536,9760,9979,29071,1201,21336,13061,
    22160,24005,30729,7644,27475,31693,25514,14139,22088,26521,
    5202,9171,4434,28317,24582,6815,4586,9653,26306,7174,18451,
    23448,6473,32434,8193,14110,24748,28210,29320,32049,12956,
    14162,4166,14997,7793,32310,21391,19799,7926,14905,25885,
    2582,15610,5000,8052,30965,20120,32380,15639,26204,24385,
    12475,15725,17265,3214,19471,11376,4697,25543,23297,14619,
    23087,3123,31549,18065,24256,18973,20901,25613,6157,9899,
    9267,22413,9598,18526,13711,10046,14566,18536,15988,19878,
    13626,4273,8387,1171,32017,3752,12388,21191,11483,18122,
    11744,18528,15585,5363,20159,5641,18176,9575,28578,27363,
    27685,29344,19489,17713,5511,21461,22626,8645,3496,26703,
    6270,13870,11529,27499,4500,8607,5808,15725,12457,16542,
    16474,11531,17222,3952,17024,19894,24015,18247,11276,26278,
    19365,8746,21976,18092,25851,29088,29163,2231,26233,29732,
    21106,5411,9874,5448,9344,27589,17574,1191,6789};
/***
      130,10982,1090,11656,7117,17595,6415,22948,31126,9004,14558,3571,
      22879,18492,1360,5412,26721,22463,25047,27119,31441,7190,13985,31214,
      27509,30252,26571,14779,19816,21681,19651,17995,23593,3734,13310,3979,
      21995,15561,16092,18489,11288,28466,8664,5892,13863,22766,5364,17639,
      21151,20427,100,25795,8812,15108,12666,12347,19042,19774,9169,5589,
      26383,9666,10941,13390,7878,13565,1779,16190,32233,53,13429,2285,2422,
      8333,31937,11636,13268,6460,6458,6936,8160,24842,29142,29667,24115,
      15116,17418,1156,4279,15008,15859,19561,8297,3755,22981,21275,29040,
      28690,1401,18137,16735,20343,25267,8312,7111,7733,10993,18554,4353,
      20126,1018,31086,6970,26484,20614,23431,23999,18086,18730,5504,10891,
      28492,27015,20143,31246,32484,32180,24168,16704,9679,23528,9365,20966,
      16135,5740,18323,12580,25378,12736,21327,4164,4748,11020,30113,21445,
      21249,23243,21480,21672,23625,32691,13799,18422,12344,32231,480,30870,
      14821,7776,17903,16205,20522,23192,19113,25878,14172,121,27381,23461,
      32332,14982,11562,30774,21118,18505,22889,7323,10152,29436,2365,31365,
      20079,2683,27762,23826,22109,30313,16179,9367,22310,10146,11623,24752,
      32028,30177,8013,13446,29935,13747,11094,29025,4778,4763,10563,4974,
      20459,31111,8831,3281,32099,8051,7103,2798,17294,28764,29656,8693,
      20147,29287,21472,2732,16926,26962,27785,24193,20125,17948,31930,
      32207,2104,12016,23918,3184,22326,11096,3794,12421,8269,16543,666,
      32642,40,2695,8100,17788,13855};
***/

  int rnd;
  int p;
  
  for (p=0; p<2; p++) {
  rnd = 0;

  for (k=0; k<SHUFFLE_PIECE_ORDER; k++) {

  piece_no = random[rnd++] % PIECE_NO;

  for (i=0; i<PIECE_DIRECTION; i++) {
    for (j=0 ;j<PIECE_CELL_NO-1; j++) {
      x = piece[p][piece_no].type[i].x[j];
      y = piece[p][piece_no].type[i].y[j];
      piece[p][piece_no].type[i].x[j] = piece[p][0].type[i].x[j];
      piece[p][piece_no].type[i].y[j] = piece[p][0].type[i].y[j];
      piece[p][0].type[i].x[j] = x;
      piece[p][0].type[i].y[j] = y;
    }
  }
  no = piece[p][piece_no].no;
  piece[p][piece_no].no = piece[p][0].no;
  piece[p][0].no = no;
  for (m=0; m<SHUFFLE_PIECE_DIR; m++) {
    type_no = random[rnd++] % no;
    for (j=0; j<PIECE_CELL_NO-1; j++) {
      x = piece[p][0].type[type_no].x[j];
      y = piece[p][0].type[type_no].y[j];
      piece[p][0].type[type_no].x[j] = piece[p][0].type[0].x[j];
      piece[p][0].type[type_no].y[j] = piece[p][0].type[0].y[j];
      piece[p][0].type[0].x[j] = x;
      piece[p][0].type[0].y[j] = y;
    }
  }
  }
  }

}

void init_piece(void)
{
  int i,j,k,p;
  int no;
  struct piece_org_s piece_tmp;

  static struct piece_org_s piece_org[PIECE_NO] = {
     0,0,  1,0,  2,0,  3,0,  4,0,  5,0,  /*  1.  XXXXXX   */

     0,0,  1,0,  2,0,  3,0,  4,0,  4,1,  /*  2.  XXXXX    */
                                         /*          X    */

     0,0,  1,0,  2,0,  3,0,  4,0,  3,1,  /*  3.  XXXXX    */
                                         /*         X     */

     0,0,  1,0,  2,0,  3,0,  4,0,  2,1,  /*  4.  XXXXX    */
                                         /*        X      */

     0,0,  1,0,  2,0,  3,0,  2,1,  3,1,  /*  5.  XXXX     */
                                         /*        XX     */

     0,0,  1,0,  2,0,  3,0,  1,1,  2,1,  /*  6.  XXXX     */
                                         /*       XX      */

     0,0,  1,0,  2,0,  3,0,  3,1,  4,1,  /*  7.  XXXX     */
                                         /*         XX    */

     0,0,  1,0,  2,0,  3,0,  0,1,  3,1,  /*  8.  XXXX     */
                                         /*      X  X     */

     0,0,  1,0,  2,0,  3,0,  0,1,  2,1,  /*  9.  XXXX     */
                                         /*      X X      */

     0,0,  1,0,  2,0,  0,1,  1,1,  2,1,  /* 10.  XXX      */
                                         /*      XXX      */

     0,0,  1,0,  2,0,  1,1,  2,1,  3,1,  /* 11.  XXX      */
                                         /*       XXX     */

     0,0,  1,0,  2,0,  2,1,  3,1,  4,1,  /* 12.  XXX      */
                                         /*        XXX    */

     0,0,  2,0,  3,0,  0,1,  1,1,  2,1,  /* 13.  X XX    */
                                         /*      XXX     */

     0,0,  1,0,  2,0,  3,0,  3,1,  3,2,  /* 14.  XXXX     */
                                         /*         X     */
                                         /*         X     */

     0,0,  1,0,  2,0,  3,0,  2,1,  2,2,  /* 15.  XXXX     */
                                         /*        X      */
                                         /*        X      */

     0,0,  1,0,  2,0,  2,1,  2,2,  3,2,  /* 16.  XXX      */
                                         /*        X      */
                                         /*        XX     */

     0,0,  1,0,  2,0,  1,1,  1,2,  2,2,  /* 17.  XXX      */
                                         /*       X       */
                                         /*       XX      */

     0,0,  1,0,  2,0,  0,1,  0,2,  1,2,  /* 18.  XXX      */
                                         /*      X        */
                                         /*      XX       */

     0,0,  1,0,  2,0,  0,1,  1,1,  0,2,  /* 19.  XXX      */
                                         /*      XX       */
                                         /*      X        */

     0,0,  1,0,  2,0,  0,1,  1,1,  1,2,  /* 20.  XXX      */
                                         /*      XX       */
                                         /*       X       */

     1,0,  0,1,  1,1,  2,1,  2,2,  3,2,  /* 21.   X       */
                                         /*      XXX      */
                                         /*        XX     */

     0,0,  1,0,  1,1,  2,1,  2,2,  3,2,  /* 22.  XX       */
                                         /*       XX      */
                                         /*        XX     */

     0,0,  1,0,  1,1,  2,1,  1,2,  2,2,  /* 23.  XX       */
                                         /*       XX      */
                                         /*       XX      */

     0,0,  1,0,  1,1,  2,1,  0,2,  1,2,  /* 24.  XX       */
                                         /*       XX      */
                                         /*      XX       */

     0,0,  1,0,  0,1,  1,1,  2,1,  1,2,  /* 25.  XX       */
                                         /*      XXX      */
                                         /*       X       */

     0,0,  0,1,  1,1,  2,1,  3,1,  0,2,  /* 26.  X        */
                                         /*      XXXX     */
                                         /*      X        */

     0,0,  0,1,  1,1,  2,1,  3,1,  1,2,  /* 27.  X        */
                                         /*      XXXX     */
                                         /*       X       */

     0,0,  0,1,  1,1,  2,1,  3,1,  2,2,  /* 28.  X        */
                                         /*      XXXX     */
                                         /*        X      */

     0,0,  0,1,  1,1,  2,1,  3,1,  3,2,  /* 29.  X        */
                                         /*      XXXX     */
                                         /*         X     */

     0,0,  0,1,  1,1,  2,1,  2,2,  3,2,  /* 30.  X        */
                                         /*      XXX      */
                                         /*        XX     */

     1,0,  0,1,  1,1,  2,1,  3,1,  2,2,  /* 31.   X       */
                                         /*      XXXX     */
                                         /*        X      */

     1,0,  0,1,  1,1,  2,1,  3,1,  1,2,  /* 32.   X       */
                                         /*      XXXX     */
                                         /*       X       */

     0,0,  1,0,  2,0,  2,1,  3,1,  2,2,  /* 33.  XXX      */
                                         /*        XX     */
                                         /*        X      */

     0,0,  0,1,  1,1,  2,1,  1,2,  1,3,  /* 34.  X        */
                                         /*      XXX      */
                                         /*       X       */
                                         /*       X       */

     0,0,  1,0,  1,1,  2,1,  2,2,  2,3,  /* 35.  XX       */
                                         /*       XX      */
                                         /*        X      */
                                         /*        X      */
};

  /*** Init ***/
  for (p=0; p<2; p++) {
  for (i=0; i<PIECE_NO; i++) {
    piece[p][i].no = 0;
    for (j=0; j<PIECE_DIRECTION; j++) {
      for (k=0; k<PIECE_CELL_NO-1; k++) {
        piece[p][i].type[j].x[k] = 0;
        piece[p][i].type[j].y[k] = 0;
      }
    }
  }
  }

  /*** Main ***/
  for (i=0; i<PIECE_NO; i++) {
    for (j=0; j<2; j++) {    /*** normal and mirror   ***/
      if (j==0) copy_piece  (&piece_tmp,&piece_org[i]);
      else      mirror_piece(&piece_tmp,&piece_org[i]);
      for (k=0; k<4; k++) {  /*** 4 rotate directions ***/
        if (k>0) rotate_piece(&piece_tmp);
        entry_piece(i,&piece_tmp);
      }
    }
  }

#if !LEFT15
  change_piece_order();
#endif

  /*** Dump ***/
/***
  for (p=0;p<2;p++) {
  for (i=0; i<PIECE_NO; i++) {
    no = piece[p][i].no;
    printf("PIECE KIND=%d  NO=%d\n",i+1,no);
    for (j=0; j<no; j++) {
      for(k=0; k<PIECE_CELL_NO-1;k++) {
        printf(" %2d,%2d", piece[p][i].type[j].x[k],
                           piece[p][i].type[j].y[k]);
      }2
      printf("\n");
    }
  }
  }
  dump_piece();
***/
}


void disp_piece(void) {
  int i, j;

#if 0
  for (j=0; j<MAX_Y; j++) {
    for (i=0; i<MAX_X; i++) {
      printf("%3d", board[i][j]);
    }
    printf("\n");
  }
#endif 
}

/*------------------------*/
/*  display result        */
/*------------------------*/
void display()
{
#define    MAX_COL  85
  char lp1[MAX_COL];
  char lp2[MAX_COL];

  int x,y,i;

  t2 = clock();
  printf("   seq_no=%d  time=%f\n",
         seq_no,((float)(t2-t1))/(float)CLOCKS_PER_SEC);

  for (y=0; y<=size_y; y++) {

    for(x=0; x<MAX_COL; x++) {
      lp1[x] = ' ';
      lp2[x] = ' ';
    }

    for (x=0; x<=size_x; x++) {
      if (board[x][y]!=board[x+1][y]) {
        lp1[4*x+3] = '|';
        lp2[4*x+3] = '+';
      }
      if (board[x][y]!=board[x][y+1]) {
        lp2[4*x-1] = '+';
        lp2[4*x  ] = '-';
        lp2[4*x+1] = '-';
        lp2[4*x+2] = '-';
        lp2[4*x+3] = '+';
      }
    }

#if LEFT15
    lp1[2*size_x+6] = '\0';
    lp2[2*size_x+6] = '\0';
#else
    lp1[4*size_x+4] = '\0';
    lp2[4*size_x+4] = '\0';
#endif
    if (y>0)
      printf("%s\n",lp1);
    printf("%s\n",lp2);
  }

//  printf("\n\n");
  fflush(stdout);
}

int blank_no;
/*------------------------*/
/*  check_blank_area      */
/*------------------------*/
void search_blank(int x,int y) {
    board[x][y] = VACANT_FLAG;
    blank_no++;
    if (board[x][y+1]==VACANT) search_blank(x,y+1);
    if (board[x+1][y]==VACANT) search_blank(x+1,y);
    if (board[x-1][y]==VACANT) search_blank(x-1,y);
    if (board[x][y-1]==VACANT) search_blank(x,y-1);
  }

void search_blank_clear(int x,int y) {
    while(x<=size_x) {
      while(y<=size_y) {
        if (board[x][y]==VACANT_FLAG) board[x][y] = VACANT;
        y++;
      }
      y = 1;
      x++;
    }
  }

void search_blank_clear2(int x,int y) {
    while(y<=size_y) {
      while(x<=size_x) {
        if (board[x][y]==VACANT_FLAG) board[x][y] = VACANT;
        x++;
      }
      x = CHANGE_APPROCH_COL;
      y++;
    }
  }


/*------------------------*/
/*  check_board           */
/*------------------------*/
int check_board(int x,int y,int p)
{

  if (p==0) {
    if (board[x+1][y]!=0 &&
        board[x][y+1]!=0) return NG;

    if (board[x][y+2]!=0 &&
        board[x+1][y+1]!=0 &&
        board[x+1][y]!=0) return NG;

    if (board[x][y+1]!=0 &&
        board[x+1][y+1]!=0 &&
        board[x+2][y]!=0 &&
        board[x+1][y-1]!=0) return NG;

    blank_no =0;
    search_blank(x,y);
    search_blank_clear(x,y);
  }
  else {
    if (board[x+1][y]!=0 &&
        board[x][y+1]!=0) return NG;

    if (board[x+2][y]!=0 &&
        board[x+1][y+1]!=0 &&
        board[x][y+1]!=0) return NG;

    if (board[x+1][y]!=0 &&
        board[x+1][y+1]!=0 &&
        board[x][y+2]!=0 &&
        board[x-1][y+1]!=0) return NG;

    blank_no =0;
    search_blank(x,y);
    search_blank_clear2(x,y);
  }
    
//  printf("blank %d\n", blank_no);
  if (blank_no%PIECE_CELL_NO!=0) return NG;

  return GOOD;
}


void dump_usepiece()
{
  int i;
  printf("use_piece\n");
  for (i=0;i<PIECE_NO;i++)
    printf("%d:%d\n",i,use_piece[i]);
}

/*------------------------*/
/*  put_piece             */
/*------------------------*/
void search(int posx,int posy,int put_no,int p)
{
  int i,j;
  int avno;
  int piece_no;

  if (p==0) {
    while(board[posx][posy]!=VACANT) {
      posy++;
      if (posy>size_y) {
        posy = 1;
        posx++;
        if (posx>=CHANGE_APPROCH_COL) {
          p = 1;
          break;
        }
      }
    }
  }
  if (p==1) {
    while(board[posx][posy]!=VACANT) {
      posx++;
      if (posx>size_x) {
        posx = CHANGE_APPROCH_COL;
        posy++;
      }
    }
  }

//printf("posx, y %d %d\n", posx, posy);

  /** check board **/
  if (check_board(posx, posy,p)) return;

// disp_piece(); getch();
//display();

  for (i=0; i<PIECE_NO; i++) {

    if (use_piece[i]==UNUSE) {

      for (j=0; j<piece[p][i].no; j++) {

        /*** area check ***/
        if (board[piece[p][i].type[j].x[0]+posx]
                 [piece[p][i].type[j].y[0]+posy]==VACANT &&
            board[piece[p][i].type[j].x[1]+posx]
                 [piece[p][i].type[j].y[1]+posy]==VACANT &&
            board[piece[p][i].type[j].x[2]+posx]
                 [piece[p][i].type[j].y[2]+posy]==VACANT &&
            board[piece[p][i].type[j].x[3]+posx]
                 [piece[p][i].type[j].y[3]+posy]==VACANT &&
            board[piece[p][i].type[j].x[4]+posx]
                 [piece[p][i].type[j].y[4]+posy]==VACANT) {
          /*** put ***/
          board[posx][posy] =
          board[piece[p][i].type[j].x[0]+posx]
               [piece[p][i].type[j].y[0]+posy] =
          board[piece[p][i].type[j].x[1]+posx]
               [piece[p][i].type[j].y[1]+posy] =
          board[piece[p][i].type[j].x[2]+posx]
               [piece[p][i].type[j].y[2]+posy] =
          board[piece[p][i].type[j].x[3]+posx]
               [piece[p][i].type[j].y[3]+posy] =
          board[piece[p][i].type[j].x[4]+posx]
               [piece[p][i].type[j].y[4]+posy] = put_no;

// display(); getch();
//printf("put_no %d\n", put_no);
          if (put_no!=PIECE_NO) {
            use_piece[i] = put_no;
/**
            if (put_no>20) display();
**/
            /*** search next piece place ***/
            if (p==0) search(posx,posy+1,put_no+1,p);
            else      search(posx+1,posy,put_no+1,p);
            use_piece[i] = UNUSE;
          }
          else {
            /*** display ***/
//printf("seq_no %d\n", seq_no);
            seq_no++;
//printf("seq_no %d\n", seq_no);
            if (seq_no%DISPLAY_INTERVAL==0 || seq_no==1) display();
            if (seq_no>REQUIRE_SOLUTION-1) exit(0);
          }

          /*** get last piece ***/
          board[posx][posy] =
          board[piece[p][i].type[j].x[0]+posx]
               [piece[p][i].type[j].y[0]+posy] =
          board[piece[p][i].type[j].x[1]+posx]
               [piece[p][i].type[j].y[1]+posy] =
          board[piece[p][i].type[j].x[2]+posx]
               [piece[p][i].type[j].y[2]+posy] =
          board[piece[p][i].type[j].x[3]+posx]
               [piece[p][i].type[j].y[3]+posy] =
          board[piece[p][i].type[j].x[4]+posx]
               [piece[p][i].type[j].y[4]+posy] = VACANT;
        }

      } /* end of for-j loop */

    }  /* end of unuse if (unuse piece) */

  }  /* end of for-i loop */

  return;

} /* end of search */

/*------------------------*/
/*  initialize            */
/*------------------------*/
void init(void)
{
  int i,j;

  /*** set area type ***/
  size_x = 19;
  size_y = 12;

  /*** init counter ***/
  seq_no = 0;

  /*** init board ***/
  for (i=0; i<MAX_X; i++)
    for (j=0; j<MAX_Y; j++)
      board[i][j] = INHIBIT;

  for (j=2; j<=4; j++)
    for (i=1; i<=9; i++)
      board[i][j] = VACANT;

  for (j=5; j<=7; j++)
    for (i=1; i<=7; i++)
      board[i][j] = VACANT;

  j=8;
    for (i=1; i<=8; i++)
      board[i][j] = VACANT;

  j=9;
    for (i=1; i<=10; i++)
      board[i][j] = VACANT;

  j=10;
    for (i=1; i<=9; i++)
      board[i][j] = VACANT;

  j=11;
    for (i=1; i<=8; i++)
      board[i][j] = VACANT;

  j=12;
    for (i=1; i<=7; i++)
      board[i][j] = VACANT;

  disp_piece();
//  getch();

  /*** init use_piece ***/
#if !LEFT15
  for (i=0; i<PIECE_NO; i++)
    use_piece[i] = UNUSE;
#endif

} /*** end of init ***/

/*------------------------*/
/*  main                  */
/*------------------------*/
void main(void)
{
  t1 = clock();

  init_piece();
  init();
  display();
#if LEFT15
  search(1,2,21,1);
#else
  search(1,2,1,0);
#endif
}
/*------------------------------------------------*/
/*  end of file                                   */
/*------------------------------------------------*/