/*------------------------------------------------*/
/*     Copyright(C) T.Nakamura 2001               */
/*     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  99999
#define MAX_X           22
#define MAX_Y           15
#define GOOD             0
#define NG               1

/*------------------------*/
/*  external variable     */
/*------------------------*/
int  board[MAX_X][MAX_Y];
int  use_piece[PIECE_NO];
int  seq_no;
int  size_x;
int  size_y;
int  hsize_x;
int  hsize_y;

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

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);
}

void origin_piece(struct piece_org_s *target)
{
  int i;
  qsort(&(target->piece[0]),PIECE_CELL_NO,sizeof(struct piece_s),
        sort_piece);
  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;
  }
}

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

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

  origin_piece(target);

/*** 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[piece_no].no; i++) {
    if (piece[piece_no].type[i].x[0] == target->piece[1].x &&
        piece[piece_no].type[i].y[0] == target->piece[1].y &&
        piece[piece_no].type[i].x[1] == target->piece[2].x &&
        piece[piece_no].type[i].y[1] == target->piece[2].y &&
        piece[piece_no].type[i].x[2] == target->piece[3].x &&
        piece[piece_no].type[i].y[2] == target->piece[3].y &&
        piece[piece_no].type[i].x[3] == target->piece[4].x &&
        piece[piece_no].type[i].y[3] == target->piece[4].y) {
       same = 1;
       break;
     }
  }

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

}

void dump_piece()
{

  int i,j,k,m;
  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 (i=0; i<PIECE_NO; i++) {
      for (j=0; j<piece[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[i].type[j].x[0]+posx]
               [piece[i].type[j].y[0]+posy] =
          board[piece[i].type[j].x[1]+posx]
               [piece[i].type[j].y[1]+posy] =
          board[piece[i].type[j].x[2]+posx]
               [piece[i].type[j].y[2]+posy] =
          board[piece[i].type[j].x[3]+posx]
               [piece[i].type[j].y[3]+posy] = seq_no;

          display();
       }
     }
}

void init_piece()
{
  int i,j,k;
  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 (i=0; i<PIECE_NO; i++) {
    piece[i].no = 0;
    for (j=0; j<PIECE_DIRECTION; j++) {
      for (k=0; k<PIECE_CELL_NO-1; k++) {
        piece[i].type[j].x[k] = 0;
        piece[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);
      }
    }
  }

  /*** Dump for DEBUG ***/
/***
  for (i=0; i<PIECE_NO; i++) {
    no = piece[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[i].type[j].x[k],
                           piece[i].type[j].y[k]);
      }
      printf("\n");
    }
  }
  dump_piece();
***/
}

/*------------------------*/
/*  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);
}

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++;
    }
  }

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

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

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

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

  blank_no =0;
  search_blank(x,y);
  search_blank_clear(x,y);
  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 i,j;
  int avno;
  int piece_no;

  while(board[posx][posy]!=VACANT) {
    posy++;
    if (posy>size_y) {
      posy = 1;
      posx++;
    }
  }
  /** check board **/
  if (check_board(posx, posy)) return;

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

    if (use_piece[i]==UNUSE) {

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

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

          if (put_no!=PIECE_NO) {
            use_piece[i] = put_no;
            /*** search next piece place ***/
            search(posx,posy+1,put_no+1);
            use_piece[i] = UNUSE;
          }
          else {
            /*** display ***/
            seq_no++;
            display();
          }

          /*** get last piece ***/
          board[posx][posy] =
          board[piece[i].type[j].x[0]+posx]
               [piece[i].type[j].y[0]+posy] =
          board[piece[i].type[j].x[1]+posx]
               [piece[i].type[j].y[1]+posy] =
          board[piece[i].type[j].x[2]+posx]
               [piece[i].type[j].y[2]+posy] =
          board[piece[i].type[j].x[3]+posx]
               [piece[i].type[j].y[3]+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_board(int argc, char **argv)
{
  int i,j;

  /*** set area type ***/
  size_x = 10;
  size_y =  6;
  hsize_x = 5;
  hsize_y = 3;
  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;
    }
    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;
    }
    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;
    }
    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;
    }
    else if (strcmp(argv[1],"8*8")==0) {
      size_x =  8;
      size_y =  8;
      hsize_x = 4;
      hsize_y = 4;
    }
  }

  /*** 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 (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;
  }

  /*** init use_piece ***/
  for (i=0; i<PIECE_NO; i++)
    use_piece[i] = UNUSE;

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

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

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

    search(1,1,put_no+1);

    /*** get ***/
    board[posx][posy] =
    board[piece[0].type[0].x[0]+posx]
         [piece[0].type[0].y[0]+posy] =
    board[piece[0].type[0].x[1]+posx]
         [piece[0].type[0].y[1]+posy] =
    board[piece[0].type[0].x[2]+posx]
         [piece[0].type[0].y[2]+posy] =
    board[piece[0].type[0].x[3]+posx]
         [piece[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);
  display();
  search_start();

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