/***********************************************************************
 * PENTA.C - Solve the Pentomino Puzzle
 * Syntax:  PENTA [filename]
 * use PENTA NUL to count solutions only

***********************************************************************/
/* program by Tenie Remmel 
* box draw charater ooutput added by Jan W. Stumpel
*/

#include <stdio.h>
#include <string.h>

typedef unsigned char uchar;

/***********************************************************************
 * #define's - HEIGHT, WIDTH, NPIECES, PSIZE
 * HEIGHT is the height of the field.
 * WIDTH is the width of the field.
 * NPIECES is the number of puzzle pieces.
 * PSIZE is the number of sq's in each puzzle piece.
 */

#define HEIGHT          6
#define WIDTH           10
#define NPIECES         12
#define PSIZE           5

/***********************************************************************
 * Function prototypes
 */

void InitField(void);
void InitTables(void);
int  PlacePiece(int x, int y, int piece, int rot);
void PrintField(void);
void Recurse(void);
void RemovePiece(void);
void ResetSq(int x, int y);
void SetSq(int x, int y, int type);
void MakePic (void);


/***********************************************************************
 * Global variables - Field_On, Field_Type, Field_Bord, SolFile, Sols,
 *      PiecesPlaced, Used, PieceNum, PlacedX, PlacedY, PlacedR
 * Field_On[x][y] contains 0 if (x, y) is off, 1 if it is on.
 * Field_Type[x][y] indicates what piece covers (x, y) (0 = no piece).
 * Field_Bord[x][y] is the number of bordering squares that are on.
 * SolFile is the solution output file.
 * Sols is the solution counter.
 * PiecesPlaced is the number of pieces on the field.
 * Used[p] indicates whether piece p has been used yet.
 * PieceNum[n] indicates what the nth placed piece is.
 * PlacedX[p] is the current X-coord of piece p.
 * PlacedY[p] is the current Y-coord of piece p.
 * PlacedR[p] is the current rotation of piece p.
 */

uchar Field_On[WIDTH + PSIZE][HEIGHT + PSIZE];
uchar Field_Type[WIDTH + PSIZE][HEIGHT + PSIZE];
uchar Field_Bord[WIDTH + PSIZE][HEIGHT + PSIZE];

FILE *SolFile;

int Sols = 0, PiecesPlaced = 0;

uchar Used[NPIECES], PieceNum[NPIECES];
int PlacedX[NPIECES], PlacedY[NPIECES], PlacedR[NPIECES];

/***********************************************************************
 * Piece rotation table - Piece_Type, Piece_Rots, Piece_XY,
 *                        Piece_X, Piece_Y
 * Piece_Type[p] is the type character for piece p.
 * Piece_Rots[p] is the number of rotations for piece p.
 * Piece_XY[p][r] is the coord's of each sq in piece p, rotation r.
 *  These coordinates MUST be in lexicographical order!
 * Piece_X[p][r] is the X-coord's of each sq in piece p, rotation r.
 * Piece_Y[p][r] is the Y-coord's of each sq in piece p, rotation r.
 */

uchar Piece_Type[NPIECES] =
    "FILNPTUVWXYZ";
uchar Piece_Rots[NPIECES] = {
    8,2,8,8,8,4,4,4,4,1,8,4
};

int Piece_X[NPIECES][8][PSIZE];
int Piece_Y[NPIECES][8][PSIZE];

