/**
 * Pentominoes compiler/generator.
 *
 * Copyright (C) 1985-2001, Stan Chesnutt
 *
 * $Id: pentos.c,v 1.1.1.1 2005/12/30 22:08:07 chesnutt Exp $
 */

#include <assert.h>
#include <stdio.h>

#define	MAX_X		31
#define	MAX_Y		31

/**
 * The table of pieces has one entry per pento component.  The first
 * one is assumed to be at the current point, and each other component
 * is stored as an offset from the current point.  Since pentos have
 * five components, we only store four offsets.
 */
#define	PIECESIZE	4

/**
 * There are twelve distinct pentominoes
 */
#define	NUMPIECES	12

/**
 * Each piece can max four orientations, plus a reflection.  So
 * there are eight possible orientations of each piece.  Certain
 * pieces have fewer, and the X pentomino has only one orientation
 */
#define	NUMORIENT	8

typedef struct {
  int             delt [PIECESIZE];
  int             maxforward;
} ORIENTDEF, *ORIENTPTR;

typedef struct  {
        ORIENTDEF       orient [NUMORIENT];
        } PIECEDEF;

typedef	int             *BINODPTR;
typedef PIECEDEF        *PIECEPTR;

static  PIECEDEF     piece [NUMPIECES];
static  int         table [(MAX_X+1) * (MAX_Y+1)];
static  char         num_orientations [NUMPIECES];
static  unsigned int	width, height, scaled_width;

#define	map_to_linear(q,v)	(((v) * (width + 1)) + (q))

static  char    * screen = "# XIVTUSWPRZYL";

static void
print_table()
{
  register int    i, j;
  static int sno;

  sno++;
  printf ("Solution #%-d\n", sno);

  for (j = 0; j <= width + 1; j++)
    putchar ('#');

  putchar ('\n');

  for (j = 0; j < (height + 1); j++) {
    putchar ('#');

    for (i = 0; i <= width; i++)
      putchar (screen [table [map_to_linear (i, j)] + 1]);

    putchar ('\n');
  }

  putchar ('\n');
  fflush (stdout);
}

