/*------------------------------------------------*/
/*     Copyright(C) T.Nakamura 2002               */
/*     E-Mail: nakamura (at) tokyo.email.ne.jp    */
/*------------------------------------------------*/
/*  pentomino                                     */
/*                                                */
/*  usage : pento [ { "6*10" | "10*6" |           */
/*                    "5*12" | "12*5" |           */
/*                    "4*15" | "15*4" |           */
/*                    "3*20" | "20*3" |           */
/*                    "8*8"  } ]                  */
/*                                                */
/*          default ... "6*10"                    */
/*                                                */
/*------------------------------------------------*/
#include <stdio.h>
#include <string.h>
#include <time.h>

/*------------------------*/
/*  define constant       */
/*------------------------*/
#define PIECE_NO        12
#define PIECE_CELL_NO    5
#define PIECE_DIRECTION  8
#define UNUSE            0
#define USE              1
#define INHIBIT         -1
#define VACANT           0
#define VACANT_FLAG   9999
#define MAX_X           22
#define MAX_Y           15
#define GOOD             0
#define NG               1
#define APPROCH_DIRECTION  2

/*------------------------*/
/*  external variable     */
/*------------------------*/
int board[MAX_X][MAX_Y];
int seq_no;
int size_x;
int size_y;
int hsize_x;
int hsize_y;
int tried_no;
int blank_no;
int approch_direction_change;

/*------------------------*/
struct piece_s {
 int x;
 int y;
};

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

struct piece_all_s {
 int no;
 int approch;
  struct {
    int x0,x1,x2,x3,x4,x5;
    int y0,y1,y2,y3,y4,y5;
  } type[PIECE_DIRECTION];
} piece_all[MAX_X][MAX_Y][PIECE_NO];

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

struct remaining_piece_s {
  struct remaining_piece_s *next;
  int piece_no;
} remaining_piece[PIECE_NO];

struct remaining_piece_s *used_piece[PIECE_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;
  }
}

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

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

  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) {
       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;
    }
  }
  } /* end of p-loop */

}

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

  static struct piece_org_s piece_org[PIECE_NO] = {
     1,0,  0,1,  1,1,  2,1,  1,2,   /*  0.   X      */
                                    /*      XXX     */
                                    /*       X      */

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

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

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

     0,0,  1,0,  2,0,  0,1,  2,1,   /*  4.  XXX     */
                                    /*      X X     */

     0,0,  1,0,  2,0,  0,1,  1,1,   /*  5.  XXX     */
                                    /*      XX      */

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

     0,0,  0,1,  1,1,  2,1,  1,2,   /*  7.  X       */
                                    /*      XXX     */
                                    /*       X      */

     0,0,  0,1,  1,1,  2,1,  2,2,   /*  8.  X       */
                                    /*      XXX     */
                                    /*        X     */

     0,0,  1,0,  1,1,  2,1,  2,2,   /*  9.  XX      */
                                    /*       XX     */
                                    /*        X     */

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

     0,0,  1,0,  2,0,  1,1,  1,2,   /* 12.  XXX     */
                                    /*       X      */
                                    /*       X      */
  };

  /*** Init ***/
  for (p=0; p<APPROCH_DIRECTION; 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);
      }
    }
  }

}