uchar Piece_XY[NPIECES][8][PSIZE][2] = {
  { {{0,0},{0,1},{1,1},{1,2},{2,1}},{{0,2},{1,0},{1,1},{1,2},{2,1}},
    {{0,1},{1,0},{1,1},{1,2},{2,0}},{{0,1},{1,0},{1,1},{2,1},{2,2}},
    {{0,0},{1,0},{1,1},{1,2},{2,1}},{{0,1},{0,2},{1,0},{1,1},{2,1}},
    {{0,1},{1,1},{1,2},{2,0},{2,1}},{{0,1},{1,0},{1,1},{1,2},{2,2}}},
  { {{0,0},{1,0},{2,0},{3,0},{4,0}},{{0,0},{0,1},{0,2},{0,3},{0,4}}},
  { {{0,0},{0,1},{1,0},{2,0},{3,0}},{{0,0},{0,1},{0,2},{0,3},{1,3}},
    {{0,0},{1,0},{1,1},{1,2},{1,3}},{{0,1},{1,1},{2,1},{3,0},{3,1}},
    {{0,0},{0,1},{0,2},{0,3},{1,0}},{{0,0},{1,0},{2,0},{3,0},{3,1}},
    {{0,0},{0,1},{1,1},{2,1},{3,1}},{{0,3},{1,0},{1,1},{1,2},{1,3}}},
  { {{0,0},{1,0},{2,0},{2,1},{3,1}},{{0,2},{0,3},{1,0},{1,1},{1,2}},
    {{0,0},{1,0},{1,1},{2,1},{3,1}},{{0,1},{0,2},{0,3},{1,0},{1,1}},
    {{0,0},{0,1},{1,1},{1,2},{1,3}},{{0,1},{1,0},{1,1},{2,0},{3,0}},
    {{0,0},{0,1},{0,2},{1,2},{1,3}},{{0,1},{1,1},{2,0},{2,1},{3,0}}},
  { {{0,0},{0,1},{1,0},{1,1},{2,0}},{{0,1},{1,0},{1,1},{2,0},{2,1}},
    {{0,0},{0,1},{0,2},{1,1},{1,2}},{{0,0},{0,1},{1,0},{1,1},{1,2}},
    {{0,0},{1,0},{1,1},{2,0},{2,1}},{{0,0},{0,1},{1,0},{1,1},{2,1}},
    {{0,0},{0,1},{0,2},{1,0},{1,1}},{{0,1},{0,2},{1,0},{1,1},{1,2}}},
  { {{0,0},{1,0},{1,1},{1,2},{2,0}},{{0,0},{0,1},{0,2},{1,1},{2,1}},
    {{0,2},{1,0},{1,1},{1,2},{2,2}},{{0,1},{1,1},{2,0},{2,1},{2,2}}},
  { {{0,0},{0,1},{1,1},{2,0},{2,1}},{{0,0},{0,1},{1,0},{2,0},{2,1}},
    {{0,0},{0,2},{1,0},{1,1},{1,2}},{{0,0},{0,1},{0,2},{1,0},{1,2}}},
  { {{0,0},{0,1},{0,2},{1,0},{2,0}},{{0,0},{1,0},{2,0},{2,1},{2,2}},
    {{0,0},{0,1},{0,2},{1,2},{2,2}},{{0,2},{1,2},{2,0},{2,1},{2,2}}},
  { {{0,0},{1,0},{1,1},{2,1},{2,2}},{{0,0},{0,1},{1,1},{1,2},{2,2}},
    {{0,2},{1,1},{1,2},{2,0},{2,1}},{{0,1},{0,2},{1,0},{1,1},{2,0}}},
  { {{0,1},{1,0},{1,1},{1,2},{2,1}}},
  { {{0,0},{1,0},{1,1},{2,0},{3,0}},{{0,0},{0,1},{0,2},{0,3},{1,2}},
    {{0,1},{1,0},{1,1},{1,2},{1,3}},{{0,1},{1,1},{2,0},{2,1},{3,1}},
    {{0,0},{0,1},{0,2},{0,3},{1,1}},{{0,0},{1,0},{2,0},{2,1},{3,0}},
    {{0,1},{1,0},{1,1},{2,1},{3,1}},{{0,2},{1,0},{1,1},{1,2},{1,3}}},
  { {{0,0},{1,0},{1,1},{1,2},{2,2}},{{0,1},{0,2},{1,1},{2,0},{2,1}},
    {{0,0},{0,1},{1,1},{2,1},{2,2}},{{0,2},{1,0},{1,1},{1,2},{2,0}}}
};

