/*
 * @(#)CubesS.c
 *
 * Taken from the X puzzle by Don Bennett, HP Labs
 *
 * Copyright 2003 - 2021 David A. Bagley, bagleyd AT verizon.net
 *
 * All rights reserved.
 *
 * Permission to use, copy, modify, and distribute this software and
 * its documentation for any purpose and without fee is hereby granted,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear in
 * supporting documentation, and that the name of the author not be
 * used in advertising or publicity pertaining to distribution of the
 * software without specific, written prior permission.
 *
 * This program 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.
 */

/*
 * $XConsortium: puzzle.c,v 1.14 94/03/28 18:34:10 gildea Exp $
 */

/*
 * Puzzle - (C) Copyright 1987, 1988 Don Bennett.
 *
 * Permission to use, copy, modify, and distribute this software and its
 * documentation for any purpose and without fee is hereby granted,
 * provided that the above copyright notice appear in all copies and that
 * both that copyright notice and this permission notice appear in
 * supporting documentation.
 */

/*
 *  Puzzle
 *
 * Don Bennett, HP Labs
 *
 * this is the code that does the real work to solve the
 * puzzle.  (Commonly seen as a 4x4 grid of sliding pieces
 * numbered 1-15 with one empty space.)
 *
 * The idea for the solution algorithm - solving the puzzle
 * in layers working from the outside in - comes to me
 * indirectly from John Nagle.
 */

/*
 *  TODO
 *    o handle x != 1 && y != 1 && z != 1, i.e. 3d
 *
 */

#define JMP
#ifdef JMP
#include <setjmp.h> /* longjmp ... interrupt */
#endif
#include "CubesP.h"
#define MAX_PLAN	1000
#define QUEUE_SIZE	1000
#define SOLVE_COORD	6

/* PUZZLE_SIZE MUST be a multiple of 2; */
#define PUZZLE_SIZE ((MAX(MAX(MIN(w->cubes.sizeX, w->cubes.sizeY),\
  MIN(w->cubes.sizeY, w->cubes.sizeZ)),MIN(w->cubes.sizeZ,w->cubes.sizeX))>>1)<<1)
#define DIST(loc1,loc2)	(ABS(toColumn(loc1)-toColumn(loc2))+\
  ABS(toRow(loc1)-toRow(loc2))+ABS(toStack(loc1)-toStack(loc2)))

static int otherDir[SOLVE_COORD] = { BOTTOM, LEFT, TOP, RIGHT, OUTWARDS, INWARDS };

/* layer info macros -> (innermost 4 tiles are layer zero,
 *			ordinal goes up as you move out)
 * layerHeight		- returns number of (rows down),
 *			(cols across) the layer starts;
 * layerWidth		- number of blocks wide the layer is;
 */

#define layerHeight(l)	(layers-1-(l))
#define layerWidth(l)	(PUZZLE_SIZE-2*layerHeight(l))

/* macros for finding the corners of each layer */

#define UL_Z(l) (layerHeight(l)*(PUZZLE_SIZE+1)+\
  extraRows*w->cubes.sizeX+extraColumns*(layers-(l)))
#define UR_Z(l) (layerHeight(l)*(PUZZLE_SIZE+1)+layerWidth(l)-1+\
  extraRows*w->cubes.sizeX+extraColumns*(layers-(l)))
#define LL_Z(l) ((layerHeight(l)+layerWidth(l)-1)*PUZZLE_SIZE+layerHeight(l)+\
  extraRows*PUZZLE_SIZE+extraColumns*(w->cubes.sizeY+1+(l)-layers))
#define LR_Z(l) ((layerHeight(l)+layerWidth(l)-1)*(PUZZLE_SIZE+1)+\
  extraRows*PUZZLE_SIZE+extraColumns*(w->cubes.sizeY+1+(l)-layers))

#define UL_Y(l) (layerHeight(l)*(PUZZLE_SIZE+1)+\
  extraStacks*w->cubes.sizeX+extraColumns*(layers-(l)))
#define UR_Y(l) (layerHeight(l)*(PUZZLE_SIZE+1)+layerWidth(l)-1+\
  extraStacks*w->cubes.sizeX+extraColumns*(layers-(l)))
#define LL_Y(l) ((layerHeight(l)+layerWidth(l)-1)*PUZZLE_SIZE+layerHeight(l)+\
  extraStacks*PUZZLE_SIZE+extraColumns*(w->cubes.sizeZ+1+(l)-layers))
#define LR_Y(l) ((layerHeight(l)+layerWidth(l)-1)*(PUZZLE_SIZE+1)+\
  extraStacks*PUZZLE_SIZE+extraColumns*(w->cubes.sizeZ+1+(l)-layers))

#define UL_X(l) (layerHeight(l)*(PUZZLE_SIZE+1)+\
  extraStacks*w->cubes.sizeY+extraRows*(layers-(l)))
#define UR_X(l) (layerHeight(l)*(PUZZLE_SIZE+1)+layerWidth(l)-1+\
  extraStacks*w->cubes.sizeY+extraRows*(layers-(l)))
#define LL_X(l) ((layerHeight(l)+layerWidth(l)-1)*PUZZLE_SIZE+layerHeight(l)+\
  extraStacks*PUZZLE_SIZE+extraRows*(w->cubes.sizeZ+1+(l)-layers))
