/* glpuzzle - written by Kevin Smith (kpsmith@engr.sgi.com) */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <time.h>
#include <math.h>
#include <GL/glut.h>
#include "trackball.h"

#define WIDTH 4
#define HEIGHT 5
#define PIECES 10
#define OFFSETX -2
#define OFFSETY -2.5
#define OFFSETZ -0.5

typedef unsigned char Config[HEIGHT][WIDTH];

struct puzzle {
  struct puzzle *backptr;
  struct puzzle *solnptr;
  Config pieces;
  struct puzzle *next;
  unsigned hashvalue;
};

#define HASHSIZE 10691

struct puzzlelist {
  struct puzzle *puzzle;
  struct puzzlelist *next;
};

static char convert[PIECES + 1] =
{0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 4};

static unsigned char colors[PIECES + 1][3] =
{
  {0, 0, 0},
  {255, 255, 127},
  {255, 255, 127},
  {255, 255, 127},
  {255, 255, 127},
  {255, 127, 255},
  {255, 127, 255},
  {255, 127, 255},
  {255, 127, 255},
  {255, 127, 127},
  {255, 255, 255},
};

void changeState(void);

static struct puzzle *hashtable[HASHSIZE];
static struct puzzle *startPuzzle;
static struct puzzlelist *puzzles;
static struct puzzlelist *lastentry;

int curX, curY, visible;

#define MOVE_SPEED 0.2
static unsigned char movingPiece;
static float move_x, move_y;
static float curquat[4];
static int doubleBuffer = 1;
static int depth = 1;

static char xsize[PIECES + 1] =
{0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2};
static char ysize[PIECES + 1] =
{0, 1, 1, 1, 1, 2, 2, 2, 2, 1, 2};
static float zsize[PIECES + 1] =
{0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0.6};

static Config startConfig =
{
  {8, 10, 10, 7},
  {8, 10, 10, 7},
  {6, 9, 9, 5},
  {6, 4, 3, 5},
  {2, 0, 0, 1}
};

static Config thePuzzle =
{
  {8, 10, 10, 7},
  {8, 10, 10, 7},
  {6, 9, 9, 5},
  {6, 4, 3, 5},
  {2, 0, 0, 1}
};

static int xadds[4] =
{-1, 0, 1, 0};
static int yadds[4] =
{0, -1, 0, 1};

static int W = 400, H = 300;
static GLint viewport[4];

#define srandom srand
#define random() (rand() >> 2)

unsigned
hash(Config config)
{
  int i, j, value;

  value = 0;
  for (i = 0; i < HEIGHT; i++) {
    for (j = 0; j < WIDTH; j++) {
      value = value + convert[config[i][j]];
      value *= 6;
    }
  }
  return (value);
}

int
solution(Config config)
{
  if (config[4][1] == 10 && config[4][2] == 10)
    return (1);
  return (0);
}

float boxcoords[][3] =
{
  {0.2, 0.2, 0.9},
  {0.8, 0.2, 0.9},
  {0.8, 0.8, 0.9},
  {0.2, 0.8, 0.9},
  {0.2, 0.1, 0.8},
  {0.8, 0.1, 0.8},
  {0.9, 0.2, 0.8},
  {0.9, 0.8, 0.8},
  {0.8, 0.9, 0.8},
  {0.2, 0.9, 0.8},
  {0.1, 0.8, 0.8},
  {0.1, 0.2, 0.8},
  {0.2, 0.1, 0.2},
  {0.8, 0.1, 0.2},
  {0.9, 0.2, 0.2},
  {0.9, 0.8, 0.2},
  {0.8, 0.9, 0.2},
  {0.2, 0.9, 0.2},
  {0.1, 0.8, 0.2},
  {0.1, 0.2, 0.2},
  {0.2, 0.2, 0.1},
  {0.8, 0.2, 0.1},
  {0.8, 0.8, 0.1},
  {0.2, 0.8, 0.1},
};

float boxnormals[][3] =
{
  {0, 0, 1},            /* 0 */
  {0, 1, 0},
  {1, 0, 0},
  {0, 0, -1},
  {0, -1, 0},
  {-1, 0, 0},
  {0.7071, 0.7071, 0.0000},  /* 6 */
  {0.7071, -0.7071, 0.0000},
  {-0.7071, 0.7071, 0.0000},
  {-0.7071, -0.7071, 0.0000},
  {0.7071, 0.0000, 0.7071},  /* 10 */
  {0.7071, 0.0000, -0.7071},
  {-0.7071, 0.0000, 0.7071},
  {-0.7071, 0.0000, -0.7071},
  {0.0000, 0.7071, 0.7071},  /* 14 */
  {0.0000, 0.7071, -0.7071},
  {0.0000, -0.7071, 0.7071},
  {0.0000, -0.7071, -0.7071},
  {0.5774, 0.5774, 0.5774},  /* 18 */
  {0.5774, 0.5774, -0.5774},
  {0.5774, -0.5774, 0.5774},
  {0.5774, -0.5774, -0.5774},
  {-0.5774, 0.5774, 0.5774},
  {-0.5774, 0.5774, -0.5774},
  {-0.5774, -0.5774, 0.5774},
  {-0.5774, -0.5774, -0.5774},
};

