/*
 * @(#)RubikS.c
 *
 * Taken from code originally written by
 * Michael B. Martin <martinm@sps1.phys.vt.edu>
 * From cubist10.c-- for IBM PC.
 * Used by permission.
 * Taken from the algorithm in the Ideal Solution book.
 * Break ability taken from the X puzzle by Don Bennett, HP Labs
 *
 * Copyright 1994 - 2010  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.
 */

/* For break code */
/* 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.
 */

/* Solver file for Rubik */

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

/* Mappings of Ideal notation to my General nxnxn cube notation */
#define rotateLeft(w)	movePuzzlePiece(w,2,0,LEFT,TRUE)
#define rotateRight(w)	movePuzzlePiece(w,2,0,RIGHT,TRUE)
#define rotateUp(w)	movePuzzlePiece(w,2,0,TOP,TRUE)
#define rotateDown(w)	movePuzzlePiece(w,2,0,BOTTOM,TRUE)
#define rotateCw(w)	movePuzzlePiece(w,0,0,RIGHT,TRUE)
#define rotateCcw(w)	movePuzzlePiece(w,0,0,LEFT,TRUE)

#define rotateTopLeft(w)	movePuzzlePiece(w,2,0,LEFT,FALSE)
#define rotateCenterLeft(w)	movePuzzlePiece(w,2,w->rubik.sizex,LEFT,FALSE)
#define rotateBottomLeft(w)	movePuzzlePiece(w,2,w->rubik.sizex*(w->rubik.sizex-1),LEFT,FALSE)
#define rotateTopRight(w)	movePuzzlePiece(w,2,0,RIGHT,FALSE)
#define rotateCenterRight(w)	movePuzzlePiece(w,2,w->rubik.sizex,RIGHT,FALSE)
#define rotateBottomRight(w)	movePuzzlePiece(w,2,w->rubik.sizex*(w->rubik.sizex-1),RIGHT,FALSE)
#define rotateLeftUp(w)		movePuzzlePiece(w,2,0,TOP,FALSE)
#define rotateCenterUp(w)	movePuzzlePiece(w,2,1,TOP,FALSE)
#define rotateRightUp(w)	movePuzzlePiece(w,2,w->rubik.sizex-1,TOP,FALSE)
#define rotateLeftDown(w)	movePuzzlePiece(w,2,0,BOTTOM,FALSE)
#define rotateCenterDown(w)	movePuzzlePiece(w,2,1,BOTTOM,FALSE)
#define rotateRightDown(w)	movePuzzlePiece(w,2,w->rubik.sizex-1,BOTTOM,FALSE)
#define rotateFrontCw(w)	movePuzzlePiece(w,0,w->rubik.sizex*(w->rubik.sizex-1),RIGHT,FALSE)
#define rotateFrontCcw(w)	movePuzzlePiece(w,0,w->rubik.sizex*(w->rubik.sizex-1),LEFT,FALSE)

#define BLUE 0
#define WHITE 1
#define RED 2
#define YELLOW 3
#define GREEN 4
#define ORANGE 5

#ifdef DEBUG
static int mapGeneralToIdeal[MAX_FACES] =
{5, 4, 1, 2, 6, 3};

#endif
static int mapIdealToGeneral[MAX_FACES] =
{2, 3, 5, 1, 0, 4};		/* Remember to subtract 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(RubikWidget 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(RubikWidget w)
{
	XEvent event;

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

static void
movePuzzlePiece(RubikWidget w,
	const int face, const int position, const int direction,
	const 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, control);
}

static int
colorSide(RubikWidget w, int m, int c)
{
	int d, i, j;

	d = mapIdealToGeneral[m - 1];
	i = c % 3;
	j = c / 3;
	if (i == 2)
		i = w->rubik.sizex - 1;
	if (j == 2)
		j = w->rubik.sizex - 1;
	return w->rubik.cubeLoc[d][j * w->rubik.sizex + i].face;
}

static int
mapFace(RubikWidget w, int m)
{
	int d;

	d = mapIdealToGeneral[m - 1];
	return ((w->rubik.cubeLoc[d][4].rotation -
		w->rubik.cubeLoc[d][0].rotation + MAX_ORIENT) % MAX_ORIENT);
}

/* This procedure finds the location of a specified corner.  An */
/* improperly-specified color combination will result in a return */
/* value of 9. */
static int
findCorner(RubikWidget w, int color1, int color2, int color3)
{
	int corner = 0, temp = 1;

	do {
		if (colorSide(w, 5, 6) == color1) {
			if (colorSide(w, 1, 0) == color2 &&
					colorSide(w, 4, 2) == color3)
				corner = temp;
		} else if (colorSide(w, 5, 6) == color2) {
			if (colorSide(w, 1, 0) == color3 &&
					colorSide(w, 4, 2) == color1)
				corner = temp;
		} else if (colorSide(w, 5, 6) == color3 &&
				colorSide(w, 1, 0) == color1 &&
				colorSide(w, 4, 2) == color2) {
			corner = temp;
		}
		if (corner == 0) {
			if (temp < 4)
				rotateLeft(w);
			else if (temp == 4) {
				rotateCw(w);
				rotateCw(w);
			} else if (temp < 8)
				rotateRight(w);
			else if (temp == 8)
				corner = 9;
			temp++;
		}
	} while (corner == 0);

	/* put the cube back to the way it was */
	if (corner == 2)
		rotateRight(w);
	else if (corner == 3) {
		rotateRight(w);
		rotateRight(w);
	} else if (corner == 4)
		rotateLeft(w);
	else if (corner == 5) {
		rotateCw(w);
		rotateCw(w);
		rotateLeft(w);
	} else if (corner == 6) {
		rotateCw(w);
		rotateCw(w);
	} else if (corner == 7) {
		rotateCw(w);
		rotateCw(w);
		rotateRight(w);
	} else if (corner == 8) {
		rotateCw(w);
		rotateCw(w);
		rotateRight(w);
		rotateRight(w);
	}
	return (corner);
}

