/*------------------------------------------------*/
/*     Copyright(C) T.Nakamura 1999               */
/*     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" } ]         */
/*                                                */
/*          default ... "6*10"                    */
/*                                                */
/*------------------------------------------------*/
#include <stdio.h>
#include <string.h>

/*------------------------*/
/*  define constant       */
/*------------------------*/
#define PIECE_NO 12
#define UNUSE     0
#define USE       1
#define INHIBIT  -1
#define EMPTY     0
#define MAX_X    32
#define MAX_Y     8

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

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

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

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

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

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

  return 0;
}

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

static struct piece_s {
  int no;
  struct {
    int x[4];
    int y[4];
    } type[8];
  } piece[PIECE_NO] = {

    8, /*** type L ***/
    0,0,0,1,      1,2,3,3,
    0,-1,-2,-3,   1,1,1,1,
    1,1,1,1,      0,1,2,3,
    0,1,2,3,      1,0,0,0,
    0,0,0,-1,     1,2,3,3,
    0,1,2,3,      1,1,1,1,
    1,0,0,0,      0,1,2,3,
    1,2,3,3,      0,0,0,1,

    4, /*** type T ***/
    1,2,1,1,      0,0,1,2,
    0,1,2,0,      1,1,1,2,
    0,-1,0,1,     1,2,2,2,
    0,-1,-2,0,    1,1,1,2,
    0,0,0,0,      0,0,0,0,
    0,0,0,0,      0,0,0,0,
    0,0,0,0,      0,0,0,0,
    0,0,0,0,      0,0,0,0,

    2, /*** type I ***/
    0,0,0,0,      1,2,3,4,
    1,2,3,4,      0,0,0,0,
    0,0,0,0,      0,0,0,0,
    0,0,0,0,      0,0,0,0,
    0,0,0,0,      0,0,0,0,
    0,0,0,0,      0,0,0,0,
    0,0,0,0,      0,0,0,0,
    0,0,0,0,      0,0,0,0,

    4, /*** type U ***/
    0,1,2,2,      1,1,1,0,
    1,1,1,0,      0,1,2,2,
    0,1,2,2,      1,0,0,1,
    1,0,0,1,      0,1,2,2,
    0,0,0,0,      0,0,0,0,
    0,0,0,0,      0,0,0,0,
    0,0,0,0,      0,0,0,0,
    0,0,0,0,      0,0,0,0,

    8, /*** type f ***/
    1,1,1,2,      0,1,2,1,
    -1,0,1,-1,    1,1,1,2,
    -1,0,0,1,     1,1,2,2,
    0,-1,-2,-1,   1,1,1,2,
    1,0,-1,0,     0,1,1,2,
    -1,0,1,1,     1,1,1,2,
    0,1,0,-1,     1,1,2,2,
    0,1,2,1,      1,1,1,2,

    4, /*** type W ***/
    0,1,1,2,      1,1,2,2,
    0,-1,-1,-2,   1,1,2,2,
    1,1,2,2,      0,1,1,2,
    1,0,-1,-1,    0,1,1,2,
    0,0,0,0,      0,0,0,0,
    0,0,0,0,      0,0,0,0,
    0,0,0,0,      0,0,0,0,
    0,0,0,0,      0,0,0,0,

    8, /*** type y ***/
    0,1,0,0,      1,1,2,3,
    1,2,3,2,      0,0,0,1,
    0,0,0,-1,     1,2,3,2,
    -1,0,1,2,     1,1,1,1,
    0,-1,0,0,     1,1,2,3,
    1,1,2,3,      0,1,0,0,
    0,0,1,0,      1,2,2,3,
    0,-1,-2,1,    1,1,1,1,

    8, /*** type N ***/
    0,-1,-1,-1,   1,1,2,3,
    1,1,2,3,      0,1,1,1,
    0,0,-1,-1,    1,2,2,3,
    1,2,2,3,      0,0,1,1,
    0,1,1,1,      1,1,2,3,
    1,0,-1,-2,    0,1,1,1,
    0,0,1,1,      1,2,2,3,
    0,-1,1,2,     1,1,0,0,

    1, /*** type X ***/
    -1,0,1,0,     1,1,1,2,
    0,0,0,0,      0,0,0,0,
    0,0,0,0,      0,0,0,0,
    0,0,0,0,      0,0,0,0,
    0,0,0,0,      0,0,0,0,
    0,0,0,0,      0,0,0,0,
    0,0,0,0,      0,0,0,0,
    0,0,0,0,      0,0,0,0,

    4, /*** type V ***/
    0,0,1,2,      1,2,2,2,
    0,0,-1,-2,    1,2,2,2,
    0,0,1,2,      1,2,0,0,
    1,2,2,2,      0,0,1,2,
    0,0,0,0,      0,0,0,0,
    0,0,0,0,      0,0,0,0,
    0,0,0,0,      0,0,0,0,
    0,0,0,0,      0,0,0,0,

    8, /*** type P ***/
    1,1,0,0,      0,1,1,2,
    1,0,1,2,      0,1,1,1,
    -1,0,-1,0,    1,1,2,2,
    1,2,1,2,      0,0,1,1,
    1,1,0,1,      0,1,1,2,
    1,1,0,-1,     0,1,1,1,
    0,1,0,1,      1,1,2,2,
    0,1,1,2,      1,1,0,0,

    4, /*** type Z ***/
    1,1,1,2,      0,1,2,2,
    0,-1,-2,-2,   1,1,1,2,
    1,0,0,-1,     0,1,2,2,
    0,1,2,2,      1,1,1,2,
    0,0,0,0,      0,0,0,0,
    0,0,0,0,      0,0,0,0,
    0,0,0,0,      0,0,0,0,
    0,0,0,0,      0,0,0,0,

  };

  while(board[posx][posy]!=0) {
    posx++;
    if (posx>size_x) {
      posx = 1;
      posy++;
    }
  }

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

  for (i=0; 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]==EMPTY &&
            board[piece[i].type[j].x[1]+posx]
                 [piece[i].type[j].y[1]+posy]==EMPTY &&
            board[piece[i].type[j].x[2]+posx]
                 [piece[i].type[j].y[2]+posy]==EMPTY &&
            board[piece[i].type[j].x[3]+posx]
                 [piece[i].type[j].y[3]+posy]==EMPTY) {
          /*** 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] = USE;
            /*** search next piece place ***/
            search(posx+1,posy,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] = EMPTY;
        }

      } /* end of for-j loop */

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

  }  /* end of for-i loop */

  return;

} /* end of search */


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

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

  /*** 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] = EMPTY;

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

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

/*------------------------*/
/*  main                  */
/*------------------------*/
main(int argc, char **argv)
{
  init(argc,argv);
  display();
  search(1,1,1);
}
/*------------------------------------------------*/
/*  end of file                                   */
/*------------------------------------------------*/