int boxfaces[][4] =
{
  {0, 1, 2, 3},         /* 0 */
  {9, 8, 16, 17},
  {6, 14, 15, 7},
  {20, 23, 22, 21},
  {12, 13, 5, 4},
  {19, 11, 10, 18},
  {7, 15, 16, 8},       /* 6 */
  {13, 14, 6, 5},
  {18, 10, 9, 17},
  {19, 12, 4, 11},
  {1, 6, 7, 2},         /* 10 */
  {14, 21, 22, 15},
  {11, 0, 3, 10},
  {20, 19, 18, 23},
  {3, 2, 8, 9},         /* 14 */
  {17, 16, 22, 23},
  {4, 5, 1, 0},
  {20, 21, 13, 12},
  {2, 7, 8, -1},        /* 18 */
  {16, 15, 22, -1},
  {5, 6, 1, -1},
  {13, 21, 14, -1},
  {10, 3, 9, -1},
  {18, 17, 23, -1},
  {11, 4, 0, -1},
  {20, 12, 19, -1},
};

#define NBOXFACES (sizeof(boxfaces)/sizeof(boxfaces[0]))

/* Draw a box.  Bevel as desired. */
void
drawBox(int piece, float xoff, float yoff)
{
  int xlen, ylen;
  int i, k;
  float x, y, z;
  float zlen;
  float *v;

  xlen = xsize[piece];
  ylen = ysize[piece];
  zlen = zsize[piece];

  glColor3ubv(colors[piece]);
  glBegin(GL_QUADS);
  for (i = 0; i < 18; i++) {
    glNormal3fv(boxnormals[i]);
    for (k = 0; k < 4; k++) {
      if (boxfaces[i][k] == -1)
        continue;
      v = boxcoords[boxfaces[i][k]];
      x = v[0] + OFFSETX;
      if (v[0] > 0.5)
        x += xlen - 1;
      y = v[1] + OFFSETY;
      if (v[1] > 0.5)
        y += ylen - 1;
      z = v[2] + OFFSETZ;
      if (v[2] > 0.5)
        z += zlen - 1;
      glVertex3f(xoff + x, yoff + y, z);
    }
  }
  glEnd();
  glBegin(GL_TRIANGLES);
  for (i = 18; i < NBOXFACES; i++) {
    glNormal3fv(boxnormals[i]);
    for (k = 0; k < 3; k++) {
      if (boxfaces[i][k] == -1)
        continue;
      v = boxcoords[boxfaces[i][k]];
      x = v[0] + OFFSETX;
      if (v[0] > 0.5)
        x += xlen - 1;
      y = v[1] + OFFSETY;
      if (v[1] > 0.5)
        y += ylen - 1;
      z = v[2] + OFFSETZ;
      if (v[2] > 0.5)
        z += zlen - 1;
      glVertex3f(xoff + x, yoff + y, z);
    }
  }
  glEnd();
}

float containercoords[][3] =
{
  {-0.1, -0.1, 1.0},
  {-0.1, -0.1, -0.1},
  {4.1, -0.1, -0.1},
  {4.1, -0.1, 1.0},
  {1.0, -0.1, 0.6},     /* 4 */
  {3.0, -0.1, 0.6},
  {1.0, -0.1, 0.0},
  {3.0, -0.1, 0.0},
  {1.0, 0.0, 0.0},      /* 8 */
  {3.0, 0.0, 0.0},
  {3.0, 0.0, 0.6},
  {1.0, 0.0, 0.6},
  {0.0, 0.0, 1.0},      /* 12 */
  {4.0, 0.0, 1.0},
  {4.0, 0.0, 0.0},
  {0.0, 0.0, 0.0},
  {0.0, 5.0, 0.0},      /* 16 */
  {0.0, 5.0, 1.0},
  {4.0, 5.0, 1.0},
  {4.0, 5.0, 0.0},
  {-0.1, 5.1, -0.1},    /* 20 */
  {4.1, 5.1, -0.1},
  {4.1, 5.1, 1.0},
  {-0.1, 5.1, 1.0},
};

float containernormals[][3] =
{
  {0, -1, 0},
  {0, -1, 0},
  {0, -1, 0},
  {0, -1, 0},
  {0, -1, 0},
  {0, 1, 0},
  {0, 1, 0},
  {0, 1, 0},
  {1, 0, 0},
  {1, 0, 0},
  {1, 0, 0},
  {-1, 0, 0},
  {-1, 0, 0},
  {-1, 0, 0},
  {0, 1, 0},
  {0, 0, -1},
  {0, 0, -1},
  {0, 0, 1},
  {0, 0, 1},
  {0, 0, 1},
  {0, 0, 1},
  {0, 0, 1},
  {0, 0, 1},
  {0, 0, 1},
};

