// Copyright 2005 Thomas R. Davis
//
// This file is part of Pentamino.
//
// Pentamino is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 2 of the License, or
// (at your option) any later version.
//
// Pentamino is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with Pentamino; if not, write to the Free Software Foundation,
// Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

// This code solves the problem of packing the 12 pentaminos into
// a 12x5 rectangular grid.  It basically does it by brute force.
// To eliminate a lot of the duplicates, only 9 positions for the
// 'X' pentamino are used.  There are still some duplicates because
// any solution with the center of the 'X' on the center line can
// be mirrored and this code will find both mirror images.

// It's a hack job, but it works.  It could be made to run a lot
// faster by packing the bits for the pieces into two 32-bit words
// and doing the text in two steps instead of 5.

#include <stdio.h>

// With just a little messing around, the 12 and 5 below can
// be changed to get the solutions for different board sizes.

#define WIDTH 12
#define HEIGHT 5

// The following are the loop counters.  They're global because I
// was too lazy to pass 12 parameters to the solution printer.

int qx, qi, qt, qv, qw, qu, ql, qy, qf, qp, qn, qz;

// Here are the coordinates for a typical piece in some configuration.
// As long as one of the squares is at (0,0) or an adjacent square,
// the code will work.


int ipiece[5][2] = {
  {0, 0}, {0, 1}, {0, 2}, {0, 3}, {0, 4}
};

int lpiece[5][2] = {
  {0, 0}, {0, 1}, {0, 2}, {0, 3}, {1, 3}
};

int ypiece[5][2] = {
  {0, 0}, {0, 1}, {0, 2}, {0, 3}, {1, 2}
};

int tpiece[5][2] = {
  {1, 0}, {1, 1}, {1, 2}, {0, 2}, {2, 2}
};

int fpiece[5][2] = {
  {1, 0}, {1, 1}, {1, 2}, {0, 1}, {2, 2}
};

int xpiece[5][2] = {
  {1, 0}, {1, 1}, {1, 2}, {0, 1}, {2, 1}
};

int ppiece[5][2] = {
  {0, 0}, {0, 1}, {0, 2}, {1, 0}, {1, 1}
};

int vpiece[5][2] = {
  {0, 0}, {0, 1}, {0, 2}, {1, 2}, {2, 2}
};

int wpiece[5][2] = {
  {0, 0}, {0, 1}, {1, 1}, {1, 2}, {2, 2}
};

int upiece[5][2] = {
  {0, 0}, {0, 1}, {0, 2}, {1, 0}, {1, 2}
};

int npiece[5][2] = {
  {0, 0}, {0, 1}, {0, 2}, {1, 2}, {1, 3}
};

int zpiece[5][2] = {
  {0, 0}, {1, 0}, {1, 1}, {1, 2}, {2, 2}
};

int ctest[WIDTH][HEIGHT];
int doingu = 0;

// ucheck checks to see if the 'U' is in a reasonable position.
// In other words -- that it doesn't cut off a single square.

int ucheck(int index, int l[400][5][2])
{
  int i, j;

  for (i = 0; i < WIDTH; i++)
    for (j = 0; j < HEIGHT; j++)
        ctest[i][j] = 0;
  for (i = 0; i < 5; i++)
    ctest[l[index][i][0]][l[index][i][1]] = 1;

  if (ctest[0][0] == 1 && (ctest[0][1] == 0 || ctest[1][0] == 0)) return 0;
  if (ctest[WIDTH-1][0] == 1 && (ctest[WIDTH-1][1] == 0 || ctest[WIDTH-2][0] == 0)) return 0;
  if (ctest[0][HEIGHT-1] == 1 && (ctest[0][HEIGHT-2] == 0 || ctest[1][HEIGHT-1] == 0)) return 0;
  if (ctest[WIDTH-1][HEIGHT-1] == 1 && (ctest[WIDTH-1][HEIGHT-2] == 0 || ctest[WIDTH-2][HEIGHT-1] == 0)) return 0;
  return 1;
}

