/*
 * @(#)OctS.c
 *
 * Break ability taken from the X puzzle by Don Bennett, HP Labs
 *
 * Copyright 2010 - 2013  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.
 */

/* Solver file for Oct */

#include "rngs.h"
#define JMP
#ifdef JMP
#include <setjmp.h> /* longjmp ... interrupt */
#endif
#include "OctP.h"

#define MAX_CORNERS 6

static int indexToEdges[3] = {3, 6, 1};
static int indexToEdgesMate[3] = {1, 6, 3};
static int edgesToIndex[9] = {3, 2, 3, 0, 3, 3, 1, 3, 3};
static int edgeMateFace[MAX_FACES][3] =
{
	{3, 6, 1}, {0, 5, 2}, {1, 4, 3}, {2, 7, 0},
	{7, 2, 5}, {4, 1, 6}, {5, 0, 7}, {6, 3, 4}
};
static int facesAtCorner[MAX_CORNERS][4] =
{
	{0, 1, 2, 3},
	{0, 6, 5, 1}, {1, 5, 4, 2}, {2, 4, 7, 3}, {3, 7, 6, 0},
	{6, 7, 4, 5}
};
static int orientAtCorner[MAX_CORNERS][4] =
{
	{0, 0, 0, 0},
	{2, 1, 2, 1}, {2, 1, 2, 1}, {2, 1, 2, 1}, {2, 1, 2, 1},
	{0, 0, 0, 0}
};
static int facesToCorner[MAX_FACES][3] =
{
	{0, 4, 1}, {0, 1, 2}, {0, 2, 3}, {0, 3, 4},
	{5, 3, 2}, {5, 2, 1}, {5, 1, 4}, {5, 4, 3},
};
static int faceCornerToOther[MAX_FACES][3][3] =
{
	{{1, 2, 3}, {3, 7, 6}, {6, 5, 1}},
	{{2, 3, 0}, {0, 6, 5}, {5, 4, 2}},
	{{3, 0, 1}, {1, 5, 4}, {4, 7, 3}},
	{{0, 1, 2}, {2, 4, 7}, {7, 6, 0}},
	{{5, 6, 7}, {7, 3, 2}, {2, 1, 5}},
	{{6, 7, 4}, {4, 2, 1}, {1, 0, 6}},
	{{7, 4, 5}, {5, 1, 0}, {0, 3, 7}},
	{{4, 5, 6}, {6, 0, 3}, {3, 2, 4}}
};
static int orientCornerToOther[3][3] =
{
	{0, 0, 0}, {2, 1, 2}, {1, 2, 1}
};

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(OctWidget 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(OctWidget w)
{
	XEvent event;

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

static void
movePuzzlePiece(OctWidget w, int face, int position,
	int direction, int style, int control)
{
#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
	movePuzzleDelay(w, face, position, direction, style, control);
}

static int
orientToLittlePosition(OctWidget w, int orient)
{
	if (orient == 0) {
		return 0;
	} else if (orient == 1) {
		return w->oct.sizeSize - 1;
	} else /* if (orient == 2) */ {
		return w->oct.sizeSize - 2 * w->oct.size + 1;
	}
}

static int
orientToBigPosition(OctWidget w, int orient)
{
	if (orient == 0) {
		return 2;
	} else if (orient == 1) {
		return w->oct.sizeSize - 2;
	} else /* if (orient == 2) */ {
		return w->oct.sizeSize - 2 * w->oct.size + 2;
	}
}

static void
rotateCornerCW(OctWidget w, int corner)
{
	int face = facesAtCorner[corner][3];
	int position = orientToBigPosition(w, orientAtCorner[corner][3]);

	if (corner == 0 || corner == 5)
		movePuzzlePiece(w, face, position, CW, PERIOD4, FALSE);
	else
		movePuzzlePiece(w, face, position,
			((TL / 2 + corner - 1) % 4 * 2 + TR), PERIOD4, FALSE);
}

static void
rotateCornerCCW(OctWidget w, int corner)
{
	int face = facesAtCorner[corner][0];
	int position = orientToBigPosition(w, orientAtCorner[corner][0]);

	if (corner == 0 || corner == 5)
		movePuzzlePiece(w, face, position, CCW, PERIOD4, FALSE);
	else
		movePuzzlePiece(w, face, position,
			((BR / 2 + corner - 1) % 4 * 2 + TR), PERIOD4, FALSE);
}

static void
rotateCornerHalf(OctWidget w, int corner)
{
	if (NRAND(2) == 0) {
		rotateCornerCW(w, corner);
		rotateCornerCW(w, corner);
	} else {
		rotateCornerCCW(w, corner);
		rotateCornerCCW(w, corner);
	}
}

static void
rotatePuzzleCW(OctWidget w, int corner)
{
	int face = facesAtCorner[corner][3];
	int position = orientToBigPosition(w, orientAtCorner[corner][3]);

	if (corner == 0 || corner == 5)
		movePuzzlePiece(w, face, position, CW, PERIOD4, TRUE);
	else
		movePuzzlePiece(w, face, position,
			((TL / 2 + corner - 1) % 4 * 2 + TR), PERIOD4, TRUE);
}

static void
rotatePuzzleCCW(OctWidget w, int corner)
{
	int face = facesAtCorner[corner][0];
	int position = orientToBigPosition(w, orientAtCorner[corner][0]);

	if (corner == 0 || corner == 5)
		movePuzzlePiece(w, face, position, CCW, PERIOD4, TRUE);
	else
		movePuzzlePiece(w, face, position,
			((BR / 2 + corner - 1) % 4 * 2 + TR), PERIOD4, TRUE);
}

static void
rotatePuzzleHalf(OctWidget w, int corner)
{
	if (NRAND(2) == 0) {
		rotatePuzzleCW(w, corner);
		rotatePuzzleCW(w, corner);
	} else {
		rotatePuzzleCCW(w, corner);
		rotatePuzzleCCW(w, corner);
	}
}

static void
rotateLittleCornerCW(OctWidget w, int corner)
{
	int face = facesAtCorner[corner][3];
	int position = orientToLittlePosition(w, orientAtCorner[corner][3]);

	if (corner == 0 || corner == 5)
		movePuzzlePiece(w, face, position, CW, PERIOD4, FALSE);
	else
		movePuzzlePiece(w, face, position,
			((TL / 2 + corner - 1) % 4 * 2 + TR), PERIOD4, FALSE);
}

static void
rotateLittleCornerCCW(OctWidget w, int corner)
{
	int face = facesAtCorner[corner][0];
	int position = orientToLittlePosition(w, orientAtCorner[corner][0]);

	if (corner == 0 || corner == 5)
		movePuzzlePiece(w, face, position, CCW, PERIOD4, FALSE);
	else
		movePuzzlePiece(w, face, position,
			((BR / 2 + corner - 1) % 4 * 2 + TR), PERIOD4, FALSE);
}

static void
rotateLittleCornerHalf(OctWidget w, int corner)
{
	if (NRAND(2) == 0) {
		rotateLittleCornerCW(w, corner);
		rotateLittleCornerCW(w, corner);
	} else {
		rotateLittleCornerCCW(w, corner);
		rotateLittleCornerCCW(w, corner);
	}
}

/* This is impossible to do with Drag and Drop as implemented.
 * Use the keypad.  Turn the little corners so that the
 * colors match the adjacent pieces all around. */
static void
orientLittleCorners(OctWidget w, int corner)
{
	int face = facesAtCorner[corner][0];
	int orient = orientAtCorner[corner][0];
	int littlePosition = orientToLittlePosition(w, orient);
	int bigPosition = orientToBigPosition(w, orient);
	int littleColor = w->oct.facetLoc[face][littlePosition].face;
	int bigColor = w->oct.facetLoc[face][bigPosition].face;

	if (littleColor == bigColor) {
		return;
	}
	face = facesAtCorner[corner][1];
	orient = orientAtCorner[corner][1];
	bigPosition = orientToBigPosition(w, orient);
	bigColor = w->oct.facetLoc[face][bigPosition].face;
	if (littleColor == bigColor) {
		rotateLittleCornerCW(w, corner);
		return;
	}
	face = facesAtCorner[corner][2];
	orient = orientAtCorner[corner][2];
	bigPosition = orientToBigPosition(w, orient);
	bigColor = w->oct.facetLoc[face][bigPosition].face;
	if (littleColor == bigColor) {
		rotateLittleCornerHalf(w, corner);
		return;
	}
	face = facesAtCorner[corner][3];
	orient = orientAtCorner[corner][3];
	bigPosition = orientToBigPosition(w, orient);
	bigColor = w->oct.facetLoc[face][bigPosition].face;
	if (littleColor == bigColor) {
		rotateLittleCornerCCW(w, corner);
		return;
	}
	(void) printf("no match %d\n", corner);
}

static int
findFaceColor(OctWidget w, int face)
{
	int colors[8];
	int point, color;

	for (color = 0; color < MAX_FACES; color++)
		colors[color] = 0;
	for (point = 0; point < 3; point++) {
		int side;
		int corner = facesToCorner[face][point];

		for (side = 0; side < 4; side++) {
			int otherFace = facesAtCorner[corner][side];
			int position = orientToBigPosition(w,
				orientAtCorner[corner][side]);

			color = w->oct.facetLoc[otherFace][position].face;
			colors[color]++;
			if (colors[color] == 3) {
#ifdef DEBUG
				(void) printf("Color for face %d is %d\n",
					face, color);
#endif
				return color;
			}
		}
	}
	(void) printf("No color found for %d\n", face);
	return MAX_FACES;
}

static void
faceCorner(OctWidget w, int face, int faceColor, int point)
{
	int side;
	int corner = facesToCorner[face][point];
	int otherFace = face;
	int otherOrient = point;

	for (side = 0; side < 4; side++) {
		int position = orientToBigPosition(w, otherOrient);

		if (faceColor == w->oct.facetLoc[otherFace][position].face) {
			if (side == 1)
				rotateCornerCCW(w, corner);
			else if (side == 3)
				rotateCornerCW(w, corner);
			else if (side == 2)
				rotateCornerHalf(w, corner);
			return;
		} else if (side < 3) {
			otherFace = faceCornerToOther[face][point][side];
			otherOrient = orientCornerToOther[point][side];
		}
	}
}

static void
faceCorners(OctWidget w, int face, int faceColor)
{
	int point;

	for (point = 0; point < 3; point++) {
		faceCorner(w, face, faceColor, point);
	}
}

static void
faceLittleCorners(OctWidget w)
{
	int point;

	for (point = 0; point < 3; point++) {
		orientLittleCorners(w, facesToCorner[0][point]);
	}
}

static void
allLittleCorners(OctWidget w)
{
	int corner;

	for (corner = 0; corner < MAX_CORNERS; corner++) {
		orientLittleCorners(w, corner);
	}
}

static Boolean
checkPiece(OctWidget w, int color, int face, int position)
{
	int newFace, newPosition, positionIndex;

	positionIndex = edgesToIndex[position];
	if (positionIndex == 3) {
		positionIndex = 0;
		(void) printf("position %d incorrect\n", position);
	}
	newFace = edgeMateFace[face][positionIndex];
	newPosition = indexToEdgesMate[positionIndex];
	if (w->oct.facetLoc[newFace][newPosition].face == color) {
		return True;
	}
	return False;
}

static void
findPiece(OctWidget w, int color0, int color1, int *face, int *position)
{
	int positionIndex;

	for (*face = 0; *face < MAX_FACES; (*face)++) {
		for (positionIndex = 0; positionIndex < 3; positionIndex++) {
			*position = indexToEdges[positionIndex];
			if (w->oct.facetLoc[*face][*position].face == color0 &&
					checkPiece(w, color1, *face, *position)) {
				return;
			}
		}
	}
	(void) printf("Piece %d %d not found!\n", color0, color1);
}

static Boolean
onFace(int target, int face, int position)
{
	int side;

	if (face == target)
		return True;
	for (side = 0; side < 3; side++) {
		if (face == edgeMateFace[target][side] &&
				position == indexToEdgesMate[side])
			return True;
	}
	return False;
}

static Boolean
bottomRing(int face, int position)
{
	return ((face > 3) && position != 6);
}

static Boolean
rightRing(int face, int position)
{
	if  ((face == 1 || face == 2 || face == 4 || face == 5) &&
			 position == 6)
		return True;
	if  ((face == 1 && position == 1) ||
			(face == 2 && position == 3) ||
			(face == 4 && position == 1) ||
			(face == 5 && position == 3))
		return True;
	return False;
}

static Boolean
leftRing(int face, int position)
{
	if  ((face == 2 || face == 3 || face == 4 || face == 7) &&
			 position == 6)
		return True;
	if  ((face == 2 && position == 1) ||
			(face == 3 && position == 3) ||
			(face == 4 && position == 3) ||
			(face == 7 && position == 1))
		return True;
	return False;
}

static void
face0Edge6(OctWidget w, int matchFace, int faceColor)
{
	int otherColor, face, position, matchPosition;

	matchPosition = 6;
	/* need other color */
	face = edgeMateFace[matchFace][1];
	position = matchPosition - 1; /* this is a solved piece */
	otherColor = w->oct.facetLoc[face][position].face;

	/* face and position variables are reused here */
	findPiece(w, faceColor, otherColor, &face, &position);
	if (onFace(0, face, position)) { /* 1/4 of possible */
		if (face == 0) {
			if (position == 1) {
				rotateCornerCW(w, 4);
				rotateCornerCCW(w, 0);
				rotateCornerCCW(w, 4);
				rotateCornerCW(w, 0);
			} else if (position == 3) {
				rotateCornerCCW(w, 1);
				rotateCornerCW(w, 0);
				rotateCornerCW(w, 1);
				rotateCornerCCW(w, 0);
			}
		} else if (face == 1) {
			rotateCornerCW(w, 1);
			rotateCornerCCW(w, 4);
			rotateCornerCCW(w, 1);
			rotateCornerCW(w, 4);
		} else if (face == 3) {
			rotateCornerCCW(w, 4);
			rotateCornerCW(w, 1);
			rotateCornerCW(w, 4);
			rotateCornerCCW(w, 1);
		} else { /* correct but flip */
			if (NRAND(2) == 0) {
				rotateCornerCW(w, 1);
				rotateCornerCW(w, 5);
				rotateCornerCCW(w, 1);
				rotateCornerCW(w, 4);
				rotateCornerCCW(w, 1);
				rotateCornerCCW(w, 4);
				rotateCornerCW(w, 1);
			} else {
				rotateCornerCCW(w, 4);
				rotateCornerCCW(w, 5);
				rotateCornerCW(w, 4);
				rotateCornerCCW(w, 1);
				rotateCornerCW(w, 4);
				rotateCornerCW(w, 1);
				rotateCornerCCW(w, 4);
			}
		}
		return;
	}
	if (leftRing(face, position)) {
		if  ((face == 3 || face == 7) && position == 6)
			rotateCornerCCW(w, 3);
		else if  ((face == 3 && position == 3) ||
				(face == 2 && position == 1))
			rotateCornerHalf(w, 3);
		else if  ((face == 2 || face == 4) && position == 6)
			rotateCornerCW(w, 3);
	} else if (rightRing(face, position)) {
		if  ((face == 1 || face == 5) && position == 6)
			rotateCornerCW(w, 2);
		else if  ((face == 1 && position == 1) ||
				(face == 2 && position == 3))
			rotateCornerHalf(w, 2);
		else if  ((face == 2 || face == 4) && position == 6)
			rotateCornerCCW(w, 2);
	}
	findPiece(w, faceColor, otherColor, &face, &position);
	if (!bottomRing(face, position)) {
		(void) printf("not in bottom ring is not possible\n");
		return;
	}
	if (face == 4) {
		rotateCornerHalf(w, 5);
	} else if (face == 7) {
		rotateCornerCCW(w, 5);
	} else if (face == 5) {
		rotateCornerCW(w, 5);
	}
	if (position == 3) {
		rotateCornerCCW(w, 1);
		rotateCornerCW(w, 4);
		rotateCornerCW(w, 1);
		rotateCornerCCW(w, 4);
	} else {
		rotateCornerCW(w, 4);
		rotateCornerCCW(w, 1);
		rotateCornerCCW(w, 4);
		rotateCornerCW(w, 1);
	}
}

static void
face0Edge1(OctWidget w, int matchFace, int faceColor)
{
	int otherColor, face, position, matchPosition;
	Boolean swap = False;

	matchPosition = 1;
	/* need other color */
	face = edgeMateFace[matchFace][2];
	position = matchPosition + 1; /* this is a solved piece */
	otherColor = w->oct.facetLoc[face][position].face;

	/* face and position variables are reused here */
	findPiece(w, faceColor, otherColor, &face, &position);
	if (onFace(0, face, position)) { /* 1/4 of possible */
		if (face == 0 && position == 1) {
			return;
		}
		if (face == 1) {
			rotateCornerCW(w, 0);
			rotateCornerCW(w, 2);
			rotateCornerCCW(w, 0);
		} else {
			rotateCornerHalf(w, 0);
			rotateCornerCW(w, 2);
			rotateCornerHalf(w, 0);
		}
		findPiece(w, faceColor, otherColor, &face, &position);
	}
	if (leftRing(face, position)) {
		if ((face == 3 || face == 7) && position == 6)
			rotateCornerHalf(w, 3);
		else if ((face == 2 && position == 1) || face == 3)
			rotateCornerCW(w, 3);
		else if ((face == 4 && position == 3) || face == 7)
			rotateCornerCCW(w, 3);
		findPiece(w, faceColor, otherColor, &face, &position);
	} else if (bottomRing(face, position)) {
		if ((face == 7 && position == 3) ||
				(face == 6 && position == 1))
			rotateCornerHalf(w, 5);
		else if ((face == 4 && position == 3) ||
				(face == 7 && position == 1))
			rotateCornerCW(w, 5);
		else if ((face == 6 && position == 3) ||
				(face == 5 && position == 1))
			rotateCornerCCW(w, 5);
		findPiece(w, faceColor, otherColor, &face, &position);
	}
	if (!rightRing(face, position)) {
		(void) printf("not in rightRing is not possible\n");
		return;
	}
	if (face == 4) {
		rotateCornerHalf(w, 2);
	} else if (face == 2) {
		rotateCornerCW(w, 2);
		swap = True;
	} else if (face == 5) {
		rotateCornerCCW(w, 2);
		swap = True;
	}
	if ((position == 6 && !swap) || (position != 6 && swap)) {
		rotateCornerCW(w, 1);
		rotateCornerCCW(w, 0);
		rotateCornerCCW(w, 1);
		rotateCornerCW(w, 0);
	} else {
		rotateCornerCCW(w, 0);
		rotateCornerCW(w, 1);
		rotateCornerCW(w, 0);
		rotateCornerCCW(w, 1);
	}
}

static void
face0Edge3(OctWidget w, int matchFace, int faceColor)
{
	int otherColor, face, position, matchPosition;
	Boolean swap = False;

	matchPosition = 3;
	/* need other color */
	face = edgeMateFace[matchFace][0];
	position = matchPosition - 1; /* this is a solved piece */
	otherColor = w->oct.facetLoc[face][position].face;

	/* face and position variables are reused here */
	findPiece(w, faceColor, otherColor, &face, &position);
	if (onFace(0, face, position)) { /* 1/4 of possible */
		if (face == 0 && position == 3) {
			return;
		}
		/* face == 3 */
		rotateCornerCCW(w, 0);
		rotateCornerCCW(w, 3);
		rotateCornerCW(w, 0);
		findPiece(w, faceColor, otherColor, &face, &position);
	}
	if (rightRing(face, position)) {
		if ((face == 1 || face == 5) && position == 6)
			rotateCornerHalf(w, 2);
		else if ((face == 2 && position == 3) || face == 1)
			rotateCornerCCW(w, 2);
		else if ((face == 4 && position == 1) || face == 5)
			rotateCornerCW(w, 2);
		findPiece(w, faceColor, otherColor, &face, &position);
	} else if (bottomRing(face, position)) {
		if ((face == 5 && position == 1) ||
				(face == 6 && position == 3))
			rotateCornerHalf(w, 5);
		else if ((face == 4 && position == 1) ||
				(face == 5 && position == 3)) {
			rotateCornerCCW(w, 5);
		} else if ((face == 6 && position == 1) ||
				(face == 7 && position == 3)) {
			rotateCornerCW(w, 5);
		}
		findPiece(w, faceColor, otherColor, &face, &position);
	}
	if (!leftRing(face, position)) {
		(void) printf("not in leftRing is not possible\n");
		return;
	}
	if (face == 4) {
		rotateCornerHalf(w, 3);
	} else if (face == 2) {
		rotateCornerCCW(w, 3);
		swap = True;
	} else if (face == 7) {
		rotateCornerCW(w, 3);
		swap = True;
	}
	if ((position == 6 && !swap) || (position != 6 && swap)) {
		rotateCornerCCW(w, 4);
		rotateCornerCW(w, 0);
		rotateCornerCW(w, 4);
		rotateCornerCCW(w, 0);
	} else {
		rotateCornerCW(w, 0);
		rotateCornerCCW(w, 4);
		rotateCornerCCW(w, 0);
		rotateCornerCW(w, 4);
	}
}

static void
face1Edge6(OctWidget w, int matchFace, int faceColor)
{
	int otherColor, face, position, matchPosition;

	matchPosition = 6;
	/* need other color */
	face = edgeMateFace[matchFace][1];
	position = matchPosition - 1; /* this is a solved piece */
	otherColor = w->oct.facetLoc[face][position].face;

	/* face and position variables are reused here */
	findPiece(w, faceColor, otherColor, &face, &position);
	if (onFace(1, face, position)) {
		if (face == 1 && position == 6) {
			return;
		}
		if (face == 5 && position == 6) {
			rotateCornerCW(w, 2);
			rotateCornerCW(w, 5);
			rotateCornerCCW(w, 2);
		} else {
			rotateCornerHalf(w, 2);
			rotateCornerCW(w, 5);
			rotateCornerHalf(w, 2);
		}
		findPiece(w, faceColor, otherColor, &face, &position);
	} else if (leftRing(face, position)) {
		if ((face == 3 || face == 7) && position == 6) {
			rotateCornerCCW(w, 3);
		} else if ((face == 2 || face == 4) && position == 6) {
			rotateCornerCW(w, 3);
		} else if ((face == 3  && position == 3) ||
				(face == 2 && position == 1)) {
			rotateCornerHalf(w, 3);
		}
		findPiece(w, faceColor, otherColor, &face, &position);
	}
	if (!bottomRing(face, position)) {
		(void) printf("not in bottomRing is not possible\n");
		return;
	}
	if (face == 7) {
		rotateCornerHalf(w, 5);
	} else if (face == 4) {
		rotateCornerCW(w, 5);
	} else if (face == 6) {
		rotateCornerCCW(w, 5);
	}
	if (position == 1) {
		rotateCornerCW(w, 1);
		rotateCornerCCW(w, 2);
		rotateCornerCCW(w, 1);
		rotateCornerCW(w, 2);
	} else {
		rotateCornerCCW(w, 2);
		rotateCornerCW(w, 1);
		rotateCornerCW(w, 2);
		rotateCornerCCW(w, 1);
	}
}

static void
face1Edge1(OctWidget w, int matchFace, int faceColor)
{
	int otherColor, face, position, matchPosition;
	Boolean swap = False;

	matchPosition = 1;
	/* need other color */
	face = edgeMateFace[matchFace][2];
	position = matchPosition + 1; /* this is a solved piece */
	otherColor = w->oct.facetLoc[face][position].face;

	/* face and position variables are reused here */
	findPiece(w, faceColor, otherColor, &face, &position);
	if (onFace(1, face, position)) {
		if (face == 1 && position == 1) {
			return;
		}
		rotateCornerCCW(w, 2);
		rotateCornerCW(w, 3);
		rotateCornerCW(w, 2);
		findPiece(w, faceColor, otherColor, &face, &position);
	} else if (bottomRing(face, position)) {
		if ((face == 4 && position == 1) ||
				(face == 5 && position == 3)) {
			rotateCornerCCW(w, 5);
		} else if ((face == 5 && position == 1) || 
				(face == 6 && position == 3)) {
			rotateCornerHalf(w, 5);
		} else if ((face == 6  && position == 1) ||
				(face == 7 && position == 3)) {
			rotateCornerCW(w, 5);
		}
		findPiece(w, faceColor, otherColor, &face, &position);
	}
	if (!leftRing(face, position)) {
		(void) printf("not in leftRing is not possible\n");
		return;
	}
	if (face == 7) {
		rotateCornerHalf(w, 3);
	} else if (face == 4) {
		rotateCornerCCW(w, 3);
		swap = True;
	} else if (face == 3) {
		rotateCornerCW(w, 3);
		swap = True;
	}
	if ((position == 6 && !swap) || (position != 6 && swap)) {
		rotateCornerCW(w, 2);
		rotateCornerCCW(w, 0);
		rotateCornerCCW(w, 2);
		rotateCornerCW(w, 0);
	} else {
		rotateCornerCCW(w, 0);
		rotateCornerCW(w, 2);
		rotateCornerCW(w, 0);
		rotateCornerCCW(w, 2);
	}
}

static void
face3Edge6(OctWidget w, int matchFace, int faceColor)
{
	int otherColor, face, position, matchPosition;

	matchPosition = 6;
	/* need other color */
	face = edgeMateFace[matchFace][1];
	position = matchPosition - 1; /* this is a solved piece */
	otherColor = w->oct.facetLoc[face][position].face;

	/* face and position variables are reused here */
	findPiece(w, faceColor, otherColor, &face, &position);
	if (leftRing(face, position)) {
		if (face == 3 && position == 6) {
			return;
		}
		if (face == 7 && position == 6) {
			rotateCornerCCW(w, 3);
			rotateCornerCCW(w, 5);
			rotateCornerCW(w, 3);
		} else if ((face == 3 && position == 3) || 
				(face == 2 && position == 1)) {
			rotateCornerHalf(w, 3);
			rotateCornerCCW(w, 5);
			rotateCornerHalf(w, 3);
		} else if ((face == 2 || face == 4) && position == 6) {
			rotateCornerCW(w, 3);
			rotateCornerCCW(w, 5);
			rotateCornerCCW(w, 3);
		}
		findPiece(w, faceColor, otherColor, &face, &position);
	}
	if (!bottomRing(face, position)) {
		(void) printf("not in bottomRing is not possible\n");
		return;
	}
	if (face == 5) {
		rotateCornerHalf(w, 5);
	} else if (face == 4) {
		rotateCornerCCW(w, 5);
	} else if (face == 6) {
		rotateCornerCW(w, 5);
	}
	if (position == 1) {
		rotateCornerCW(w, 3);
		rotateCornerCCW(w, 4);
		rotateCornerCCW(w, 3);
		rotateCornerCW(w, 4);
	} else {
		rotateCornerCCW(w, 4);
		rotateCornerCW(w, 3);
		rotateCornerCW(w, 4);
		rotateCornerCCW(w, 3);
	}
}

static void
face3Edge3(OctWidget w, int matchFace, int faceColor)
{
	int otherColor, face, position, matchPosition;

	matchPosition = 3;
	/* need other color */
	face = edgeMateFace[matchFace][0];
	position = matchPosition - 1; /* this is a solved piece */
	otherColor = w->oct.facetLoc[face][position].face;

	/* face and position variables are reused here */
	findPiece(w, faceColor, otherColor, &face, &position);
	if (leftRing(face, position)) {
		if (face == 3 && position == 3) {
			return;
		}
		if (face == 2 && position == 1) {
			rotateCornerHalf(w, 3);
			rotateCornerCW(w, 5);
			rotateCornerHalf(w, 3);
		} else if (position == 6) {
			rotateCornerCW(w, 3);
			rotateCornerCW(w, 5);
			rotateCornerCCW(w, 3);
		} else {
			rotateCornerCW(w, 5);
		}
		findPiece(w, faceColor, otherColor, &face, &position);
	}
	if (!bottomRing(face, position)) {
		(void) printf("not in bottomRing is not possible\n");
		return;
	}
	rotateCornerCW(w, 3);
	if (face == 5)
		rotateCornerCCW(w, 5);
	else if (face == 6)
		rotateCornerHalf(w, 5);
	else if (face == 7)
		rotateCornerCW(w, 5);
	if ((position == 1)) {
		rotateCornerCW(w, 2);
		rotateCornerCCW(w, 3);
		rotateCornerCCW(w, 2);
		rotateCornerCW(w, 3);
	} else {
		rotateCornerCCW(w, 3);
		rotateCornerCW(w, 2);
		rotateCornerCW(w, 3);
		rotateCornerCCW(w, 2);
	}
	rotateCornerCCW(w, 3);
}

static void
face2Edge6(OctWidget w, int matchFace, int faceColor)
{
	int otherColor, face, position, matchPosition;

	matchPosition = 6;
	/* need other color */
	face = edgeMateFace[matchFace][1];
	position = matchPosition - 1; /* this is a solved piece */
	otherColor = w->oct.facetLoc[face][position].face;

	/* face and position variables are reused here */
	findPiece(w, faceColor, otherColor, &face, &position);
	if (leftRing(face, position)) {
		if (face == 2 && position == 6) {
			return;
		}
		rotateCornerCW(w, 3);
		rotateCornerCCW(w, 5);
		rotateCornerCCW(w, 3);
		findPiece(w, faceColor, otherColor, &face, &position);
	}
	if (!bottomRing(face, position)) {
		(void) printf("not in bottomRing is not possible\n");
		return;
	}
	if (face == 5) {
		rotateCornerCCW(w, 5);
	} else if (face == 6) {
		rotateCornerHalf(w, 5);
	} else if (face == 7) {
		rotateCornerCW(w, 5);
	}
	if (position == 1) {
		rotateCornerCW(w, 2);
		rotateCornerCCW(w, 3);
		rotateCornerCCW(w, 2);
		rotateCornerCW(w, 3);
	} else {
		rotateCornerCCW(w, 3);
		rotateCornerCW(w, 2);
		rotateCornerCW(w, 3);
		rotateCornerCCW(w, 2);
	}
}

static void
face4Edge1(OctWidget w, int matchFace, int faceColor)
{
	int otherColor, face, position, matchPosition;

	matchPosition = 1;
	/* need other color */
	face = edgeMateFace[matchFace][2];
	position = matchPosition + 1; /* this is a solved piece */
	otherColor = w->oct.facetLoc[face][position].face;

	/* face and position variables are reused here */
	findPiece(w, faceColor, otherColor, &face, &position);
	if (!bottomRing(face, position)) {
		(void) printf("not in bottomRing is not possible\n");
		return;
	}
	if (face == 4 && position == 1) {
		return;
	}
	/* try rotating puzzle in case of solved pieces */
	if ((w->oct.facetLoc[4][3].face ==
			w->oct.facetLoc[4][2].face) &&
			(w->oct.facetLoc[7][1].face ==
			w->oct.facetLoc[7][2].face)) {
		rotatePuzzleCW(w, 5);
		return;
	} else if ((w->oct.facetLoc[6][3].face ==
			w->oct.facetLoc[6][2].face) &&
			(w->oct.facetLoc[5][1].face ==
			w->oct.facetLoc[5][2].face)) {
		rotatePuzzleCCW(w, 5);
		return;
	} else if ((w->oct.facetLoc[7][3].face ==
			w->oct.facetLoc[7][2].face) &&
			(w->oct.facetLoc[6][1].face ==
			w->oct.facetLoc[6][2].face)) {
		rotatePuzzleHalf(w, 5);
		return;
	}
	if (face == 4 && position == 3) {
		rotateCornerCW(w, 1);
		rotateCornerCW(w, 2);
		rotateCornerCCW(w, 3);
		rotateCornerCW(w, 2);
		rotateCornerCW(w, 3);
		rotateCornerHalf(w, 2);
		rotateCornerCCW(w, 1);
	} else if (face == 5 && position == 1) {
		rotateCornerCW(w, 1);
		rotateCornerCW(w, 2);
		rotateCornerCW(w, 3);
		rotateCornerCCW(w, 5);
		rotateCornerCCW(w, 3);
		rotateCornerCW(w, 5);
		rotateCornerCCW(w, 2);
		rotateCornerCCW(w, 1);
	} else if (face == 5 && position == 3) {
		rotateCornerCW(w, 1);
		rotateCornerHalf(w, 2);
		rotateCornerCCW(w, 3);
		rotateCornerCCW(w, 2);
		rotateCornerCW(w, 3);
		rotateCornerCCW(w, 2);
		rotateCornerCW(w, 5);
		rotateCornerCW(w, 2);
		rotateCornerCCW(w, 5);
		rotateCornerCCW(w, 2);
		rotateCornerCCW(w, 1);
	} else if (face == 6 && position == 1) {
		rotateCornerCCW(w, 4);
		rotateCornerCCW(w, 3);
		rotateCornerCW(w, 2);
		rotateCornerCCW(w, 3);
		rotateCornerCCW(w, 2);
		rotateCornerHalf(w, 3);
		rotateCornerCW(w, 4);
	} else if (face == 6 && position == 3) {
		rotateCornerCCW(w, 3);
		rotateCornerCCW(w, 2);
		rotateCornerCW(w, 1);
		rotateCornerCCW(w, 2);
		rotateCornerCCW(w, 1);
		rotateCornerHalf(w, 2);
		rotateCornerCW(w, 3);
	} else if (face == 7 && position == 1) {
		rotateCornerCW(w, 1);
		/*rotateCornerCW(w, 2);
		rotateCornerCCW(w, 2);*/
		rotateCornerCW(w, 5);
		rotateCornerCW(w, 2);
		rotateCornerCCW(w, 5);
		rotateCornerCCW(w, 2);
		rotateCornerCCW(w, 1);
	} else if (face == 7 && position == 3) {
		rotateCornerCCW(w, 4);
		rotateCornerCCW(w, 3);
		rotateCornerCW(w, 5);
		rotateCornerCCW(w, 2);
		rotateCornerCCW(w, 5);
		rotateCornerCW(w, 2);
		rotateCornerCW(w, 3);
		rotateCornerCW(w, 4);
	}
}

static void
lastEdges(OctWidget w, int matchFace0, int faceColor0,
		int matchFace1, int faceColor1)
{
	int otherColor, face0, position0, face1, position1, matchPosition;

	matchPosition = 3;
	/* need other color */
	face0 = edgeMateFace[matchFace0][0];
	position0 = matchPosition - 1; /* this is a solved piece */
	otherColor = w->oct.facetLoc[face0][position0].face;

	/* face and position variables are reused here */
	findPiece(w, faceColor0, otherColor, &face0, &position0);

	matchPosition = 1;
	/* need other color */
	face1 = edgeMateFace[matchFace1][2];
	position1 = matchPosition + 1; /* this is a solved piece */
	otherColor = w->oct.facetLoc[face1][position1].face;

	/* face and position variables are reused here */
	findPiece(w, faceColor1, otherColor, &face1, &position1);

	/* 12 possibilities */
	if (face0 == 4 && position0 == 3 && face1 == 5 && position1 == 1) {
#ifdef DEBUG
		(void) printf("done\n");
#endif
		return;
	}
	if (face0 == 4 && position0 == 3 &&
			face1 == 6 && position1 == 3) {
#ifdef DEBUG
		(void) printf("4363!!\n");
#endif
		rotateCornerCCW(w, 1);
		rotateCornerCW(w, 4);
		rotateCornerCW(w, 1);
		rotateCornerCCW(w, 4);
		rotateCornerCW(w, 5);
		rotateCornerCCW(w, 4);
		rotateCornerCCW(w, 5);
		rotateCornerCW(w, 4);
	} else if (face0 == 5 && position0 == 1 &&
			face1 == 6 && position1 == 1) {
#ifdef DEBUG
		(void) printf("5161!\n");
#endif
		rotateCornerCCW(w, 1);
		rotateCornerCCW(w, 4);
		rotateCornerCW(w, 5);
		rotateCornerCCW(w, 3);
		rotateCornerCCW(w, 5);
		rotateCornerCW(w, 3);
		rotateCornerCW(w, 4);
		rotateCornerCW(w, 1);
	} else if (face0 == 5 && position0 == 1 &&
			face1 == 7 && position1 == 3) {
#ifdef DEBUG
		(void) printf("5173!\n");
#endif
		rotateCornerCCW(w, 1);
		/*rotateCornerCCW(w, 4);
		rotateCornerCW(w, 4);*/
		rotateCornerCCW(w, 5);
		rotateCornerCCW(w, 4);
		rotateCornerCW(w, 5);
		rotateCornerCW(w, 4);
		rotateCornerCW(w, 1);
	} else if (face0 == 6 && position0 == 1 &&
			face1 == 4 && position1 == 3) {
#ifdef DEBUG
		(void) printf("6143!\n");
#endif
		rotateCornerCCW(w, 1);
		rotateCornerCCW(w, 4);
		rotateCornerCCW(w, 3);
		rotateCornerCW(w, 5);
		rotateCornerCW(w, 3);
		rotateCornerCCW(w, 5);
		rotateCornerCW(w, 4);
		rotateCornerCW(w, 1);
	} else if (face0 == 6 && position0 == 1 &&
			face1 == 7 && position1 == 1) {
#ifdef DEBUG
		(void) printf("6171!\n");
#endif
		rotateCornerCCW(w, 1);
		rotateCornerHalf(w, 4);
		rotateCornerCW(w, 3);
		rotateCornerCW(w, 4);
		rotateCornerCCW(w, 3);
		rotateCornerCW(w, 4);
		rotateCornerCW(w, 1);
	} else if (face0 == 6 && position0 == 3 &&
			face1 == 6 && position1 == 1) {
#ifdef DEBUG
		(void) printf("6361!\n");
#endif
		rotateCornerCW(w, 3);
		rotateCornerCW(w, 5);
		rotateCornerCW(w, 4);
		rotateCornerHalf(w, 5);
		rotateCornerCW(w, 1);
		rotateCornerCW(w, 5);
		rotateCornerCCW(w, 1);
		rotateCornerCCW(w, 4);
		rotateCornerCCW(w, 3);
	} else if (face0 == 6 && position0 == 3 &&
			face1 == 7 && position1 == 3) {
#ifdef DEBUG
		(void) printf("6373!\n");
#endif
		rotateCornerCCW(w, 1);
		rotateCornerCCW(w, 4);
		rotateCornerCW(w, 3);
		rotateCornerCCW(w, 4);
		rotateCornerCCW(w, 3);
		rotateCornerHalf(w, 4);
		rotateCornerCW(w, 1);
	} else if (face0 == 7 && position0 == 1 &&
			face1 == 5 && position1 == 1) {
#ifdef DEBUG
		(void) printf("7151!!\n");
#endif
		rotateCornerCCW(w, 4);
		rotateCornerCW(w, 3);
		rotateCornerCW(w, 4);
		rotateCornerCCW(w, 3);
		rotateCornerCW(w, 5);
		rotateCornerCCW(w, 3);
		rotateCornerCCW(w, 5);
		rotateCornerCW(w, 3);
	} else if (face0 == 7 && position0 == 1 &&
			face1 == 6 && position1 == 3) {
#ifdef DEBUG
		(void) printf("7163!!\n");
#endif
		rotateCornerCCW(w, 1);
		rotateCornerHalf(w, 4);
		rotateCornerCW(w, 3);
		rotateCornerCW(w, 4);
		rotateCornerCCW(w, 3);
		rotateCornerCW(w, 5);
		rotateCornerCCW(w, 3);
		rotateCornerCCW(w, 5);
		rotateCornerCW(w, 3);
		rotateCornerCW(w, 4);
		rotateCornerCW(w, 1);
	} else if (face0 == 7 && position0 == 3 &&
			face1 == 4 && position1 == 3) {
#ifdef DEBUG
		(void) printf("7343!\n");
#endif
		rotateCornerCCW(w, 1);
		rotateCornerCCW(w, 4);
		rotateCornerCCW(w, 5);
		rotateCornerCW(w, 4);
		rotateCornerCW(w, 5);
		rotateCornerCW(w, 1);
	} else if (face0 == 7 && position0 == 3 &&
			face1 == 7 && position1 == 1) {
#ifdef DEBUG
		(void) printf("7371!\n");
#endif
		rotateCornerCCW(w, 1);
		rotateCornerCCW(w, 5);
		rotateCornerCCW(w, 4);
		rotateCornerHalf(w, 5);
		rotateCornerCCW(w, 3);
		rotateCornerCCW(w, 5);
		rotateCornerCW(w, 3);
		rotateCornerCW(w, 4);
		rotateCornerCW(w, 1);
	} else {
		(void) printf("13th case, not possible\n");
	}
}

static void
solveTopFace(OctWidget w)
{
	/* Pick a face (0) and determine which color is present at each
	 * corner.  */
	int topFace = 0;
	int faceColor = findFaceColor(w, topFace);

	faceCorners(w, topFace, faceColor);
	faceLittleCorners(w);
	face0Edge6(w, topFace, faceColor);
	face0Edge1(w, topFace, faceColor);
	face0Edge3(w, topFace, faceColor);
}

static void
solveSecondFace(OctWidget w)
{
	int rightFace = 1;
	int faceColor = findFaceColor(w, rightFace);

	faceCorner(w, rightFace, faceColor, 2);
	orientLittleCorners(w, facesToCorner[1][2]);
	face1Edge6(w, rightFace, faceColor);
	face1Edge1(w, rightFace, faceColor);
}

static void
solveThirdCorner(OctWidget w)
{
	int leftFace = 3, bottomFace = 2;
	int faceColor = findFaceColor(w, leftFace);

	faceCorner(w, leftFace, faceColor, 1);
	orientLittleCorners(w, facesToCorner[3][1]);
	face3Edge6(w, leftFace, faceColor);
	face3Edge3(w, leftFace, faceColor);
	faceColor = findFaceColor(w, bottomFace);
	face2Edge6(w, bottomFace, faceColor);
}

static void
solveLastCorner(OctWidget w)
{
	int bottomFace = 4, rightFace = 5;
	int faceColor0 = findFaceColor(w, bottomFace), faceColor1;

	faceCorner(w, bottomFace, faceColor0, 0);
	orientLittleCorners(w, facesToCorner[5][0]);
	/* Now for the hard part... last 4 */
	face4Edge1(w, bottomFace, faceColor0);
	/* Also relatively hard, redo in case rotated */
	faceColor0 = findFaceColor(w, bottomFace);
	faceColor1 = findFaceColor(w, rightFace);
	lastEdges(w, bottomFace, faceColor0, rightFace, faceColor1);
}

/* This procedure coordinates the solution process. */
void
solveSomePieces(OctWidget w)
{
	setPuzzle(w, ACTION_RESET);
	if (solvingFlag)
		return;
#ifdef JMP
	if (!setjmp(solve_env))
#endif
	{
		solvingFlag = True;

		if (!checkSolved(w)) {
			if (w->oct.size > 2) {
				solveTopFace(w);
				solveSecondFace(w);
				solveThirdCorner(w);
				solveLastCorner(w);
			} else {
				allLittleCorners(w);
			}
		}
	}
#ifdef JMP
	abortSolvingFlag = False;
#endif
	solvingFlag = False;
	w->oct.cheat = True; /* Assume the worst. */
	setPuzzle(w, ACTION_COMPUTED);
}
