/*---------------------------------------------------*/
/*  3D Pentomino Solver                              */
/*                                                   */
/*  usage : pento [ x y z ]                          */
/*                                                   */
/*          default ... "4 3 5"                      */
/*                                                   */
/* 注）Iピースによる重複排除は 4 3 5のときのみ。     */
/*     PIC用データ出力時は #define PICDATA を有効化。*/
/*                                                   */
/*  2008.3.28 T.Nakamura (c)                         */
/*---------------------------------------------------*/
#include <stdio.h>
#include <string.h>
#include <time.h>

// #define PICDATA
/*------------------------*/
/*  define constant       */
/*------------------------*/
#define PIECE_NO 12
#define UNUSE     0
#define USE       1
#define INHIBIT  -1
#define EMPTY     0
#define MAX_X     7
#define MAX_Y     7
#define MAX_Z    12

/*------------------------*/
/*  external variable     */
/*------------------------*/
int eval_cnt,eval_cnt_m;
char board[MAX_X][MAX_Y][MAX_Z];
struct board_piece_s {
   int no;
   struct piece3d_xyz_s* type[24];
} board_piece[PIECE_NO][MAX_X][MAX_Y][MAX_Z];

int  use_piece[PIECE_NO];
int  seq_no;
int  size_x;
int  size_y;
int  size_z;
int  blank_no;
static char piece_char[13] = {
  '.', 'I', 'L', 'T',  'U', 'f', 'W', 'y', 'N', 'X', 'V', 'P', 'Z'};

clock_t ts,te;

struct piece_stak_s {
  int type;
  int x[5],y[5],z[5];
} piece_stack[12];
int stackp;

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

  int x,y,z,i,j,p;
  char t;

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

  for (z=1; z<=size_z; z++) {
  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][z]!=board[x+1][y][z]) {
        lp1[4*x+3] = '|';
        lp2[4*x+3] = '+';
      }
      if (board[x][y][z]!=board[x][y+1][z]) {
        lp2[4*x-1] = '+';
        lp2[4*x  ] = '-';
        lp2[4*x+1] = '-';
        lp2[4*x+2] = '-';
        lp2[4*x+3] = '+';
      }
      if (board[x][y][z]!=INHIBIT)
        lp1[4*x+1] = piece_char[board[x][y][z]];
    }

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

#ifdef PICDATA
  for (i=0;i<PIECE_NO;i++) {
    for (j=0;j<5;j++) {
      t = piece_char[piece_stack[i].type];
      x = piece_stack[i].x[j] - 1;
      y = piece_stack[i].y[j] - 1;
      z = piece_stack[i].z[j] - 1;
      p = z * 16 + y * 4 + x;
      printf("\tRETLW\tD'%d'\t\t;  %c  (%d,%d,%d)\n",p,t,x,y,z);
    }
  }
  printf("\n\n");
#endif

}

/*------------------------*/
/*  check_board           */
/*------------------------*/
struct piece3d_xyz_s {
  struct xyz_s {
    int x;
    int y;
    int z;
  } pos[4];
};

struct piece3d_s {
  int    no;
  struct piece3d_xyz_s type[24];
  int  same[24];
} piece3d[PIECE_NO],piece3dx[PIECE_NO];

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

    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,

    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,


    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,0,1,     1,1,2,2,
    -1,0,1,-1,    1,1,1,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,
  };

int check_board(int i, int j, int posx, int posy, int posz) {
  struct  piece3d_xyz_s* bp;

  bp = board_piece[i][posx][posy][posz].type[j];
  if (board[bp->pos[0].x+posx]
           [bp->pos[0].y+posy]
           [bp->pos[0].z+posz]==EMPTY &&
      board[bp->pos[1].x+posx]
           [bp->pos[1].y+posy]
           [bp->pos[1].z+posz]==EMPTY &&
      board[bp->pos[2].x+posx]
           [bp->pos[2].y+posy]
           [bp->pos[2].z+posz]==EMPTY &&
      board[bp->pos[3].x+posx]
           [bp->pos[3].y+posy]
           [bp->pos[3].z+posz]==EMPTY) return 1;
  return 0;
}