// cornercheck sees if a piece is in an impossible position.  This
// usually means that a corner is cut off.

int cornercheck(int index, int l[400][5][2])
{
  int i, j;
  
  if (doingu) return ucheck(index, l);

  for (i = 0; i < WIDTH; i++)
    for (j = 0; j < HEIGHT; j++)
        ctest[i][j] = 0;
  for (i = 0; i < 5; i++)
    ctest[l[index][i][0]][l[index][i][1]] = 1;
  if (ctest[0][0] == 0) {
    if (!((ctest[0][1] == 0 && ctest[0][2] == 0 && ctest[0][3] == 0) ||
    (ctest[1][0] == 0 && ctest[2][0] == 0 && ctest[3][0] == 0))) return 0;
  }
  if (ctest[WIDTH-1][0] == 0) {
    if (!((ctest[WIDTH-1][1] == 0 && ctest[WIDTH-1][2] == 0 && ctest[WIDTH-1][3] == 0) ||
    (ctest[WIDTH-2][0] == 0 && ctest[WIDTH-3][0] == 0 && ctest[WIDTH-4][0] == 0))) return 0;
  }
  if (ctest[0][HEIGHT-1] == 0) {
    if (!((ctest[0][HEIGHT-2] == 0 && ctest[0][HEIGHT-3] == 0 && ctest[0][HEIGHT-4] == 0) ||
    (ctest[1][HEIGHT-1] == 0 && ctest[2][HEIGHT-1] == 0 && ctest[3][HEIGHT-1] == 0))) return 0;
  }
  if (ctest[WIDTH-1][HEIGHT-1] == 0) {
    if (!((ctest[WIDTH-1][HEIGHT-2] == 0 && ctest[WIDTH-1][HEIGHT-3] == 0 && ctest[WIDTH-1][HEIGHT-4] == 0) ||
    (ctest[WIDTH-2][HEIGHT-1] == 0 && ctest[WIDTH-3][HEIGHT-1] == 0 && ctest[WIDTH-4][HEIGHT-1] == 0))) return 0;
  }
return 1;
}

// generate special possible positions for the 'X' piece.

int xgen(int p[5][2], int l[400][5][2])
{
  int pp[5][2];
  int i, j, k;
  int index = 0, ok;
  
  for (i = 0; i < 5; i++)
    for (j = 0; j < 2; j++)
        pp[i][j] = p[i][j];
  for (i = 0; i < 5; i++)
    for (j = 0; j < 2; j++) {
      for (k = 0; k < 5; k++) {
        l[index][k][0] = pp[k][0] + i;
        l[index][k][1] = pp[k][1] + j;
      }
      ok = 1;
      if (i == 0 && j == 0) ok = 0;
      for (k = 0; k < 5; k++) {
        if (l[index][k][0] < 0) ok = 0;
        if (l[index][k][0] > WIDTH-1) ok = 0;
        if (l[index][k][1] < 0) ok = 0;
        if (l[index][k][1] > HEIGHT-1) ok = 0;
      }
      if (ok) {
        for (k = 0; k < 5; k++)
          l[index][k][0] = l[index][k][0]*HEIGHT+l[index][k][1];
        index++;
      }
    }
  return index;
}

// twogen is used for the 'I' piece only since it has so many
// symmetries.