int containerfaces[][4] =
{
  {1, 6, 4, 0},
  {0, 4, 5, 3},
  {1, 2, 7, 6},
  {7, 2, 3, 5},
  {16, 19, 18, 17},

  {23, 22, 21, 20},
  {12, 11, 8, 15},
  {10, 13, 14, 9},

  {15, 16, 17, 12},
  {2, 21, 22, 3},
  {6, 8, 11, 4},

  {1, 0, 23, 20},
  {14, 13, 18, 19},
  {9, 7, 5, 10},

  {12, 13, 10, 11},

  {1, 20, 21, 2},
  {4, 11, 10, 5},

  {15, 8, 19, 16},
  {19, 8, 9, 14},
  {8, 6, 7, 9},
  {0, 3, 13, 12},
  {13, 3, 22, 18},
  {18, 22, 23, 17},
  {17, 23, 0, 12},
};

#define NCONTFACES (sizeof(containerfaces)/sizeof(containerfaces[0]))

/* Draw the container */
void
drawContainer(void)
{
  int i, k;
  float *v;

  /* Y is reversed here because the model has it reversed */

  /* Arbitrary bright wood-like color */
  glColor3ub(209, 103, 23);
  glBegin(GL_QUADS);
  for (i = 0; i < NCONTFACES; i++) {
    v = containernormals[i];
    glNormal3f(v[0], -v[1], v[2]);
    for (k = 3; k >= 0; k--) {
      v = containercoords[containerfaces[i][k]];
      glVertex3f(v[0] + OFFSETX, -(v[1] + OFFSETY), v[2] + OFFSETZ);
    }
  }
  glEnd();
}

void
drawAll(void)
{
  int i, j;
  int piece;
  char done[PIECES + 1];
  float m[4][4];

  build_rotmatrix(m, curquat);
  glMatrixMode(GL_MODELVIEW);
  glLoadIdentity();
  glTranslatef(0, 0, -10);
  glMultMatrixf(&(m[0][0]));
  glRotatef(180, 0, 0, 1);

  if (depth) {
    glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
  } else {
    glClear(GL_COLOR_BUFFER_BIT);
  }
  for (i = 1; i <= PIECES; i++) {
    done[i] = 0;
  }
  glLoadName(0);
  drawContainer();
  for (i = 0; i < HEIGHT; i++) {
    for (j = 0; j < WIDTH; j++) {
      piece = thePuzzle[i][j];
      if (piece == 0)
        continue;
      if (done[piece])
        continue;
      done[piece] = 1;
      glLoadName(piece);
      if (piece == movingPiece) {
        drawBox(piece, move_x, move_y);
      } else {
        drawBox(piece, j, i);
      }
    }
  }
}

void
redraw(void)
{
  glMatrixMode(GL_PROJECTION);
  glLoadIdentity();
  gluPerspective(45, 1.0, 0.1, 100.0);

  drawAll();

  if (doubleBuffer)
    glutSwapBuffers();
  else
    glFinish();
}

void
solidifyChain(struct puzzle *puzzle)
{
  int i;
  char buf[256];

  i = 0;
  while (puzzle->backptr) {
    i++;
    puzzle->backptr->solnptr = puzzle;
    puzzle = puzzle->backptr;
  }
  sprintf(buf, "%d moves to complete!", i);
  glutSetWindowTitle(buf);
}

int
addConfig(Config config, struct puzzle *back)
{
  unsigned hashvalue;
  struct puzzle *newpiece;
  struct puzzlelist *newlistentry;

  hashvalue = hash(config);

  newpiece = hashtable[hashvalue % HASHSIZE];
  while (newpiece != NULL) {
    if (newpiece->hashvalue == hashvalue) {
      int i, j;

      for (i = 0; i < WIDTH; i++) {
        for (j = 0; j < HEIGHT; j++) {
          if (convert[config[j][i]] !=
            convert[newpiece->pieces[j][i]])
            goto nomatch;
        }
      }
      return 0;
    }
  nomatch:
    newpiece = newpiece->next;
  }

  newpiece = (struct puzzle *) malloc(sizeof(struct puzzle));
  newpiece->next = hashtable[hashvalue % HASHSIZE];
  newpiece->hashvalue = hashvalue;
  memcpy(newpiece->pieces, config, HEIGHT * WIDTH);
  newpiece->backptr = back;
  newpiece->solnptr = NULL;
  hashtable[hashvalue % HASHSIZE] = newpiece;

  newlistentry = (struct puzzlelist *) malloc(sizeof(struct puzzlelist));
  newlistentry->puzzle = newpiece;
  newlistentry->next = NULL;

  if (lastentry) {
    lastentry->next = newlistentry;
  } else {
    puzzles = newlistentry;
  }
  lastentry = newlistentry;

  if (back == NULL) {
    startPuzzle = newpiece;
  }
  if (solution(config)) {
    solidifyChain(newpiece);
    return 1;
  }
  return 0;
}