static void
initpieces()
{
  num_orientations [0] = 1;        /* X */
  piece [0].orient[0].delt[0] = ( 0 + (scaled_width) * 1 );
  piece [0].orient[0].delt[1] = ( 1 + (scaled_width) * 1 );
  piece [0].orient[0].delt[2] = (-1 + (scaled_width) * 1 );
  piece [0].orient[0].delt[3] = ( 0 + (scaled_width) * 2 );
  piece[0].orient[0].maxforward = 1;


  if (height > 4)
    num_orientations [1] = 2;
  else
    num_orientations [1] = 1;        /* I */

  piece [1].orient[0].delt[0] = ( 1 + (scaled_width) * 0 );
  piece [1].orient[0].delt[1] = ( 2 + (scaled_width) * 0 );
  piece [1].orient[0].delt[2] = ( 3 + (scaled_width) * 0 );
  piece [1].orient[0].delt[3] = ( 4 + (scaled_width) * 0 );
  piece[1].orient[0].maxforward = 5;

  piece [1].orient[1].delt[0] = ( 0 + (scaled_width) * 1 );
  piece [1].orient[1].delt[1] = ( 0 + (scaled_width) * 2 );
  piece [1].orient[1].delt[2] = ( 0 + (scaled_width) * 3 );
  piece [1].orient[1].delt[3] = ( 0 + (scaled_width) * 4 );
  piece[1].orient[1].maxforward = 1;

  num_orientations [2] = 4;        /* V */
  piece [2].orient[0].delt[0] = ( 1 + (scaled_width) * 0 );
  piece [2].orient[0].delt[1] = ( 2 + (scaled_width) * 0 );
  piece [2].orient[0].delt[2] = ( 0 + (scaled_width) * 1 );
  piece [2].orient[0].delt[3] = ( 0 + (scaled_width) * 2 );
  piece[2].orient[0].maxforward = 3;

  piece [2].orient[1].delt[0] = ( 1 + (scaled_width) * 0 );
  piece [2].orient[1].delt[1] = ( 2 + (scaled_width) * 0 );
  piece [2].orient[1].delt[2] = ( 2 + (scaled_width) * 1 );
  piece [2].orient[1].delt[3] = ( 2 + (scaled_width) * 2 );
  piece[2].orient[1].maxforward = 3;

  piece [2].orient[2].delt[0] = ( 1 + (scaled_width) * 2 );
  piece [2].orient[2].delt[1] = ( 2 + (scaled_width) * 2 );
  piece [2].orient[2].delt[2] = ( 0 + (scaled_width) * 1 );
  piece [2].orient[2].delt[3] = ( 0 + (scaled_width) * 2 );
  piece[2].orient[2].maxforward = 3;

  piece [2].orient[3].delt[0] = ( -1 + (scaled_width) * 2 );
  piece [2].orient[3].delt[1] = ( -2 + (scaled_width) * 2 );
  piece [2].orient[3].delt[2] = ( 0 + (scaled_width) * 1 );
  piece [2].orient[3].delt[3] = ( 0 + (scaled_width) * 2 );
  piece[2].orient[3].maxforward = 1;

  num_orientations [3] = 4;         /*  T  */
  piece[3].orient[0].delt[0] = ( 1 + (scaled_width) * 0 );
  piece[3].orient[0].delt[1] = ( 2 + (scaled_width) * 0 );
  piece[3].orient[0].delt[2] = ( 1 + (scaled_width) * 1 );
  piece[3].orient[0].delt[3] = ( 1 + (scaled_width) * 2 );
  piece[3].orient[0].maxforward = 3;

  piece[3].orient[1].delt[0] = (-1 + (scaled_width) * 2 );
  piece[3].orient[1].delt[1] = ( 1 + (scaled_width) * 2 );
  piece[3].orient[1].delt[2] = ( 0 + (scaled_width) * 1 );
  piece[3].orient[1].delt[3] = ( 0 + (scaled_width) * 2 );
  piece[3].orient[0].maxforward = 1;

  piece[3].orient[2].delt[0] = ( 1 + (scaled_width) * 1 );
  piece[3].orient[2].delt[1] = ( 2 + (scaled_width) * 1 );
  piece[3].orient[2].delt[2] = ( 0 + (scaled_width) * 1 );
  piece[3].orient[2].delt[3] = ( 0 + (scaled_width) * 2 );
  piece[3].orient[2].maxforward = 1;

  piece[3].orient[3].delt[0] = ( -1 + (scaled_width) * 1 );
  piece[3].orient[3].delt[1] = ( -2 + (scaled_width) * 1 );
  piece[3].orient[3].delt[2] = ( 0 + (scaled_width) * 1 );
  piece[3].orient[3].delt[3] = ( 0 + (scaled_width) * 2 );
  piece[3].orient[3].maxforward = 1;

  num_orientations [4] = 4;      /*  U  */
  piece[4].orient[0].delt[0] = ( 1 + (scaled_width) * 0 );
  piece[4].orient[0].delt[1] = ( 2 + (scaled_width) * 0 );
  piece[4].orient[0].delt[2] = ( 0 + (scaled_width) * 1 );
  piece[4].orient[0].delt[3] = ( 2 + (scaled_width) * 1 );
  piece[4].orient[0].maxforward = 3;

  piece[4].orient[1].delt[0] = ( 2 + (scaled_width) * 0 );
  piece[4].orient[1].delt[1] = ( 2 + (scaled_width) * 1 );
  piece[4].orient[1].delt[2] = ( 1 + (scaled_width) * 1 );
  piece[4].orient[1].delt[3] = ( 0 + (scaled_width) * 1 );
  piece[4].orient[1].maxforward = 3;

  piece[4].orient[2].delt[0] = ( 1 + (scaled_width) * 0 );
  piece[4].orient[2].delt[1] = ( 1 + (scaled_width) * 1 );
  piece[4].orient[2].delt[2] = ( 1 + (scaled_width) * 2 );
  piece[4].orient[2].delt[3] = ( 0 + (scaled_width) * 2 );
  piece[4].orient[2].maxforward = 2;

  piece[4].orient[3].delt[0] = ( 0 + (scaled_width) * 1 );
  piece[4].orient[3].delt[1] = ( 1 + (scaled_width) * 0 );
  piece[4].orient[3].delt[2] = ( 0 + (scaled_width) * 2 );
  piece[4].orient[3].delt[3] = ( 1 + (scaled_width) * 2 );
  piece[4].orient[3].maxforward = 2;

  num_orientations [5] = 4;     /*   S   */
  piece[5].orient[0].delt[0] = ( 0 + (scaled_width) * 1 );
  piece[5].orient[0].delt[1] = ( 1 + (scaled_width) * 1 );
  piece[5].orient[0].delt[2] = ( 2 + (scaled_width) * 1 );
  piece[5].orient[0].delt[3] = ( 2 + (scaled_width) * 2 );
  piece[5].orient[0].maxforward = 1;

  piece[5].orient[1].delt[0] = ( 0 + (scaled_width) * 1 );
  piece[5].orient[1].delt[1] = (-1 + (scaled_width) * 1 );
  piece[5].orient[1].delt[2] = (-2 + (scaled_width) * 1 );
  piece[5].orient[1].delt[3] = (-2 + (scaled_width) * 2 );
  piece[5].orient[1].maxforward = 1;

  piece[5].orient[2].delt[0] = ( 1 + (scaled_width) * 0 );
  piece[5].orient[2].delt[1] = ( 1 + (scaled_width) *  1 );
  piece[5].orient[2].delt[2] = ( 1 + (scaled_width) * 2 );
  piece[5].orient[2].delt[3] = ( 2 + (scaled_width) * 2 );
  piece[5].orient[2].maxforward = 2;

  piece[5].orient[3].delt[0] = ( 1 + (scaled_width) * 0 );
  piece[5].orient[3].delt[1] = ( 0  + (scaled_width) * 1 );
  piece[5].orient[3].delt[2] = ( 0 + (scaled_width) *  2 );
  piece[5].orient[3].delt[3] = (-1 + (scaled_width) *  2 );
  piece[5].orient[3].maxforward = 2;

  num_orientations [6] = 4;       /*   W   */
  piece[6].orient[0].delt[0] = ( 1 + (scaled_width) * 0 );
  piece[6].orient[0].delt[1] = ( 0 + (scaled_width) * 1 );
  piece[6].orient[0].delt[2] = (-1 + (scaled_width) * 1 );
  piece[6].orient[0].delt[3] = (-1 + (scaled_width) * 2 );
  piece[6].orient[0].maxforward = 2;

  piece[6].orient[1].delt[0] = ( 0 + (scaled_width) * 1 );
  piece[6].orient[1].delt[1] = ( -1 + (scaled_width) * 1 );
  piece[6].orient[1].delt[2] = ( -1 + (scaled_width) * 2 );
  piece[6].orient[1].delt[3] = ( -2 + (scaled_width) * 2 );
  piece[6].orient[1].maxforward = 1;

  piece[6].orient[2].delt[0] = ( 0 + (scaled_width) * 1 );
  piece[6].orient[2].delt[1] = ( 1 + (scaled_width) * 1 );
  piece[6].orient[2].delt[2] = ( 1 + (scaled_width) * 2 );
  piece[6].orient[2].delt[3] = ( 2 + (scaled_width) * 2 );
  piece[6].orient[2].maxforward = 2;

  piece[6].orient[3].delt[0] = ( 1 + (scaled_width) * 0 );
  piece[6].orient[3].delt[1] = ( 1 + (scaled_width) * 1 );
  piece[6].orient[3].delt[2] = ( 2 + (scaled_width) * 1 );
  piece[6].orient[3].delt[3] = ( 2 + (scaled_width) * 2 );
  piece[6].orient[3].maxforward = 2;

  num_orientations [7] = 8;
  piece[7].orient[0].delt[0] = ( 1 + (scaled_width) * 1 );
  piece[7].orient[0].delt[1] = ( 1 + (scaled_width) * 2 );
  piece[7].orient[0].delt[2] = ( 0 + (scaled_width) * 1 );
  piece[7].orient[0].delt[3] = ( 0 + (scaled_width) * 2 );
  piece[7].orient[0].maxforward = 1;

  piece[7].orient[1].delt[0] = ( 0 + (scaled_width) * 1 );
  piece[7].orient[1].delt[1] = ( 0 + (scaled_width) * 2 );
  piece[7].orient[1].delt[2] = (-1 + (scaled_width) * 1 );
  piece[7].orient[1].delt[3] = (-1 + (scaled_width) * 2 );
  piece[7].orient[1].maxforward = 1;

  piece[7].orient[2].delt[0] = ( 1 + (scaled_width) * 0 );
  piece[7].orient[2].delt[1] = ( 1 + (scaled_width) * 1 );
  piece[7].orient[2].delt[2] = ( 0 + (scaled_width) * 1 );
  piece[7].orient[2].delt[3] = ( 2 + (scaled_width) * 0 );
  piece[7].orient[2].maxforward = 3;

  piece[7].orient[3].delt[0] = ( 1 + (scaled_width) * 0 );
  piece[7].orient[3].delt[1] = ( 1 + (scaled_width) * 1 );
  piece[7].orient[3].delt[2] = ( 0 + (scaled_width) * 1 );
  piece[7].orient[3].delt[3] = ( 2 + (scaled_width) * 1 );
  piece[7].orient[3].maxforward = 2;

  piece[7].orient[4].delt[0] = ( 1 + (scaled_width) * 0 );
  piece[7].orient[4].delt[1] = ( 1 + (scaled_width) * 1 );
  piece[7].orient[4].delt[2] = ( 0 + (scaled_width) * 1 );
  piece[7].orient[4].delt[3] = ( 1 + (scaled_width) * 2 );
  piece[7].orient[4].maxforward = 2;

  piece[7].orient[5].delt[0] = ( 1 + (scaled_width) * 0 );
  piece[7].orient[5].delt[1] = ( 1 + (scaled_width) * 1 );
  piece[7].orient[5].delt[2] = ( 0 + (scaled_width) * 1 );
  piece[7].orient[5].delt[3] = ( 0 + (scaled_width) * 2 );
  piece[7].orient[5].maxforward = 2;

  piece[7].orient[6].delt[0] = ( 1 + (scaled_width) * 0 );
  piece[7].orient[6].delt[1] = ( 1 + (scaled_width) * 1 );
  piece[7].orient[6].delt[2] = ( 0 + (scaled_width) * 1 );
  piece[7].orient[6].delt[3] = ( -1 + (scaled_width) * 1 );
  piece[7].orient[6].maxforward = 2;

  piece[7].orient[7].delt[0] = ( 1 + (scaled_width) * 0 );
  piece[7].orient[7].delt[1] = ( 1 + (scaled_width) * 1 );
  piece[7].orient[7].delt[2] = ( 2 + (scaled_width) * 1 );
  piece[7].orient[7].delt[3] = ( 2 + (scaled_width) * 0 );
  piece[7].orient[7].maxforward = 3;

  num_orientations [8] = 8;
  piece[8].orient[0].delt[0] = ( 0 + (scaled_width) * 1 );
  piece[8].orient[0].delt[1] = ( -1 + (scaled_width) * 1 );
  piece[8].orient[0].delt[2] = ( 0 + (scaled_width) * 2 );
  piece[8].orient[0].delt[3] = ( 1 + (scaled_width) * 2 );
  piece[8].orient[0].maxforward = 1;

  piece[8].orient[1].delt[0] = ( 0 + (scaled_width) * 1 );
  piece[8].orient[1].delt[1] = ( -1 + (scaled_width) * 1 );
  piece[8].orient[1].delt[2] = ( -2 + (scaled_width) * 1 );
  piece[8].orient[1].delt[3] = ( -1 + (scaled_width) * 2 );
  piece[8].orient[1].maxforward = 1;

  piece[8].orient[2].delt[0] = ( 1 + (scaled_width) * 0 );
  piece[8].orient[2].delt[1] = ( 1 + (scaled_width) * 1 );
  piece[8].orient[2].delt[2] = ( 1 + (scaled_width) * 2 );
  piece[8].orient[2].delt[3] = ( 2 + (scaled_width) * 1 );
  piece[8].orient[2].maxforward = 2;

  piece[8].orient[3].delt[0] = ( 0 + (scaled_width) * 1 );
  piece[8].orient[3].delt[1] = ( 1 + (scaled_width) * 1 );
  piece[8].orient[3].delt[2] = (-1 + (scaled_width) * 1 );
  piece[8].orient[3].delt[3] = (-1 + (scaled_width) * 2 );
  piece[8].orient[3].maxforward = 1;

  piece[8].orient[4].delt[0] = ( 0 + (scaled_width) * 1 );
  piece[8].orient[4].delt[1] = ( 1 + (scaled_width) * 1 );
  piece[8].orient[4].delt[2] = (-1 + (scaled_width) * 1 );
  piece[8].orient[4].delt[3] = ( 1 + (scaled_width) * 2 );
  piece[8].orient[4].maxforward = 1;

  piece[8].orient[5].delt[0] = ( 1 + (scaled_width) * 0 );
  piece[8].orient[5].delt[1] = ( 0 + (scaled_width) * 2 );
  piece[8].orient[5].delt[2] = ( 0 + (scaled_width) * 1 );
  piece[8].orient[5].delt[3] = (-1 + (scaled_width) * 1 );
  piece[8].orient[5].maxforward = 2;

  piece[8].orient[6].delt[0] = ( 0 + (scaled_width) * 1 );
  piece[8].orient[6].delt[1] = ( 1 + (scaled_width) * 1 );
  piece[8].orient[6].delt[2] = ( 1 + (scaled_width) * 2 );
  piece[8].orient[6].delt[3] = ( 2 + (scaled_width) * 1 );
  piece[8].orient[6].maxforward = 1;

  piece[8].orient[7].delt[0] = ( 0 + (scaled_width) * 1 );
  piece[8].orient[7].delt[1] = ( 1 + (scaled_width) * 1 );
  piece[8].orient[7].delt[2] = ( 0 + (scaled_width) * 2 );
  piece[8].orient[7].delt[3] = (-1 + (scaled_width) * 2 );
  piece[8].orient[7].maxforward = 1;

  if (height > 3)
    num_orientations [9] = 8;
  else
    num_orientations [9] = 4;

  piece[9].orient[0].delt[0] = ( 1 + (scaled_width) * 0 );
  piece[9].orient[0].delt[1] = ( 0 + (scaled_width) * 1 );
  piece[9].orient[0].delt[2] = (-1 + (scaled_width) * 1 );
  piece[9].orient[0].delt[3] = (-2 + (scaled_width) * 1 );
  piece[9].orient[0].maxforward = 2;

  piece[9].orient[1].delt[0] = ( 1 + (scaled_width) * 0 );
  piece[9].orient[1].delt[1] = ( 2 + (scaled_width) * 0 );
  piece[9].orient[1].delt[2] = ( 2 + (scaled_width) * 1 );
  piece[9].orient[1].delt[3] = ( 3 + (scaled_width) * 1 );
  piece[9].orient[1].maxforward = 3;

  piece[9].orient[2].delt[0] = ( 1 + (scaled_width) * 0 );
  piece[9].orient[2].delt[1] = ( 2 + (scaled_width) * 0 );
  piece[9].orient[2].delt[2] = ( 0 + (scaled_width) * 1 );
  piece[9].orient[2].delt[3] = (-1 + (scaled_width) * 1 );
  piece[9].orient[2].maxforward = 3;

  piece[9].orient[3].delt[0] = ( 1 + (scaled_width) * 1 );
  piece[9].orient[3].delt[1] = ( 2 + (scaled_width) * 1 );
  piece[9].orient[3].delt[2] = ( 3 + (scaled_width) * 1 );
  piece[9].orient[3].delt[3] = ( 1 + (scaled_width) * 0 );
  piece[9].orient[3].maxforward = 2;

  piece[9].orient[4].delt[0] = ( 0 + (scaled_width) * 1 );
  piece[9].orient[4].delt[1] = (-1 + (scaled_width) * 1 );
  piece[9].orient[4].delt[2] = (-1 + (scaled_width) * 2 );
  piece[9].orient[4].delt[3] = (-1 + (scaled_width) * 3 );
  piece[9].orient[4].maxforward = 1;

  piece[9].orient[5].delt[0] = ( 0 + (scaled_width) * 1 );
  piece[9].orient[5].delt[1] = ( 1 + (scaled_width) * 1 );
  piece[9].orient[5].delt[2] = ( 1 + (scaled_width) * 2 );
  piece[9].orient[5].delt[3] = ( 1 + (scaled_width) * 3 );
  piece[9].orient[5].maxforward = 1;

  piece[9].orient[6].delt[0] = ( 0 + (scaled_width) * 1 );
  piece[9].orient[6].delt[1] = ( 0 + (scaled_width) * 2 );
  piece[9].orient[6].delt[2] = ( 1 + (scaled_width) * 2 );
  piece[9].orient[6].delt[3] = ( 1 + (scaled_width) * 3 );
  piece[9].orient[6].maxforward = 1;

  piece[9].orient[7].delt[0] = ( 0 + (scaled_width) * 1 );
  piece[9].orient[7].delt[1] = ( 0 + (scaled_width) * 2 );
  piece[9].orient[7].delt[2] = ( -1 + (scaled_width) * 2 );
  piece[9].orient[7].delt[3] = ( -1 + (scaled_width) * 3 );
  piece[9].orient[7].maxforward = 1;

  if (height > 3)
    num_orientations [10] = 8;
  else
    num_orientations [10] = 4;

  piece[10].orient[0].delt[0] = ( 1 + (scaled_width) * 0 );
  piece[10].orient[0].delt[1] = ( 2 + (scaled_width) * 0 );
  piece[10].orient[0].delt[2] = ( 3 + (scaled_width) * 0 );
  piece[10].orient[0].delt[3] = ( 2 + (scaled_width) * 1 );
  piece[10].orient[0].maxforward = 4;
  
  piece[10].orient[1].delt[0] = ( 1 + (scaled_width) * 0 );
  piece[10].orient[1].delt[1] = ( 2 + (scaled_width) * 0 );
  piece[10].orient[1].delt[2] = ( 3 + (scaled_width) * 0 );
  piece[10].orient[1].delt[3] = ( 1 + (scaled_width) * 1 );
  piece[10].orient[1].maxforward = 4;

  piece[10].orient[2].delt[0] = (-1 + (scaled_width) * 1 );
  piece[10].orient[2].delt[1] = ( 0 + (scaled_width) * 1 );
  piece[10].orient[2].delt[2] = ( 2 + (scaled_width) * 1 );
  piece[10].orient[2].delt[3] = ( 1 + (scaled_width) * 1 );
  piece[10].orient[2].maxforward = 1;

  piece[10].orient[3].delt[0] = (-2 + (scaled_width) * 1 );
  piece[10].orient[3].delt[1] = (-1 + (scaled_width) * 1 );
  piece[10].orient[3].delt[2] = ( 0 + (scaled_width) * 1 );
  piece[10].orient[3].delt[3] = ( 1 + (scaled_width) * 1 );
  piece[10].orient[3].maxforward = 1;

  piece[10].orient[4].delt[0] = ( 0 + (scaled_width) * 1 );
  piece[10].orient[4].delt[1] = ( 0 + (scaled_width) * 2 );
  piece[10].orient[4].delt[2] = ( 0 + (scaled_width) * 3 );
  piece[10].orient[4].delt[3] = ( 1 + (scaled_width) * 2 );
  piece[10].orient[4].maxforward = 1;

  piece[10].orient[5].delt[0] = ( 0 + (scaled_width) * 1 );
  piece[10].orient[5].delt[1] = ( 0 + (scaled_width) * 2 );
  piece[10].orient[5].delt[2] = ( 0 + (scaled_width) * 3 );
  piece[10].orient[5].delt[3] = ( 1 + (scaled_width) * 1 );
  piece[10].orient[5].maxforward = 1;

  piece[10].orient[6].delt[0] = ( 0 + (scaled_width) * 1 );
  piece[10].orient[6].delt[1] = ( 0 + (scaled_width) * 2 );
  piece[10].orient[6].delt[2] = ( 0 + (scaled_width) * 3 );
  piece[10].orient[6].delt[3] = ( -1 + (scaled_width) * 1 );
  piece[10].orient[6].maxforward = 1;

  piece[10].orient[7].delt[0] = ( 0 + (scaled_width) * 1 );
  piece[10].orient[7].delt[1] = ( 0 + (scaled_width) * 2 );
  piece[10].orient[7].delt[2] = ( 0 + (scaled_width) * 3 );
  piece[10].orient[7].delt[3] = ( -1 + (scaled_width) * 2 );
  piece[10].orient[7].maxforward = 1;

  if (height > 3)
    num_orientations [11] = 8;
  else
    num_orientations [11] = 4;

  piece[11].orient[0].delt[0] = ( 1 + (scaled_width) * 0 );
  piece[11].orient[0].delt[1] = ( 2 + (scaled_width) * 0 );
  piece[11].orient[0].delt[2] = ( 3 + (scaled_width) * 0 );
  piece[11].orient[0].delt[3] = ( 3 + (scaled_width) * 1 );
  piece[11].orient[0].maxforward = 4;

  piece[11].orient[1].delt[0] = ( 1 + (scaled_width) * 0 );
  piece[11].orient[1].delt[1] = ( 2 + (scaled_width) * 0 );
  piece[11].orient[1].delt[2] = ( 3 + (scaled_width) * 0 );
  piece[11].orient[1].delt[3] = ( 0 + (scaled_width) * 1 );
  piece[11].orient[1].maxforward = 4;

  piece[11].orient[2].delt[0] = ( 1 + (scaled_width) * 1 );
  piece[11].orient[2].delt[1] = ( 2 + (scaled_width) * 1 );
  piece[11].orient[2].delt[2] = ( 3 + (scaled_width) * 1 );
  piece[11].orient[2].delt[3] = ( 0 + (scaled_width) * 1 );
  piece[11].orient[2].maxforward = 1;

  piece[11].orient[3].delt[0] = ( 0 + (scaled_width) * 1 );
  piece[11].orient[3].delt[1] = (-1 + (scaled_width) * 1 );
  piece[11].orient[3].delt[2] = (-2 + (scaled_width) * 1 );
  piece[11].orient[3].delt[3] = (-3 + (scaled_width) * 1 );
  piece[11].orient[3].maxforward = 1;

  piece[11].orient[4].delt[0] = ( 0 + (scaled_width) * 1 );
  piece[11].orient[4].delt[1] = ( 0 + (scaled_width) * 2 );
  piece[11].orient[4].delt[2] = ( 0 + (scaled_width) * 3 );
  piece[11].orient[4].delt[3] = ( 1 + (scaled_width) * 3 );
  piece[11].orient[4].maxforward = 1;

  piece[11].orient[5].delt[0] = ( 0 + (scaled_width) * 1 );
  piece[11].orient[5].delt[1] = ( 0 + (scaled_width) * 2 );
  piece[11].orient[5].delt[2] = ( 0 + (scaled_width) * 3 );
  piece[11].orient[5].delt[3] = ( 1 + (scaled_width) * 0 );
  piece[11].orient[5].maxforward = 2;

  piece[11].orient[6].delt[0] = ( 1 + (scaled_width) * 1 );
  piece[11].orient[6].delt[1] = ( 1 + (scaled_width) * 2 );
  piece[11].orient[6].delt[2] = ( 1 + (scaled_width) * 3 );
  piece[11].orient[6].delt[3] = ( 1 + (scaled_width) * 0 );
  piece[11].orient[6].maxforward = 2;

  piece[11].orient[7].delt[0] = ( 0 + (scaled_width) * 1 );
  piece[11].orient[7].delt[1] = ( 0 + (scaled_width) * 2 );
  piece[11].orient[7].delt[2] = ( 0 + (scaled_width) * 3 );
  piece[11].orient[7].delt[3] = ( -1 + (scaled_width) * 3 );
  piece[11].orient[7].maxforward = 1;
}