#define LR_X(l) ((layerHeight(l)+layerWidth(l)-1)*(PUZZLE_SIZE+1)+\
  extraStacks*PUZZLE_SIZE+extraRows*(w->cubes.sizeZ+1+(l)-layers))

/* get the x and y and z coordinates of a location in the matrix */

#define toColumn(loc)	(((loc)%w->cubes.sizeRect)%w->cubes.sizeX)
#define toRow(loc)	(((loc)%w->cubes.sizeRect)/w->cubes.sizeX)
#define toStack(loc)	((loc)/w->cubes.sizeRect)
#define toPosition(x,y,z)	((z)*w->cubes.sizeRect+((y)*w->cubes.sizeX)+(x))
#define spaceX	toColumn(w->cubes.spacePosition)
#define spaceY	toRow(w->cubes.spacePosition)
#define spaceZ	toStack(w->cubes.spacePosition)

#define nextLeft(loc)	((loc)-1)
#define nextRight(loc)	((loc)+1)
#define nextUp(loc)	((loc)-w->cubes.sizeX)
#define nextDown(loc)	((loc)+w->cubes.sizeX)
#define nextIn(loc)	((loc)-w->cubes.sizeRect)
#define nextOut(loc)	((loc)+w->cubes.sizeRect)

static int sizeX = 0, sizeY = 0, sizeZ = 0;
static int extraColumns = 0;
static int extraRows = 0;
static int extraStacks = 0;
static int layers;
static int *tmpMatrix;
static int *targetM;
static Boolean *locked;
static int *locList;

static Boolean solvingFlag = False;
#ifdef JMP
static Boolean abortSolvingFlag = False;
static jmp_buf solve_env;

static void
abortSolving(void)
{
	if (solvingFlag)
		abortSolvingFlag = True;
}

#ifdef WINVER
static Boolean
processMessage(UINT msg)
{
	switch (msg) {
	case WM_KEYDOWN:
	case WM_CLOSE:
	case WM_LBUTTONDOWN:
	case WM_RBUTTONDOWN:
		abortSolving();
		return True;
	default:
		return False;
	}
}
#else
static void
processButton(void /*XButtonEvent *event*/)
{
	abortSolving();
}

static void
processVisibility(XVisibilityEvent *event)
{
	if (event->state != VisibilityUnobscured)
		abortSolving();
}

static void
getNextEvent(CubesWidget w, XEvent *event)
{
	if (!XCheckMaskEvent(XtDisplay(w), VisibilityChangeMask, event))
		(void) XNextEvent(XtDisplay(w), event);
}

static void
processEvent(XEvent *event)
{
	switch(event->type) {
	case KeyPress:
	case ButtonPress:
		processButton(/*&event->xbutton*/);
		break;
	case VisibilityNotify:
		processVisibility(&event->xvisibility);
		break;
	default:
		break;
	}
}

static void
processEvents(CubesWidget w)
{
	XEvent event;

	while (XPending(XtDisplay(w))) {
		getNextEvent(w, &event);
		processEvent(&event);
	}
}
#endif
#endif

static int
findPiece(CubesWidget w, int piece)
{
	int i;
	char *buf1 = NULL, *buf2 = NULL;

	for (i = 0; i < w->cubes.sizeBlock; i++)
		if (w->cubes.blockOfPosition[i] == piece) {
			/*(void) printf("position=%d, piece=%d at %d\n",
				i, piece, w->cubes.blockOfPosition[i]);*/
			return i;
		}

	intCat(&buf1, "Piece ", piece);
	stringCat(&buf2, buf1, " not found, exiting.");
	free(buf1);
	DISPLAY_ERROR(buf2);
	free(buf2);
	return -1;
}

static void
logMoveSpace(CubesWidget w, int firstX, int firstY, int firstZ,
		int lastX, int lastY, int lastZ, int dir)
{
	int count = ABS(firstX - lastX) + ABS(firstY - lastY)
		+ ABS(firstZ - lastZ) + 1;
	int i;

	for (i = 0; i < count; i++)
		movePuzzleDir(w, dir, DOUBLE);
}

static void
moveSpace(CubesWidget w, int direction, int distance)
{
	int i, step, count;
	int firstX, firstY, firstZ, lastX, lastY, lastZ, shiftDir;
	int tempSpaceX = spaceX, tempSpaceY = spaceY, tempSpaceZ = spaceZ;
	int dir = direction, dist = distance;

#ifdef JMP
#ifdef WINVER
	MSG msg;

	if (PeekMessage(&msg, NULL, 0, 0, 0)) {
		if (!processMessage(msg.message)) {
			if (GetMessage(&msg, NULL, 0, 0))
				DispatchMessage(&msg);
		}
	}
#else
	processEvents(w);
#endif
	if (solvingFlag && abortSolvingFlag)
		longjmp(solve_env, 1);
#endif
	if (dist == 0)
		return;

	if (dir == LEFT) {
		dir = RIGHT;
		dist = -dist;
	} else if (dir == TOP) {
		dir = BOTTOM;
		dist = -dist;
	} else if (dir == INWARDS) {
		dir = OUTWARDS;
		dist = -dist;
	}
	firstX = spaceX;
	firstY = spaceY;
	firstZ = spaceZ;
	step = 1;
	count = dist;
	if (dist < 0) {
		step = -1;
		count = -count;
	}

	/* firstX,Y,Z are the location of the first piece to be shifted */
	if (dir == RIGHT)
		firstX += step;
	else if (dir == BOTTOM)
		firstY += step;
	else /* if (dir == OUTWARDS) */
		firstZ += step;

	/* shiftDir is the direction the pieces need to be shifted */
	if (dist < 0) {
		shiftDir = dir;
	} else {
		shiftDir = otherDir[dir];
	}
	for (i = 0; i < count; i++) {
		if (dir == RIGHT) {
			tempSpaceX += step;
		} else if (dir == BOTTOM) {
			tempSpaceY += step;
		} else { /* if (dir == OUTWARDS) */
			tempSpaceZ += step;
		}
	}
	lastX = tempSpaceX;
	lastY = tempSpaceY;
	lastZ = tempSpaceZ;

	/* the blocks firstX,Y,Z through lastX,Y,Z need to be shifted
	 * one block in the shiftDir direction;
	 */

	logMoveSpace(w, firstX, firstY, firstZ, lastX, lastY, lastZ, shiftDir);
}