/* Checks if a space can move */
int
canmove0(Config pieces, int x, int y, int dir, Config newpieces)
{
  char piece;
  int xadd, yadd;
  int l, m;

  xadd = xadds[dir];
  yadd = yadds[dir];

  if (x + xadd < 0 || x + xadd >= WIDTH ||
    y + yadd < 0 || y + yadd >= HEIGHT)
    return 0;
  piece = pieces[y + yadd][x + xadd];
  if (piece == 0)
    return 0;
  memcpy(newpieces, pieces, HEIGHT * WIDTH);
  for (l = 0; l < WIDTH; l++) {
    for (m = 0; m < HEIGHT; m++) {
      if (newpieces[m][l] == piece)
        newpieces[m][l] = 0;
    }
  }
  xadd = -xadd;
  yadd = -yadd;
  for (l = 0; l < WIDTH; l++) {
    for (m = 0; m < HEIGHT; m++) {
      if (pieces[m][l] == piece) {
        int newx, newy;

        newx = l + xadd;
        newy = m + yadd;
        if (newx < 0 || newx >= WIDTH ||
          newy < 0 || newy >= HEIGHT)
          return 0;
        if (newpieces[newy][newx] != 0)
          return 0;
        newpieces[newy][newx] = piece;
      }
    }
  }
  return 1;
}

/* Checks if a piece can move */
int
canmove(Config pieces, int x, int y, int dir, Config newpieces)
{
  int xadd, yadd;

  xadd = xadds[dir];
  yadd = yadds[dir];

  if (x + xadd < 0 || x + xadd >= WIDTH ||
    y + yadd < 0 || y + yadd >= HEIGHT)
    return 0;
  if (pieces[y + yadd][x + xadd] == pieces[y][x]) {
    return canmove(pieces, x + xadd, y + yadd, dir, newpieces);
  }
  if (pieces[y + yadd][x + xadd] != 0)
    return 0;
  return canmove0(pieces, x + xadd, y + yadd, (dir + 2) % 4, newpieces);
}

int
generateNewConfigs(struct puzzle *puzzle)
{
  int i, j, k;
  Config pieces;
  Config newpieces;

  memcpy(pieces, puzzle->pieces, HEIGHT * WIDTH);
  for (i = 0; i < WIDTH; i++) {
    for (j = 0; j < HEIGHT; j++) {
      if (pieces[j][i] == 0) {
        for (k = 0; k < 4; k++) {
          if (canmove0(pieces, i, j, k, newpieces)) {
            if (addConfig(newpieces, puzzle))
              return 1;
          }
        }
      }
    }
  }
  return 0;
}

void
freeSolutions(void)
{
  struct puzzlelist *nextpuz;
  struct puzzle *puzzle, *next;
  int i;

  while (puzzles) {
    nextpuz = puzzles->next;
    free((char *) puzzles);
    puzzles = nextpuz;
  }
  lastentry = NULL;
  for (i = 0; i < HASHSIZE; i++) {
    puzzle = hashtable[i];
    hashtable[i] = NULL;
    while (puzzle) {
      next = puzzle->next;
      free((char *) puzzle);
      puzzle = next;
    }
  }
  startPuzzle = NULL;
}

int
continueSolving(void)
{
  struct puzzle *nextpuz;
  int i, j;
  int movedPiece;
  int movedir;
  int fromx, fromy;
  int tox, toy;

  if (startPuzzle == NULL)
    return 0;
  if (startPuzzle->solnptr == NULL) {
    freeSolutions();
    return 0;
  }
  nextpuz = startPuzzle->solnptr;
  movedPiece = 0;
  movedir = 0;
  for (i = 0; i < HEIGHT; i++) {
    for (j = 0; j < WIDTH; j++) {
      if (startPuzzle->pieces[i][j] != nextpuz->pieces[i][j]) {
        if (startPuzzle->pieces[i][j]) {
          movedPiece = startPuzzle->pieces[i][j];
          fromx = j;
          fromy = i;
          if (i < HEIGHT - 1 && nextpuz->pieces[i + 1][j] == movedPiece) {
            movedir = 3;
          } else {
            movedir = 2;
          }
          goto found_piece;
        } else {
          movedPiece = nextpuz->pieces[i][j];
          if (i < HEIGHT - 1 &&
            startPuzzle->pieces[i + 1][j] == movedPiece) {
            fromx = j;
            fromy = i + 1;
            movedir = 1;
          } else {
            fromx = j + 1;
            fromy = i;
            movedir = 0;
          }
          goto found_piece;
        }
      }
    }
  }
  glutSetWindowTitle("What!  No change?");
  freeSolutions();
  return 0;

found_piece:
  if (!movingPiece) {
    movingPiece = movedPiece;
    move_x = fromx;
    move_y = fromy;
  }
  move_x += xadds[movedir] * MOVE_SPEED;
  move_y += yadds[movedir] * MOVE_SPEED;

  tox = fromx + xadds[movedir];
  toy = fromy + yadds[movedir];

  if (move_x > tox - MOVE_SPEED / 2 && move_x < tox + MOVE_SPEED / 2 &&
    move_y > toy - MOVE_SPEED / 2 && move_y < toy + MOVE_SPEED / 2) {
    startPuzzle = nextpuz;
    movingPiece = 0;
  }
  memcpy(thePuzzle, startPuzzle->pieces, HEIGHT * WIDTH);
  changeState();
  return 1;
}