enum x86_registers {
  EAX, ECX, EDX, EBX, ESP, EBP, ESI, EDI
} REGISTER;

enum x86_modrm_modes {
  DISPLACEMENT_NONE,
  DISPLACEMENT_8,
  DISPLACEMENT_32,
  DIRECT
} MODE;

static inline int modRM(int mode, int sub_mode, int reg)
{
  return((mode * 0x040) + (sub_mode * 8) + reg);
}

static inline int sib(int v, int regA, int regB)
{
  return((v * 0x40) + (regA * 8) + regB);
}

static inline int fitsInByte(int i) {
  if (i < 0)
    return(i > -127);
  else
    return(i < 128);
}

static inline void put_i4(void * pointer, int x) {
  *((int *) pointer) = x;
}

static inline void put_i1(void * pointer, int x) {
  assert ((x < 128) && (x > -127));
  *((char *) pointer) = x;
}

static inline void loadstoreDisp(char ** code_pointer, int regA, int disp,
				 int regB, int opcode)
{
  char * pointer = *code_pointer;
  int mode;

  *pointer++ = opcode;

  if (disp == 0)
    mode = DISPLACEMENT_NONE;
  else if (fitsInByte(disp))
    mode = DISPLACEMENT_8;
  else
    mode = DISPLACEMENT_32;

  if (regB == -1)
    *pointer++ = modRM(DISPLACEMENT_NONE, regA, EBP);
  else
    *pointer++ = modRM(mode, regA, regB);

  if (regB == ESP) /* sp requires scaled mode */
    *pointer++ = sib(0, ESP, ESP);

  if (mode == DISPLACEMENT_8) {
    *pointer++ = (disp) & 0xff;
  } else if (disp != 0) {
    put_i4(pointer, disp);
    pointer += 4;
  }
  *code_pointer = pointer;
}