#ifdef DEBUG
static void
printMatrix(CubesWidget w, int **mat)
{
	int i, j, k;

	for (k = 0; k < w->cubes.sizeZ; k++) {
		for (j = 0; j < w->cubes.sizeY; j++) {
			for (i = 0; i < w->cubes.sizeX; i++)
				(void) printf(" %2d ",
					(*mat)[toPosition(i, j, k)]);
			(void) printf("\n");
		}
		(void) printf("\n");
	}
	(void) printf("\n");
}
#endif

static void
planMove(CubesWidget w, int startLoc, int endLoc, int **path)
{
	int i, nextLoc = 0, nextDist, chosen, moveNum;
	Boolean foundPath = False;
	int locX, locY, locZ;
	int locQueue[QUEUE_SIZE];
	int locDist[QUEUE_SIZE];
	Boolean locQueueUsed[QUEUE_SIZE];
	int queueHead = 0, queueTail = 0;
	int candidate[SOLVE_COORD];

	for (i = 0; i < w->cubes.sizeBlock; i++) {
		tmpMatrix[i] = (locked[i]) ? -1 : 0;
		locList[i] = -1;
	}

	for (i = 0; i < QUEUE_SIZE; i++)
		locQueueUsed[i] = False;

	locQueue[0] = startLoc;
	locDist[0] = DIST(endLoc, startLoc);
	tmpMatrix[startLoc] = 1;
	queueTail++;

	/* if the selected element has a distance of zero,
	 * we have found it; (This really is not a queue,
	 * but rather a range of elements to be searched
	 * for an element of the desired properties;
	 */

	/* as we search for a path,
	 * LINK array is used to indicate the direction from which
	 * we moved into a location;
	 * TMP_MATRIX array is used to keep track of the move number;
	 */

	while (queueHead < queueTail && !foundPath) {
		/* find the entry that
		 * (1) has the smallest distance and
		 * (2) has the smallest move number;
		 */

		nextLoc = locQueue[queueHead];
		nextDist = locDist[queueHead];
		chosen = queueHead;

		for (i = queueHead + 1; i < queueTail; i++)
			if (!locQueueUsed[i] &&
					((locDist[i] < nextDist) ||
					((locDist[i] == nextDist) &&
					(tmpMatrix[locQueue[i]] <
					tmpMatrix[nextLoc])))) {
				nextLoc = locQueue[i];
				nextDist = locDist[i];
				chosen = i;
			}
		if (nextDist == 0) {
			foundPath = True;
			break;
		}
		locQueueUsed[chosen] = True;

		/* permute the chosen element */
		candidate[TOP] = nextUp(nextLoc);
		candidate[LEFT] = nextLeft(nextLoc);
		candidate[BOTTOM] = nextDown(nextLoc);
		candidate[RIGHT] = nextRight(nextLoc);
		candidate[INWARDS] = nextIn(nextLoc);
		candidate[OUTWARDS] = nextOut(nextLoc);
		locX = toColumn(nextLoc);
		locY = toRow(nextLoc);
		locZ = toStack(nextLoc);
		if (locX == 0)
			candidate[LEFT] = -1;
		if (locX == w->cubes.sizeX - 1)
			candidate[RIGHT] = -1;
		if (locY == 0)
			candidate[TOP] = -1;
		if (locY == w->cubes.sizeY - 1)
			candidate[BOTTOM] = -1;
		if (locZ == 0)
			candidate[INWARDS] = -1;
		if (locZ == w->cubes.sizeZ - 1)
			candidate[OUTWARDS] = -1;
		moveNum = tmpMatrix[nextLoc] + 1;
		for (i = 0; i < SOLVE_COORD; i++)
			if (candidate[i] != -1 &&
					tmpMatrix[candidate[i]] == 0) {
				tmpMatrix[candidate[i]] = moveNum;
				/*
				 * the next line works because the
				 * candidate index is same as the
				 * direction moved to reach the
				 * candidate;
				 */
				locList[candidate[i]] = i;
				locQueue[queueTail] = candidate[i];
				locDist[queueTail] =
					DIST(endLoc, candidate[i]);
				queueTail++;
				if (queueTail == QUEUE_SIZE) {
					DISPLAY_ERROR(
					"Queue size is exceeded, exiting.");
						return;
				}
			}

		/* delete used items from the front of the queue */
		while (locQueueUsed[queueHead] && queueHead < queueTail)
			queueHead++;
	}

#ifdef DEBUG
	printMatrix(w, &(w->cubes.blockOfPosition));
	printMatrix(w, &locked);
#endif /* DEBUG */
	if (!foundPath) {
		char *buf1 = NULL, *buf2 = NULL;

		intCat(&buf1, "Could not find a way to move ", startLoc);
		stringCat(&buf2, buf1, " (");
		free(buf1);
		intCat(&buf1, buf2, toColumn(startLoc));
		free(buf2);
		stringCat(&buf2, buf1, ",");
		free(buf1);
		intCat(&buf1, buf2, toRow(startLoc));
		free(buf2);
		stringCat(&buf2, buf1, ",");
		free(buf1);
		intCat(&buf1, buf2, toStack(startLoc));
		free(buf2);
		stringCat(&buf2, buf1, ") to ");
		free(buf1);
		intCat(&buf1, buf2, endLoc);
		free(buf2);
		stringCat(&buf2, buf1, " (");
		free(buf1);
		intCat(&buf1, buf2, toColumn(endLoc));
		free(buf2);
		stringCat(&buf2, buf1, ",");
		free(buf1);
		intCat(&buf1, buf2, toRow(endLoc));
		free(buf2);
		stringCat(&buf2, buf1, ",");
		free(buf1);
		intCat(&buf1, buf2, toStack(endLoc));
		free(buf2);
		stringCat(&buf2, buf1, "), exiting.");
		free(buf1);
		DISPLAY_ERROR(buf2);
		free(buf2);
		return;
	}

	/*
	 * copy the path we found into the path array;
	 * element 0 will contain the number of moves in the path;
	 * by the time we get there, nextLoc is in the final location
	 */

	(*path)[0] = tmpMatrix[nextLoc] - 1;
	for (i = (*path)[0]; i > 0; i--) {
		(*path)[i] = locList[nextLoc];
		switch(locList[nextLoc]) {
		case LEFT:
			nextLoc = nextRight(nextLoc);
			break;
		case RIGHT:
			nextLoc = nextLeft(nextLoc);
			break;
		case TOP:
			nextLoc = nextDown(nextLoc);
			break;
		case BOTTOM:
			nextLoc = nextUp(nextLoc);
			break;
		case INWARDS:
			nextLoc = nextOut(nextLoc);
			break;
		case OUTWARDS:
			nextLoc = nextIn(nextLoc);
			break;
		}
	}
}