int
solvePuzzle(void)
{
  struct puzzlelist *nextpuz;
  char buf[256];
  int i;

  if (solution(thePuzzle)) {
    glutSetWindowTitle("Puzzle already solved!");
    return 0;
  }
  addConfig(thePuzzle, NULL);
  i = 0;

  while (puzzles) {
    i++;
    if (generateNewConfigs(puzzles->puzzle))
      break;
    nextpuz = puzzles->next;
    free((char *) puzzles);
    puzzles = nextpuz;
  }
  if (puzzles == NULL) {
    freeSolutions();
    sprintf(buf, "I can't solve it! (%d positions examined)", i);
    glutSetWindowTitle(buf);
    return 1;
  }
  return 1;
}

int
selectPiece(int mousex, int mousey)
{
  long hits;
  GLuint selectBuf[1024];
  GLuint closest;
  GLuint dist;

  glSelectBuffer(1024, selectBuf);
  (void) glRenderMode(GL_SELECT);
  glInitNames();

  /* Because LoadName() won't work with no names on the stack */
  glPushName(-1);

  glMatrixMode(GL_PROJECTION);
  glLoadIdentity();
  gluPickMatrix(mousex, H - mousey, 4, 4, viewport);
  gluPerspective(45, 1.0, 0.1, 100.0);

  drawAll();

  hits = glRenderMode(GL_RENDER);
  if (hits <= 0) {
    return 0;
  }
  closest = 0;
  dist = 4294967295U;
  while (hits) {
    if (selectBuf[(hits - 1) * 4 + 1] < dist) {
      dist = selectBuf[(hits - 1) * 4 + 1];
      closest = selectBuf[(hits - 1) * 4 + 3];
    }
    hits--;
  }
  return closest;
}

void
nukePiece(int piece)
{
  int i, j;

  for (i = 0; i < HEIGHT; i++) {
    for (j = 0; j < WIDTH; j++) {
      if (thePuzzle[i][j] == piece) {
        thePuzzle[i][j] = 0;
      }
    }
  }
}

void
multMatrices(const GLfloat a[16], const GLfloat b[16], GLfloat r[16])
{
  int i, j;

  for (i = 0; i < 4; i++) {
    for (j = 0; j < 4; j++) {
      r[i * 4 + j] =
        a[i * 4 + 0] * b[0 * 4 + j] +
        a[i * 4 + 1] * b[1 * 4 + j] +
        a[i * 4 + 2] * b[2 * 4 + j] +
        a[i * 4 + 3] * b[3 * 4 + j];
    }
  }
}

void
makeIdentity(GLfloat m[16])
{
  m[0 + 4 * 0] = 1;
  m[0 + 4 * 1] = 0;
  m[0 + 4 * 2] = 0;
  m[0 + 4 * 3] = 0;
  m[1 + 4 * 0] = 0;
  m[1 + 4 * 1] = 1;
  m[1 + 4 * 2] = 0;
  m[1 + 4 * 3] = 0;
  m[2 + 4 * 0] = 0;
  m[2 + 4 * 1] = 0;
  m[2 + 4 * 2] = 1;
  m[2 + 4 * 3] = 0;
  m[3 + 4 * 0] = 0;
  m[3 + 4 * 1] = 0;
  m[3 + 4 * 2] = 0;
  m[3 + 4 * 3] = 1;
}

/*
   ** inverse = invert(src)
 */
int
invertMatrix(const GLfloat src[16], GLfloat inverse[16])
{
  int i, j, k, swap;
  double t;
  GLfloat temp[4][4];

  for (i = 0; i < 4; i++) {
    for (j = 0; j < 4; j++) {
      temp[i][j] = src[i * 4 + j];
    }
  }
  makeIdentity(inverse);

  for (i = 0; i < 4; i++) {
    /* 
       ** Look for largest element in column */
    swap = i;
    for (j = i + 1; j < 4; j++) {
      if (fabs(temp[j][i]) > fabs(temp[i][i])) {
        swap = j;
      }
    }

    if (swap != i) {
      /* 
         ** Swap rows. */
      for (k = 0; k < 4; k++) {
        t = temp[i][k];
        temp[i][k] = temp[swap][k];
        temp[swap][k] = t;

        t = inverse[i * 4 + k];
        inverse[i * 4 + k] = inverse[swap * 4 + k];
        inverse[swap * 4 + k] = t;
      }
    }
    if (temp[i][i] == 0) {
      /* 
         ** No non-zero pivot.  The matrix is singular, which
         shouldn't ** happen.  This means the user gave us a
         bad matrix. */
      return 0;
    }
    t = temp[i][i];
    for (k = 0; k < 4; k++) {
      temp[i][k] /= t;
      inverse[i * 4 + k] /= t;
    }
    for (j = 0; j < 4; j++) {
      if (j != i) {
        t = temp[j][i];
        for (k = 0; k < 4; k++) {
          temp[j][k] -= temp[i][k] * t;
          inverse[j * 4 + k] -= inverse[i * 4 + k] * t;
        }
      }
    }
  }
  return 1;
}