static inline void alu_op_reg(char ** code_pointer, int regA, int regB,
			      int opcode)
{
  char * pointer = *code_pointer;
  *pointer++ = opcode;
  *pointer++ = modRM(DIRECT, regB, regA);
  *code_pointer = pointer;
}

static inline void alu_op(char ** code_pointer, int reg, int imm,
			  int eax_code, int code_8, int code_32, int digit)
{
  char * pointer = *code_pointer;

  if (fitsInByte (imm)) {
    *pointer++ = code_8;
    *pointer++ = modRM(DIRECT, digit, reg);
    *pointer++ = imm;
  } else {
    if (reg == EAX)
      *pointer++ = eax_code;
    else {
      *pointer++ = code_32;
      *pointer++ = modRM(DIRECT, digit, reg);
    }

    put_i4(pointer, imm);
    pointer += 4;
  }

  *code_pointer = pointer;
}

static inline void INC(char ** code_pointer, int reg) {
  char * pointer = *code_pointer;
  *pointer++ = 0xFF;
  *pointer++ = modRM(DIRECT, 0, reg);
  *code_pointer = pointer;
}

static inline void ORi(char ** code_pointer, int reg, int val) {
  alu_op(code_pointer, reg, val, 0x0D, 0x83, 0x81, 1);
}