/* This procedure finds the location of a specified edge.  An */
/* improperly-specified color combination will result in a return */
/* value of 13. */
static int
findEdge(RubikWidget w, int color1, int color2)
{
	int edge = 0, temp = 1;

	do {
		if (colorSide(w, 5, 7) == color1) {
			if (colorSide(w, 1, 1) == color2)
				edge = temp;
		} else if (colorSide(w, 5, 7) == color2 &&
				colorSide(w, 1, 1) == color1) {
			edge = temp;
		}
		if (edge == 0) {
			if (temp < 4)
				rotateLeft(w);
			else if (temp == 4) {
				rotateLeft(w);
				rotateCw(w);
			} else if (temp < 8)
				rotateUp(w);
			else if (temp == 8) {
				rotateUp(w);
				rotateCw(w);
			} else if (temp < 12)
				rotateRight(w);
			else if (temp == 12)
				edge = 13;	/* end condition, just in case */
			temp++;
		}
	} while (edge == 0);

	/* put the cube back to the way it was */
	if (edge == 2) {
		rotateRight(w);
	} else if (edge == 3) {
		rotateRight(w);
		rotateRight(w);
	} else if (edge == 4) {
		rotateLeft(w);
	} else if (edge == 5) {
		rotateCcw(w);
	} else if (edge == 6) {
		rotateCcw(w);
		rotateRight(w);
	} else if (edge == 7) {
		rotateCcw(w);
		rotateRight(w);
		rotateRight(w);
	} else if (edge == 8) {
		rotateCcw(w);
		rotateLeft(w);
	} else if (edge == 9) {
		rotateCcw(w);
		rotateCcw(w);
	} else if (edge == 10) {
		rotateCcw(w);
		rotateCcw(w);
		rotateRight(w);
	} else if (edge == 11) {
		rotateUp(w);
		rotateUp(w);
	} else if (edge == 12) {
		rotateUp(w);
		rotateUp(w);
		rotateRight(w);
	}
	return (edge);
}

/* This procedure places the specified edge piece in edge position */
/* #1 (front top). */
static void
placeEdge(RubikWidget w, int edge, int top_color)
{
	/* first put the edge piece in position #8 (center row, left rear) */
	if (edge == 1) {
		if (colorSide(w, 5, 7) == top_color)
			return;	/* already in place */
		else {
			rotateFrontCcw(w);
			rotateCenterLeft(w);
			rotateFrontCw(w);
		}
	} else if (edge == 2) {
		rotateTopLeft(w);
		rotateFrontCcw(w);
		rotateCenterLeft(w);
		rotateFrontCw(w);
		rotateTopRight(w);
	} else if (edge == 3) {
		rotateTopLeft(w);
		rotateTopLeft(w);
		rotateFrontCcw(w);
		rotateCenterLeft(w);
		rotateFrontCw(w);
		rotateTopRight(w);
		rotateTopRight(w);
	} else if (edge == 4) {
		rotateTopRight(w);
		rotateFrontCcw(w);
		rotateCenterLeft(w);
		rotateFrontCw(w);
		rotateTopLeft(w);
	} else if (edge == 5) {
		rotateCenterLeft(w);
	} else if (edge == 6) {
		rotateCenterLeft(w);
		rotateCenterLeft(w);
	} else if (edge == 7) {
		rotateCenterRight(w);
	} else if (edge == 9) {
		rotateFrontCw(w);
		rotateCenterLeft(w);
		rotateFrontCcw(w);
	} else if (edge == 10) {
		rotateBottomLeft(w);
		rotateFrontCw(w);
		rotateCenterLeft(w);
		rotateFrontCcw(w);
		rotateBottomRight(w);
	} else if (edge == 11) {
		rotateBottomLeft(w);
		rotateBottomLeft(w);
		rotateFrontCw(w);
		rotateCenterLeft(w);
		rotateFrontCcw(w);
		rotateBottomRight(w);
		rotateBottomRight(w);
	} else if (edge == 12) {
		rotateBottomRight(w);
		rotateFrontCw(w);
		rotateCenterLeft(w);
		rotateFrontCcw(w);
		rotateBottomLeft(w);
	}
	/* put the piece in place */
	if (colorSide(w, 4, 3) == top_color) {
		rotateFrontCw(w);
		rotateCenterRight(w);
		rotateCenterRight(w);
		rotateFrontCcw(w);
	} else {
		rotateFrontCcw(w);
		rotateCenterRight(w);
		rotateFrontCw(w);
	}
}