static void
myMoveSpaceTo(CubesWidget w, int loc) {
	int i, currentDir, dist = 0;
	int plan[MAX_PLAN];
	int *planPtr = &(plan[0]);

	planMove(w, toPosition(spaceX, spaceY, spaceZ), loc, &planPtr);
	currentDir = plan[1];
	for (i = 1; i <= plan[0]; i++) {
		if (plan[i] == currentDir) {
			dist++;
		} else if (plan[i] == otherDir[currentDir]) {
			dist--;
		} else {
			moveSpace(w, currentDir, dist);
			currentDir = plan[i];
			dist = 1;
		}
	}
	moveSpace(w, currentDir, dist);
}

static void
movePiece(CubesWidget w, int location, int targetLoc) {
	int i;
	int plan[MAX_PLAN];
	int *planPtr = &(plan[0]);
	int loc = location;

	planMove(w, loc, targetLoc, &planPtr);
	for (i = 1; i <= plan[0]; i++)
		switch(plan[i]) {
		case LEFT:
			locked[loc] = True;
			myMoveSpaceTo(w, nextLeft(loc));
			locked[loc] = False;
			myMoveSpaceTo(w, loc);
			loc = nextLeft(loc);
			break;
		case RIGHT:
			locked[loc] = True;
			myMoveSpaceTo(w, nextRight(loc));
			locked[loc] = False;
			myMoveSpaceTo(w, loc);
			loc = nextRight(loc);
			break;
		case TOP:
			locked[loc] = True;
			myMoveSpaceTo(w, nextUp(loc));
			locked[loc] = False;
			myMoveSpaceTo(w, loc);
			loc = nextUp(loc);
			break;
		case BOTTOM:
			locked[loc] = True;
			myMoveSpaceTo(w, nextDown(loc));
			locked[loc] = False;
			myMoveSpaceTo(w, loc);
			loc = nextDown(loc);
			break;
		case INWARDS:
			locked[loc] = True;
			myMoveSpaceTo(w, nextIn(loc));
			locked[loc] = False;
			myMoveSpaceTo(w, loc);
			loc = nextIn(loc);
			break;
		case OUTWARDS:
			locked[loc] = True;
			myMoveSpaceTo(w, nextOut(loc));
			locked[loc] = False;
			myMoveSpaceTo(w, loc);
			loc = nextOut(loc);
			break;
		}
}

/* SYSV386 gets this from libBerk.a */
#if defined(USG) && !defined(CRAY) && !defined(SYSV386)
int gettimeofday (tvp, tzp)
    struct timeval *tvp;
    struct timezone *tzp;
{
    time (&tvp->tv_sec);
    tvp->tv_usec = 0L;

    /* ignore tzp for now since this file doesn't use it */
}
#endif

static void
myFree(void)
{
	if (tmpMatrix)
		free(tmpMatrix);
	if (targetM)
		free(targetM);
	if (locked)
		free(locked);
	if (locList)
		free(locList);
}