int twogen(int p[5][2], int l[400][5][2])
{
  int pp[5][2];
  int i, j, k;
  int index = 0, ok;
  
  for (i = 0; i < 5; i++)
    for (j = 0; j < 2; j++)
        pp[i][j] = p[i][j];
  for (i = 0; i < WIDTH; i++)
    for (j = 0; j < HEIGHT; j++) {
      for (k = 0; k < 5; k++) {
        l[index][k][0] = pp[k][0] + i;
        l[index][k][1] = pp[k][1] + j;
      }
      ok = 1;
      for (k = 0; k < 5; k++) {
        if (l[index][k][0] < 0) ok = 0;
        if (l[index][k][0] > WIDTH-1) ok = 0;
        if (l[index][k][1] < 0) ok = 0;
        if (l[index][k][1] > HEIGHT-1) ok = 0;
      }
      if (ok) {
        for (k = 0; k < 5; k++)
          l[index][k][0] = l[index][k][0]*HEIGHT+l[index][k][1];
        index++;
      }
    }
  for (i = 0; i < 5; i++)
    for (j = 0; j < 2; j++) {
        pp[i][0] = p[i][1];
        pp[i][1] = p[i][0];
    }
  for (i = 0; i < WIDTH; i++)
    for (j = 0; j < HEIGHT; j++) {
      for (k = 0; k < 5; k++) {
        l[index][k][0] = pp[k][0] + i;
        l[index][k][1] = pp[k][1] + j;
      }
      ok = 1;
      for (k = 0; k < 5; k++) {
        if (l[index][k][0] < 0) ok = 0;
        if (l[index][k][0] > WIDTH-1) ok = 0;
        if (l[index][k][1] < 0) ok = 0;
        if (l[index][k][1] > HEIGHT-1) ok = 0;
      }
      if (ok) {
        for (k = 0; k < 5; k++)
          l[index][k][0] = l[index][k][0]*HEIGHT+l[index][k][1];
        index++;
      }
    }
  return index;
}

// fourgen gets all the positions for pieces without rotational
// symmetry, but with an axis of symmetry.

int fourgen(int p[5][2], int l[400][5][2])
{
  int pp[5][2];
  int i, j, k;
  int index = 0, ok;
  
  for (i = 0; i < 5; i++)
    for (j = 0; j < 2; j++)
        pp[i][j] = p[i][j];
  for (i = 0; i < WIDTH; i++)
    for (j = 0; j < HEIGHT; j++) {
      for (k = 0; k < 5; k++) {
        l[index][k][0] = pp[k][0] + i;
        l[index][k][1] = pp[k][1] + j;
      }
      ok = 1;
      for (k = 0; k < 5; k++) {
        if (l[index][k][0] < 0) ok = 0;
        if (l[index][k][0] > WIDTH-1) ok = 0;
        if (l[index][k][1] < 0) ok = 0;
        if (l[index][k][1] > HEIGHT-1) ok = 0;
      }
      if (ok)
        ok = cornercheck(index, l);
      if (ok) {
        for (k = 0; k < 5; k++)
          l[index][k][0] = l[index][k][0]*HEIGHT+l[index][k][1];
        index++;
      }
    }
    
  for (i = 0; i < 5; i++)
    for (j = 0; j < 2; j++) {
        pp[i][0] = -p[i][1];
        pp[i][1] = p[i][0];
    }
  for (i = 0; i < WIDTH*2; i++)
    for (j = 0; j < HEIGHT*2; j++) {
      for (k = 0; k < 5; k++) {
        l[index][k][0] = pp[k][0] + i;
        l[index][k][1] = pp[k][1] + j;
      }
      ok = 1;
      for (k = 0; k < 5; k++) {
        if (l[index][k][0] < 0) ok = 0;
        if (l[index][k][0] > WIDTH-1) ok = 0;
        if (l[index][k][1] < 0) ok = 0;
        if (l[index][k][1] > HEIGHT-1) ok = 0;
      }
      if (ok)
        ok = cornercheck(index, l);
      if (ok) {
        for (k = 0; k < 5; k++)
          l[index][k][0] = l[index][k][0]*HEIGHT+l[index][k][1];
        index++;
      }
    }
    
  for (i = 0; i < 5; i++)
    for (j = 0; j < 2; j++) {
        pp[i][0] = -p[i][0];
        pp[i][1] = -p[i][1];
    }
  for (i = 0; i < WIDTH*2; i++)
    for (j = 0; j < HEIGHT*2; j++) {
      for (k = 0; k < 5; k++) {
        l[index][k][0] = pp[k][0] + i;
        l[index][k][1] = pp[k][1] + j;
      }
      ok = 1;
      for (k = 0; k < 5; k++) {
        if (l[index][k][0] < 0) ok = 0;
        if (l[index][k][0] > WIDTH-1) ok = 0;
        if (l[index][k][1] < 0) ok = 0;
        if (l[index][k][1] > HEIGHT-1) ok = 0;
      }
      if (ok)
        ok = cornercheck(index, l);
      if (ok) {
        for (k = 0; k < 5; k++)
          l[index][k][0] = l[index][k][0]*HEIGHT+l[index][k][1];
        index++;
      }
    }
    
  for (i = 0; i < 5; i++)
    for (j = 0; j < 2; j++) {
        pp[i][0] = p[i][1];
        pp[i][1] = -p[i][0];
    }
  for (i = 0; i < WIDTH*2; i++)
    for (j = 0; j < HEIGHT*2; j++) {
      for (k = 0; k < 5; k++) {
        l[index][k][0] = pp[k][0] + i;
        l[index][k][1] = pp[k][1] + j;
      }
      ok = 1;
      for (k = 0; k < 5; k++) {
        if (l[index][k][0] < 0) ok = 0;
        if (l[index][k][0] > WIDTH-1) ok = 0;
        if (l[index][k][1] < 0) ok = 0;
        if (l[index][k][1] > HEIGHT-1) ok = 0;
      }
      if (ok)
        ok = cornercheck(index, l);
      if (ok) {
        for (k = 0; k < 5; k++)
          l[index][k][0] = l[index][k][0]*HEIGHT+l[index][k][1];
        index++;
      }
    }
    
  return index;
}