/* This procedure solves the top (BLUE) side, except for one edge. */
static void
solveTop(RubikWidget w)
{
	int corner, edge;

	/* put the blue face on the top */
	if (colorSide(w, 1, 4) == BLUE)
		rotateUp(w);
	else if (colorSide(w, 2, 4) == BLUE)
		rotateCcw(w);
	else if (colorSide(w, 3, 4) == BLUE)
		rotateDown(w);
	else if (colorSide(w, 4, 4) == BLUE)
		rotateCw(w);
	else if (colorSide(w, 6, 4) == BLUE) {
		rotateUp(w);
		rotateUp(w);
	}
	/* first find the blue-red-white corner and place it */
	corner = findCorner(w, BLUE, RED, WHITE);
	if (corner == 1) {
		if (colorSide(w, 5, 6) == RED) {
			rotateFrontCw(w);
			rotateTopLeft(w);
		} else if (colorSide(w, 5, 6) == WHITE) {
			rotateLeftUp(w);
			rotateTopRight(w);
		}
	} else if (corner == 2) {
		if (colorSide(w, 5, 8) == BLUE)
			rotateTopLeft(w);
		else if (colorSide(w, 5, 8) == RED) {
			rotateRightUp(w);
			rotateTopLeft(w);
			rotateTopLeft(w);
		} else if (colorSide(w, 5, 8) == WHITE)
			rotateFrontCcw(w);
	} else if (corner == 3) {
		if (colorSide(w, 5, 2) == BLUE) {
			rotateTopLeft(w);
			rotateTopLeft(w);
		} else if (colorSide(w, 5, 2) == RED) {
			rotateTopRight(w);
			rotateLeftDown(w);
		} else if (colorSide(w, 5, 2) == WHITE) {
			rotateRightDown(w);
			rotateTopLeft(w);
		}
	} else if (corner == 4) {
		if (colorSide(w, 5, 0) == BLUE)
			rotateTopRight(w);
		else if (colorSide(w, 5, 0) == RED)
			rotateLeftDown(w);
		else if (colorSide(w, 5, 0) == WHITE) {
			rotateTopRight(w);
			rotateLeftUp(w);
			rotateTopRight(w);
		}
	} else if (corner == 5) {
		if (colorSide(w, 6, 0) == BLUE) {
			rotateBottomLeft(w);
			rotateLeftUp(w);
			rotateLeftUp(w);
		} else if (colorSide(w, 6, 0) == RED)
			rotateLeftUp(w);
		else if (colorSide(w, 6, 0) == WHITE)
			rotateFrontCw(w);
	} else if (corner == 6) {
		if (colorSide(w, 6, 2) == BLUE) {
			rotateFrontCw(w);
			rotateFrontCw(w);
		} else if (colorSide(w, 6, 2) == RED) {
			rotateBottomLeft(w);
			rotateLeftUp(w);
		} else if (colorSide(w, 6, 2) == WHITE) {
			rotateBottomLeft(w);
			rotateFrontCw(w);
		}
	} else if (corner == 7) {
		if (colorSide(w, 6, 8) == BLUE) {
			rotateBottomLeft(w);
			rotateFrontCw(w);
			rotateFrontCw(w);
		} else if (colorSide(w, 6, 8) == RED) {
			rotateBottomLeft(w);
			rotateBottomLeft(w);
			rotateLeftUp(w);
		} else if (colorSide(w, 6, 8) == WHITE) {
			rotateBottomLeft(w);
			rotateBottomLeft(w);
			rotateFrontCw(w);
		}
	} else if (corner == 8) {
		if (colorSide(w, 6, 6) == BLUE) {
			rotateLeftUp(w);
			rotateLeftUp(w);
		} else if (colorSide(w, 6, 6) == RED) {
			rotateBottomRight(w);
			rotateLeftUp(w);
		} else if (colorSide(w, 6, 6) == WHITE) {
			rotateBottomRight(w);
			rotateFrontCw(w);
		}
	}
	/* now find the blue-yellow-red corner and place it */
	rotateLeft(w);
	corner = findCorner(w, BLUE, YELLOW, RED);
	if (corner == 1) {
		if (colorSide(w, 5, 6) == YELLOW) {
			rotateFrontCcw(w);
			rotateBottomRight(w);
			rotateFrontCcw(w);
			rotateFrontCcw(w);
		} else if (colorSide(w, 5, 6) == RED) {
			rotateFrontCw(w);
			rotateFrontCw(w);
			rotateBottomLeft(w);
			rotateFrontCw(w);
		}
	} else if (corner == 2) {
		if (colorSide(w, 5, 8) == BLUE) {
			rotateRightDown(w);
			rotateBottomLeft(w);
			rotateFrontCw(w);
		} else if (colorSide(w, 5, 8) == YELLOW) {
			rotateRightDown(w);
			rotateFrontCw(w);
			rotateFrontCw(w);
		} else if (colorSide(w, 5, 8) == RED)
			rotateFrontCcw(w);
	} else if (corner == 3) {
		if (colorSide(w, 5, 2) == BLUE) {
			rotateRightDown(w);
			rotateRightDown(w);
			rotateFrontCw(w);
			rotateFrontCw(w);
		} else if (colorSide(w, 5, 2) == YELLOW) {
			rotateRightDown(w);
			rotateFrontCcw(w);
		} else if (colorSide(w, 5, 2) == RED) {
			rotateRightDown(w);
			rotateRightDown(w);
			rotateBottomLeft(w);
			rotateFrontCw(w);
		}
	} else if (corner == 5) {
		if (colorSide(w, 6, 0) == BLUE) {
			rotateBottomRight(w);
			rotateFrontCw(w);
			rotateFrontCw(w);
		} else if (colorSide(w, 6, 0) == YELLOW) {
			rotateBottomRight(w);
			rotateRightUp(w);
			rotateFrontCcw(w);
		} else if (colorSide(w, 6, 0) == RED)
			rotateFrontCw(w);
	} else if (corner == 6) {
		if (colorSide(w, 6, 2) == BLUE) {
			rotateFrontCw(w);
			rotateFrontCw(w);
		} else if (colorSide(w, 6, 2) == YELLOW) {
			rotateRightUp(w);
			rotateFrontCcw(w);
		} else if (colorSide(w, 6, 2) == RED) {
			rotateBottomLeft(w);
			rotateFrontCw(w);
		}
	} else if (corner == 7) {
		if (colorSide(w, 6, 8) == BLUE) {
			rotateBottomLeft(w);
			rotateFrontCw(w);
			rotateFrontCw(w);
		} else if (colorSide(w, 6, 8) == YELLOW) {
			rotateBottomLeft(w);
			rotateRightUp(w);
			rotateFrontCcw(w);
		} else if (colorSide(w, 6, 8) == RED) {
			rotateBottomLeft(w);
			rotateBottomLeft(w);
			rotateFrontCw(w);
		}
	} else if (corner == 8) {
		if (colorSide(w, 6, 6) == BLUE) {
			rotateBottomRight(w);
			rotateBottomRight(w);
			rotateFrontCw(w);
			rotateFrontCw(w);
		} else if (colorSide(w, 6, 6) == YELLOW) {
			rotateBottomRight(w);
			rotateBottomRight(w);
			rotateRightUp(w);
			rotateFrontCcw(w);
		} else if (colorSide(w, 6, 6) == RED) {
			rotateBottomRight(w);
			rotateFrontCw(w);
		}
	}
	/* now find the blue-orange-yellow corner and place it */
	rotateLeft(w);
	corner = findCorner(w, BLUE, ORANGE, YELLOW);
	if (corner == 1) {
		if (colorSide(w, 5, 6) == ORANGE) {
			rotateFrontCcw(w);
			rotateBottomRight(w);
			rotateFrontCcw(w);
			rotateFrontCcw(w);
		} else if (colorSide(w, 5, 6) == YELLOW) {
			rotateFrontCw(w);
			rotateFrontCw(w);
			rotateBottomLeft(w);
			rotateFrontCw(w);
		}
	} else if (corner == 2) {
		if (colorSide(w, 5, 8) == BLUE) {
			rotateRightDown(w);
			rotateBottomLeft(w);
			rotateRightUp(w);
			rotateFrontCw(w);
		} else if (colorSide(w, 5, 8) == ORANGE) {
			rotateFrontCw(w);
			rotateBottomLeft(w);
			rotateFrontCw(w);
		} else if (colorSide(w, 5, 8) == YELLOW)
			rotateFrontCcw(w);
	} else if (corner == 5) {
		if (colorSide(w, 6, 0) == BLUE) {
			rotateBottomRight(w);
			rotateFrontCw(w);
			rotateFrontCw(w);
		} else if (colorSide(w, 6, 0) == ORANGE) {
			rotateRightDown(w);
			rotateBottomRight(w);
			rotateRightUp(w);
			rotateFrontCcw(w);
		} else if (colorSide(w, 6, 0) == YELLOW)
			rotateFrontCw(w);
	} else if (corner == 6) {
		if (colorSide(w, 6, 2) == BLUE) {
			rotateFrontCw(w);
			rotateFrontCw(w);
		} else if (colorSide(w, 6, 2) == ORANGE) {
			rotateBottomLeft(w);
			rotateRightDown(w);
			rotateBottomRight(w);
			rotateRightUp(w);
			rotateFrontCcw(w);
		} else if (colorSide(w, 6, 2) == YELLOW) {
			rotateBottomLeft(w);
			rotateFrontCw(w);
		}
	} else if (corner == 7) {
		if (colorSide(w, 6, 8) == BLUE) {
			rotateBottomLeft(w);
			rotateFrontCw(w);
			rotateFrontCw(w);
		} else if (colorSide(w, 6, 8) == ORANGE) {
			rotateBottomLeft(w);
			rotateBottomLeft(w);
			rotateRightDown(w);
			rotateBottomRight(w);
			rotateRightUp(w);
			rotateFrontCcw(w);
		} else if (colorSide(w, 6, 8) == YELLOW) {
			rotateBottomLeft(w);
			rotateBottomLeft(w);
			rotateFrontCw(w);
		}
	} else if (corner == 8) {
		if (colorSide(w, 6, 6) == BLUE) {
			rotateBottomRight(w);
			rotateBottomRight(w);
			rotateFrontCw(w);
			rotateFrontCw(w);
		} else if (colorSide(w, 6, 6) == ORANGE) {
			rotateRightDown(w);
			rotateBottomRight(w);
			rotateBottomRight(w);
			rotateRightUp(w);
			rotateFrontCcw(w);
		} else if (colorSide(w, 6, 6) == YELLOW) {
			rotateBottomRight(w);
			rotateFrontCw(w);
		}
	}
	/* and now find the blue-white-orange corner and place it */
	rotateLeft(w);
	corner = findCorner(w, BLUE, WHITE, ORANGE);
	if (corner == 1) {
		if (colorSide(w, 5, 6) == WHITE) {
			rotateLeftDown(w);
			rotateBottomRight(w);
			rotateLeftUp(w);
			rotateBottomLeft(w);
			rotateBottomLeft(w);
			rotateFrontCcw(w);
			rotateBottomRight(w);
			rotateFrontCw(w);
		} else if (colorSide(w, 5, 6) == ORANGE) {
			rotateFrontCcw(w);
			rotateBottomLeft(w);
			rotateFrontCw(w);
			rotateBottomRight(w);
			rotateBottomRight(w);
			rotateLeftDown(w);
			rotateBottomLeft(w);
			rotateLeftUp(w);
		}
	} else if (corner == 5) {
		if (colorSide(w, 6, 0) == BLUE) {
			rotateBottomRight(w);
			rotateLeftDown(w);
			rotateBottomLeft(w);
			rotateBottomLeft(w);
			rotateLeftUp(w);
			rotateBottomRight(w);
			rotateLeftDown(w);
			rotateBottomLeft(w);
			rotateLeftUp(w);
		} else if (colorSide(w, 6, 0) == WHITE) {
			rotateBottomRight(w);
			rotateLeftDown(w);
			rotateBottomLeft(w);
			rotateLeftUp(w);
		} else if (colorSide(w, 6, 0) == ORANGE) {
			rotateBottomLeft(w);
			rotateFrontCcw(w);
			rotateBottomRight(w);
			rotateFrontCw(w);
		}
	} else if (corner == 6) {
		if (colorSide(w, 6, 2) == BLUE) {
			rotateBottomRight(w);
			rotateFrontCcw(w);
			rotateBottomLeft(w);
			rotateFrontCw(w);
			rotateBottomLeft(w);
			rotateFrontCcw(w);
			rotateBottomRight(w);
			rotateFrontCw(w);
		} else if (colorSide(w, 6, 2) == WHITE) {
			rotateLeftDown(w);
			rotateBottomLeft(w);
			rotateLeftUp(w);
		} else if (colorSide(w, 6, 2) == ORANGE) {
			rotateBottomLeft(w);
			rotateBottomLeft(w);
			rotateFrontCcw(w);
			rotateBottomRight(w);
			rotateFrontCw(w);
		}
	} else if (corner == 7) {
		if (colorSide(w, 6, 8) == BLUE) {
			rotateLeftDown(w);
			rotateBottomRight(w);
			rotateLeftUp(w);
			rotateBottomRight(w);
			rotateLeftDown(w);
			rotateBottomLeft(w);
			rotateLeftUp(w);
		} else if (colorSide(w, 6, 8) == WHITE) {
			rotateLeftDown(w);
			rotateBottomLeft(w);
			rotateBottomLeft(w);
			rotateLeftUp(w);
		} else if (colorSide(w, 6, 8) == ORANGE) {
			rotateFrontCcw(w);
			rotateBottomLeft(w);
			rotateBottomLeft(w);
			rotateFrontCw(w);
		}
	} else if (corner == 8) {
		if (colorSide(w, 6, 6) == BLUE) {
			rotateFrontCcw(w);
			rotateBottomRight(w);
			rotateBottomRight(w);
			rotateFrontCw(w);
			rotateBottomLeft(w);
			rotateFrontCcw(w);
			rotateBottomRight(w);
			rotateFrontCw(w);
		} else if (colorSide(w, 6, 6) == WHITE) {
			rotateBottomRight(w);
			rotateBottomRight(w);
			rotateLeftDown(w);
			rotateBottomLeft(w);
			rotateLeftUp(w);
		} else if (colorSide(w, 6, 6) == ORANGE) {
			rotateFrontCcw(w);
			rotateBottomRight(w);
			rotateFrontCw(w);
		}
	}
	rotateLeft(w);

	/* find the blue-red edge and place it */
	edge = findEdge(w, BLUE, RED);
	placeEdge(w, edge, BLUE);
	rotateLeft(w);

	/* find the blue-yellow edge and place it */
	edge = findEdge(w, BLUE, YELLOW);
	placeEdge(w, edge, BLUE);
	rotateLeft(w);

	/* find the blue-orange edge and place it */
	edge = findEdge(w, BLUE, ORANGE);
	placeEdge(w, edge, BLUE);
	rotateLeft(w);

	rotateUp(w);		/* put the blue side to the back */
}