void put_get_piece(int i, int j, int posx, int posy, int posz, int piece_no) {
  struct  piece3d_xyz_s* bp;

  bp = board_piece[i][posx][posy][posz].type[j];
  board[posx][posy][posz] =
  board[bp->pos[0].x+posx]
       [bp->pos[0].y+posy]
       [bp->pos[0].z+posz] =
  board[bp->pos[1].x+posx]
       [bp->pos[1].y+posy]
       [bp->pos[1].z+posz] =
  board[bp->pos[2].x+posx]
       [bp->pos[2].y+posy]
       [bp->pos[2].z+posz] =
  board[bp->pos[3].x+posx]
       [bp->pos[3].y+posy]
       [bp->pos[3].z+posz] = piece_no;

#ifdef PICDATA
  if (piece_no!=EMPTY) {
    piece_stack[stackp].type = piece_no;
    piece_stack[stackp].x[0] = posx;
    piece_stack[stackp].y[0] = posy;
    piece_stack[stackp].z[0] = posz;
    piece_stack[stackp].x[1] = bp->pos[0].x+posx;
    piece_stack[stackp].y[1] = bp->pos[0].y+posy;
    piece_stack[stackp].z[1] = bp->pos[0].z+posz;
    piece_stack[stackp].x[2] = bp->pos[1].x+posx;
    piece_stack[stackp].y[2] = bp->pos[1].y+posy;
    piece_stack[stackp].z[2] = bp->pos[1].z+posz;
    piece_stack[stackp].x[3] = bp->pos[2].x+posx;
    piece_stack[stackp].y[3] = bp->pos[2].y+posy;
    piece_stack[stackp].z[3] = bp->pos[2].z+posz;
    piece_stack[stackp].x[4] = bp->pos[3].x+posx;
    piece_stack[stackp].y[4] = bp->pos[3].y+posy;
    piece_stack[stackp].z[4] = bp->pos[3].z+posz;
    stackp++;
  }
  else {
   stackp--;
  }
#endif

}

int check_pos(int x,int y,int z)
{
  if (board[x][y+1][z]!=0 &&
      board[x+1][y][z]!=0 &&
      board[x][y][z+1]!=0) return 1;

  return 0;
}

void search(int posx,int posy,int posz,int put_no)
{
  int i,j;
  struct piece3d_xyz_s* bp;

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

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

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

    if (use_piece[i]==UNUSE) {

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

        eval_cnt++;
        if (eval_cnt>1000000) {
          eval_cnt = 0;
          eval_cnt_m++;
        }

        if (check_board(i,j,posx,posy,posz)) {
          put_get_piece(i,j,posx,posy,posz,i+1);

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

          /*** get last piece ***/
          put_get_piece(i,j,posx,posy,posz,EMPTY);
        }

      } /* end of for-j loop */

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

  }  /* end of for-i loop */

} /* end of search */


int sort_piece3d( struct xyz_s *a, struct xyz_s *b)
//int sort_piece3d( const void *a, const void *b)
{
  if (a->x > b->x) return(1);
  else if (a->x == b->x) {
    if (a->y > b->y) return(1);
    else if (a->y == b->y) {
      if (a->z > b->z) return(1);
    }
  }
  return(-1);
}

void make_piece3d()
{
  int x,y,z;
  int i,j,k,m,jj,jj0,r,diff;
  int min_z,min_y;
  int piece_data_no;

  for (i=0;i<PIECE_NO;i++) {
    jj = 0;
    for (j=0;j<piece[i].no;j++) {
      piece3d[i].same[jj] = 0;
      for (k=0;k<4;k++) {
        piece3d[i].type[jj].pos[k].x = piece[i].type[j].x[k];
        piece3d[i].type[jj].pos[k].y = piece[i].type[j].y[k];
        piece3d[i].type[jj].pos[k].z = 0;
      }
      /** tateru **/
      jj++;
      piece3d[i].same[jj] = 0;
      for (k=0;k<4;k++) {
        piece3d[i].type[jj].pos[k].x = piece[i].type[j].x[k];
        piece3d[i].type[jj].pos[k].y = 0;
        piece3d[i].type[jj].pos[k].z = piece[i].type[j].y[k];
      }

      /** tateru **/
      jj++;
      piece3d[i].same[jj] = 0;
      min_z = 0;
      min_y = 5;
      for (k=0;k<4;k++) {
        piece3d[i].type[jj].pos[k].x = 0;
        piece3d[i].type[jj].pos[k].y = piece[i].type[j].y[k];
        piece3d[i].type[jj].pos[k].z = piece[i].type[j].x[k];

        if (piece3d[i].type[jj].pos[k].z < min_z) {
          min_z = piece3d[i].type[jj].pos[k].z;
          min_y = piece3d[i].type[jj].pos[k].y;
        }
        else {
          if (piece3d[i].type[jj].pos[k].z == min_z) {
            if (piece3d[i].type[jj].pos[k].y < min_y) {
              min_z = piece3d[i].type[jj].pos[k].z;
              min_y = piece3d[i].type[jj].pos[k].y;
            }
          }
        }
      }

      /**** 原点補正 ***/
      if (min_z < 0) {
        for (k=0;k<4;k++) {
          piece3d[i].type[jj].pos[k].y -= min_y;
          piece3d[i].type[jj].pos[k].z -= min_z;

          if (piece3d[i].type[jj].pos[k].y==0 && piece3d[i].type[jj].pos[k].z==0) {
            piece3d[i].type[jj].pos[k].y -= min_y;
            piece3d[i].type[jj].pos[k].z -= min_z;
          }
        }
      }

      jj++;
      }
    piece3d[i].no = jj;

    for (j=0;j<piece3d[i].no;j++) {
      /*** sort ***/
      qsort(&(piece3d[i].type[j].pos[0]),4,sizeof(struct xyz_s),
            sort_piece3d);
    }

    for (j=0;j<piece3d[i].no - 1;j++) {
      for (k=j+1;k<piece3d[i].no;k++) {
        if (piece3d[i].same[j]==0) {
           diff = 0;
           for (m=0;m<4;m++) {
             if (piece3d[i].type[j].pos[m].x != piece3d[i].type[k].pos[m].x ||
                 piece3d[i].type[j].pos[m].y != piece3d[i].type[k].pos[m].y ||
                 piece3d[i].type[j].pos[m].z != piece3d[i].type[k].pos[m].z) {
               diff = 1;
               break;
             }
           }
           if (diff==0)  piece3d[i].same[k] = 1;
         }
      }
    }

    jj = 0;
    for (j=0;j<piece3d[i].no;j++) {
      if (piece3d[i].same[j]==0) {
        for (m=0;m<4;m++) {
          piece3dx[i].type[jj].pos[m].x = piece3d[i].type[j].pos[m].x;
          piece3dx[i].type[jj].pos[m].y = piece3d[i].type[j].pos[m].y;
          piece3dx[i].type[jj].pos[m].z = piece3d[i].type[j].pos[m].z;
        }
        jj++;
      }
    }
    piece3dx[i].no = jj;

  }
}