static inline void ORWdisp(char ** code_pointer, int regA, int offset,
			   int regB)
{
  loadstoreDisp(code_pointer, regA, offset, regB, 0x0B);
}

static inline void XORi(char ** code_pointer, int reg, int val) {
  alu_op(code_pointer, reg, val, 0x35, 0x83, 0x81, 6);
}

static inline void CMPi(char ** code_pointer, int reg, int val) {
  alu_op(code_pointer, reg, val, 0x3D, 0x83, 0x81, 7);
}

static inline void TESTi(char ** code_pointer, int reg, int val) {
  alu_op(code_pointer, reg, val, 0xA9, 0xF6, 0xF7, 0);
}

static inline void ADDi(char ** code_pointer, int reg, int val) {
  alu_op(code_pointer, reg, val, 0x05, 0x83, 0x81, 0);
}

static inline void XOR(char ** code_pointer, int regA, int regB) {
  alu_op_reg(code_pointer, regA, regB, 0x33);
}

static inline void TEST(char ** code_pointer, int regA, int regB) {
  alu_op_reg(code_pointer, regA, regB, 0x85);
}

static inline void MOVi(char ** code_pointer, int reg_code, int value) {
  char * pointer = *code_pointer;
  *pointer++ = 0xB8 + reg_code;
  put_i4(pointer, value);
  pointer += 4;
  *code_pointer = pointer;
}