static void
myInitialize(CubesWidget w)
{
	/* Initialize the position and
	 * the targetM matrices;
	 */
	int i;
	int spX, spY, spZ;

	sizeX=w->cubes.sizeX;
	sizeY=w->cubes.sizeY;
	sizeZ=w->cubes.sizeZ;

	layers = PUZZLE_SIZE >> 1;

	extraColumns = w->cubes.sizeX - PUZZLE_SIZE;
	extraRows = w->cubes.sizeY - PUZZLE_SIZE;
	extraStacks = w->cubes.sizeZ - PUZZLE_SIZE;

	tmpMatrix = (int *) malloc(sizeof (int) * (size_t) w->cubes.sizeBlock);
	targetM = (int *) malloc(sizeof (int) * (size_t) w->cubes.sizeBlock);
	locked = (Boolean *) malloc(sizeof (int) * (size_t) w->cubes.sizeBlock);
	locList = (int *) malloc(sizeof (int) * (size_t) w->cubes.sizeBlock);

	for (i = 0; i < w->cubes.sizeBlock; i++)
		locked[i] = False;

	if (!tmpMatrix || !targetM || !locked || !locList ||
			!w->cubes.blockOfPosition) {
		DISPLAY_ERROR("Not enough memory, exiting.");
	}

	for (i = 0; i < w->cubes.sizeBlock - 1; i++) {
		targetM[i] = i + 1;
	}
	targetM[w->cubes.sizeBlock - 1] = 0;

	/*
	 * Move the space into the LR_* corner of the
	 * innermost layer;
	 * For each of the outer layers, move the space
	 * left one and up one;
	 */

	spX = w->cubes.sizeX - 1;
	spY = w->cubes.sizeY - 1;
	spZ = w->cubes.sizeZ - 1;

	/* Make solution with space at center bottom right */
	for (i = 0; i < layers - 1; i++) {
		if (spX > 0) {
			/* move the space left one; */
			targetM[toPosition(spX, spY, spZ)] =
				targetM[toPosition((spX - 1), spY, spZ)];
			targetM[toPosition((spX - 1), spY, spZ)] = 0;
			spX -= 1;
		}
		if (spY > 0) {
			/* move the space up one; */
			targetM[toPosition(spX, spY, spZ)] =
				targetM[toPosition(spX, (spY - 1), spZ)];
			targetM[toPosition(spX, (spY - 1), spZ)] = 0;
			spY -= 1;
		}
		if (spZ > 0) {
			/* move the space in one; */
			targetM[toPosition(spX, spY, spZ)] =
				targetM[toPosition(spX, spY, (spZ - 1))];
			targetM[toPosition(spX, spY, (spZ - 1))] = 0;
			spZ -= 1;
		}
	}
}

/*
 * To solve this puzzle, work from the outside in;
 * For each successive ring working your way in,
 *
 * (1) put the corners in place;
 * (2) finish off the rest of the boundaries;
 * (3) do the next layer in;
 */

static void
solveLayerZ0(CubesWidget w)
{
	movePiece(w, findPiece(w, targetM[UL_Z(0)]), UL_Z(0));
	myMoveSpaceTo(w, LR_Z(0));
}

static void
solveLayerY0(CubesWidget w)
{
	movePiece(w, findPiece(w, targetM[UL_Y(0)]), UL_Y(0));
	myMoveSpaceTo(w, LR_Y(0));
}

static void
solveLayerX0(CubesWidget w)
{
	movePiece(w, findPiece(w, targetM[UL_X(0)]), UL_X(0));
	myMoveSpaceTo(w, LR_X(0));
}

static void
doLastTwoOnEdge(CubesWidget w, int ntLast, int last, int tmp, int emergency)
{
	int lastPiece, ntLastPiece;

	lastPiece = targetM[last];
	ntLastPiece = targetM[ntLast];

	movePiece(w, findPiece(w, ntLastPiece), last);
	locked[last] = True;

	/*
	 * if the last piece is stuck where the next to the last
	 * piece should go, do some magic to fix things up;
	 */
	if (findPiece(w, 0) == ntLast)
		myMoveSpaceTo(w, tmp);

	if (findPiece(w, lastPiece) == ntLast) {
		/* a rescue is necessary */
		locked[last] = False;
		movePiece(w, findPiece(w, ntLastPiece), ntLast);
		locked[ntLast] = True;
		movePiece(w, findPiece(w, lastPiece), emergency);
		locked[emergency] = True;
		locked[ntLast] = False;
		movePiece(w, findPiece(w, ntLastPiece), last);
		locked[emergency] = False;
		locked[last] = True;
	}

	movePiece(w, findPiece(w, lastPiece), tmp);
	locked[tmp] = True;
	myMoveSpaceTo(w, ntLast);
	locked[tmp] = False;
	locked[last] = False;
	myMoveSpaceTo(w, last);
	myMoveSpaceTo(w, tmp);
	locked[ntLast] = True;
	locked[last] = True;
}