/* This procedure swaps the the bottom front corners. */
static void
swapBottomCorners(RubikWidget w)
{
	rotateTopRight(w);
	rotateFrontCw(w);
	rotateTopLeft(w);
	rotateLeftUp(w);
	rotateTopLeft(w);
	rotateLeftDown(w);
	rotateTopRight(w);
	rotateFrontCw(w);
	rotateFrontCw(w);
}

/* This procedure places the front (GREEN) four corners into */
/* their correct positions. */
static void
alignCorners(RubikWidget w)
{
	int corner;

	/* find and place the green-orange-white corner (upper left) */
	corner = findCorner(w, GREEN, ORANGE, WHITE);
	if (corner == 2)
		rotateFrontCcw(w);
	else if (corner == 5)
		rotateFrontCw(w);
	else if (corner == 6) {
		rotateFrontCw(w);
		rotateFrontCw(w);
	}
	/* find and place the green-yellow-orange corner (lower left) */
	corner = findCorner(w, GREEN, YELLOW, ORANGE);
	if (corner == 2) {
		rotateCw(w);
		swapBottomCorners(w);
		rotateCcw(w);
		swapBottomCorners(w);
	} else if (corner == 6)
		swapBottomCorners(w);

	/* find and place the green-red-yellow corner (lower right) */
	corner = findCorner(w, GREEN, RED, YELLOW);
	if (corner == 2) {
		rotateCw(w);
		swapBottomCorners(w);
		rotateCcw(w);
	}
}