/*
   ** This is a screwball function.  What it does is the following:
   ** Given screen x and y coordinates, compute the corresponding object space 
   **   x and y coordinates given that the object space z is 0.9 + OFFSETZ.
   ** Since the tops of (most) pieces are at z = 0.9 + OFFSETZ, we use that 
   **   number.
 */
int
computeCoords(int piece, int mousex, int mousey,
  GLfloat * selx, GLfloat * sely)
{
  GLfloat modelMatrix[16];
  GLfloat projMatrix[16];
  GLfloat finalMatrix[16];
  GLfloat in[4];
  GLfloat a, b, c, d;
  GLfloat top, bot;
  GLfloat z;
  GLfloat w;
  GLfloat height;

  if (piece == 0)
    return 0;
  height = zsize[piece] - 0.1 + OFFSETZ;

  glGetFloatv(GL_PROJECTION_MATRIX, projMatrix);
  glGetFloatv(GL_MODELVIEW_MATRIX, modelMatrix);
  multMatrices(modelMatrix, projMatrix, finalMatrix);
  if (!invertMatrix(finalMatrix, finalMatrix))
    return 0;

  in[0] = (2.0 * (mousex - viewport[0]) / viewport[2]) - 1;
  in[1] = (2.0 * ((H - mousey) - viewport[1]) / viewport[3]) - 1;

  a = in[0] * finalMatrix[0 * 4 + 2] +
    in[1] * finalMatrix[1 * 4 + 2] +
    finalMatrix[3 * 4 + 2];
  b = finalMatrix[2 * 4 + 2];
  c = in[0] * finalMatrix[0 * 4 + 3] +
    in[1] * finalMatrix[1 * 4 + 3] +
    finalMatrix[3 * 4 + 3];
  d = finalMatrix[2 * 4 + 3];

  /* 
     ** Ok, now we need to solve for z: **   (a + b z) / (c + d 

     z) = height. ** ("height" is the height in object space we 

     want to solve z for) ** ** ==>  a + b z = height c +
     height d z **      bz - height d z = height c - a ** z =
     (height c - a) / (b - height d) */
  top = height * c - a;
  bot = b - height * d;
  if (bot == 0.0)
    return 0;

  z = top / bot;

  /* 
     ** Ok, no problem. ** Now we solve for x and y.  We know
     that w = c + d z, so we compute it. */
  w = c + d * z;

  /* 
     ** Now for x and y: */
  *selx = (in[0] * finalMatrix[0 * 4 + 0] +
    in[1] * finalMatrix[1 * 4 + 0] +
    z * finalMatrix[2 * 4 + 0] +
    finalMatrix[3 * 4 + 0]) / w - OFFSETX;
  *sely = (in[0] * finalMatrix[0 * 4 + 1] +
    in[1] * finalMatrix[1 * 4 + 1] +
    z * finalMatrix[2 * 4 + 1] +
    finalMatrix[3 * 4 + 1]) / w - OFFSETY;
  return 1;
}

static int selected;
static int selectx, selecty;
static float selstartx, selstarty;

void
grabPiece(int piece, float selx, float sely)
{
  int hit;

  selectx = selx;
  selecty = sely;
  if (selectx < 0 || selecty < 0 || selectx >= WIDTH || selecty >= HEIGHT) {
    return;
  }
  hit = thePuzzle[selecty][selectx];
  if (hit != piece)
    return;
  if (hit) {
    movingPiece = hit;
    while (selectx > 0 && thePuzzle[selecty][selectx - 1] == movingPiece) {
      selectx--;
    }
    while (selecty > 0 && thePuzzle[selecty - 1][selectx] == movingPiece) {
      selecty--;
    }
    move_x = selectx;
    move_y = selecty;
    selected = 1;
    selstartx = selx;
    selstarty = sely;
  } else {
    selected = 0;
  }
  changeState();
}

void
moveSelection(float selx, float sely)
{
  float deltax, deltay;
  int dir;
  Config newpieces;

  if (!selected)
    return;
  deltax = selx - selstartx;
  deltay = sely - selstarty;

  if (fabs(deltax) > fabs(deltay)) {
    deltay = 0;
    if (deltax > 0) {
      if (deltax > 1)
        deltax = 1;
      dir = 2;
    } else {
      if (deltax < -1)
        deltax = -1;
      dir = 0;
    }
  } else {
    deltax = 0;
    if (deltay > 0) {
      if (deltay > 1)
        deltay = 1;
      dir = 3;
    } else {
      if (deltay < -1)
        deltay = -1;
      dir = 1;
    }
  }
  if (canmove(thePuzzle, selectx, selecty, dir, newpieces)) {
    move_x = deltax + selectx;
    move_y = deltay + selecty;
    if (deltax > 0.5) {
      memcpy(thePuzzle, newpieces, HEIGHT * WIDTH);
      selectx++;
      selstartx++;
    } else if (deltax < -0.5) {
      memcpy(thePuzzle, newpieces, HEIGHT * WIDTH);
      selectx--;
      selstartx--;
    } else if (deltay > 0.5) {
      memcpy(thePuzzle, newpieces, HEIGHT * WIDTH);
      selecty++;
      selstarty++;
    } else if (deltay < -0.5) {
      memcpy(thePuzzle, newpieces, HEIGHT * WIDTH);
      selecty--;
      selstarty--;
    }
  } else {
    if (deltay > 0 && thePuzzle[selecty][selectx] == 10 &&
      selectx == 1 && selecty == 3) {
      /* Allow visual movement of solution piece outside of the 

         box */
      move_x = selectx;
      move_y = sely - selstarty + selecty;
    } else {
      move_x = selectx;
      move_y = selecty;
    }
  }
}

