/*
 * @(#)CubesS.c
 *
 * Taken from the X puzzle by Don Bennett, HP Labs
 *
 * Copyright 2003 - 2008  David A. Bagley, bagleyd@tux.org
 *
 * 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 < 4x4 and 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	4 /* not 6 for 3D yet */

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

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

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

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

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

#define UL(l) (layerDepth(l)*(PUZZLE_SIZE+1)+\
  extraRows*w->cubes.sizeX + extraColumns*(layers-(l)))
#define UR(l) (layerDepth(l)*(PUZZLE_SIZE+1)+layerWidth(l)-1+\
  extraRows*w->cubes.sizeX+extraColumns*(layers-(l)))
#define LL(l) ((layerDepth(l)+layerWidth(l)-1)*PUZZLE_SIZE+layerDepth(l)+\
  extraRows*PUZZLE_SIZE+extraColumns*(w->cubes.sizeY+1+(l)-layers))
#define LR(l) ((layerDepth(l)+layerWidth(l)-1)*(PUZZLE_SIZE+1)+\
  extraRows*PUZZLE_SIZE+extraColumns*(w->cubes.sizeY+1+(l)-layers))

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

#define toColumn(loc)	((loc)%w->cubes.sizeX)
#define toRow(loc)	((loc)/w->cubes.sizeX)
#define toPosition(x,y)	(((y)*w->cubes.sizeX)+(x))
#define spaceX	toColumn(w->cubes.spacePosition)
#define spaceY	toRow(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)

static int sizeX = 0, sizeY = 0;
static int extraRows = 0;
static int extraColumns = 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.sizeRect; i++)
		if (w->cubes.blockOfPosition[i] == piece)
			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 lastX, int lastY, int dir)
{
	int count = ABS(firstX - lastX) + ABS(firstY - lastY);

	animateSlide(w, count + 1, dir, NORMAL, True);
}

static void
moveSpace(CubesWidget w, int direction, int distance)
{
	int i, step, count;
	int firstX, firstY, lastX, lastY, shiftDir;
	int tempSpaceX = spaceX, tempSpaceY = spaceY;
	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;
	}
	if (dir == TOP) {
		dir = BOTTOM;
		dist = -dist;
	}
	firstX = spaceX;
	firstY = spaceY;
	step = 1;
	count = dist;
	if (dist < 0) {
		step = -1;
		count = -count;
	}

	/* firstX,Y are the location of the first piece to be shifted */
	if (dir == RIGHT)
		firstX += step;
	else
		firstY += 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 { /* dir == BOTTOM */
			tempSpaceY += step;
		}
	}
	lastX = tempSpaceX;
	lastY = tempSpaceY;

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

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

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

	for (j = 0; j < w->cubes.sizeY; j++) {
		for (i = 0; i < w->cubes.sizeX; i++)
			(void) printf(" %2d ",(*mat)[toPosition(i, j)]);
		(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;
	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.sizeRect; 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);
		locX = toColumn(nextLoc);
		locY = toRow(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;
		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
	print_matrix(w, &(w->cubes.blockOfPosition));
	print_matrix(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, ") 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, "), 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;
		}
	}
}

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), 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;
		}
}

/* 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;

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

	layers = PUZZLE_SIZE >> 1;

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

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

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

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

	for (i = 0; i < w->cubes.sizeRect - 1; i++) {
		targetM[i] = i + 1;
	}
	targetM[w->cubes.sizeRect - 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;

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

		/* move the space up one; */
		targetM[toPosition(spX, spY)] =
			targetM[toPosition(spX, (spY - 1))];
		targetM[toPosition(spX, (spY - 1))] = 0;
		spY -= 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
solveLayer0(CubesWidget w)
{
	movePiece(w, findPiece(w, targetM[UL(0)]), UL(0));
	myMoveSpaceTo(w, LR(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
solveLayer(CubesWidget w, int layer)
{
	int i, tmp, last, ntLast, emergency;
	int ul, ur, ll, lr;

	if (layer == 0) {
		solveLayer0(w);
	} else {
		/* find and put each of the corners into place */
		ul = UL(layer);
		ur = UR(layer);
		ll = LL(layer);
		lr = LR(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(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(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(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(layer - 1);
		emergency = nextLeft(tmp);
		doLastTwoOnEdge(w, ntLast, last, tmp, emergency);
	}
}

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

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

static void
solveCol(CubesWidget w, int col)
{
	int i, loc, last, ntLast, tmp, emergency;

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

/* This procedure coordinates the solution process. */
void
solveSomeBlocks(CubesWidget w)
{
	int i;

	if (sizeX != w->cubes.sizeX || sizeY != w->cubes.sizeY) {
		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
	{
		solvingFlag = True;
		for (i = 0; i < w->cubes.sizeRect; i++)
			locked[i] = False;
		/* solve the extra rows and cols */
		for (i = 0; i < extraRows; i++)
			solveRow(w, i);
		for (i = 0; i < extraColumns; i++)
			solveCol(w, i);

		/* solve each layer */
		for (i = layers - 1; i >= 0; i--) {
			solveLayer(w, i);
		}
		/* move the space back out to the LR corner; */
		/* i is the layer the space is moving into */
		for (i = 1; i < layers; i++) {
			moveSpace(w, BOTTOM, 1);
			moveSpace(w, RIGHT, 1);
		}
	}
#ifdef JMP
	else {
		drawAllBlocks(w);
	}
	abortSolvingFlag = False;
#endif
	for (i = 0; i < w->cubes.sizeRect; i++)
		locked[i] = False;
	solvingFlag = False;
	w->cubes.cheat = True; /* Assume the worst. */
        setPuzzle(w, ACTION_COMPUTED);
}