/***************************************************************
 * Console graphics characters, defined for PC-DOS and VT-100 
 *
 * GCHAR[0]   bottom right corner
 * GCHAR[1]   top right corner
 * GCHAR[2]   top left corner
 * GCHAR[3]   bottom left corner
 * GCHAR[4]   cross
 * GCHAR[5]   horizontal line
 * GCHAR[6]   left tee
 * GCHAR[7]   right tee
 * GCHAR[8]   bottom tee
 * GCHAR[9]   top tee
 * GCHAR[10]  vertical bar  */

#ifdef __MSDOS__
unsigned char GCHAR[11] =
{217, 191, 218, 192, 197, 196, 195, 180, 193, 194, 179};
#else
unsigned char GCHAR[11] =
{106, 107, 108, 109, 110, 113, 116, 117, 118, 119, 120};
#endif


/***********************************************************************
 * main() function
 */

main(int argc, char *argv[])
{
    int i;
    setvbuf(stdout, NULL, _IONBF, 0);

    if(argc >= 2) {
        SolFile = fopen(argv[1], "wt");
    } else SolFile = stdout;

    InitTables();
    InitField();

    memset(Used, 0, NPIECES);
    Piece_Rots[0] = 2; /* Avoid symmetry trouble */
    Recurse();

    if(argc >= 2) fclose(SolFile);
    return 0;
}

/***********************************************************************
 * Recurse() - Recursive search for solutions
 */

void Recurse()
{
    int i, j, x, y, r;
/*PrintField();
getchar();*/
    if(PiecesPlaced < NPIECES) {
        for(x = 1; x <= WIDTH; x++)
            for(y = 1; y <= HEIGHT; y++)
                if(Field_On[x][y] == 0) goto R_break;
R_break:
        for(i = 0; i < NPIECES; i++) {
            if(!Used[i]) {
                for(r = 0; r < Piece_Rots[i]; r++)
                    if(PlacePiece(x, y - Piece_Y[i][r][0], i, r)) {
                        Recurse();
                        RemovePiece();
                    }
            }
        }
    } else MakePic(); /* was PrintField();*/
}

/***********************************************************************
 * InitField() - Initializes the field
 */

void InitField(void)
{
    int i, j;

    for(i = 0; i < WIDTH + PSIZE; i++) {
        for(j = 0; j < HEIGHT + PSIZE; j++) {
            Field_On[i][j] = 0;
            Field_Type[i][j] = 0;
            Field_Bord[i][j] = 0;
            if(i > WIDTH || j > HEIGHT || i < 1 || j < 1)
                Field_On[i][j] = 1;
        }
    }

    for(i = 1; i <= WIDTH; i++) {
        Field_Bord[i][1]++;
        Field_Bord[i][HEIGHT]++;
    }

    for(i = 1; i <= HEIGHT; i++) {
        Field_Bord[1][i]++;
        Field_Bord[WIDTH][i]++;
    }
}

/***********************************************************************
 * InitTables() - Splits Piece_XY table into Piece_X and Piece_Y
 */

void InitTables(void)
{
    int p, r, n;

    for(p = 0; p < NPIECES; p++)
        for(r = 0; r < 8; r++)
            for(n = 0; n < PSIZE; n++) {
                Piece_X[p][r][n] = Piece_XY[p][r][n][0];
                Piece_Y[p][r][n] = Piece_XY[p][r][n][1];
            }
}

/***********************************************************************
 * PlacePiece() - Places a piece on the field
 * Places piece <piece>, rotation <rot> at position (<x>, <y>)
 * Returns 1 = success, 0 = doesn't fit
 */