void
dropSelection(void)
{
  if (!selected)
    return;
  movingPiece = 0;
  selected = 0;
  changeState();
}

static int left_mouse, middle_mouse;
static int mousex, mousey;
static int solving;
static int spinning;
static float lastquat[4];
static int sel_piece;

static void
Reshape(int width, int height)
{

  W = width;
  H = height;
  glViewport(0, 0, W, H);
  glGetIntegerv(GL_VIEWPORT, viewport);
}

void
toggleSolve(void)
{
    if (solving) {
      freeSolutions();
      solving = 0;
      glutChangeToMenuEntry(1, "Solving", 1);
      glutSetWindowTitle("glpuzzle");
      movingPiece = 0;
    } else {
      glutChangeToMenuEntry(1, "Stop solving", 1);
      glutSetWindowTitle("Solving...");
      if (solvePuzzle()) {
        solving = 1;
      }
    }
    changeState();
    glutPostRedisplay();
}

void reset(void)
{
    if (solving) {
      freeSolutions();
      solving = 0;
      glutChangeToMenuEntry(1, "Solving", 1);
      movingPiece = 0;
      changeState();
    }
    glutSetWindowTitle("glpuzzle");
    memcpy(thePuzzle, startConfig, HEIGHT * WIDTH);
    glutPostRedisplay();
}

void
keyboard(unsigned char c, int x, int y)
{
  int piece;

  switch (c) {
  case 27:
    exit(0);
    break;
  case 'D':
  case 'd':
    if (solving) {
      freeSolutions();
      solving = 0;
      glutChangeToMenuEntry(1, "Solving", 1);
      glutSetWindowTitle("glpuzzle");
      movingPiece = 0;
      changeState();
    }
    piece = selectPiece(x, y);
    if (piece) {
      nukePiece(piece);
    }
    glutPostRedisplay();
    break;
  case 'R':
  case 'r':
    reset();
    break;
  case 'S':
  case 's':
    toggleSolve();
    break;
  case 'b':
  case 'B':
    depth = 1 - depth;
    if (depth) {
      glEnable(GL_DEPTH_TEST);
    } else {
      glDisable(GL_DEPTH_TEST);
    }
    glutPostRedisplay();
    break;
  default:
    break;
  }
}

void
motion(int x, int y)
{
  float selx, sely;

  if (middle_mouse && !left_mouse) {
    if (mousex != x || mousey != y) {
      trackball(lastquat,
        (2.0*mousex - W) / W,
        (H - 2.0*mousey) / H,
        (2.0*x - W) / W,
        (H - 2.0*y) / H);
      spinning = 1;
    } else {
      spinning = 0;
    }
    changeState();
  } else {
    computeCoords(sel_piece, x, y, &selx, &sely);
    moveSelection(selx, sely);
  }
  mousex = x;
  mousey = y;
  glutPostRedisplay();
}

void
mouse(int b, int s, int x, int y)
{
  float selx, sely;

  mousex = x;
  mousey = y;
  curX = x;
  curY = y;
  if (s == GLUT_DOWN) {
    switch (b) {
    case GLUT_LEFT_BUTTON:
      if (solving) {
        freeSolutions();
        solving = 0;
      glutChangeToMenuEntry(1, "Solving", 1);
        glutSetWindowTitle("glpuzzle");
        movingPiece = 0;
      }
      left_mouse = GL_TRUE;
      sel_piece = selectPiece(mousex, mousey);
      if (computeCoords(sel_piece, mousex, mousey, &selx, &sely)) {
        grabPiece(sel_piece, selx, sely);
      }
      glutPostRedisplay();
      break;
    case GLUT_MIDDLE_BUTTON:
      middle_mouse = GL_TRUE;
      glutPostRedisplay();
      break;
    }
  } else {
    switch (b) {
    case GLUT_LEFT_BUTTON:
      left_mouse = GL_FALSE;
      dropSelection();
      glutPostRedisplay();
      break;
    case GLUT_MIDDLE_BUTTON:
      middle_mouse = GL_FALSE;
      glutPostRedisplay();
      break;
    }
  }
  motion(x, y);
}

void
animate(void)
{
  if (spinning) {
    add_quats(lastquat, curquat, curquat);
  }
  glutPostRedisplay();
  if (solving) {
    if (!continueSolving()) {
      solving = 0;
      glutChangeToMenuEntry(1, "Solving", 1);
      glutSetWindowTitle("glpuzzle");
    }
  }
  if (!solving && !spinning && !visible) {
    glutIdleFunc(NULL);
  }
}