/* This procedure aligns the bottom corner colors (may need to be repeated). */
static void
colorAlignFront(RubikWidget w)
{
	rotateTopRight(w);
	rotateFrontCw(w);
	rotateFrontCw(w);
	rotateTopLeft(w);
	rotateFrontCw(w);
	rotateTopRight(w);
	rotateFrontCw(w);
	rotateTopLeft(w);
	rotateFrontCw(w);
	rotateFrontCw(w);
}

/* This procedure moves the remaining BLUE edge piece into position */
/* from edge position #6. */
static void
alignLastEdge(RubikWidget w)
{
	/* edge piece should be in edge position #6 */
	/* check its orientation and decide which sequence to perform */
	if (colorSide(w, 1, 5) == BLUE) {
		rotateCenterLeft(w);
		rotateFrontCw(w);
		rotateCenterRight(w);
		rotateFrontCcw(w);
		rotateCenterLeft(w);
		rotateFrontCcw(w);
		rotateCenterRight(w);
		rotateFrontCw(w);
	} else {
		rotateFrontCcw(w);
		rotateCenterLeft(w);
		rotateFrontCw(w);
		rotateCenterRight(w);
		rotateFrontCw(w);
		rotateCenterLeft(w);
		rotateFrontCcw(w);
	}
}