// special fourgen for the 'Z' piece.  The 'Z' is not mirror
// symmetric, but has rotational symmetry for 4 total.

int fourzgen(int p[5][2], int l[400][5][2])
{
  int pp[5][2];
  int i, j, k;
  int index = 0, ok;
  
  for (i = 0; i < 5; i++)
    for (j = 0; j < 2; j++)
        pp[i][j] = p[i][j];
  for (i = 0; i < WIDTH; i++)
    for (j = 0; j < HEIGHT; j++) {
      for (k = 0; k < 5; k++) {
        l[index][k][0] = pp[k][0] + i;
        l[index][k][1] = pp[k][1] + j;
      }
      ok = 1;
      for (k = 0; k < 5; k++) {
        if (l[index][k][0] < 0) ok = 0;
        if (l[index][k][0] > WIDTH-1) ok = 0;
        if (l[index][k][1] < 0) ok = 0;
        if (l[index][k][1] > HEIGHT-1) ok = 0;
      }
      if (ok)
        ok = cornercheck(index, l);
      if (ok) {
        for (k = 0; k < 5; k++)
          l[index][k][0] = l[index][k][0]*HEIGHT+l[index][k][1];
        index++;
      }
    }
    
  for (i = 0; i < 5; i++)
    for (j = 0; j < 2; j++) {
        pp[i][0] = -p[i][1];
        pp[i][1] = p[i][0];
    }
  for (i = 0; i < WIDTH*2; i++)
    for (j = 0; j < HEIGHT*2; j++) {
      for (k = 0; k < 5; k++) {
        l[index][k][0] = pp[k][0] + i;
        l[index][k][1] = pp[k][1] + j;
      }
      ok = 1;
      for (k = 0; k < 5; k++) {
        if (l[index][k][0] < 0) ok = 0;
        if (l[index][k][0] > WIDTH-1) ok = 0;
        if (l[index][k][1] < 0) ok = 0;
        if (l[index][k][1] > HEIGHT-1) ok = 0;
      }
      if (ok)
        ok = cornercheck(index, l);
      if (ok) {
        for (k = 0; k < 5; k++)
          l[index][k][0] = l[index][k][0]*HEIGHT+l[index][k][1];
        index++;
      }
    }
    
  for (i = 0; i < 5; i++)
    for (j = 0; j < 2; j++) {
        pp[i][0] = -p[i][0];
        pp[i][1] = p[i][1];
    }
  for (i = 0; i < WIDTH*2; i++)
    for (j = 0; j < HEIGHT*2; j++) {
      for (k = 0; k < 5; k++) {
        l[index][k][0] = pp[k][0] + i;
        l[index][k][1] = pp[k][1] + j;
      }
      ok = 1;
      for (k = 0; k < 5; k++) {
        if (l[index][k][0] < 0) ok = 0;
        if (l[index][k][0] > WIDTH-1) ok = 0;
        if (l[index][k][1] < 0) ok = 0;
        if (l[index][k][1] > HEIGHT-1) ok = 0;
      }
      if (ok)
        ok = cornercheck(index, l);
      if (ok) {
        for (k = 0; k < 5; k++)
          l[index][k][0] = l[index][k][0]*HEIGHT+l[index][k][1];
        index++;
      }
    }
    
  for (i = 0; i < 5; i++)
    for (j = 0; j < 2; j++) {
        pp[i][0] = p[i][1];
        pp[i][1] = p[i][0];
    }
  for (i = 0; i < WIDTH*2; i++)
    for (j = 0; j < HEIGHT*2; j++) {
      for (k = 0; k < 5; k++) {
        l[index][k][0] = pp[k][0] + i;
        l[index][k][1] = pp[k][1] + j;
      }
      ok = 1;
      for (k = 0; k < 5; k++) {
        if (l[index][k][0] < 0) ok = 0;
        if (l[index][k][0] > WIDTH-1) ok = 0;
        if (l[index][k][1] < 0) ok = 0;
        if (l[index][k][1] > HEIGHT-1) ok = 0;
      }
      if (ok)
        ok = cornercheck(index, l);
      if (ok) {
        for (k = 0; k < 5; k++)
          l[index][k][0] = l[index][k][0]*HEIGHT+l[index][k][1];
        index++;
      }
    }
    
  return index;
}