static void
solveLayerZ(CubesWidget w, int layer)
{
	int i, tmp, last, ntLast, emergency;
	int ul, ur, ll, lr;

	if (layer == 0) {
		solveLayerZ0(w);
	} else {
		/* find and put each of the corners into place */
		ul = UL_Z(layer);
		ur = UR_Z(layer);
		ll = LL_Z(layer);
		lr = LR_Z(layer);

		movePiece(w, findPiece(w, targetM[ul]), ul);
		locked[ul] = True;
		movePiece(w, findPiece(w, targetM[ur]), ur);
		locked[ur] = True;
		movePiece(w, findPiece(w, targetM[ll]), ll);
		locked[ll] = True;
		movePiece(w, findPiece(w, targetM[lr]), lr);
		locked[lr] = True;

		/*
		 * Strategy for doing the pieces between the corners:
		 * (1) put all but the last two edge pieces in place;
		 * (2) put the next to the last piece next to the
		 *	corner;
		 * (3) put the last piece one move in from its final
		 *	position;
		 * (4) move the space to the final position of the
		 *	next to the last piece;
		 * (5) slide the next to the last piece over and the
		 *	last piece into the edge where it goes.
		 */

		/* top edge */
		for (i = ul + 1; i < ur - 2; i++) {
			movePiece(w, findPiece(w, targetM[i]), i);
			locked[i] = True;
		}

		ntLast = i;
		last = i + 1;
		tmp = UR_Z(layer - 1);
		emergency = nextDown(tmp);
		doLastTwoOnEdge(w, ntLast, last, tmp, emergency);

		/* bottom edge */
		for (i = ll + 1; i < lr - 2; i++) {
			movePiece(w, findPiece(w, targetM[i]), i);
			locked[i] = True;
		}

		ntLast = i;
		last = i + 1;
		tmp = LR_Z(layer - 1);
		emergency = nextUp(tmp);
		doLastTwoOnEdge(w, ntLast, last, tmp, emergency);

		/* left side */
		for (i = ul + w->cubes.sizeX; i < ll - 2 * w->cubes.sizeX;
				i += w->cubes.sizeX) {
			movePiece(w, findPiece(w, targetM[i]), i);
			locked[i] = True;
		}

		ntLast = i;
		last = i + w->cubes.sizeX;
		tmp = LL_Z(layer - 1);
		emergency = nextRight(tmp);
		doLastTwoOnEdge(w, ntLast, last, tmp, emergency);

		/* right side */
		for (i = ur + w->cubes.sizeX; i < lr - 2 * w->cubes.sizeX;
				i += w->cubes.sizeX) {
			movePiece(w, findPiece(w, targetM[i]), i);
			locked[i] = True;
		}

		ntLast = i;
		last = i + w->cubes.sizeX;
		tmp = LR_Z(layer - 1);
		emergency = nextLeft(tmp);
		doLastTwoOnEdge(w, ntLast, last, tmp, emergency);
	}
}

static void
solveLayerY(CubesWidget w, int layer)
{
	int i, tmp, last, ntLast, emergency;
	int ul, ur, ll, lr;

	if (layer == 0) {
		solveLayerY0(w);
	} else {
		/* find and put each of the corners into place */
		ul = UL_Y(layer);
		ur = UR_Y(layer);
		ll = LL_Y(layer);
		lr = LR_Y(layer);

		movePiece(w, findPiece(w, targetM[ul]), ul);
		locked[ul] = True;
		movePiece(w, findPiece(w, targetM[ur]), ur);
		locked[ur] = True;
		movePiece(w, findPiece(w, targetM[ll]), ll);
		locked[ll] = True;
		movePiece(w, findPiece(w, targetM[lr]), lr);
		locked[lr] = True;

		/*
		 * Strategy for doing the pieces between the corners:
		 * (1) put all but the last two edge pieces in place;
		 * (2) put the next to the last piece next to the
		 *	corner;
		 * (3) put the last piece one move in from its final
		 *	position;
		 * (4) move the space to the final position of the
		 *	next to the last piece;
		 * (5) slide the next to the last piece over and the
		 *	last piece into the edge where it goes.
		 */

		/* inner edge */
		for (i = ul + 1; i < ur - 2; i++) {
			movePiece(w, findPiece(w, targetM[i]), i);
			locked[i] = True;
		}

		ntLast = i;
		last = i + 1;
		tmp = UR_Y(layer - 1);
		emergency = nextOut(tmp);
		doLastTwoOnEdge(w, ntLast, last, tmp, emergency);

		/* outer edge */
		for (i = ll + 1; i < lr - 2; i++) {
			movePiece(w, findPiece(w, targetM[i]), i);
			locked[i] = True;
		}

		ntLast = i;
		last = i + 1;
		tmp = LR_Y(layer - 1);
		emergency = nextIn(tmp);
		doLastTwoOnEdge(w, ntLast, last, tmp, emergency);

		/* left side */
		for (i = ul + w->cubes.sizeX; i < ll - 2 * w->cubes.sizeX;
				i += w->cubes.sizeX) {
			movePiece(w, findPiece(w, targetM[i]), i);
			locked[i] = True;
		}

		ntLast = i;
		last = i + w->cubes.sizeX;
		tmp = LL_Y(layer - 1);
		emergency = nextRight(tmp);
		doLastTwoOnEdge(w, ntLast, last, tmp, emergency);

		/* right side */
		for (i = ur + w->cubes.sizeX; i < lr - 2 * w->cubes.sizeX;
				i += w->cubes.sizeX) {
			movePiece(w, findPiece(w, targetM[i]), i);
			locked[i] = True;
		}

		ntLast = i;
		last = i + w->cubes.sizeX;
		tmp = LR_Y(layer - 1);
		emergency = nextLeft(tmp);
		doLastTwoOnEdge(w, ntLast, last, tmp, emergency);
	}
}