void
changeState(void)
{
  if (visible) {
    if (!solving && !spinning) {
      glutIdleFunc(NULL);
    } else {
      glutIdleFunc(animate);
    }
  } else {
    glutIdleFunc(NULL);
  }
}

void
init(void)
{
  static float lmodel_ambient[] =
  {0.0, 0.0, 0.0, 0.0};
  static float lmodel_twoside[] =
  {GL_FALSE};
  static float lmodel_local[] =
  {GL_FALSE};
  static float light0_ambient[] =
  {0.1, 0.1, 0.1, 1.0};
  static float light0_diffuse[] =
  {1.0, 1.0, 1.0, 0.0};
  static float light0_position[] =
  {0.8660254, 0.5, 1, 0};
  static float light0_specular[] =
  {0.0, 0.0, 0.0, 0.0};
  static float bevel_mat_ambient[] =
  {0.0, 0.0, 0.0, 1.0};
  static float bevel_mat_shininess[] =
  {40.0};
  static float bevel_mat_specular[] =
  {0.0, 0.0, 0.0, 0.0};
  static float bevel_mat_diffuse[] =
  {1.0, 0.0, 0.0, 0.0};

  glEnable(GL_CULL_FACE);
  glCullFace(GL_BACK);
  glEnable(GL_DEPTH_TEST);
  glClearDepth(1.0);

  glClearColor(0.5, 0.5, 0.5, 0.0);
  glLightfv(GL_LIGHT0, GL_AMBIENT, light0_ambient);
  glLightfv(GL_LIGHT0, GL_DIFFUSE, light0_diffuse);
  glLightfv(GL_LIGHT0, GL_SPECULAR, light0_specular);
  glLightfv(GL_LIGHT0, GL_POSITION, light0_position);
  glEnable(GL_LIGHT0);

  glLightModelfv(GL_LIGHT_MODEL_LOCAL_VIEWER, lmodel_local);
  glLightModelfv(GL_LIGHT_MODEL_TWO_SIDE, lmodel_twoside);
  glLightModelfv(GL_LIGHT_MODEL_AMBIENT, lmodel_ambient);
  glEnable(GL_LIGHTING);

  glMaterialfv(GL_FRONT, GL_AMBIENT, bevel_mat_ambient);
  glMaterialfv(GL_FRONT, GL_SHININESS, bevel_mat_shininess);
  glMaterialfv(GL_FRONT, GL_SPECULAR, bevel_mat_specular);
  glMaterialfv(GL_FRONT, GL_DIFFUSE, bevel_mat_diffuse);

  glColorMaterial(GL_FRONT_AND_BACK, GL_DIFFUSE);
  glEnable(GL_COLOR_MATERIAL);
  glShadeModel(GL_FLAT);

  trackball(curquat, 0.0, 0.0, 0.0, 0.0);
  srandom(time(NULL));
}

static void
Usage(void)
{
  printf("Usage: puzzle [-s]\n");
  printf("   -s:  Run in single buffered mode\n");
  exit(-1);
}

void
visibility(int v)
{
  if (v == GLUT_VISIBLE) {
    visible = 1;
  } else {
    visible = 0;
  }
  changeState();
}

void
menu(int choice)
{
   switch(choice) {
   case 1:
      toggleSolve();
      break;
   case 2:
      reset();
      break;
   case 3:
      exit(0);
      break;
   }
}

int
main(int argc, char **argv)
{
  long i;

  glutInit(&argc, argv);
  for (i = 1; i < argc; i++) {
    if (argv[i][0] == '-') {
      switch (argv[i][1]) {
      case 's':
        doubleBuffer = 0;
        break;
      default:
        Usage();
      }
    } else {
      Usage();
    }
  }

  glutInitWindowSize(W, H);
  if (doubleBuffer) {
    glutInitDisplayMode(GLUT_DEPTH | GLUT_RGB | GLUT_DOUBLE | GLUT_MULTISAMPLE);
  } else {
    glutInitDisplayMode(GLUT_DEPTH | GLUT_RGB | GLUT_SINGLE | GLUT_MULTISAMPLE);
  }

  glutCreateWindow("glpuzzle");

  init();

  glGetIntegerv(GL_VIEWPORT, viewport);

  printf("\n");
  printf("r   Reset puzzle\n");
  printf("s   Solve puzzle (may take a few seconds to compute)\n");
  printf("d   Destroy a piece - makes the puzzle easier\n");
  printf("b   Toggles the depth buffer on and off\n");
  printf("\n");
  printf("Left mouse moves pieces\n");
  printf("Middle mouse spins the puzzle\n");
  printf("Right mouse has menu\n");

  glutReshapeFunc(Reshape);
  glutDisplayFunc(redraw);
  glutKeyboardFunc(keyboard);
  glutMotionFunc(motion);
  glutMouseFunc(mouse);
  glutVisibilityFunc(visibility);
  glutCreateMenu(menu);
  glutAddMenuEntry("Solve", 1);
  glutAddMenuEntry("Reset", 2);
  glutAddMenuEntry("Quit", 3);
  glutAttachMenu(GLUT_RIGHT_BUTTON);
  glutMainLoop();
  return 0;             /* ANSI C requires main to return int. */
}