// eightgen is the general ugly situation where all eight
// rotations and mirrorings of a piece are different.

int eightgen(int p[5][2], int l[400][5][2])
{
  int pp[5][2];
  int i, j, k;
  int index = 0, ok;
  
  for (i = 0; i < 5; i++)
    for (j = 0; j < 2; j++)
        pp[i][j] = p[i][j];
  for (i = 0; i < WIDTH; i++)
    for (j = 0; j < HEIGHT; j++) {
      for (k = 0; k < 5; k++) {
        l[index][k][0] = pp[k][0] + i;
        l[index][k][1] = pp[k][1] + j;
      }
      ok = 1;
      for (k = 0; k < 5; k++) {
        if (l[index][k][0] < 0) ok = 0;
        if (l[index][k][0] > WIDTH-1) ok = 0;
        if (l[index][k][1] < 0) ok = 0;
        if (l[index][k][1] > HEIGHT-1) ok = 0;
      }
      if (ok)
        ok = cornercheck(index, l);
      if (ok) {
        for (k = 0; k < 5; k++)
          l[index][k][0] = l[index][k][0]*HEIGHT+l[index][k][1];
        index++;
      }
    }
    
  for (i = 0; i < 5; i++)
    for (j = 0; j < 2; j++) {
        pp[i][0] = -p[i][1];
        pp[i][1] = p[i][0];
    }
  for (i = 0; i < WIDTH*2; i++)
    for (j = 0; j < HEIGHT*2; j++) {
      for (k = 0; k < 5; k++) {
        l[index][k][0] = pp[k][0] + i;
        l[index][k][1] = pp[k][1] + j;
      }
      ok = 1;
      for (k = 0; k < 5; k++) {
        if (l[index][k][0] < 0) ok = 0;
        if (l[index][k][0] > WIDTH-1) ok = 0;
        if (l[index][k][1] < 0) ok = 0;
        if (l[index][k][1] > HEIGHT-1) ok = 0;
      }
      if (ok)
        ok = cornercheck(index, l);
      if (ok) {
        for (k = 0; k < 5; k++)
          l[index][k][0] = l[index][k][0]*HEIGHT+l[index][k][1];
        index++;
      }
    }
    
  for (i = 0; i < 5; i++)
    for (j = 0; j < 2; j++) {
        pp[i][0] = -p[i][0];
        pp[i][1] = -p[i][1];
    }
  for (i = 0; i < WIDTH*2; i++)
    for (j = 0; j < HEIGHT*2; j++) {
      for (k = 0; k < 5; k++) {
        l[index][k][0] = pp[k][0] + i;
        l[index][k][1] = pp[k][1] + j;
      }
      ok = 1;
      for (k = 0; k < 5; k++) {
        if (l[index][k][0] < 0) ok = 0;
        if (l[index][k][0] > WIDTH-1) ok = 0;
        if (l[index][k][1] < 0) ok = 0;
        if (l[index][k][1] > HEIGHT-1) ok = 0;
      }
      if (ok)
        ok = cornercheck(index, l);
      if (ok) {
        for (k = 0; k < 5; k++)
          l[index][k][0] = l[index][k][0]*HEIGHT+l[index][k][1];
        index++;
      }
    }
    
  for (i = 0; i < 5; i++)
    for (j = 0; j < 2; j++) {
        pp[i][0] = p[i][1];
        pp[i][1] = -p[i][0];
    }
  for (i = 0; i < WIDTH*2; i++)
    for (j = 0; j < HEIGHT*2; j++) {
      for (k = 0; k < 5; k++) {
        l[index][k][0] = pp[k][0] + i;
        l[index][k][1] = pp[k][1] + j;
      }
      ok = 1;
      for (k = 0; k < 5; k++) {
        if (l[index][k][0] < 0) ok = 0;
        if (l[index][k][0] > WIDTH-1) ok = 0;
        if (l[index][k][1] < 0) ok = 0;
        if (l[index][k][1] > HEIGHT-1) ok = 0;
      }
      if (ok)
        ok = cornercheck(index, l);
      if (ok) {
        for (k = 0; k < 5; k++)
          l[index][k][0] = l[index][k][0]*HEIGHT+l[index][k][1];
        index++;
      }
    }
    
  for (i = 0; i < 5; i++)
    for (j = 0; j < 2; j++) {
        pp[i][0] = p[i][0];
        pp[i][1] = -p[i][1];
    }
  for (i = 0; i < WIDTH*2; i++)
    for (j = 0; j < HEIGHT*2; j++) {
      for (k = 0; k < 5; k++) {
        l[index][k][0] = pp[k][0] + i;
        l[index][k][1] = pp[k][1] + j;
      }
      ok = 1;
      for (k = 0; k < 5; k++) {
        if (l[index][k][0] < 0) ok = 0;
        if (l[index][k][0] > WIDTH-1) ok = 0;
        if (l[index][k][1] < 0) ok = 0;
        if (l[index][k][1] > HEIGHT-1) ok = 0;
      }
      if (ok)
        ok = cornercheck(index, l);
      if (ok) {
        for (k = 0; k < 5; k++)
          l[index][k][0] = l[index][k][0]*HEIGHT+l[index][k][1];
        index++;
      }
    }
    
  for (i = 0; i < 5; i++)
    for (j = 0; j < 2; j++) {
        pp[i][0] = -p[i][1];
        pp[i][1] = -p[i][0];
    }
  for (i = 0; i < WIDTH*2; i++)
    for (j = 0; j < HEIGHT*2; j++) {
      for (k = 0; k < 5; k++) {
        l[index][k][0] = pp[k][0] + i;
        l[index][k][1] = pp[k][1] + j;
      }
      ok = 1;
      for (k = 0; k < 5; k++) {
        if (l[index][k][0] < 0) ok = 0;
        if (l[index][k][0] > WIDTH-1) ok = 0;
        if (l[index][k][1] < 0) ok = 0;
        if (l[index][k][1] > HEIGHT-1) ok = 0;
      }
      if (ok)
        ok = cornercheck(index, l);
      if (ok) {
        for (k = 0; k < 5; k++)
          l[index][k][0] = l[index][k][0]*HEIGHT+l[index][k][1];
        index++;
      }
    }
    
  for (i = 0; i < 5; i++)
    for (j = 0; j < 2; j++) {
        pp[i][0] = -p[i][0];
        pp[i][1] = p[i][1];
    }
  for (i = 0; i < WIDTH*2; i++)
    for (j = 0; j < HEIGHT*2; j++) {
      for (k = 0; k < 5; k++) {
        l[index][k][0] = pp[k][0] + i;
        l[index][k][1] = pp[k][1] + j;
      }
      ok = 1;
      for (k = 0; k < 5; k++) {
        if (l[index][k][0] < 0) ok = 0;
        if (l[index][k][0] > WIDTH-1) ok = 0;
        if (l[index][k][1] < 0) ok = 0;
        if (l[index][k][1] > HEIGHT-1) ok = 0;
      }
      if (ok)
        ok = cornercheck(index, l);
      if (ok) {
        for (k = 0; k < 5; k++)
          l[index][k][0] = l[index][k][0]*HEIGHT+l[index][k][1];
        index++;
      }
    }
    
  for (i = 0; i < 5; i++)
    for (j = 0; j < 2; j++) {
        pp[i][0] = p[i][1];
        pp[i][1] = p[i][0];
    }
  for (i = 0; i < WIDTH*2; i++)
    for (j = 0; j < HEIGHT*2; j++) {
      for (k = 0; k < 5; k++) {
        l[index][k][0] = pp[k][0] + i;
        l[index][k][1] = pp[k][1] + j;
      }
      ok = 1;
      for (k = 0; k < 5; k++) {
        if (l[index][k][0] < 0) ok = 0;
        if (l[index][k][0] > WIDTH-1) ok = 0;
        if (l[index][k][1] < 0) ok = 0;
        if (l[index][k][1] > HEIGHT-1) ok = 0;
      }
      if (ok)
        ok = cornercheck(index, l);
      if (ok) {
        for (k = 0; k < 5; k++)
          l[index][k][0] = l[index][k][0]*HEIGHT+l[index][k][1];
        index++;
      }
    }
    
  return index;
}