/* This procedure "shuffles" the three center edges on the front and */
/* top faces. */
static void
shuffleEdges(RubikWidget w)
{
	rotateCenterUp(w);
	rotateTopRight(w);
	rotateTopRight(w);
	rotateCenterDown(w);
	rotateTopRight(w);
	rotateTopRight(w);
}

/* This procedure should be used when the two opposing top front and back */
/* edge pieces are in position but not color aligned (this sequence is */
/* known as Rubik's Maneuver). */
static void
recolorTopEdges(RubikWidget w)
{
	rotateCenterUp(w);
	rotateTopRight(w);
	rotateCenterUp(w);
	rotateTopRight(w);
	rotateCenterUp(w);
	rotateTopRight(w);
	rotateTopRight(w);
	rotateCenterDown(w);
	rotateTopRight(w);
	rotateCenterDown(w);
	rotateTopRight(w);
	rotateCenterDown(w);
	rotateTopRight(w);
	rotateTopRight(w);
}

/* This procedure completes the GREEN side by color-aligning the GREEN */
/* corners and putting the GREEN edges in place. */
static void
solveBottom(RubikWidget w)
{
	int aligned;

	/* the GREEN corners (currently in the front) should now be in their */
	/* proper locations; next, we color align them, and then move the */
	/* bottom edges into place */
	do {
		aligned = 0;
		if (colorSide(w, 1, 0) == GREEN)
			aligned++;
		if (colorSide(w, 1, 2) == GREEN)
			aligned++;
		if (colorSide(w, 1, 6) == GREEN)
			aligned++;
		if (colorSide(w, 1, 8) == GREEN)
			aligned++;

		if (aligned == 0) {
			colorAlignFront(w);
		} else if (aligned == 1) {
			/* place aligned corner in upper right */
			if (colorSide(w, 1, 0) == GREEN)
				rotateFrontCw(w);
			if (colorSide(w, 1, 6) == GREEN) {
				rotateFrontCw(w);
				rotateFrontCw(w);
			}
			if (colorSide(w, 1, 8) == GREEN)
				rotateFrontCcw(w);
			colorAlignFront(w);
		} else if (aligned == 2) {
			if (colorSide(w, 1, 0) != GREEN)
				rotateFrontCw(w);
			else if (colorSide(w, 1, 2) == GREEN)
				rotateFrontCw(w);
			if (colorSide(w, 1, 0) != GREEN)
				rotateFrontCw(w);
			colorAlignFront(w);
		} else if (aligned == 3)	/* not sure if this is possible */
			colorAlignFront(w);
	} while (aligned < 4);
}

static void
solve_2_2(RubikWidget w)
{
	int i;

	for (i = 0; i < 3; i++)	/* This is not always efficient */
		if (!checkSolved(w, False))
			rotateFrontCw(w);
}