void check_board_piece() {
  int i,j,k,x,y,z;
  int piece_i,piece_j;

  for (x=1;x<=size_x;x++) {
    for (y=1;y<=size_y;y++) {
      for (z=1;z<=size_z;z++) {
        for (i=0;i<PIECE_NO;i++) {
          piece_j = 0;
          for (j=0;j<piece3dx[i].no;j++) {
            if (board[piece3dx[i].type[j].pos[0].x+x]
                     [piece3dx[i].type[j].pos[0].y+y]
                     [piece3dx[i].type[j].pos[0].z+z]==EMPTY &&
                board[piece3dx[i].type[j].pos[1].x+x]
                     [piece3dx[i].type[j].pos[1].y+y]
                     [piece3dx[i].type[j].pos[1].z+z]==EMPTY &&
                board[piece3dx[i].type[j].pos[2].x+x]
                     [piece3dx[i].type[j].pos[2].y+y]
                     [piece3dx[i].type[j].pos[2].z+z]==EMPTY &&
                board[piece3dx[i].type[j].pos[3].x+x]
                     [piece3dx[i].type[j].pos[3].y+y]
                     [piece3dx[i].type[j].pos[3].z+z]==EMPTY) {
                  board_piece[i][x][y][z].type[piece_j] = &(piece3dx[i].type[j].pos[0]);
              piece_j++;
            } // endif
          } // j loop
          board_piece[i][x][y][z].no = piece_j;
        } // i loop
      } // z loop
    } // y loop
  } // x loop

}

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

  /*** set area type ***/
  size_x =  4;
  size_y =  3;
  size_z =  5;
  if (argc==4) {
    if (atoi(argv[1]) * atoi(argv[2]) * atoi(argv[3])==60) {
      size_x = atoi(argv[1]);
      size_y = atoi(argv[2]);
      size_z = atoi(argv[3]);
    }
    else {
      printf(" size error!\n");
      exit();
    }
  }

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

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

  for (i=1; i<=size_x; i++)
    for (j=1; j<=size_y; j++)
      for (k=1; k<=size_z; k++)
         board[i][j][k] = EMPTY;

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

  /*** init piece3d ***/
  make_piece3d();

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

/*------------------------*/
/*  main                  */
/*------------------------*/
main(int argc, char **argv)
{

  int i;

  init(argc,argv);
  check_board_piece();

  display();
  ts = clock();

  if (size_x==4 && size_y==3 && size_z==5) {
    for (i=0;i<6;i++) {
      put_get_piece(0, 0, (int)(i%2+1), (int)(i/2+1), 1, 1);
      use_piece[0] = USE;
      search(1,1,1,2);
      put_get_piece(0, 0, (int)(i%2+1), (int)(i/2+1), 1, EMPTY);
    }
  }
  else {
    search(1,1,1,1);
  }

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