// these hold all the valid positions on the board.  Initially,
// they contained the x and y coordinates of the points, but for
// speed, I later combined them into a single entry and replaced
// the x-coordinate by it.

int li[400][5][2],
    ll[400][5][2],
    ly[400][5][2],
    lt[400][5][2],
    lf[400][5][2],
    lx[400][5][2],
    lp[400][5][2],
    lv[400][5][2],
    lw[400][5][2],
    lu[400][5][2],
    ln[400][5][2],
    lz[400][5][2];
int icount, lcount, ycount, tcount, fcount, xcount,
    pcount, vcount, wcount, ucount, ncount, zcount;
    
// test is the "board" into which we cram the virtual pieces.
    
int test[WIDTH*HEIGHT];

void zerotest()
{
  int i;
  for (i = 0; i < WIDTH*HEIGHT; i++)
        test[i] = 0;
}

// the code to print the results opens, appends, and
// closes the file in case you want to run this over
// multiple sessions.

void printtest()
{
  FILE *f;
  int i, j;
  f = fopen("goodpentout.txt", "a");
  for (i = 0; i < HEIGHT*WIDTH; i++) {
      fprintf(f, "%c", test[i]? test[i]:' ');
  }
  fprintf(f, "\n");
  fclose(f);
  fprintf(stderr, "bingo!\n");
}