static inline void LOADdisp(char ** code_pointer, int regA,
			    int displacement, int regB)
{
  loadstoreDisp(code_pointer, regA, displacement, regB, 0x8B);
}

static inline void STOREdisp(char ** code_pointer, int regA,
			     int displacement, int regB)
{
  loadstoreDisp(code_pointer, regA, displacement, regB, 0x89);
}

static inline void PUSH(char ** code_pointer, int reg_code) {
  char * pointer = *code_pointer;
  *pointer = (char) (0x50 + reg_code);
  *code_pointer = *code_pointer + 1;
}

static inline void POP(char ** code_pointer, int reg_code) {
  char * pointer = *code_pointer;
  *pointer++ = (char) (0x58 + reg_code);
  *code_pointer = pointer;
}

/**
 * call relative, immediate displacement
 */
static inline void CALLi(char ** code_pointer, char * dest) {
  char * pointer = *code_pointer;
  char * next_instr = pointer + 5;
  *pointer++ = 0xE8;
  put_i4(pointer, dest - next_instr);
  pointer += 4;
  *code_pointer = pointer;
}

static inline void JMPi(char ** code_pointer, int address) {
  char * pointer = *code_pointer;
  *pointer++ = 0xE9;
  put_i4(pointer, address);
  pointer += 4;
  *code_pointer = pointer;
}