/*-------------------------------------*/
/*  連続した空きスペースをチェック     */
/*-------------------------------------*/
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 init_piece_all(int area_x, int area_y)
{
  int x,y,p,t,d,a,a_tmp;
  int posx,posy;

  /* initialize */
  for (x=1;x<=area_x;x++)
    for (y=1;y<=area_y;y++)
      for(p=1;p<PIECE_NO;p++)
        piece_all[x][y][p].no = 0;

  /* loop all area */
  a = 0;
  for (x=1;x<=area_x;x++) {
    if (x>approch_direction_change) a = 1;
    for (y=1;y<=area_y;y++) {
      for (p=1;p<=PIECE_NO;p++) {
        for (t=0;t<piece[a][p].no;t++) {
          if (board[x]
                   [y]==VACANT &&
              board[piece[a][p].type[t].x[0]+x]
                   [piece[a][p].type[t].y[0]+y]==VACANT &&
              board[piece[a][p].type[t].x[1]+x]
                   [piece[a][p].type[t].y[1]+y]==VACANT &&
              board[piece[a][p].type[t].x[2]+x]
                   [piece[a][p].type[t].y[2]+y]==VACANT &&
              board[piece[a][p].type[t].x[3]+x]
                   [piece[a][p].type[t].y[3]+y]==VACANT) {
              /* 置いてみて、５の倍数スペースチェック */
            board[x]
                 [y] =
            board[piece[a][p].type[t].x[0]+x]
                 [piece[a][p].type[t].y[0]+y] =
            board[piece[a][p].type[t].x[1]+x]
                 [piece[a][p].type[t].y[1]+y] =
            board[piece[a][p].type[t].x[2]+x]
                 [piece[a][p].type[t].y[2]+y] =
            board[piece[a][p].type[t].x[3]+x]
                 [piece[a][p].type[t].y[3]+y] = p;

            posx = x;
            posy = y;
            a_tmp = a;
            if (a_tmp==0) {
              while(board[posx][posy]!=VACANT) {
                posy++;
                if (posy>size_y) {
                  posy = 1;
                  posx++;
                  if (posx>size_x) posx = 1;
                  if (posx>approch_direction_change) {
                    a_tmp = 1;
                    break;
                  }
                }
              }
            }
            if (a_tmp==1) {
              while(board[posx][posy]!=VACANT) {
                posx++;
                if (posx>size_x) {
                  posx = approch_direction_change + 1;
                  posy++;
                  if (posy>size_y) posy = 1;
                }
              }
            }

            blank_no =0;
            search_blank(posx,posy);
            search_blank_clear(1,1);

            if (blank_no%5==0) {
              d = piece_all[x][y][p].no++;
              piece_all[x][y][p].type[d].x0 = piece[a][p].type[t].x[0]+x;
              piece_all[x][y][p].type[d].y0 = piece[a][p].type[t].y[0]+y;
              piece_all[x][y][p].type[d].x1 = piece[a][p].type[t].x[1]+x;
              piece_all[x][y][p].type[d].y1 = piece[a][p].type[t].y[1]+y;
              piece_all[x][y][p].type[d].x2 = piece[a][p].type[t].x[2]+x;
              piece_all[x][y][p].type[d].y2 = piece[a][p].type[t].y[2]+y;
              piece_all[x][y][p].type[d].x3 = piece[a][p].type[t].x[3]+x;
              piece_all[x][y][p].type[d].y3 = piece[a][p].type[t].y[3]+y;
              /* 次のピースを置く場所のスタート位置 */
              piece_all[x][y][p].type[d].x4 = posx;
              piece_all[x][y][p].type[d].y4 = posy;
            }
            board[x]
                 [y] =
            board[piece[a][p].type[t].x[0]+x]
                 [piece[a][p].type[t].y[0]+y] =
            board[piece[a][p].type[t].x[1]+x]
                 [piece[a][p].type[t].y[1]+y] =
            board[piece[a][p].type[t].x[2]+x]
                 [piece[a][p].type[t].y[2]+y] =
            board[piece[a][p].type[t].x[3]+x]
                 [piece[a][p].type[t].y[3]+y] = VACANT;
          }
        }
      }
    }
  }
}

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

  int x,y,i;

  printf("   seq_no=%d\n",seq_no);

  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] = '+';
      }
    }

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

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

#define CHECK_BOARD_0(posx,posy) { \
   if ( board[posx+1][posy]  !=VACANT &&  \
       (board[posx][posy+1]  !=VACANT ||  \
       (board[posx][posy+2]  !=VACANT && board[posx+1][posy+1]!=VACANT)) \
      ) return; \
   }

#define CHECK_BOARD_1(posx,posy) { \
  if (board[posx][posy+1]!=VACANT &&  \
      (board[posx+1][posy]!=VACANT || \
      (board[posx+2][posy]!=VACANT && board[posx+1][posy+1]!=VACANT)) \
      ) return; \
  }

#define NEXT_SPACE_1(posx,posy) { \
    while(board[posx][posy]!=VACANT) { \
      posx++; \
      if (posx>size_x) { \
        posx = approch_direction_change + 1; \
        posy++; \
      } \
    } \
  }