// load takes a piece and sees if it will fit.  If
// so, the piece is added and it returns 1; otherwise
// it does nothing and returns 0.

int load(int l[400][5][2], int index, int v)
{
    int i;
    static int inc = 0;
    
    inc++;
    if (inc == 100000000) {
      inc = 0;
      fprintf(stderr, "%d %d %d %d %d %d %d %d %d %d %d %d\n",
qx, qi, qt, qv, qw, qu, ql, qy, qf, qp, qn, qz);
}
    
    for (i = 0; i < 5; i++) {
        if (test[l[index][i][0]]) return 0;
    }
    for (i = 0; i < 5; i++) {
        test[l[index][i][0]] = v;
    }
    return 1;
}

// unload removes a piece from the virtual board.
    
void unload(int l[400][5][2], int index)
{
    int i;
    
    for (i = 0; i < 5; i++) {
        test[l[index][i][0]] = 0;
    }
}

// finally, here's the code to generate all possible
// positions and then do the horrible nested loop thing.
// It takes hours to run ...

// I got 1308 solutions and when I eliminated the duplicates
// that were mirror images, I got 1010 unique solutions.
    
int main(int argc, char **argv)
{
  int i, j;
  int inc = 0;
  
  
  xcount = xgen(xpiece, lx);
  icount = twogen(ipiece, li);
  tcount = fourgen(tpiece, lt);
  vcount = fourgen(vpiece, lv);
  wcount = fourgen(wpiece, lw);
  doingu = 1;
  ucount = fourgen(upiece, lu);
  doingu = 0;
  lcount = eightgen(lpiece, ll);
  ycount = eightgen(ypiece, ly);
  fcount = eightgen(fpiece, lf);
  pcount = eightgen(ppiece, lp);
  ncount = eightgen(npiece, ln);
  zcount = fourzgen(zpiece, lz);
  
  printf("%d %d %d %d %d %d %d %d %d %d %d %d\n",
   xcount,
   icount, tcount, vcount, wcount, ucount, lcount,
   ycount, fcount, pcount, ncount, zcount);
   
  zerotest();

  for (qx = 0; qx < xcount; qx++) {
    load(lx, qx, 'x');
    for (qi = 0; qi < icount; qi++) {
      if (0 == load(li, qi, 'i')) goto labi;
      for (qt = 0; qt < tcount; qt++) {
        if (0 == load(lt, qt, 't')) goto labt;
        for (qv = 0; qv < vcount; qv++) {
          if (0 == load(lv, qv, 'v')) goto labv;
          for (qw = 0; qw < wcount; qw++) {
            if (0 == load(lw, qw, 'w')) goto labw;
            for (qu = 0; qu < ucount; qu++) {
              if (0 == load(lu, qu, 'u')) goto labu;
              for (qz = 0; qz < zcount; qz++) {
                if (0 == load(lz, qz, 'z')) goto labz;
                for (qy = 0; qy < ycount; qy++) {
                  if (0 == load(ly, qy, 'y')) goto laby;
                  for (qf = 0; qf < fcount; qf++) {
                    if (0 == load(lf, qf, 'f')) goto labf;
                    for (qp = 0; qp < pcount; qp++) {
                      if (0 == load(lp, qp, 'p')) goto labp;
                      for (qn = 0; qn < ncount; qn++) {
                        if (0 == load(ln, qn, 'n')) goto labn;
                        for (ql = 0; ql < lcount; ql++) {
                          if (0 == load(ll, ql, 'l')) goto labl;
                          printtest();
                          unload(ll, ql);
                        labl:;}
                      unload(ln, qn);
                      labn:;}
                    unload(lp, qp);
                    labp:;}
                  unload(lf, qf);
                  labf:;}
                unload(ly, qy);
                laby:;}
              unload(lz, qz);
              labz:;}
            unload(lu, qu);
            labu:;}
          unload(lw, qw);
          labw:;}
        unload(lv, qv);
        labv:;}
      unload(lt, qt);
      labt:;}
    unload(li, qi);
    labi:;}
  unload(lx, qx);
  }
  
  
   return 0;
}