static void
solveLayerX(CubesWidget w, int layer)
{
	int i, tmp, last, ntLast, emergency;
	int ul, ur, ll, lr;

	if (layer == 0) {
		solveLayerX0(w);
	} else {
		/* find and put each of the corners into place */
		ul = UL_X(layer);
		ur = UR_X(layer);
		ll = LL_X(layer);
		lr = LR_X(layer);

		movePiece(w, findPiece(w, targetM[ul]), ul);
		locked[ul] = True;
		movePiece(w, findPiece(w, targetM[ur]), ur);
		locked[ur] = True;
		movePiece(w, findPiece(w, targetM[ll]), ll);
		locked[ll] = True;
		movePiece(w, findPiece(w, targetM[lr]), lr);
		locked[lr] = True;

		/*
		 * Strategy for doing the pieces between the corners:
		 * (1) put all but the last two edge pieces in place;
		 * (2) put the next to the last piece next to the
		 *	corner;
		 * (3) put the last piece one move in from its final
		 *	position;
		 * (4) move the space to the final position of the
		 *	next to the last piece;
		 * (5) slide the next to the last piece over and the
		 *	last piece into the edge where it goes.
		 */

		/* inner edge */
		for (i = ul + 1; i < ur - 2; i++) {
			movePiece(w, findPiece(w, targetM[i]), i);
			locked[i] = True;
		}

		ntLast = i;
		last = i + 1;
		tmp = UR_X(layer - 1);
		emergency = nextOut(tmp);
		doLastTwoOnEdge(w, ntLast, last, tmp, emergency);

		/* outer edge */
		for (i = ll + 1; i < lr - 2; i++) {
			movePiece(w, findPiece(w, targetM[i]), i);
			locked[i] = True;
		}

		ntLast = i;
		last = i + 1;
		tmp = LR_X(layer - 1);
		emergency = nextIn(tmp);
		doLastTwoOnEdge(w, ntLast, last, tmp, emergency);

		/* top edge */
		for (i = ul + w->cubes.sizeY; i < ll - 2 * w->cubes.sizeY;
				i += w->cubes.sizeY) {
			movePiece(w, findPiece(w, targetM[i]), i);
			locked[i] = True;
		}

		ntLast = i;
		last = i + w->cubes.sizeY;
		tmp = LL_X(layer - 1);
		emergency = nextDown(tmp);
		doLastTwoOnEdge(w, ntLast, last, tmp, emergency);

		/* bottom edge */
		for (i = ur + w->cubes.sizeY; i < lr - 2 * w->cubes.sizeY;
				i += w->cubes.sizeY) {
			movePiece(w, findPiece(w, targetM[i]), i);
			locked[i] = True;
		}

		ntLast = i;
		last = i + w->cubes.sizeY;
		tmp = LR_X(layer - 1);
		emergency = nextUp(tmp);
		doLastTwoOnEdge(w, ntLast, last, tmp, emergency);
	}
}

static void
solveRowZ(CubesWidget w, int row, int z)
{
	int i, loc, last, ntLast, tmp, emergency;

	for (i = 0; i < w->cubes.sizeX - 2; i++) {
		loc = toPosition(i, row, z);
		movePiece(w, findPiece(w, targetM[loc]), loc);
		locked[loc] = True;
	}
	ntLast = toPosition(w->cubes.sizeX - 2, row, z);
	last = toPosition(w->cubes.sizeX - 1, row, z);
	tmp = last + w->cubes.sizeX;
	emergency = tmp + w->cubes.sizeX;
	doLastTwoOnEdge(w, ntLast, last, tmp, emergency);
}

static void
solveColumnZ(CubesWidget w, int column, int z)
{
	int i, loc, last, ntLast, tmp, emergency;

	for (i = 0; i < w->cubes.sizeY - 2; i++) {
		loc = toPosition(column, i, z);
		movePiece(w, findPiece(w, targetM[loc]), loc);
		locked[loc] = True;
	}
	ntLast = toPosition(column, w->cubes.sizeY - 2, z);
	last = toPosition(column, w->cubes.sizeY - 1, z);
	tmp = last + 1;
	emergency = tmp + 1;
	doLastTwoOnEdge(w, ntLast, last, tmp, emergency);
}

static void
solveStackY(CubesWidget w, int stack, int y)
{
	int i, loc, last, ntLast, tmp, emergency;

	for (i = 0; i < w->cubes.sizeX - 2; i++) {
		loc = toPosition(i, y, stack);
		movePiece(w, findPiece(w, targetM[loc]), loc);
		locked[loc] = True;
	}
	ntLast = toPosition(w->cubes.sizeX - 2, y, stack);
	last = toPosition(w->cubes.sizeX - 1, y, stack);
	tmp = last + w->cubes.sizeX;
	emergency = tmp + w->cubes.sizeX;
	doLastTwoOnEdge(w, ntLast, last, tmp, emergency);
}

static void
solveColumnY(CubesWidget w, int column, int y)
{
	int i, loc, last, ntLast, tmp, emergency;

	for (i = 0; i < w->cubes.sizeZ - 2; i++) {
		loc = toPosition(column, y, i);
		movePiece(w, findPiece(w, targetM[loc]), loc);
		locked[loc] = True;
	}
	ntLast = toPosition(column, y, w->cubes.sizeZ - 2);
	last = toPosition(column, y, w->cubes.sizeZ - 1);
	tmp = last + 1;
	emergency = tmp + 1;
	doLastTwoOnEdge(w, ntLast, last, tmp, emergency);
}