static void
solveBottomEdges(RubikWidget w)
{
	int edge, color;

	/* next we move the bottom edges into place */
	rotateDown(w);		/* put the green face on top */
	rotateCw(w);
	rotateCw(w);

	color = colorSide(w, 1, 0);	/* get upper front corner color */
	edge = findEdge(w, GREEN, color);
	placeEdge(w, edge, GREEN);
	rotateTopRight(w);

	color = colorSide(w, 1, 0);	/* get upper front corner color */
	edge = findEdge(w, GREEN, color);
	placeEdge(w, edge, GREEN);
	rotateTopRight(w);

	color = colorSide(w, 1, 0);	/* get upper front corner color */
	edge = findEdge(w, GREEN, color);
	placeEdge(w, edge, GREEN);
	rotateTopRight(w);

	color = colorSide(w, 1, 0);	/* get upper front corner color */
	edge = findEdge(w, GREEN, color);
	placeEdge(w, edge, GREEN);
	rotateTopRight(w);

	/* now, align the fourth blue edge piece (if necessary) */
	rotateCw(w);
	rotateCw(w);
	edge = findEdge(w, BLUE, WHITE);
	if (edge == 1) {
		if (colorSide(w, 1, 1) == BLUE) {
			rotateFrontCcw(w);
			rotateCenterLeft(w);
			rotateFrontCw(w);
			rotateCenterLeft(w);
			rotateFrontCw(w);
			rotateCenterLeft(w);
			rotateFrontCcw(w);
		}
	} else {
		if (edge == 5)
			rotateCenterRight(w);
		else if (edge == 7)
			rotateCenterLeft(w);
		else if (edge == 8) {
			rotateCenterRight(w);
			rotateCenterRight(w);
		}
		alignLastEdge(w);
	}
}

/* This procedure completes the solution process by placing the */
/* remaining edges in place and alignment. */
static void
alignEdges(RubikWidget w)
{
	int aligned, color, edge;

	/* move the red side to the front */
	if (colorSide(w, 1, 4) == YELLOW)
		rotateRight(w);
	else if (colorSide(w, 1, 4) == ORANGE) {
		rotateRight(w);
		rotateRight(w);
	} else if (colorSide(w, 1, 4) == WHITE)
		rotateLeft(w);

	/* rotate the top until its aligned with the center colors */
	edge = findEdge(w, BLUE, RED);
	if (edge == 2)
		rotateTopLeft(w);
	else if (edge == 3) {
		rotateTopLeft(w);
		rotateTopLeft(w);
	} else if (edge == 4)
		rotateTopRight(w);

	/* rotate the bottom until its aligned with the center colors */
	edge = findEdge(w, GREEN, RED);
	if (edge == 10)
		rotateBottomLeft(w);
	else if (edge == 11) {
		rotateBottomLeft(w);
		rotateBottomLeft(w);
	} else if (edge == 12)
		rotateBottomRight(w);

	if (checkSolved(w, False))
		return;

	rotateCcw(w);		/* place unaligned edges vertically */

	/* see if any edges are in correct position */
	aligned = 0;
	edge = findEdge(w, RED, YELLOW);
	if (edge == 1)
		aligned++;
	edge = findEdge(w, YELLOW, ORANGE);
	if (edge == 3)
		aligned++;
	edge = findEdge(w, ORANGE, WHITE);
	if (edge == 11)
		aligned++;
	edge = findEdge(w, WHITE, RED);
	if (edge == 9)
		aligned++;

	if (aligned == 0) {
		shuffleEdges(w);	/* put one edge into position */
		aligned++;
	}
	if (aligned == 1) {
		/* find the correct piece and move it to the back bottom edge */
		edge = findEdge(w, RED, YELLOW);
		if (edge == 1) {
			rotateDown(w);
			rotateDown(w);
		} else {
			edge = findEdge(w, YELLOW, ORANGE);
			if (edge == 3)
				rotateUp(w);
			else {
				edge = findEdge(w, WHITE, RED);
				if (edge == 9)
					rotateDown(w);
			}
		}

		/* shuffle */
		color = colorSide(w, 1, 4);
		if (colorSide(w, 1, 7) == color) {
			rotateRight(w);
			rotateRight(w);
			rotateDown(w);
			shuffleEdges(w);
		} else if (colorSide(w, 6, 1) == color) {
			rotateRight(w);
			rotateRight(w);
			rotateDown(w);
			shuffleEdges(w);
		} else
			shuffleEdges(w);
	}
	/* pieces should be in place; complete color alignment */
	/* find number of unaligned edge pieces and fix them */
	aligned = 0;
	if (colorSide(w, 1, 1) == colorSide(w, 1, 4))
		aligned++;
	if (colorSide(w, 1, 7) == colorSide(w, 1, 4))
		aligned++;
	if (colorSide(w, 3, 1) == colorSide(w, 3, 4))
		aligned++;
	if (colorSide(w, 3, 7) == colorSide(w, 3, 4))
		aligned++;
	if (aligned == 0) {
		recolorTopEdges(w);
		rotateDown(w);
		rotateDown(w);
		recolorTopEdges(w);
	} else if (aligned == 2) {
		if (colorSide(w, 1, 1) == colorSide(w, 1, 4))
			do {
				rotateDown(w);
			} while (colorSide(w, 1, 1) == colorSide(w, 1, 4));
		if (colorSide(w, 1, 7) != colorSide(w, 1, 4))
			rotateUp(w);
		recolorTopEdges(w);
		if (!checkSolved(w, False)) {
			rotateDown(w);
			recolorTopEdges(w);
		}
	}
}