static inline void JNE8(char ** code_pointer, char offset) {
  char * pointer = *code_pointer;
  *pointer++ = 0x75;
  *pointer++ = offset;
  *code_pointer = pointer;
}

static inline void JNE32(char ** code_pointer, int offset) {
  char * pointer = *code_pointer;
  *pointer++ = 0x0F;
  *pointer++ = 0x85;
  put_i4(pointer, offset);
  pointer += 4;
  *code_pointer = pointer;
}

static inline void RET(char ** code_pointer) {
  char * pointer = *code_pointer;
  *pointer++ = 0xC3;
  *code_pointer = pointer;
}

#define CODESIZE (2048)

#include <stdlib.h>

typedef void (*PFV)();

PFV    placements[12];

static
void
genCode(int timer, char * code_array[], int piece_index, char pieceCode,
	int orientations, PIECEDEF * pieceInfo)
{
  char   * code = code_array[piece_index];
  char   * return_addr = code;
  int    i;

  /* construct a piece-placing routine, for the piece numbered "piece_index",
     with description stored at "pieceInfo"
  */

  PUSH(&code, ESI);                /* save the start location */
  INC(&code, ECX);                 /* increment nesting count */

  /* mark this piece as in use.  it just has to be nonzero */
  ORi(&code, EBX, 1 << piece_index);

  /* seek a place to try the next piece */
  ADDi(&code, ESI, 4);
  LOADdisp(&code, EAX, 0, ESI);
  TEST(&code, EAX, EAX);
  JNE8(&code, -9);

  for (i = 0; i < orientations; i++) {
      char * branch_location = NULL, * brancharound_print = NULL,
	* branchfrom_print = NULL;
      int  j;

      /* first, find out if all five squares used by this piece
	 are empty.  Do this by "or"ing together the contents of
	 each candidate location, then test the result.  We already
	 know that the current (ESI) square is empty.
      */
      LOADdisp(&code, EDX, pieceInfo -> orient[i].delt[0] * 4, ESI);
      ORWdisp(&code, EDX, pieceInfo -> orient[i].delt[1] * 4, ESI);
      ORWdisp(&code, EDX, pieceInfo -> orient[i].delt[2] * 4, ESI);
      ORWdisp(&code, EDX, pieceInfo -> orient[i].delt[3] * 4, ESI);
      TEST(&code, EDX, EDX);
      JNE32(&code, 0);
      branch_location = code - 4;

      /* get the code for this piece, and put it into each square
	 that is occupied for this piece
      */
      MOVi(&code, EAX, pieceCode);

      /* test to see if this is the last piece.  condition code is checked
	 later.
      */
      CMPi(&code, ECX, 12);

      /* mark the squares in the table as occupied by this piece */
      STOREdisp(&code, EAX, 0, ESI);
      STOREdisp(&code, EAX, pieceInfo -> orient[i].delt[0] * 4, ESI);
      STOREdisp(&code, EAX, pieceInfo -> orient[i].delt[1] * 4, ESI);
      STOREdisp(&code, EAX, pieceInfo -> orient[i].delt[2] * 4, ESI);
      STOREdisp(&code, EAX, pieceInfo -> orient[i].delt[3] * 4, ESI);

      if (timer == 0) {
	/* if this is the last piece, then print the table */
	JNE8(&code, 0);    brancharound_print = code - 1;

	/* print out the map, and don't try to put further pieces into map */
	PUSH(&code, ECX);
	CALLi(&code, (char *) print_table);
	POP(&code, ECX);
	MOVi(&code, EAX, 0);
	JMPi(&code, 0);       branchfrom_print = code - 4;

	put_i1(brancharound_print, (code - brancharound_print) - 1);
      }

      /* check all other pieces.  If they haven't been placed yet,
	 try them!
      */

      for (j = 0; j < 12; j++)
	if (j != piece_index) {
	  char * branch_source;

	  TESTi(&code, EBX, 1 << j);
	  JNE8(&code, 0);     branch_source = code - 1;
	  CALLi(&code, code_array[j]);
	  put_i1(branch_source, (code - branch_source) - 1);
	}

      if (timer == 0)
	put_i4(branchfrom_print, (code - branchfrom_print) - 4);

      /* remove the piece we have just placed. EAX has a zero  */
      STOREdisp(&code, EAX, pieceInfo -> orient[i].delt[0] * 4, ESI);
      STOREdisp(&code, EAX, pieceInfo -> orient[i].delt[1] * 4, ESI);
      STOREdisp(&code, EAX, pieceInfo -> orient[i].delt[2] * 4, ESI);
      STOREdisp(&code, EAX, pieceInfo -> orient[i].delt[3] * 4, ESI);

      put_i4(branch_location, (code - branch_location) - 4);
  }

  /* mark the start square as now empty */
  STOREdisp(&code, EAX, 0, ESI);

  /* mark this piece as free */
  XORi(&code, EBX, 1 << piece_index);

  ADDi(&code, ECX, -1);
  POP(&code, ESI);
  RET(&code);

  assert(code < return_addr + CODESIZE);
  printf("Code size is %d\n", code - return_addr);
}