static void
solveStackX(CubesWidget w, int stack, int x)
{
	int i, loc, last, ntLast, tmp, emergency;

	for (i = 0; i < w->cubes.sizeY - 2; i++) {
		loc = toPosition(x, i, stack);
		movePiece(w, findPiece(w, targetM[loc]), loc);
		locked[loc] = True;
	}
	ntLast = toPosition(x, w->cubes.sizeY - 2, stack);
	last = toPosition(x, w->cubes.sizeY - 1, stack);
	tmp = last + w->cubes.sizeY;
	emergency = tmp + w->cubes.sizeY;
	doLastTwoOnEdge(w, ntLast, last, tmp, emergency);
}

static void
solveRowX(CubesWidget w, int row, int x)
{
	int i, loc, last, ntLast, tmp, emergency;

	for (i = 0; i < w->cubes.sizeZ - 2; i++) {
		loc = toPosition(x, row, i);
		movePiece(w, findPiece(w, targetM[loc]), loc);
		locked[loc] = True;
	}
	ntLast = toPosition(x, row, w->cubes.sizeZ - 2);
	last = toPosition(x, row, w->cubes.sizeZ - 1);
	tmp = last + 1;
	emergency = tmp + 1;
	doLastTwoOnEdge(w, ntLast, last, tmp, emergency);
}

/* This procedure coordinates the solution process. */
static void
solveSinglePlaneZ(CubesWidget w, int plane)
{
	int i;

	/* solve the extra rows and columns */
	for (i = 0; i < extraRows; i++)
		solveRowZ(w, i, plane);
	for (i = 0; i < extraColumns; i++)
		solveColumnZ(w, i, plane);

	/* solve each layer */
	for (i = layers - 1; i >= 0; i--) {
		solveLayerZ(w, i);
	}
	/* move the space back out to the LR_Z corner; */
	/* i is the layer the space is moving into */
	for (i = 1; i < layers; i++) {
		moveSpace(w, BOTTOM, 1);
		moveSpace(w, RIGHT, 1);
	}
}

static void
solveSinglePlaneY(CubesWidget w, int plane)
{
	int i;

	/* solve the extra stacks and columns */
	for (i = 0; i < extraStacks; i++)
		solveStackY(w, i, plane);
	for (i = 0; i < extraColumns; i++)
		solveColumnY(w, i, plane);

	/* solve each layer */
	for (i = layers - 1; i >= 0; i--) {
		solveLayerY(w, i);
	}
	/* move the space back out to the LR_Y corner; */
	/* i is the layer the space is moving into */
	for (i = 1; i < layers; i++) {
		moveSpace(w, OUTWARDS, 1);
		moveSpace(w, RIGHT, 1);
	}
}

static void
solveSinglePlaneX(CubesWidget w, int plane)
{
	int i;

	/* solve the extra stacks and rows */
	for (i = 0; i < extraStacks; i++)
		solveStackX(w, i, plane);
	for (i = 0; i < extraRows; i++)
		solveRowX(w, i, plane);

	/* solve each layer */
	for (i = layers - 1; i >= 0; i--) {
		solveLayerX(w, i);
	}
	/* move the space back out to the LR_X corner; */
	/* i is the layer the space is moving into */
	for (i = 1; i < layers; i++) {
		moveSpace(w, OUTWARDS, 1);
		moveSpace(w, BOTTOM, 1);
	}
}

void
solveSomeBlocks(CubesWidget w)
{
	int i;

	if (sizeX != w->cubes.sizeX || sizeY != w->cubes.sizeY
			|| sizeZ != w->cubes.sizeZ) {
		myFree();
		myInitialize(w);
	}
	setPuzzle(w, ACTION_RESET);
	/*
	 * determine the position we want to be in when
	 * we are done; This position will have the space in
	 * the center;  Then, we'll move the space back to
	 * the outside.
	 */
	if (solvingFlag)
		return;

#ifdef JMP
	if (!setjmp(solve_env))
#endif
	if (w->cubes.sizeY == 1 && w->cubes.sizeZ == 1)
		moveSpace(w, RIGHT, w->cubes.sizeX - spaceX - 1);
	else if (w->cubes.sizeX == 1 && w->cubes.sizeZ == 1)
		moveSpace(w, BOTTOM, w->cubes.sizeY - spaceY - 1);
	else if (w->cubes.sizeX == 1 && w->cubes.sizeY == 1)
		moveSpace(w, OUTWARDS, w->cubes.sizeZ - spaceZ - 1);
	else if (w->cubes.sizeZ == 1) {
		solvingFlag = True;
		solveSinglePlaneZ(w, 0);
	} else if (w->cubes.sizeY == 1) {
		solvingFlag = True;
		solveSinglePlaneY(w, 0);
	} else if (w->cubes.sizeX == 1) {
		solvingFlag = True;
		solveSinglePlaneX(w, 0);
	} else { /* This fails but for 3x3x3 solves a few tiles */
		solvingFlag = True;
		for (i = 0; i < w->cubes.sizeZ; i++)
			solveSinglePlaneZ(w, i);
	}
#ifdef JMP
	else {
		drawAllBlocks(w);
	}
	abortSolvingFlag = False;
#endif
	for (i = 0; i < w->cubes.sizeBlock; i++)
		locked[i] = False;
	solvingFlag = False;
	w->cubes.cheat = True; /* Assume the worst. */
	setPuzzle(w, ACTION_COMPUTED);
}