/* Wrong center rotation on top and front */
static void
shuffle2_180(RubikWidget w)
{
	int i;

	for (i = 0; i < 3; i++)
		shuffleEdges(w);
}

/* Wrong center rotation on top */
static void
shuffle1_180(RubikWidget w, Boolean Top)
{
	int i;

	if (Top) {
		for (i = 0; i < 30; i++) {
			rotateTopRight(w);
			rotateFrontCw(w);
			rotateFrontCw(w);
		}
	} else {
		for (i = 0; i < 30; i++) {
			rotateTopRight(w);
			rotateTopRight(w);
			rotateFrontCw(w);
		}
	}
}

/* Pairs off by 90 degrees */
static void
shuffle2_90(RubikWidget w, Boolean CounterTop, Boolean CounterFront)
{
	int i, num;

	num = ((CounterTop && !CounterFront) || (!CounterTop && CounterFront)) ?
		63 : 105;
	for (i = 0; i < num; i++) {
		if (CounterFront)
			rotateFrontCcw(w);
		else
			rotateFrontCw(w);
		if (CounterTop)
			rotateTopRight(w);
		else
			rotateTopLeft(w);
	}
}

static void
solveAdjCenters(RubikWidget w)
{
	int face0 = mapFace(w, 5), face1 = mapFace(w, 1);

	if ((face0 == 2 && face1 != 0) ||
			(face1 == 2 && face0 != 0)) {
		shuffle2_180(w);
	} else if (face0 == 2 && face1 == 0) {
		shuffle1_180(w, True);
	} else if (face0 == 0 && face1 == 2) {
		shuffle1_180(w, False);
	} else if (face0 == 1 && face1 == 1) {
		shuffle2_90(w, True, True);
	} else if (face0 == 3 && face1 == 1) {
		shuffle2_90(w, True, False);
	} else if (face0 == 1 && face1 == 3) {
		shuffle2_90(w, False, True);
	} else if (face0 == 3 && face1 == 3) {
		shuffle2_90(w, False, False);
	}
}

static void
solveOppCenters(RubikWidget w)
{
	int face0, face1, face2;
	Boolean fixOp = False;

	face0 = mapFace(w, 5);
	face1 = mapFace(w, 1);
	face2 = mapFace(w, 4);
	if ((face1 == 1) || (face1 == 3)) {
		rotateUp(w);
		fixOp = True;
	} else if ((face2 == 1) || (face2 == 3)) {
		rotateCw(w);
		fixOp = True;
	} else if ((face0 == 1) || (face0 == 3))
		fixOp = True;
	if (!fixOp)
		return;
	face0 = mapFace(w, 5);
	face1 = mapFace(w, 1);
	if (face0 == 1)
		shuffle2_90(w, False, True);
	else /* face0 == 3 */
		shuffle2_90(w, True, False);
	rotateUp(w);
	face0 = mapFace(w, 5);
	face1 = mapFace(w, 1);
	if (face0 == 1 && face1 == 1) {
		shuffle2_90(w, True, True);
	} else if (face0 == 3 && face1 == 1) {
		shuffle2_90(w, True, False);
	} else if (face0 == 1 && face1 == 3) {
		shuffle2_90(w, False, True);
	} else if (face0 == 3 && face1 == 3) {
		shuffle2_90(w, False, False);
	}
}

static void
solveCenters(RubikWidget w)
{
	solveAdjCenters(w); /* 5-1 */
	rotateUp(w);
	rotateUp(w);
	solveAdjCenters(w); /* 6-3 */
	rotateCw(w);
	solveAdjCenters(w); /* 4-3 */
	rotateUp(w);
	solveAdjCenters(w); /* 3-2 */
	/* only 90 degree matches left */
	rotateUp(w);
	solveAdjCenters(w); /* 2-1 */
	rotateUp(w);
	solveAdjCenters(w); /* 1-4 */
	rotateCcw(w);
	solveAdjCenters(w); /* 5-4 */
	rotateUp(w);
	solveAdjCenters(w); /* 4-6 */
	rotateUp(w);
	solveAdjCenters(w); /* 6-2 */
	rotateUp(w);
	solveAdjCenters(w); /* 2-5 */
	rotateCcw(w);
	rotateUp(w);
	solveAdjCenters(w); /* 1-6 */
	rotateUp(w);
	rotateUp(w);
	solveAdjCenters(w); /* 3-5 */
	/* only 1 90 degree matches left possible on opposite sides */
	solveOppCenters(w);
}

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

		if (!checkSolved(w, w->rubik.orient)) {
			solveTop(w);
			alignCorners(w);
			solveBottom(w);
			if (w->rubik.sizex > 2) {
				solveBottomEdges(w);
				alignEdges(w);
				if (w->rubik.orient)
					solveCenters(w);
			} else if (w->rubik.sizex == 2)
				solve_2_2(w);
		}
	}
#ifdef JMP
	else {
		drawAllPieces(w);
	}
	abortSolvingFlag = False;
#endif
	solvingFlag = False;
	w->rubik.cheat = True; /* Assume the worst. */
	setPuzzle(w, ACTION_CHEAT);
	setPuzzle(w, ACTION_COMPUTED);
}