/*------------------------*/
/*  探索のメイン処理      */
/*------------------------*/
void search(int posx,int posy,int put_no, int p)
{
  int i,j;
  int avno;
  int piece_no;
  struct remaining_piece_s *ip,*ip_before;

  if (p==1 || posx>approch_direction_change) {
    p = 1;
    NEXT_SPACE_1(posx,posy)
    /* 孤立スペースチェック */
    CHECK_BOARD_1(posx,posy)
  }
  else { /* p==0 の時 */
    while(board[posx][posy]!=VACANT) {
      posy++;
      if (posy>size_y) {
        posy = 1;
        posx++;
        if (posx>approch_direction_change) {
          p = 1;
          NEXT_SPACE_1(posx,posy)
          /* 孤立スペースチェック */
          CHECK_BOARD_1(posx,posy)
          break;
        }
      }
    }
    /* 孤立スペースチェック */
    CHECK_BOARD_0(posx,posy)
  }

  for (ip=remaining_piece[0].next,ip_before=&remaining_piece[0];
       ip!=NULL;
       ip_before=ip, ip=ip->next) {

    i = ip->piece_no;

    for (j=0; j<piece_all[posx][posy][i].no; j++) {

      /*** area check ***/
      tried_no++;
      if (board[piece_all[posx][posy][i].type[j].x0]
               [piece_all[posx][posy][i].type[j].y0] == VACANT &&
          board[piece_all[posx][posy][i].type[j].x1]
               [piece_all[posx][posy][i].type[j].y1] == VACANT &&
          board[piece_all[posx][posy][i].type[j].x2]
               [piece_all[posx][posy][i].type[j].y2] == VACANT &&
          board[piece_all[posx][posy][i].type[j].x3]
               [piece_all[posx][posy][i].type[j].y3] == VACANT) {
        /*** put ***/
        board[posx][posy] =
        board[piece_all[posx][posy][i].type[j].x0]
             [piece_all[posx][posy][i].type[j].y0] =
        board[piece_all[posx][posy][i].type[j].x1]
             [piece_all[posx][posy][i].type[j].y1] =
        board[piece_all[posx][posy][i].type[j].x2]
             [piece_all[posx][posy][i].type[j].y2] =
        board[piece_all[posx][posy][i].type[j].x3]
             [piece_all[posx][posy][i].type[j].y3] = put_no;

        if (put_no!=PIECE_NO) {
          ip_before->next = ip->next; /* 残りピースのリンクから外す */

          /*** search next piece place ***/
          search(piece_all[posx][posy][i].type[j].x4,
                 piece_all[posx][posy][i].type[j].y4,put_no+1,p);

          ip->next = ip_before->next; /* 残りピースのリンクに戻す */
          ip_before->next = ip;
          }
        else {
          /*** display ***/
          seq_no++;
/*
          display();
*/
        }

        /*** get last piece ***/
        board[posx][posy] =
        board[piece_all[posx][posy][i].type[j].x0]
             [piece_all[posx][posy][i].type[j].y0] =
        board[piece_all[posx][posy][i].type[j].x1]
             [piece_all[posx][posy][i].type[j].y1] =
        board[piece_all[posx][posy][i].type[j].x2]
             [piece_all[posx][posy][i].type[j].y2] =
        board[piece_all[posx][posy][i].type[j].x3]
             [piece_all[posx][posy][i].type[j].y3] = VACANT;

      } /* end of for-j loop */

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

  }  /* end of for-i loop */

  return;

} /* end of search */

/*------------------------*/
/*  initialize            */
/*------------------------*/
void init_board(int argc, char **argv)
{
  int i,j;

  /*** set area type ***/
  size_x = 10;
  size_y =  6;
  hsize_x = 5;
  hsize_y = 3;
  approch_direction_change = 6;
  if (argc==2) {
    if (strcmp(argv[1],"6*10")==0 ||
        strcmp(argv[1],"10*6")==0) {
      size_x = 10;
      size_y =  6;
      hsize_x = 5;
      hsize_y = 3;
      approch_direction_change = 6;
    }
    else if (strcmp(argv[1],"5*12")==0 ||
             strcmp(argv[1],"12*5")==0) {
      size_x = 12;
      size_y =  5;
      hsize_x = 6;
      hsize_y = 4;
      approch_direction_change = 12;
    }
    else if (strcmp(argv[1],"4*15")==0 ||
             strcmp(argv[1],"15*4")==0) {
      size_x = 15;
      size_y =  4;
      hsize_x = 13;
      hsize_y = 2;
      approch_direction_change = 15;
    }
    else if (strcmp(argv[1],"3*20")==0 ||
             strcmp(argv[1],"20*3")==0) {
      size_x = 20;
      size_y =  3;
      hsize_x = 10;
      hsize_y = 2;
      approch_direction_change = 20;
    }
    else if (strcmp(argv[1],"8*8")==0) {
      size_x =  8;
      size_y =  8;
      hsize_x = 4;
      hsize_y = 4;
      approch_direction_change = 3;
    }
  }

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

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

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

  if (size_x==8 && size_y==8) {
    board[4][4] = INHIBIT;
    board[4][5] = INHIBIT;
    board[5][4] = INHIBIT;
    board[5][5] = INHIBIT;
  }

  /* 残りピースを憶えるリストを作る */
  for (i=0; i<PIECE_NO; i++) {
    used_piece[i] = &remaining_piece[i];
    remaining_piece[i].piece_no = i;
    if (i<PIECE_NO-1)
      remaining_piece[i].next = &remaining_piece[i+1];
    else
      remaining_piece[i].next = NULL;
  }

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

/*------------------------*/
/*  put X piece           */
/*------------------------*/
void search_start() {
  int posy = 3;
  int posx = 1;
  int put_no = 1;
  int a = 0;

  while(posx<hsize_x) {
    /*** put ***/
    if (board[piece[a][0].type[0].x[0]+posx]
             [piece[a][0].type[0].y[0]+posy]==VACANT &&
        board[piece[a][0].type[0].x[1]+posx]
             [piece[a][0].type[0].y[1]+posy]==VACANT &&
        board[piece[a][0].type[0].x[2]+posx]
             [piece[a][0].type[0].y[2]+posy]==VACANT &&
        board[piece[a][0].type[0].x[3]+posx]
             [piece[a][0].type[0].y[3]+posy]==VACANT) {
      board[posx][posy] =
      board[piece[a][0].type[0].x[0]+posx]
           [piece[a][0].type[0].y[0]+posy] =
      board[piece[a][0].type[0].x[1]+posx]
           [piece[a][0].type[0].y[1]+posy] =
      board[piece[a][0].type[0].x[2]+posx]
           [piece[a][0].type[0].y[2]+posy] =
      board[piece[a][0].type[0].x[3]+posx]
           [piece[a][0].type[0].y[3]+posy] = put_no;

      init_piece_all(size_x,size_y);

      search(1,1,put_no+1,0);

      /*** get ***/
      board[posx][posy] =
      board[piece[a][0].type[0].x[0]+posx]
           [piece[a][0].type[0].y[0]+posy] =
      board[piece[a][0].type[0].x[1]+posx]
           [piece[a][0].type[0].y[1]+posy] =
      board[piece[a][0].type[0].x[2]+posx]
           [piece[a][0].type[0].y[2]+posy] =
      board[piece[a][0].type[0].x[3]+posx]
           [piece[a][0].type[0].y[3]+posy] = VACANT;
      }
    posy++;
    if (posy>hsize_y) {
      posy = 2;
      posx++;
    }
  }
}

/*------------------------*/
/*  main                  */
/*------------------------*/
main(int argc, char **argv)
{
  clock_t ts,time;
  ts = clock();

  init_piece();
  init_board(argc,argv);
  init_piece_all(size_x, size_y);

  search_start();

  printf("Tried No=%d\n",tried_no);
  printf("Seq   No=%d\n",seq_no);
  time = clock() - ts;
  printf("Time=%f\n",(float)time/(float)CLOCKS_PER_SEC);
}
/*------------------------------------------------*/
/*  end of file                                   */
/*------------------------------------------------*/