int PlacePiece(int x, int y, int piece, int rot)
{
    int i, *px, *py;

    if(y < 1) return 0;
    px = Piece_X[piece][rot];
    py = Piece_Y[piece][rot];

    for(i = 0; i < PSIZE; i++)
        if(Field_On[x + px[i]][y + py[i]])
            return 0;

    for(i = 0; i < PSIZE; i++)
        SetSq(x + px[i], y + py[i], Piece_Type[piece]);

    PieceNum[PiecesPlaced++] = piece;
    PlacedX[piece] = x;
    PlacedY[piece] = y;
    PlacedR[piece] = rot;
    Used[piece] = 1;
    for (x = 1; x <= WIDTH; x++)
        for ( y = 1; y <= HEIGHT; y++)
                {
                if (Field_Bord[x][y] == 4)
                        {
/*                      printf ("NBG: x = %d  y = %d\n", x, y);*/
                        RemovePiece();
                        return 0;
                        }
                }
    return 1;
}

/***********************************************************************
 * PrintField() - Prints the field to the solution file
 */

void PrintField(void)
{
    int i, j;

    printf("\rSolutions=%d", ++Sols);
    fprintf(SolFile, "\n");

    for(j = 1; j <= HEIGHT; j++) {
        for(i = 1; i <= WIDTH; i++)
            putc(Field_Type[i][j], SolFile);
        fprintf(SolFile, "\n");
    }
/*    for(j = 1; j <= HEIGHT; j++) {
        for(i = 1; i <= WIDTH; i++)
            putc(48+Field_Bord[i][j], SolFile);
        fprintf(SolFile, "\n");
    }*/
    
}

/***********************************************************************
 * RemovePiece() - Removes the most recent piece from the field
 */

void RemovePiece(void)
{
    int i, x, y, r, p;
    p = PieceNum[--PiecesPlaced];
    Used[p] = 0;
    x = PlacedX[p];
    y = PlacedY[p];
    r = PlacedR[p];

    for(i = 0; i < PSIZE; i++) {
        ResetSq(x + Piece_X[p][r][i],
                y + Piece_Y[p][r][i]);
    }
}

/***********************************************************************
 * ResetSq() - Turn off one square in the field
 * Turns off square (<x>, <y>)
 */

void ResetSq(int x, int y)
{
    if(!Field_On[x][y]) return;
    Field_On[x][y] = 0;
    Field_Type[x][y] = 0;
    Field_Bord[x][y] -= 4;

    Field_Bord[x - 1][y]--;
    Field_Bord[x + 1][y]--;
    Field_Bord[x][y - 1]--;
    Field_Bord[x][y + 1]--;
}

/***********************************************************************
 * SetSq() - Turn on one square in the field
 * Sets square (<x>, <y>) as type <type>
 */

void SetSq(int x, int y, int type)
{
    if(Field_On[x][y]) return;
    Field_On[x][y] = 1;
    Field_Bord[x][y] += 4;
    Field_Type[x][y] = type;

    Field_Bord[x - 1][y]++;
    Field_Bord[x + 1][y]++;
    Field_Bord[x][y - 1]++;
    Field_Bord[x][y + 1]++;
}