int
main(int argc, char * argv[]) {
  int    i, j;
  PFV    start_search;
  char   * code;
  int    timer = 0;
  int    clockLow, clockHigh;

  width = 12;

  // parse out options
  for (i = 1; i < argc; i++) {
    char * arg = argv[i];

    if (strcmp("-timer", arg) == 0)
      timer = 1;
    else if (strcmp("-width", arg) == 0) {
      if (i < (argc + 1)) {
	i++;
	width = atoi(argv[i]);
      }
    }
  }

  if ((width < 3) || (width > 20)) {
    printf("Width must be > 2 and < 21\n");
    exit(1);
  }

  height = 60 / width;
  scaled_width = width + 1;

  initpieces();

  for (i = 0; i < 12; i++)
    placements[i] = malloc(CODESIZE);

  for (i = 0; i < 12; i++) {
    genCode(timer, (char **) placements, i, i + 1,
	    num_orientations[i], &(piece[i]));
  }

  for (i = 0; i < width; i++)
    for (j = 0; j < height; j++)
      table[map_to_linear(i, j)] = 0;

  for (j = 0; j <= height; j++)
    table[map_to_linear(width, j)] = -1;

  for (j = 0; j <= width; j++)
    table[map_to_linear(j, height)] = -1;

  code = malloc(512);
  start_search = (PFV) code;

  PUSH(&code, EBX);       /* save register */
  XOR(&code, EBX, EBX);   /* ebx contains flags describing which pieces
			     are currently used */
  XOR(&code, ECX, ECX);   /* piece count */
  PUSH(&code, ECX);

  // start the search one position BEFORE the start of the table.  This is
  // because the search routines assume that the current position is where
  // the last piece was placed.  The search routines start by incrementing to
  // the next possible search point.
  MOVi(&code, ESI, (int) &(table[-1]));

  for (i = 0; i < 12; i ++)
    CALLi(&code, (char *) placements[i]);

  ADDi(&code, ESP, 4);
  POP(&code, EBX);
  RET(&code);

  __asm__ __volatile__("rdtsc" : "=a" (clockLow), "=d" (clockHigh));

  (* start_search)();

  if (timer) {
    int newClockLow, newClockHigh;
    unsigned long long old, new, tmpl, tmph;

    __asm__ __volatile__("rdtsc" : "=a" (newClockLow), "=d" (newClockHigh));
    tmpl = clockLow;
    tmph = clockHigh;
    old = tmph << 32 | tmpl;
    tmpl = newClockLow;
    tmph = newClockHigh;
    new = tmph << 32 | tmpl;
    printf("Elapsed ticks: %llu\n", new - old);
  }

  return(0);
}