#define CELLWIDTH 3
void MakePic (void)
/* Displays a solution by means of "box draw" characters.
   NB in this program, Field_Type[][] is 1-based (not 0-based)
   and the first index is the horizontal one */
{

  static char frame[HEIGHT * 2 + 1][WIDTH * CELLWIDTH + 1];
  int i, j, n;

  /* make the top line */
  frame [0][0] = GCHAR[2]; /* top left corner */
  for (i = 1; i < (WIDTH * CELLWIDTH); i++) frame[0][i] = GCHAR[5];
  frame[0][WIDTH * CELLWIDTH] = GCHAR[1]; /* top right corner */

  /* make the side lines */
  for (j = 1; j < HEIGHT * 2; j++)
    {
      frame[j][0] = GCHAR[10]; /* vertical line */
      for (i = 1; i < (WIDTH * CELLWIDTH); i++) frame[j][i] = ' ';
      frame[j][WIDTH * CELLWIDTH] = GCHAR[10];
    }

  /* make the bottom line */
  frame[HEIGHT * 2][0] = GCHAR[3]; /* bottom left */
  for (i = 1; i < (WIDTH * CELLWIDTH); i++) frame[HEIGHT * 2][i] = GCHAR[5];
  frame[HEIGHT * 2][WIDTH * CELLWIDTH] = GCHAR[0]; /* bottom right */

  /* make the tees on the top and bottom line */
  for (j = 1; j < WIDTH; j++)
    {
      if (Field_Type[j+1][1] != Field_Type[j][1]) 
                frame[0][CELLWIDTH * j] = GCHAR[9];
      if (Field_Type[j+1][HEIGHT] != Field_Type[j][HEIGHT])
                frame[HEIGHT * 2][CELLWIDTH * j] = GCHAR[8];
    }

  /* make the tees on the left and right line */
  for (j = 1; j < HEIGHT; j++)
    {
      if (Field_Type[1][j+1] != Field_Type[1][j])
                frame[2 * j][0] = GCHAR[6];
      if (Field_Type[WIDTH][j+1] != Field_Type[WIDTH][j])
                frame[2 * j][WIDTH * CELLWIDTH] = GCHAR[7];
    }
 
  /* make the internal verticals */
  for (j = 0; j < HEIGHT; j++)
    for (i = 1; i < WIDTH; i++)
      if (Field_Type[i+1][j+1] != Field_Type[i][j+1])
        frame[2 * j + 1][CELLWIDTH * i] = GCHAR[10];

  for (j = 0; j < HEIGHT - 1; j++)
    for (i = 1; i < WIDTH; i++)
      {
        int A = Field_Type[i][j+1], 
            B = Field_Type[i+1][j+1], 
            C = Field_Type[i][j + 2],
            D = Field_Type[i+1][j + 2];
        char k = ' ';
        switch (8 * (A == B) + 4 * (C == D) + 2 * (A == C) + (B == D))
          {
          case 0:
            k = GCHAR[4];
            break;
          case 1:
            k = GCHAR[7];
            break;
          case 2:
            k = GCHAR[6];
            break;
          case 3:
            k = GCHAR[10];
            break;
          case 4:
            k = GCHAR[8];
            break;
          case 5:
            k = GCHAR[0];
            break;
          case 6:
            k = GCHAR[3];
            break;
          case 7:
            k = ' ';
            break;
          case 8:
            k = GCHAR[9];
            break;
          case 9:
            k = GCHAR[1];
            break;
          case 10:
            k = GCHAR[2];
            break;
          case 11:
            k = ' ';
            break;
          case 12:
            k = GCHAR[5];
            break;
          case 13:
            k = ' ';
            break;
          case 14:
            k = ' ';
            break;
          case 15:
            k = ' ';
            break;
          }
        frame[2 * (j + 1)][CELLWIDTH * i] = k;
      }
  for (j = 0; j < HEIGHT - 1; j++)
    for (i = 0; i < WIDTH; i++)
      if (Field_Type[i+1][j +1] != Field_Type[i+1][j + 2])
        for (n = (1 + CELLWIDTH * i); n < (1 + i) * CELLWIDTH; n++)
          frame[2 * (j + 1)][n] = GCHAR[5];

#ifndef __MSDOS__
  printf ("\033(0");
#endif

for (j = 0; j < 2 * HEIGHT + 1; j++)
        {
           for (i = 0; i < WIDTH * CELLWIDTH + 1; i++)
             putchar (frame [j][i]);
           putchar ('\n');
        }

#ifndef __MSDOS__
  printf ("\033(B");
#endif
    printf ("               solution nr.%5d \n\n", ++Sols);
}