Volume Number: 18 (2002)
Issue Number: 06
Column Tag: Programmer's Challenge

by Bob Boonstra, Westford, MA

Matchsticks

Some time ago, Robin Landsbert sent me a suggestion for a Challenge based on a game he called Nim. In Robin’s version of the game, matchsticks were arranged in rows forming a triangle, one matchstick in the top row, two in the next, three in the next, etc. Two players take turns removing one or more matchsticks from any single row of the board. The object is to make your opponent take the last matchstick.

A little research suggests that this version of the game might not be very difficult. So, in the tradition of the Challenge, we will add a few twists that might make the game (and the Challenge) more interesting. First, we will arrange our matchsticks in a square grid instead of a triangular one, and allow players to remove matchsticks from either a single row or a single column on a given turn. Second, we will not put a matchstick in every position in the grid, leaving a small number of positions empty, perhaps on the order of 10%. Third, we will restrict a player’s moves to removing matchsticks with no intervening holes. That is, a player can remove the n+1 matchsticks in row r located in columns c through c+n only if a matchstick is present in each of those locations. And finally, we will play two versions of the game, one where the player taking the last matchstick loses the game, and one where the player taking the last one wins the game.

The prototype for the code you should write is:

void InitMatchsticks(
   short dimension,      
      /* game is played on a square board of size dimension x dimension */
   const char *board,
      /* board[row*dimension + col] is board cell (row,col) */
      /* board[]==1 represents a matchstick, ==0 represents an empty cell */
   bool playFirst,
      /* true if you will play first in this game */
   bool lastMatchstickLoses,
      /* true if taking the last matchstick loses the game, 
         false if taking the last one wins the game */
   short opponent
      /* identifier for your opponent in this game */
);

void OpponentMove(
   bool playingRow,
      /* true if opponent played along a row, false if along a column */
   short rowOrColumnNumber,
      /* number of the (origin zero) row (playingRow==true) or 
         column (playingRow==false)
         that the opponent played */
   short startingColOrRow,
   short endingColOrRow,
      /* if playingRow==true, the opponent played from 
            (row,col)==(rowOrColumnNumber,startingColOrRow)
         to (row,col)==(rowOrColumnNumber,endingColOrRow)
         if playingRow==false, the opponent played from 
            (row,col)==(startingColOrRow,rowOrColumnNumber)
         to (row,col)==(endingColOrRow,rowOrColumnNumber)
      */
   const char *board
      /* board after your opponent's move */  
);


const char *YourMove(
   bool *playingRow,
      /* true if you played along a row, false if along a column */
   short *rowOrColumnNumber,
      /* number of the (origin zero) row (playingRow==true) or 
         column (playingRow==false)
         that you played */
   short *startingColOrRow,
   short *endingColOrRow
      /* if *playingRow==true, you played from 
            (row,col)==(*rowOrColumnNumber,*startingColOrRow)
         to (row,col)==(*rowOrColumnNumber,*endingColOrRow)
         if *playingRow==false, you played from 
            (row,col)==(*startingColOrRow,*rowOrColumnNumber)
         to (row,col)==(*endingColOrRow,*rowOrColumnNumber)
      */
   /* return value is a pointer to a board after your move */  
);

The objective of the Challenge is to win as many games as possible against your fellow contestants, while expending as little execution time as possible. Each game begins with a call to your InitMatchsticks routine, where you are given the dimension of the game, the initial board configuration, the identity of your opponent, whether or not you playFirst, and whether the objective is to take or not take the last matchstick (lastMatchstickLoses). When it is your turn to move, your YourMove routine describes the move you are making (playingRow, rowOrColumnNumber, startingColOrRow, endingColOrRow) and returns a pointer to your view of what the board looks like after your move. When your opponent moves, your OpponentMove routine is provided with a description of the opponent’s move, and the board configuration after that move.

The Challenge will be scored as a round robin tournament, or another fair scheduling mechanism. Each player will play first and play second against each scheduled opponent an equal number of times for each test case. Each player will play to win by taking the last matchstick, and play to win by making the opponent take the last matchstick, an equal number of times against each scheduled opponent for each test case. A player’s score will be dimension^2 points for each win, minus a penalty of 10 points per millisecond of execution time. You can earn a bonus of up to 25% of your score based on a subjective evaluation of the clarity of your code and commentary.

This will be a native PowerPC Carbon Challenge, using the Metrowerks CodeWarrior Pro 7.0 development environment. Please be certain that your code is carbonized, as I may evaluate this Challenge using Mac OS X. Unfortunately, this Challenge cannot accommodate alternative development environments, because pairs of solutions need to compete against one another in a single executable.

Winner of the March, 2002 Challenge

The March Challenge required contestants to solve the Megaminx, a twelve-sided puzzle in the shape of a dodecahedron. Each of the twelve faces of the Megaminx can be rotated clockwise or counter-clockwise, with five consecutive rotations of a face in the same direction bringing the face back to its original position. Each face is divided into eleven facelets, five corner facelets that each border three faces, five edge facelets that each border two faces, and one center facelet. The faces are colored with six colors, opposite faces sharing the same color. The input for the Challenge was a sequence of files that each described a scrambled Megaminx, and the required output was a sequence of rotations that solved the puzzle. Scoring was based on the execution time required to solve the scrambled puzzles. Contestants earned up to a 25% reduction in their time if they also displayed the puzzle solution.

Two contestants, Ernst Munter and Allen Stenger, submitted solutions for this Challenge. Both contestants acknowledge the information provided at two Megaminx web sites, one provided by Meffert’s Puzzles at http://www.meffertspuzzles.com/puzzles/megasol1.html, and another by W. D. Joyner. Ernst used the approach described in http://web.usna.navy.mil/~wdj/megam.htm, one that solved the problem quickly, but generated solutions with a large number of moves. Ernst first moved the corner pieces to the proper positions, then moved the edge pieces to the proper positions, then oriented the corners, then oriented the edges. Allen took the nine-step approach described at the Meffert site, augmented with a modification from http://web.usna.navy.mil/~wdj/megaminx.htm, an approach that generated shorter move sequences, but took more execution time.

Both contestants provided display options in their entries. Ernst’s program has a compile-time option to generate a two-dimensional depiction of the Megaminx as the solution is generated. He included an option to display macro moves in a single step, which made it easier to see what was going on. Allen’s entry has a separate program, written in Cocoa and using OpenGL to display a three-dimensional Megaminx. Allen included options to read in a puzzle description file and a sequence of moves, controls to rotate the viewpoint, and controls to rotate a slice of the puzzle.

By the stated rules of this contest, the solution requiring the least amount of execution time, after considering the display bonus, is the winner. Congratulations to Ernst Munter (Kanata, ON, Canada) for winning the Megaminx Challenge. I am taking the somewhat unusual step, however, of providing both solutions in the online archive, and printing the better-commented solution by Allen Stenger in this article.

The table below lists, for each of the solutions submitted, the total execution time in microseconds, the time reduction awarded for providing a display option, the net penalty points after subtracting the bonus from the execution time, and the cumulative number of moves required to solve the ten test cases used to evaluate solutions. It also lists the programming language of each entry. As usual, the number in parentheses after the entrant's name is the total number of Challenge points earned in all Challenges prior to this one.

Name	Exec. Time	Display	Penalty	Moves	Language		(microsecs)	Bonus	Points
Ernst Munter (275)	37331	25%	27998	15030	C++
Allen Stenger (39)	347335	25%	260501	6440	C++/ObjC

Top Contestants . . .

Listed here are the Top Contestants for the Programmer’s Challenge, including everyone who has accumulated 20 or more points during the past two years. The numbers below include points awarded over the 24 most recent contests, including points earned by this month's entrants.

Rank	Name	Points	Wins	Total				(24 mo)	(24 mo)	Points
1.	Munter, Ernst	275	10	862
2.	Saxton, Tom	52	1	210
3.	Stenger, Allen	49	1	114
4.	Rieken, Willeke	46	2	134
5.	Wihlborg, Claes	40	2	49
6.	Taylor, Jonathan	37	1	63
9.	Gregg, Xan	20	1	140
10.	Mallett, Jeff	20	1	114
11.	Cooper, Tony	20	1	20

. . . and the Top Contestants Looking for a Recent Win

In order to give some recognition to other participants in the Challenge, we also list the high scores for contestants who have accumulated points without taking first place in a Challenge during the past two years. Listed here are all of those contestants who have accumulated 6 or more points during the past two years.

Rank	Name	Points(24 mo)	Total Points
7.	Sadetsky, Gregory	22	24
8.	Boring, Randy	21	144
13.	Schotsman, Jan	16	16
14.	Shearer, Rob	15	62
15.	Hart, Alan	14	39
16.	Nepsund, Ronald	10	57
17.	Day, Mark	10	30
18.	Desch, Noah	10	10
19.	Flowers, Sue	10	10
20.	Maurer, Sebastian	7	108
21.	Leshner, Will	7	7
22.	Miller, Mike	7	7

There are three ways to earn points: (1) scoring in the top 5 of any Challenge, (2) being the first person to find a bug in a published winning solution or, (3) being the first person to suggest a Challenge that I use. The points you can win are:

1st place			20 points
2nd place			10 points
3rd place			7 points
4th place			4 points
5th place			2 points
finding bug			2 points
suggesting Challenge			2 points

Here is Allen’s Megaminx solution:

CSolver.cpp

//////////////////////////////////////////////////////////////////////
//
// Megaminx (MacTech Programmer's Challenge, March 2002)
// Written by Allen Stenger, March 2002
//
// Conceptually we rotate colors rather than faces; this simplifies the problem of 
// determining the orientation of each edge and  corner piece.
//
// We follow the solution given by Meffert's Puzzles and Novelties;
// see http://www.mefferts-puzzles.com/puzzles/megasol1.html
//
// Terminology: corner piece is at a vertex of the Megaminx and has three facelets, 
// edge piece is at an edge between two faces and has two facelets. The smaller 
// pentagons in the center of each face never move away from the face and so we 
// ignore them.
//
// A vertex can be specified by its vertex number, however edges don't have numbers 
// and are usually specified by the two faces they lie on. There is a variety of constant 
// tables for walking through the faces.
// 
// COLOR AMBIGUITY
//
// Because the same colors are used for two faces, it appears that there might be some 
// ambiguity in the pieces; that is, radially-opposite corners have the same colors, and 
// and radially-opposite edges have the same colors,so how do we know whether to 
// place a corner or edge in the Northern or Southern part of the Megaminx?
//
// * The corners are actually not ambiguous because the orientations
//   are different; so for example there are two corners with
//   colors 1,2,3, but the one on the North Pole has the colors
//   1,2,3 in clockwise order and the one on the South Pole has
//   1,2,3 in counter-clockwise order. Therefore we can always
//   tell from the corner which part of the Megaminx it goes in.
// * The edges really are ambiguous. It is not necessary to put
//   each edge back in its original place, but in some situations
//   we would get to Step 8 and be unable to orient the South
//   Pole edges because of an earlier placement we made. To solve 
//   the Megaminx we must follow some parity rules; see
//
//       Coreyanne Rickwalt, "The Fundamental Theorem of the
//        Megaminx", http://web.usna.navy.mil/~wdj/megaminx.htm.
//
//   We will detect the problem case in Step 6 and take evasive action.
//
// A simple example of the problem is a Megaminx that is solved except
// for the two edges:
//     8,7,3
//     9,7,2
// This one cannot be solved by the published Meffert method because
// the South Pole edges are not correctly placed in Step 8.
//
//////////////////////////////////////////////////////////////////////

#include "CSolver.h"
#include "CMegaminx.h"
#include "CMegaminxApp.h"

#include 
#include 


// some fixed faces we use
const int kSouthPoleFace = 7;

//////////////////////////////////////////////////////////////////////

CSolver::CSolver(CMegaminx& rMega) :
fMega(rMega)
{
}

CSolver::~CSolver()
{
}

   
void CSolver::Solve()
{
   // call all the solution steps
   Step3();
   Step4();
   Step5();
   Step6();
   Step7();
   Step8();
   Step9();
   Step10();
   Step11();
}
   
void CSolver::DoLUU(CMegaminx::face_t leftFace, CMegaminx::face_t rightFace)
{
   fMega.WriteComment("DoLUU");
   fMega.Slice(leftFace, CMegaminx::eCounterCW, 1);
   fMega.Slice(rightFace, CMegaminx::eCW, 1);
   fMega.Slice(leftFace, CMegaminx::eCW, 1);
   fMega.Slice(rightFace, CMegaminx::eCounterCW, 1);
}

void CSolver::DoRUU(CMegaminx::face_t leftFace, CMegaminx::face_t rightFace)
{
   fMega.WriteComment("DoRUU");
   fMega.Slice(rightFace, CMegaminx::eCW, 1);
   fMega.Slice(leftFace, CMegaminx::eCounterCW, 1);
   fMega.Slice(rightFace, CMegaminx::eCounterCW, 1);
   fMega.Slice(leftFace, CMegaminx::eCW, 1);
}

void CSolver::DoRLL(CMegaminx::face_t leftFace, CMegaminx::face_t rightFace)
{
   fMega.WriteComment("DoRLL");
   fMega.Slice(rightFace, CMegaminx::eCounterCW, 1);
   fMega.Slice(leftFace, CMegaminx::eCW, 1);
   fMega.Slice(rightFace, CMegaminx::eCW, 1);
   fMega.Slice(leftFace, CMegaminx::eCounterCW, 1);
}

void CSolver::DoLLL(CMegaminx::face_t leftFace, CMegaminx::face_t rightFace)
{
   fMega.WriteComment("DoLLL");
   fMega.Slice(leftFace, CMegaminx::eCW, 1);
   fMega.Slice(rightFace, CMegaminx::eCounterCW, 1);
   fMega.Slice(leftFace, CMegaminx::eCounterCW, 1);
   fMega.Slice(rightFace, CMegaminx::eCW, 1);
}

void CSolver::VisitAllCorners(CCornerVisitor &aVisitor)
{
   for (int i = 0; i < CMegaminx::kNumVertices; i++)
      aVisitor.VisitCorner(i);
}

bool CSolver::CheckEdgeParity()
{
   // this holds the permutation of the South edges. It is
   // in two 5-edge pieces:
   // 0-4: South Equator edges, indexed same as SouthEqEdge arrays
   // 5-9: South Pole edges, indexed same as SoutPoleEdge arrays + 5
   // The entries are also these indices; perm[i] contains the edge
   // index that edge i will go to when the Megaminx becomes solved.
   // Therefore the entries in perm are the numbers 0-9 in some 
   // permuted order.
   int perm[10];
   
   for (int i = 0; i < 10; i++)
      perm[i] = 0;
      
   // South Equator edges
   for (int i = 0; i < CMegaminx::kNumSouthEqEdges; i++)
   {
      CMegaminx::color_t c0 = 
         fMega.EdgeFaceletColor(fMega.kSouthEqEdgeL[i], 
                        fMega.kSouthEqEdgeR[i]);
      CMegaminx::color_t c1 = 
         fMega.EdgeFaceletColor(fMega.kSouthEqEdgeR[i], 
                        fMega.kSouthEqEdgeL[i]);
      perm[i] = ParityLookup(c0, c1);
   }
   
   // South Pole edges
   for (int i = 0; i < CMegaminx::kNumSouthPoleEdges; i++)
   {
      CMegaminx::color_t c0 = 
         fMega.EdgeFaceletColor(fMega.kSouthPoleEdgeN[i], 
                        fMega.kSouthPoleEdgeS[i]);
      CMegaminx::color_t c1 = 
         fMega.EdgeFaceletColor(fMega.kSouthPoleEdgeS[i], 
                        fMega.kSouthPoleEdgeN[i]);
      perm[i + 5] = ParityLookup(c0, c1);
   }
   
   // Now figure out the parity of perm
   bool bVisitedPerm[10];   
         // indexed same as perm; whether we
         // have counted that transition
   int cycleLengths = 0;   // sum of (cycle length - 1)
         
   for (int i = 0; i < 10; i++)
      bVisitedPerm[i] = false;
   for (int i = 0; i < 10; i++)
   {
      if (bVisitedPerm[i])
         continue;
         
      // follow the cycle starting at perm[i]
      int next = i;
      while (!bVisitedPerm[next])
      {
         cycleLengths++;
         bVisitedPerm[next] = true;
         next = perm[next];
      }
      cycleLengths--;
   }
   
   bool bEvenParity = ((cycleLengths & 1) == 0);
   return bEvenParity;
}

// look up the correct Southern edge for these colors; returns
// index into SouthEq table, or index + 5 into SouthPole table
int CSolver::ParityLookup(CMegaminx::color_t c0, CMegaminx::color_t c1)
{
   for (int i = 0; i < CMegaminx::kNumSouthEqEdges; i++)
   {
      CMegaminx::color_t trialColor0 = 
         CMegaminx::CorrectColor(CMegaminx::kSouthEqEdgeL[i]);
      CMegaminx::color_t trialColor1 = 
         CMegaminx::CorrectColor(CMegaminx::kSouthEqEdgeR[i]);
      if ((c0 == trialColor0 && c1 == trialColor1) ||
         (c1 == trialColor0 && c0 == trialColor1))
         return i;
   }
   
   for (int i = 0; i < CMegaminx::kNumSouthPoleEdges; i++)
   {
      CMegaminx::color_t trialColor0 = 
         CMegaminx::CorrectColor(CMegaminx::kSouthPoleEdgeN[i]);
      CMegaminx::color_t trialColor1 = 
         CMegaminx::CorrectColor(CMegaminx::kSouthPoleEdgeS[i]);
      if ((c0 == trialColor0 && c1 == trialColor1) ||
         (c1 == trialColor0 && c0 == trialColor1))
         return i + 5;
   }
   
   assert(false);   // trouble, no match
   return 0;
}

#pragma mark === Solution Steps ===

//////////////////////////////////////////////////////////////////////
// Solution Steps
//////////////////////////////////////////////////////////////////////

void CSolver::Step3()
{
   Step3Edges();
   Step3Corners();
   
   Step3Verify();
}

void CSolver::Step3Edges()
{
   for (int i = 0; i < CMegaminx::kNumNorthPoleEdges; i++)
   {
      CMegaminx::face_t destFaceN = CMegaminx::kNorthPoleEdgeN[i];
      CMegaminx::face_t destFaceS = CMegaminx::kNorthPoleEdgeS[i];
      if (fMega.IsEdgeCorrect(destFaceN, destFaceS))
         continue;   // already done!
         
      // if not the correct colors, find an edge that does have
      // the correct colors and drop it to the South Pole.
      // the return value is the South Equatorial face where
      // it got dropped.
      CMegaminx::color_t c0 = fMega.CorrectColor(destFaceN);
      CMegaminx::color_t c1 = fMega.CorrectColor(destFaceS);
      CMegaminx::face_t southPoleFace = Step3_4Drop(c0, c1);
      
      // now loft it back to the North Pole; first rotate
      // the South Pole so the edge touches the "down right" face.
      CMegaminx::face_t rotToFace = 
            CMegaminx::kFaceDownRight[destFaceS];
      int dist = Distance(southPoleFace, rotToFace);
      
      fMega.Slice(kSouthPoleFace, CMegaminx::eCounterCW, dist);
      fMega.Slice(rotToFace, CMegaminx::eCW, 2);
      fMega.Slice(destFaceS, CMegaminx::eCounterCW, 2);
      
      // if the edge is not correctly oriented we need
      // to reorient it
      if (fMega.EdgeFaceletColor(destFaceN, destFaceS) != 1)
      {
         fMega.Slice(destFaceS, CMegaminx::eCounterCW, 2);
         int nextSouthFace = fMega.NextSouthEqFace(rotToFace);
         fMega.Slice(nextSouthFace, CMegaminx::eCW, 1);
         fMega.Slice(rotToFace, CMegaminx::eCW, 1),
         fMega.Slice(destFaceS, CMegaminx::eCounterCW, 2);         
      }
   }
}

// returns face we dropped it to
CMegaminx::face_t CSolver::Step3_4Drop(CMegaminx::color_t c0, 
                     CMegaminx::color_t c1)
{
   fMega.WriteComment("Step3_4Drop");
   // search the lower edges for one having these colors
   // (in either order), and if found move it to
   // the South Pole.
   
   bool bFound = false;
   CMegaminx::face_t southPoleFace = 0;   
            // edge dropped to this face-SouthPole
   
   // search the South Pole edges, and if found we are done!
   if (!bFound)
   {
      for (int i = 0; i < CMegaminx::kNumSouthPoleEdges && !bFound;
                            i++)
      {
         CMegaminx::face_t trialFaceN = 
                  CMegaminx::kSouthPoleEdgeN[i];
         CMegaminx::face_t trialFaceS = 
                  CMegaminx::kSouthPoleEdgeS[i];
         if (fMega.EdgeHasColors(trialFaceN, trialFaceS, c0, c1))
         {
            fMega.WriteComment("Step3_4Drop found on South Pole");
            bFound = true;
            southPoleFace = trialFaceN;
         }
      }
   }
   
   // search the South Equator edges, and if found drop
   // the edge to the South Pole by rotating its left face
   // CW 1
   if (!bFound)
   {
      for (int i = 0; i < CMegaminx::kNumSouthEqEdges && !bFound; 
                        i++)
      {
         CMegaminx::face_t trialFaceL = CMegaminx::kSouthEqEdgeL[i];
         CMegaminx::face_t trialFaceR = CMegaminx::kSouthEqEdgeR[i];
         if (fMega.EdgeHasColors(trialFaceL, trialFaceR, c0, c1))
         {
            fMega.WriteComment("Step3_4Drop found on South Equator");
            bFound = true;
            fMega.Slice(trialFaceL, CMegaminx::eCW, 1);
            southPoleFace = trialFaceL;
         }
      }
   }
   
   // search the Middle Equator edges, and if found drop
   // the edge to the South Pole by rotating its S face
   // either CW 2 or CCW 2
   if (!bFound)
   {
      for (int i = 0; i < CMegaminx::kNumMiddleEqEdges && !bFound; 
                        i++)
      {
         CMegaminx::face_t trialFaceN = CMegaminx::kMiddleEqEdgeN[i];
         CMegaminx::face_t trialFaceS = CMegaminx::kMiddleEqEdgeS[i];
         if (fMega.EdgeHasColors(trialFaceN, trialFaceS, c0, c1))
         {
            fMega.WriteComment("Step3_4Drop found on Middle Equator");
            bFound = true;
            southPoleFace = trialFaceS;
            // even indices are below and right of N face,
            // therefore above and left of S face
            if ((i & 1) == 0)
            {
               // above and left, so use CCW 2
               fMega.Slice(trialFaceS, CMegaminx::eCounterCW, 2);
            }
            else
            {
               // above and right, so use CW 2
               fMega.Slice(trialFaceS, CMegaminx::eCW, 2);
            }
         }
      }
   }
   
   // search the North Equator edges, and if found there drop to the
   // South Pole. The Meffert solution uses a simple transformation
   // in case 3 and a complicated one in case 4 (where it has to avoid
   // disturbing other North Equator edges), but we will use the
   // complicated one in both cases because the implementation
   // is easier.
   if (!bFound)
   {
      for (int i = 0; i < CMegaminx::kNumNorthEqEdges; i++)
      {
         CMegaminx::face_t trialFaceL = CMegaminx::kNorthEqEdgeL[i];
         CMegaminx::face_t trialFaceR = CMegaminx::kNorthEqEdgeR[i];
         if (fMega.EdgeHasColors(trialFaceL, trialFaceR, c0, c1))
         {
            fMega.WriteComment("Step3_4Drop found on North Equator");
            bFound = true;

            // drop to down left
            southPoleFace = CMegaminx::kFaceDownLeft[trialFaceL];
            
            fMega.Slice(southPoleFace, CMegaminx::eCounterCW, 1);
            DoLUU(trialFaceL, trialFaceR);
            DoLUU(trialFaceL, trialFaceR);
            fMega.Slice(southPoleFace, CMegaminx::eCW, 1);
            DoRUU(trialFaceL, trialFaceR);
            DoRUU(trialFaceL, trialFaceR);
            
            // at this point the edge is at the upper left of 
            // southPoleFace, so rotate it to put it on the
            // South Pole
            fMega.Slice(southPoleFace, CMegaminx::eCounterCW, 2);
         }      
      }
   }

   // search the North Pole edges, and if found drop to the 
   // South Pole. (This code should only be execute for Step 3,
   // because in Step 4 the North Pole edges have already been
   // set and we should have found the desired edge before now.)
   if (!bFound)
   {
      for (int i = 0; i < CMegaminx::kNumNorthPoleEdges; i++)
      {
         CMegaminx::face_t trialFaceN = 
               CMegaminx::kNorthPoleEdgeN[i];
         CMegaminx::face_t trialFaceS = 
               CMegaminx::kNorthPoleEdgeS[i];
         if (fMega.EdgeHasColors(trialFaceN, trialFaceS, c0, c1))
         {
            fMega.WriteComment("Step3_4Drop found on North Pole");
            bFound = true;
            
            southPoleFace = CMegaminx::kFaceDownRight[trialFaceS];
            fMega.Slice(trialFaceS, CMegaminx::eCW, 2);
            fMega.Slice(southPoleFace, CMegaminx::eCounterCW, 2);
         }
      }
   }

   assert(bFound);

   return southPoleFace;
}


void CSolver::Step3Corners()
{
   for (CMegaminx::vertex_t destCorner = 0; destCorner < 5; 
                        destCorner++)
   {
      // maybe corner is already done!
      if (fMega.IsCornerCorrect(destCorner))
         continue;
         
      fMega.WriteComment("Step3Corners");
      // find the corner that should be here, and drop
      // it to the South Pole and move it into place.
      CMegaminx::color_t destc0 = 
         fMega.CorrectColor(CMegaminx::kCornerFaces[destCorner][0]);
      CMegaminx::color_t destc1 = 
         fMega.CorrectColor(CMegaminx::kCornerFaces[destCorner][1]);
      CMegaminx::color_t destc2 = 
         fMega.CorrectColor(CMegaminx::kCornerFaces[destCorner][2]);
      CMegaminx::vertex_t srcCorner =    
         fMega.CornerHavingColors(destc0, destc1, destc2);
         
      // special transformation if the src is at the
      // North Pole
      if (fMega.IsNorthPoleVertex(srcCorner))
      {
         fMega.WriteComment("Step3Corners drop North Pole corner");
         CMegaminx::face_t faceL = 
                        CMegaminx::kCornerFaces[srcCorner][1];
         CMegaminx::face_t faceR = 
                        CMegaminx::kCornerFaces[srcCorner][2];
         DoRUU(faceL, faceR);
         srcCorner += 5;   // corner has dropped to North Equator
      }
      
      // drop the corner to the South Pole (if it is not
      // already there)
      if (fMega.IsNorthEquatorVertex(srcCorner))
      {
         fMega.Slice(CMegaminx::kFaceBelow[srcCorner], 
                     CMegaminx::eCW, 2);
         srcCorner += 10;   // corner has dropped to South Pole
      }
      else if (fMega.IsSouthEquatorVertex(srcCorner))
      {
         fMega.Slice(CMegaminx::kFaceBelow[srcCorner], 
                     CMegaminx::eCW, 1);
         srcCorner += 5;
      }
      
      // rotate the vertex into place
      int moveToCorner = destCorner + 15;
      int dist = Distance(srcCorner, moveToCorner);
      fMega.Slice(kSouthPoleFace, CMegaminx::eCW, dist);
      
      // lift the vertex into place on the North Equator
      int bottomFace = CMegaminx::kFaceBelow[destCorner + 5];
      fMega.Slice(bottomFace, CMegaminx::eCounterCW, 2);
      
      // figure out the orientation and apply the correct
      // transformation to lift it to the North Pole
      CMegaminx::face_t leftFace = 
                     CMegaminx::kFaceBelow[destCorner];
      CMegaminx::face_t rightFace = 
                     CMegaminx::PrevNorthEqFace(leftFace);
      if (fMega.CornerFaceletColor(leftFace, rightFace, bottomFace) 
                        == 1)
      {
         // top color at left
         // NOTE: Meffert solution wrongly states to use
         // LUU in this case.
         DoRUU(leftFace, rightFace);
      }
      else if (fMega.CornerFaceletColor(rightFace, leftFace, 
                     bottomFace) == 1)
      {
         // top color at right
         DoLUU(leftFace, rightFace);      
      }
      else
      {
         // top color at bottom
         DoLUU(leftFace, rightFace);
         DoLUU(leftFace, rightFace);
         DoLUU(leftFace, rightFace);
      }
   }
}

//////////////////////////////////////////////////////////////////////
// Step 4. Setting the northern equatorial edges
//////////////////////////////////////////////////////////////////////
//
// Very similar to Step 3 edge case; the common 3_4 routine does
// most of the work.

void CSolver::Step4()
{
   for (int i = 0; i < CMegaminx::kNumNorthEqEdges; i++)
   {
      CMegaminx::face_t destFaceL = CMegaminx::kNorthEqEdgeL[i];
      CMegaminx::face_t destFaceR = CMegaminx::kNorthEqEdgeR[i];
      if (fMega.IsEdgeCorrect(destFaceL, destFaceR))
         continue;   // already done!
         
      // if not the correct colors, find an edge that does have
      // the correct colors and drop it to the South Pole.
      // the return value is the South Equatorial face where
      // it got dropped.
      CMegaminx::color_t c0 = fMega.CorrectColor(destFaceL);
      CMegaminx::color_t c1 = fMega.CorrectColor(destFaceR);
      CMegaminx::face_t southPoleFace = Step3_4Drop(c0, c1);
      
      // now loft it back to the North Equator
      // figure the face we want to be under, and
      // rotate the South Pole to get there. The
      // desired face lies directly underneath the 
      // desired edge, and therefore below and left of
      // the destfaceR.
      CMegaminx::face_t rotToFace = 
                           CMegaminx::kFaceDownLeft[destFaceR];
      int dist = Distance(southPoleFace, rotToFace);
      fMega.Slice(kSouthPoleFace, CMegaminx::eCounterCW, dist);
      
      // rotate rotToFace either CW 2 or CCW 2 to bring
      // the edge adjacent faceL or faceR; we pick the
      // rotation so that the facelet on the face
      // has the face color. This facelet is currently
      // on the South Pole face.
      // Finally we'll move it into the correct edge.
      //
      // We combine the CW 2 and CCW 1 to get CW 1, and
      // similarly.
      int faceletColor = fMega.EdgeFaceletColor(kSouthPoleFace, 
                  rotToFace);
      if (faceletColor == destFaceL)
      {
         fMega.Slice(rotToFace, CMegaminx::eCW, 1);   // = CW 2 and CCW 1
         DoLUU(destFaceL, destFaceR);
         DoLUU(destFaceL, destFaceR);
         fMega.Slice(rotToFace, CMegaminx::eCW, 1);
         DoRUU(destFaceL, destFaceR);
         DoRUU(destFaceL, destFaceR);
      }
      else
      {
         fMega.Slice(rotToFace, CMegaminx::eCounterCW, 1);
               // = CCW 2 and CW 1
         DoRUU(destFaceL, destFaceR);
         DoRUU(destFaceL, destFaceR);
         fMega.Slice(rotToFace, CMegaminx::eCounterCW, 1);
         DoLUU(destFaceL, destFaceR);
         DoLUU(destFaceL, destFaceR);
      }
   }
   
   Step4Verify();
}



//////////////////////////////////////////////////////////////////////
// Step 5. Setting the northern equatorial corners
//////////////////////////////////////////////////////////////////////
//
// We step through the vertices, finding the correctly-oriented
// corner that belongs there. To transfer the corner, drop it to
// the South Pole, rotate, then rotate up to the North Equator.
void CSolver::Step5()
{
   for (int destVertex = CMegaminx::kFirstNorthEqVertex; 
         destVertex <= CMegaminx::kLastNorthEqVertex; destVertex++)
   {
      if (fMega.IsCornerCorrect(destVertex))
         continue;   // already OK, skip this one
      
      // Find the corner whose colors should be moved here. This 
      // may be the same corner, if it is not oriented correctly.
      int c0 = 
         fMega.CorrectColor(CMegaminx::kCornerFaces[destVertex][0]);
      int c1 = 
         fMega.CorrectColor(CMegaminx::kCornerFaces[destVertex][1]);
      int c2 = 
         fMega.CorrectColor(CMegaminx::kCornerFaces[destVertex][2]);
      int srcVertex = fMega.CornerHavingColors(c0, c1, c2);
      if (srcVertex != destVertex)
         Step5PlaceVertex(srcVertex, destVertex);
      Step5OrientVertex(destVertex);
   }
   Step5Verify();
}

// place and position the srcVertex into the destVertex
void CSolver::Step5PlaceVertex(int srcVertex, int destVertex)
{
   // drop the src to the South Pole if needed
   int southPoleFromVertex = srcVertex;
   if (fMega.IsNorthEquatorVertex(srcVertex))
   {
      fMega.WriteComment("Step5PlaceVertex from North Equator");
      southPoleFromVertex = srcVertex + 10;
      fMega.Slice(CMegaminx::kFaceBelow[srcVertex], 
               CMegaminx::eCW, 2);
   }
   else if (fMega.IsSouthEquatorVertex(srcVertex))
   {
      // moving this vertex also disturbs the North Equator
      // vertex on this face, which might already be correctly
      // placed, so we must rotate the face back after all
      // movements are done. We will handle this by
      // rotating the South Pole face CounterCW by 1 and
      // then reversing the face rotation.
      fMega.WriteComment("Step5PlaceVertex from South Equator");
      southPoleFromVertex = srcVertex + 5;
      int rot2Face = CMegaminx::kFaceBelow[srcVertex];
      fMega.Slice(rot2Face, CMegaminx::eCW, 1);
      fMega.Slice(kSouthPoleFace,CMegaminx::eCounterCW, 1);
      fMega.Slice(rot2Face, CMegaminx::eCounterCW, 1);
   }
   
   // figure where we need to rotate South Pole to, and the
   // face to rotate CounterCW to loft to final position
   fMega.WriteComment("Step5PlaceVertex move vertex into place");
   int southPoleToVertex = destVertex + 10;
   
   // rotate the South Pole CW into position
   int dist = Distance(southPoleFromVertex, southPoleToVertex);
   fMega.Slice(kSouthPoleFace, CMegaminx::eCW, dist);
   
   // raise the src into the dest
   int homeFace = CMegaminx::kFaceBelow[destVertex];
   fMega.Slice(homeFace, CMegaminx::eCounterCW, 2);
}

void CSolver::Step5OrientVertex(int destVertex)
{
   fMega.WriteComment("Step5OrientVertex");
   // orient the corner, if needed
   // figure the colors of the corner facelets and see if
   // we need to rotate the corner
   CMegaminx::face_t belowFace = 
            CMegaminx::kFaceBelow[destVertex];

   CMegaminx::color_t belowColor = fMega.CorrectColor(belowFace);
      // color of bottom face
   CMegaminx::face_t rightFace = 
            CMegaminx::kFaceAbove[destVertex];
   CMegaminx::face_t leftFace = 
            CMegaminx::NextNorthEqFace(rightFace);
   if (fMega.CornerFaceletColor(leftFace, rightFace, belowFace) ==
                   belowColor)
   {
      fMega.Slice(belowFace, CMegaminx::eCW, 2);
      fMega.Slice(kSouthPoleFace, CMegaminx::eCounterCW, 1);
      fMega.Slice(belowFace, CMegaminx::eCW, 2);
   }
   else if (fMega.CornerFaceletColor(rightFace, belowFace, 
                     leftFace) == belowColor)
   {
      fMega.Slice(belowFace, CMegaminx::eCounterCW, 2);
      fMega.Slice(kSouthPoleFace, CMegaminx::eCW, 1);
      fMega.Slice(belowFace, CMegaminx::eCounterCW, 2);   
   }
}

//////////////////////////////////////////////////////////////////////
// Step 6. Setting the middle equatorial edges

//////////////////////////////////////////////////////////////////////
//
// We step through the middle equatorial edges, checking to see if
// each already has the correctly positioned and placed edge, and if
// not then searching the South Pole edges, the South Equatorial
// edges, and finally the middle equatorial edges (after this one)
// for the needed edge. Note that each combination of colors has
// two edges with this combination, and (I think) they are
// interchangeable; this is unlike the situation for corners, where
// there are also two corners with a given combination, but they
// have opposite orientations and are not interchangeable.
void CSolver::Step6()
{
   for (int destFaceIndex = 0; 
         destFaceIndex < CMegaminx::kNumMiddleEqEdges;
         destFaceIndex++)
   {
      CMegaminx::face_t faceS = 
                  CMegaminx::kMiddleEqEdgeS[destFaceIndex];
      CMegaminx::face_t faceN = 
                  CMegaminx::kMiddleEqEdgeN[destFaceIndex];
      if (fMega.IsEdgeCorrect(faceS, faceN))
         continue;   // already correctly placed and positioned
      CMegaminx::color_t neededColorS = fMega.CorrectColor(faceS);
      CMegaminx::color_t neededColorN = fMega.CorrectColor(faceN);
      bool bFound = false;

      // search the polar edges
      for (int i = 0; 
            i < CMegaminx::kNumSouthPoleEdges && !bFound; i++)
      {
         CMegaminx::face_t searchPoleFace = 
                  CMegaminx::kSouthPoleEdgeN[i];
         if (fMega.EdgeHasColors(kSouthPoleFace, searchPoleFace, 
                        neededColorS, neededColorN))
         {
            bFound = true;
            fMega.WriteComment("Step6 move from South Pole");
            Step6PlacePoleEdge(searchPoleFace, destFaceIndex);
         }
      }
      
      // search the Southern Equatorial edges
      for (int i = 0;
            i < CMegaminx::kNumSouthEqEdges && !bFound; i++)
      {
         CMegaminx::face_t searchEqFaceL = 
                  CMegaminx::kSouthEqEdgeL[i];
         CMegaminx::face_t searchEqFaceR = 
                  CMegaminx::kSouthEqEdgeR[i];
         if (fMega.EdgeHasColors(searchEqFaceL, searchEqFaceR, 
               neededColorS, neededColorN))
         {
            bFound = true;
            fMega.WriteComment("Step6 move from South Equatorial");
            DoRLL(searchEqFaceR, searchEqFaceL);
            Step6PlacePoleEdge(searchEqFaceR, destFaceIndex);
         }
      }
      
      // search the (this or later) middle equatorial edges
      // we don't search earlier ones because they are already
      // correctly placed and we don't want to steal from them;
      // we do need to search the edge itself because it might
      // have the correct colors but wrongly placed.
      for (int searchIndex = destFaceIndex; 
            searchIndex < CMegaminx::kNumMiddleEqEdges && !bFound; 
                  searchIndex++)
      {
         CMegaminx::face_t mFaceS = 
                     CMegaminx::kMiddleEqEdgeS[searchIndex];
         CMegaminx::face_t mFaceN = 
                     CMegaminx::kMiddleEqEdgeN[searchIndex];
         if (fMega.EdgeHasColors(mFaceS, mFaceN, neededColorS, 
                     neededColorN))
         {
            bFound = true;
            fMega.WriteComment("Step6 move from Middle Equatorial");
            // lift the found edge, either right or left.
            // Lifting uses the same transformations as
            // dropping, however the lifted edge goes to the
            // adjoining face.
            if ((searchIndex & 1) == 0)
            {
               // even index, so edge is below and to right,
               // and will be lifted to next face
               CMegaminx::face_t nextMFace = 
                  fMega.NextSouthEqFace(mFaceS);
               DoLUU(mFaceS, nextMFace);
               DoLLL(mFaceS, nextMFace);
               DoRUU(mFaceS, nextMFace);
               Step6PlacePoleEdge(nextMFace, destFaceIndex);
            }
            else
            {
               // odd index, so edge is below and to left,
               // and will be lifted to previous face
               CMegaminx::face_t prevFace = 
                  fMega.PrevSouthEqFace(mFaceS);
               DoRUU(prevFace, mFaceS);
               DoRLL(prevFace, mFaceS);
               DoLUU(prevFace, mFaceS);
               Step6PlacePoleEdge(prevFace, destFaceIndex);
            }
         }         
      }
      assert(bFound);
   }
   
   bool bEdgeParityOK = CheckEdgeParity();
   if (!bEdgeParityOK)
   {
      // take evasive action; we will swap two same-colored
      // edges in the equator. This is a transposition, so
      // it should cause the edges in the South half to
      // switch to even parity. We'll somewhat arbitrarily
      // swap the two 2-4 color edges, located at 2-10
      // and 4-8. Just as in earlier Step 6 work we move one
      // edge to the South Pole, place it correctly which
      // moves the other edge to the South Pole, then place
      // that edge.
      
      fMega.WriteComment("Step6 evasive action to fix parity");
      DoLUU(10, 11);      // move 2-10 to South Pole
      DoLLL(10, 11);
      DoRUU(10, 11);   
      fMega.Slice(kSouthPoleFace, CMegaminx::eCounterCW, 2);
            // position      
      DoRUU(12, 8);      // move 2-10 to equator, 4-8 to South Pole
      DoRLL(12, 8);
      DoLUU(12, 8);
      fMega.Slice(kSouthPoleFace, CMegaminx::eCW, 2);   // position
      DoLUU(10, 11);      // move 4-8 to equator
      DoLLL(10, 11);
      DoRUU(10, 11);   
   }

   Step6Verify();
}

void CSolver::Step6PlacePoleEdge(int fromSFace, int toEdgeIndex)
{
   // rotate the edge CounterCW to the correct position
   fMega.WriteComment("Step6PlacePoleEdge");
   CMegaminx::face_t toSFace = 
                  CMegaminx::kMiddleEqEdgeS[toEdgeIndex];
   int dist = Distance(fromSFace, toSFace);
   fMega.Slice(kSouthPoleFace, CMegaminx::eCounterCW, dist);
   
   // flip the edge if it is wrongly oriented
   CMegaminx::face_t nextFace = fMega.NextSouthEqFace(toSFace);
   if (fMega.EdgeFaceletColor(toSFace, kSouthPoleFace) != 
         fMega.CorrectColor(toSFace))
   {
      fMega.WriteComment("Step6PlacePoleEdge flip edge");
      DoRLL(toSFace, nextFace);
      fMega.Slice(kSouthPoleFace, CMegaminx::eCW, 1);
   }
   
   // now drop it into position, either on left or right
   CMegaminx::face_t prevFace = fMega.PrevSouthEqFace(toSFace);
   if ((toEdgeIndex & 1) == 0)
   {
      // even index, so edge is below and to right
      DoLUU(toSFace, nextFace);
      DoLLL(toSFace, nextFace);
      DoRUU(toSFace, nextFace);
   }
   else
   {
      // odd index, so edge is below and to left
      DoRUU(prevFace, toSFace);
      DoRLL(prevFace, toSFace);
      DoLUU(prevFace, toSFace);
   }
}

//////////////////////////////////////////////////////////////////////
// Step 7. Setting the Southern Equatorial Edges
//////////////////////////////////////////////////////////////////////
//
void CSolver::Step7()
{
   for (int i = 0; i < CMegaminx::kNumSouthEqEdges; i++)
   {
      CMegaminx::face_t destFaceL = CMegaminx::kSouthEqEdgeL[i];
      CMegaminx::face_t destFaceR = CMegaminx::kSouthEqEdgeR[i];
      if (fMega.IsEdgeCorrect(destFaceL, destFaceR))
         continue;
         
      CMegaminx::color_t destColorL = fMega.CorrectColor(destFaceL);
      CMegaminx::color_t destColorR = fMega.CorrectColor(destFaceR);
      
      // check to see if needed color is on South Pole
      bool bFound = false;
      for (int j = 0; j < CMegaminx::kNumSouthPoleEdges && !bFound; 
                  j++)
      {
         CMegaminx::face_t srcFaceN = CMegaminx::kSouthPoleEdgeN[j];
         CMegaminx::face_t srcFaceS = CMegaminx::kSouthPoleEdgeS[j];
         if (fMega.EdgeHasColors(srcFaceN, srcFaceS, destColorL, 
                     destColorR))
         {
            bFound = true;
            Step7PlacePoleEdge(srcFaceN, destFaceL, destFaceR);
         }
      }
      
      // check if needed color is on South Equator; do not
      // check already-placed edges
      if (!bFound)
      {
         for (int j = i; j < CMegaminx::kNumSouthEqEdges && !bFound; 
                  j++)
         {
            int srcFaceL = CMegaminx::kSouthEqEdgeL[j];
            int srcFaceR = CMegaminx::kSouthEqEdgeR[j];
            if (fMega.EdgeHasColors(srcFaceL, srcFaceR, destColorL, 
                     destColorR))
            {
               // loft the edge using RLL, so it goes above srcFaceR,
               // then move to correct place (remember that we are
               // looking at the Megaminx upside down, so the
               // left face is srcFaceR)
               bFound = true;
               fMega.WriteComment("Step7 loft edge");
               DoRLL(srcFaceR, srcFaceL);
               Step7PlacePoleEdge(srcFaceR, destFaceL, destFaceR);      
            }
         }
      }
      assert(bFound);
   }
   Step7Verify();
}

// place an equatorial edge that is currently on the pole;
// eqFace is the equatorial face it is below.
void CSolver::Step7PlacePoleEdge(CMegaminx::face_t srcFaceN, 
                        CMegaminx::face_t destFaceL,
                        CMegaminx::face_t destFaceR)
{
   // find the face it belongs to and rotate it there;
   // find the CW distance we should move; we move it so
   // its equatorial color matches the destination face color. Then
   // lift it into position using RLL or LLL. Remember we measure
   // right and left with the Megaminx right-side up.
   fMega.WriteComment("Step7PlacePoleEdge");
   CMegaminx::color_t destFaceColor = 
      fMega.EdgeFaceletColor(srcFaceN, kSouthPoleFace);
   bool bLiftFromLeft = 
      (destFaceColor == fMega.CorrectColor(destFaceL));
   CMegaminx::face_t destFace = 
            bLiftFromLeft ? destFaceL : destFaceR;
   int dist = Distance(destFace, srcFaceN);
   fMega.Slice(kSouthPoleFace, CMegaminx::eCW, dist);
   if (bLiftFromLeft)
      DoRLL(destFaceR, destFaceL);
   else
      DoLLL(destFaceR, destFaceL);
}

//////////////////////////////////////////////////////////////////////
// Step 8. Setting the South Pole edges
//////////////////////////////////////////////////////////////////////
//
// This step both positions and orients the South Pole edges.
//
// We pick a fixed orientation to make the rotation calculations easy.
// The parked edge in on faces 8 and 9, and we rotate it for lofting
// to be on faces 7 and 8, so we'll use LLL to loft it. 
// The reference edge is on faces 7 and 10, the second edge is on faces
// 7 and 11, and the third edge is on faces 7 and 12.
//
// NOTE: All edge operations must be be done using the fixed
// edge 8-9, otherwise things won't be properly aligned
// after setting the first 3 edges.
//
// We don't have to return the South Pole after each move.

void CSolver::Step8()
{
   Step8ReferenceEdge();
   Step8SecondEdge();
   Step8ThirdEdge();
   Step8RestoreEquator();
   Step8OrientFourFive();
   
   Step8Verify();
}

void CSolver::Step8ReferenceEdge()
{
   if (fMega.IsEdgeCorrect(7, 10))
      return;   // already correct, no action needed
      
   fMega.WriteComment("Step8ReferenceEdge");
   // place and orient the reference edge
   
   // locate the correctly colored edge
   bool bFound = false;
   CMegaminx::face_t srcFace = 0;
   for (int i = 0; i < CMegaminx::kNumSouthPoleEdges && !bFound; 
                     i++)
   {
      srcFace = CMegaminx::kSouthPoleEdgeN[i];
      bFound = fMega.EdgeHasColors(srcFace, kSouthPoleFace, 1, 4);
   }
   assert(bFound);
   
   if (fMega.EdgeFaceletColor(kSouthPoleFace, srcFace) != 1)
   {
      // need to orient edge
      // first move the edge over to flipping area, at face 9
      int dist = Distance(9, srcFace);
      fMega.Slice(kSouthPoleFace, CMegaminx::eCW, dist);
      
      // now flip the edge; it will go to face 8
      DoLLL(8, 9);
      srcFace = 8;   // pretend it was here all along
   }
   
   // move the edge into position at edge 10
   int dist = Distance(10, srcFace);
   fMega.Slice(kSouthPoleFace, CMegaminx::eCW, dist);
}

void CSolver::Step8SecondEdge()
{
   if (fMega.IsEdgeCorrect(7, 11))
      return;   // already correct, no action needed
      
   // place and orient the second edge
   // For this operation we have to return the South Pole face
   // to its original position so that the reference edge will
   // be in place.
      
   // locate the correct color
   bool bFound = false;
   CMegaminx::face_t srcFace = 0;
   for (int i = 0; i < CMegaminx::kNumSouthPoleEdges && !bFound; 
                  i++)
   {
      srcFace = CMegaminx::kSouthPoleEdgeN[i];
      bFound = fMega.EdgeHasColors(srcFace, kSouthPoleFace, 1, 5);
   }
   // if not found, the desired edge is already parked, so
   // skip the parking

   if(bFound)
   {
      // we will loft using faces 8 and 9, so the South Pole
      // face must be rotated to place aFace in one of these
      // positions, but such that the reference edge (face 10)
      // does not go to either; this means our CW rotations must
      // be something other than 1 and 2.
      bool bUseRLL = true;
      int dist = Distance(9, srcFace);
      if (dist == 2)   // dist == 1 is impossible because that moves 10 to 9
      {
         dist = 3;   // rotate to 10 instead
         bUseRLL = false;
      }
         
      fMega.WriteComment("Step8SecondEdge parking");
      {
         CTempRotate rot1(fMega, kSouthPoleFace, dist, 
                     CMegaminx::eCW);
         if (bUseRLL)      // park edge 2
            DoRLL(8, 9);
         else
            DoLLL(8, 9);
      }
   }
   
   // now move the edge from the parked position to the South Pole
   fMega.WriteComment("Step8SecondEdge placing");
   {
      CTempRotate rot2(fMega, kSouthPoleFace, 2, 
                     CMegaminx::eCounterCW);
      DoRLL(8, 9);   // places the edge
      
      // if the edge is not oriented correctly, re-orient it
      if (fMega.EdgeFaceletColor(kSouthPoleFace, 8) != 1)
      {
         fMega.WriteComment("Step8SecondEdge re-orienting");
         DoRLL(8, 9);
         fMega.Slice(kSouthPoleFace, CMegaminx::eCW, 1);
         DoLLL(8, 9);
         fMega.Slice(kSouthPoleFace, CMegaminx::eCounterCW, 1);
         DoRLL(8, 9);
      }
   }
}

void CSolver::Step8ThirdEdge()
{
   if (fMega.IsEdgeCorrect(7, 12))
      return;   // already correct, no action needed
      
   // place and orient the third edge
   // For this operation we have to return the South Pole face
   // to its original position so that the reference edge will
   // be in place.
   
   // locate the correct color
   bool bFound = false;
   CMegaminx::face_t srcFace = 0;
   for (int i = 0; i < CMegaminx::kNumSouthPoleEdges && !bFound; 
                  i++)
   {
      srcFace = CMegaminx::kSouthPoleEdgeN[i];
      bFound = fMega.EdgeHasColors(srcFace, kSouthPoleFace, 1, 6);
   }
   
   // if not found, the desired edge is already parked, so
   // skip the parking

   if(bFound)
   {
      // we will loft using faces 8 and 9, so the South Pole
      // face must be rotated to place aFace in one of these
      // positions, but such that the reference edge (face 10)
      // and second edge do not go there either.
      bool bUseRLL = true;
      int dist = 0;
      switch (srcFace)
      {
         case 12:
         {
            // rotate CounterCW 1 to face 8, use LLL
            dist = 1;
            bUseRLL = false;
         }
         break;
         
         case 8:
         {
            // already in place on face 8, use LLL
            dist = 0;
            bUseRLL = false;
         }
         break;
         
         case 9:
         {
            // already in place on face 9, use RLL
            dist = 0;
            bUseRLL = true;      
         }
         break;
         
         default:
         {
            assert(false);
         }
         break;
      }
         
      fMega.WriteComment("Step8ThirdEdge parking");
      {
         CTempRotate rot1(fMega, kSouthPoleFace, dist, 
                  CMegaminx::eCounterCW);
         if (bUseRLL)
            DoRLL(8, 9);
         else
            DoLLL(8, 9);
      }
   }
      
   // now move the edge from the parked position to the South Pole
   fMega.WriteComment("Step8ThirdEdge placing");
   {
      CTempRotate rot2(fMega, kSouthPoleFace, 1, 
                  CMegaminx::eCounterCW);
      DoRLL(8, 9);   // places the edge
      
      // if the edge is not oriented correctly, re-orient it
      if (fMega.EdgeFaceletColor(kSouthPoleFace, 8) != 1)
      {
         DoRLL(8, 9);
         fMega.Slice(kSouthPoleFace, CMegaminx::eCW, 1);
         DoLLL(8, 9);
         fMega.Slice(kSouthPoleFace, CMegaminx::eCounterCW, 1);
         DoRLL(8, 9);
      }
   }
}

void CSolver::Step8RestoreEquator()
{
   // figure out which South Pole edge has the equatorial edge
   // and restore it to its correct place
   
   fMega.WriteComment("Step8RestoreEquator");
   if (fMega.EdgeFaceletColor(kSouthPoleFace, 8) != 1 &&
      fMega.EdgeFaceletColor(8, kSouthPoleFace) != 1)
      DoLLL(8, 9);   // 7-8 edge should be on equator
   else if (fMega.EdgeFaceletColor(kSouthPoleFace, 9) != 1 &&
      fMega.EdgeFaceletColor(9, kSouthPoleFace) != 1)
      DoRLL(8, 9);   // 7-9 edge should be on equator

}

void CSolver::Step8OrientFourFive()
{
   // according to the Meffert solution, 4 and 5 will have
   // the correct colors but might be oriented incorrectly.
   // check that they have the correct colors.
   assert(fMega.EdgeHasColors(kSouthPoleFace, 8, 1, 2));
   assert(fMega.EdgeHasColors(kSouthPoleFace, 9, 1, 3));
   // check that everything is correctly oriented
   bool b78OK = fMega.IsEdgeCorrect(kSouthPoleFace, 8);
   bool b79OK = fMega.IsEdgeCorrect(kSouthPoleFace, 9);
   if (b78OK && b79OK)
      return;   // we're done!
      
   // if only one is bad, then the equator is also bad, so
   // loft it to the pole first
   fMega.WriteComment("Step8OrientFourFive lofting");
   enum Lofting {eNothing = 1, eLLL, eRLL};
   Lofting whichLoft = eNothing;
   if (b78OK && !b79OK)
   {
      whichLoft = eLLL;   // loft to left
      DoLLL(8, 9);
   }
   else if (!b78OK && b79OK)
   {
      whichLoft = eRLL;   // loft to right;
      DoRLL(8, 9);
   }
      
   // now the mis-oriented edges are on the South Pole;
   // apply the special operation to re-orient them
   fMega.WriteComment("Step8OrientFourFive placing");
   for (int i = 1; i <= 4; i++)
   {
      DoRLL(8, 9);
      fMega.Slice(kSouthPoleFace, CMegaminx::eCounterCW, 1);
   }
   fMega.Slice(kSouthPoleFace, CMegaminx::eCounterCW, 1);
   for (int i = 1; i <= 4; i++)
   {
      DoRLL(8, 9);
      fMega.Slice(kSouthPoleFace, CMegaminx::eCounterCW, 1);
   }
   fMega.Slice(kSouthPoleFace, CMegaminx::eCW, 1);
   
   // now return the equatorial edge if needed
   // NOTE: we do the operation twice;
   // the published Meffert solution incorrectly shows it
   // only once.
   fMega.WriteComment("Step8OrientFourFive returning equator");
   if (whichLoft == eLLL)
   {
      DoLLL(8, 9);
      DoLLL(8, 9);
   }
   else if (whichLoft == eRLL)
   {
      DoRLL(8, 9);
      DoRLL(8, 9);
   }
}

//////////////////////////////////////////////////////////////////////
// Step 9. Placing the southern equatorial corners
//////////////////////////////////////////////////////////////////////
//
// We swap corners to get the southern equatorial corners correctly
// placed. Our basic case is when one corner is on the South Pole
// and one is on the South Equator; we convert the other case
// (both on South Equator) to the first case by lofting one of the
// corners to the South Pole.
void CSolver::Step9()
{
   for (CMegaminx::vertex_t dst = CMegaminx::kFirstSouthEqVertex; 
         dst <= CMegaminx::kLastSouthEqVertex; dst++)
   {
      if (fMega.IsCornerCorrectlyPlaced(dst))
         continue;   // already OK, so skip

      // find src, the vertex holding the corner that should be here
      // src is either on the South Pole or on the Southern Equator
      //
      CMegaminx::color_t c0 = 
         fMega.CorrectColor(CMegaminx::kCornerFaces[dst][0]);
      CMegaminx::color_t c1 = 
         fMega.CorrectColor(CMegaminx::kCornerFaces[dst][1]);
      CMegaminx::color_t c2 = 
         fMega.CorrectColor(CMegaminx::kCornerFaces[dst][2]);
      CMegaminx::vertex_t src = 
                  fMega.CornerHavingColors(c0, c1, c2);
      if (src <= CMegaminx::kLastSouthEqVertex)
      {
         // src is on South Equator, so we must loft it
         // to the South Pole
         fMega.WriteComment("Step 9 lofting");
         CMegaminx::face_t leftFace = 
            CMegaminx::kCornerFaces[src][2];
         CMegaminx::face_t rightFace = 
            CMegaminx::kCornerFaces[src][1];
         DoRLL(leftFace, rightFace);
         DoRLL(leftFace, rightFace);
         DoRLL(leftFace, rightFace);
         src += 5;   // src is now on the South Pole
      }
      Step9EquatorAndPole(dst, src);
   }
   
   Step9Verify();
}

void CSolver::Step9EquatorAndPole(CMegaminx::vertex_t dst, 
                  CMegaminx::vertex_t src)
{
   // rotate the South Pole CCW so src is directly above dst;
   // we need to rotate it back when we are finished to avoid disturbing
   // the South Pole edges.
   int dist = Distance(dst + 5, src);
   fMega.WriteComment("Step9EquatorAndPole rotating pole");
   CTempRotate rot1(fMega, kSouthPoleFace, dist, 
            CMegaminx::eCounterCW);
      
   // now swap the vertices
   fMega.WriteComment("Step9EquatorAndPole swapping");
   CMegaminx::face_t leftFace = CMegaminx::kCornerFaces[dst][2];
   CMegaminx::face_t rightFace = CMegaminx::kCornerFaces[dst][1];
   DoRLL(leftFace, rightFace);
   DoRLL(leftFace, rightFace);
   DoRLL(leftFace, rightFace);
}

//////////////////////////////////////////////////////////////////////
// Step 10. Placement Of the South Pole corners
//////////////////////////////////////////////////////////////////////
//
void CSolver::Step10()
{
   for (CMegaminx::vertex_t destCorner = CMegaminx::kFirstSouthPoleVertex; 
         destCorner <= CMegaminx::kLastSouthPoleVertex; destCorner++)
   {
      if (fMega.IsCornerCorrectlyPlaced(destCorner))
         continue;
         
      // find the corner that belongs here; do not check
      // already-placed corners. Do not check the srcCorner
      // because we already know it is not correctly placed
      // (we don't do orientation until Step 11).
      bool bFound = false;
      for (CMegaminx::vertex_t srcCorner = destCorner + 1;
            srcCorner <= CMegaminx::kLastSouthPoleVertex && !bFound;
                   srcCorner++)
      {
         if (destCorner == fMega.CorrectSouthernVertex(srcCorner))
         {
            bFound = true;
            // now move everybody; we alway rotate to vertex 15,
            // and the left and right faces are 12 and 8.
            // We use two blocks so the CTempRotate destructors will
            // rotate back to the original position in between 
            // transformations
            fMega.WriteComment("Step10");
            {
               // swap srcCorner and 10
               CTempRotate rot1(fMega, kSouthPoleFace, 
                           srcCorner - 15, CMegaminx::eCounterCW);
               DoRUU(12, 8);
               DoRUU(12, 8);
               DoRUU(12, 8);
            }
            
            {
               // swap destCorner and srcCorner (which is now in 10)
               CTempRotate rot2(fMega, kSouthPoleFace, 
                           destCorner - 15, CMegaminx::eCounterCW);
               DoRUU(12, 8);
               DoRUU(12, 8);
               DoRUU(12, 8);
            }
            
            {
               // restore 10 to its original position
               CTempRotate rot1(fMega, kSouthPoleFace, 
                           srcCorner - 15, CMegaminx::eCounterCW);
               DoRUU(12, 8);
               DoRUU(12, 8);
               DoRUU(12, 8);
            }
         
         }
      }
      assert(bFound);
   }
   Step10Verify();
}

//////////////////////////////////////////////////////////////////////
// Step 11. Orientation Of the southern equatorial and South Pole corners
//////////////////////////////////////////////////////////////////////
//
// We find pairs of oppositely-oriented corner pieces that are not
// correctly oriented, drop them to the South Pole, then
// swap them and return them to their original position. They
// have to be dropped such that they are next to each other.
// We treat the case "neither on South Pole" as the basic case
// and transform all others to that:
// (1) if both are on the South Pole, we pick two separate faces,
//     one holding each corner, and rotate those CCW to drop them
//     to the Southern Equatorial belt.
// (2) if one is on the South Pole and one not, we rotate the
//     South Pole so that corner is not touched the face the other is
//     on, then rotate a face the South Pole corner is on.

class CStep11CornerVisitor : public CCornerVisitor
{
public:
   CStep11CornerVisitor(CMegaminx& rMega) :
      fMega(rMega),
      fNeedsCounterCWCorner1(-1), fNeedsCounterCWCorner2(-1),
      fNeedsCWCorner1(-1), fNeedsCWCorner2(-1)
      {};
   ~CStep11CornerVisitor() {};
   
   virtual void VisitCorner(int cornerIndex);
   
   // member variables - these are the vertex indices
   // of corners that need 1 turn CCW or CW to be
   // correctly oriented
   CMegaminx::vertex_t fNeedsCounterCWCorner1;
   CMegaminx::vertex_t fNeedsCounterCWCorner2;
   CMegaminx::vertex_t fNeedsCWCorner1;
   CMegaminx::vertex_t fNeedsCWCorner2;
   
   CMegaminx& fMega;
};

void CStep11CornerVisitor::VisitCorner(int cornerIndex)
{
   // maybe we are already done
   if ((fNeedsCounterCWCorner1 >= 0) &&
         (fNeedsCWCorner1 >= 0) )
      return;

   // check whether the corner is correctly oriented,
   // and if not, which direction it should be turned
   
   // face numbers in CCW order
   CMegaminx::face_t f0 = CMegaminx::kCornerFaces[cornerIndex][0];
   CMegaminx::face_t f1 = CMegaminx::kCornerFaces[cornerIndex][1];
   CMegaminx::face_t f2 = CMegaminx::kCornerFaces[cornerIndex][2];
   
   // facelet color for facelet on face f0
   CMegaminx::color_t c0 = fMega.CornerFaceletColor(f0, f1, f2);

   if (c0 == CMegaminx::CorrectColor(f1))
   {
      // should turn CCW
      if (fNeedsCounterCWCorner1 < 0)
         fNeedsCounterCWCorner1 = cornerIndex;
      else if (fNeedsCounterCWCorner2 < 0)
         fNeedsCounterCWCorner2 = cornerIndex;
   }
   else if (c0 == CMegaminx::CorrectColor(f2))
   {
      // should turn CW
      if (fNeedsCWCorner1 < 0)
         fNeedsCWCorner1 = cornerIndex;
      else if (fNeedsCWCorner2 < 0)
         fNeedsCWCorner2 = cornerIndex;
   }
   // otherwise is correctly oriented, do nothing
}

void CSolver::Step11()
{
   // the transformation turns one corner CW and one corner CounterCW,
   // so ideally we would pick corners that need this to be correctly
   // positioned; however if we don't have such a pair we can pick
   // two with the same positioning, and then one will become correctly
   // positioned and one will be switched to the opposite positioning.
   for (int i = 0; i < 100; i++)   // break out if stuck in loop
   {
      CStep11CornerVisitor aVisitor(fMega);
      VisitAllCorners(aVisitor);
      int vCounterCW = aVisitor.fNeedsCounterCWCorner1;
      int vCW = aVisitor.fNeedsCWCorner1;
      if ((vCounterCW < 0) && (vCW < 0))
         break;
      
      // check that we the ideal pairing, and if not double up
      // on the other orientation
      if (vCounterCW < 0)
         vCounterCW = aVisitor.fNeedsCWCorner2;
      else if (vCW < 0)
         vCW = aVisitor.fNeedsCounterCWCorner2;
      assert(vCW >= 0 && vCounterCW >= 0);
         
      bool bCounterCWIsOnEquator = 
            fMega.IsSouthEquatorVertex(vCounterCW);
      bool bCWIsOnEquator = fMega.IsSouthEquatorVertex(vCW);

      if (bCounterCWIsOnEquator && bCWIsOnEquator)
      {
         Step11BothEquators(vCounterCW, vCW);
      }
      else
      {
         // pick two non-adjacent faces for dropping the vertices
         // to the South Equator. If one is already on the equator
         // we don't have to move it. If the vertices are directly
         // above each other (one on pole and one on equator), we need
         // to rotate the South Pole first so they can be on
         // non-adjacent faces.
         
         // first check for possibly needed pole rotation
         int spCount = 0;
         if (std::abs(vCounterCW - vCW) == 5)
         {
            // the vertices are above each other, so we'll
            // rotate the pole 1 CCW
            spCount = 1;
            if (!bCounterCWIsOnEquator)
               vCounterCW = fMega.NextCounterCWVertex(kSouthPoleFace, 
                  vCounterCW);
            else
               vCW = fMega.NextCounterCWVertex(kSouthPoleFace, vCW);
         }
         
         // now do any necessary dropping of vertices to the South Equator
         
         // check counterCW vertex
         int faceCounterCW = 0, faceCW = 0;
         fMega.FindNonAdjacentSouthFaces(vCounterCW, vCW, 
                  &faceCounterCW, &faceCW);
            
         int counterCWCount = 0, cwCount = 0;
         int nextCounterCW = vCounterCW, nextCW = vCW;
         CMegaminx::Direction directionCounterCW = CMegaminx::eCW, 
                  directionCW = CMegaminx::eCW;
         if (!bCounterCWIsOnEquator)
         {
            counterCWCount = 1;
            nextCounterCW = fMega.NextCWVertex(faceCounterCW, 
                  vCounterCW);
            directionCounterCW = CMegaminx::eCW;
            if (!fMega.IsSouthEquatorVertex(nextCounterCW))
            {
               // wrong direction, go in other direction
               nextCounterCW = fMega.NextCounterCWVertex(faceCounterCW, 
                  vCounterCW);
               directionCounterCW = CMegaminx::eCounterCW;
            }
         }
         
         // check CW vertex
         if (!bCWIsOnEquator)
         {
            cwCount = 1;
            nextCW = fMega.NextCWVertex(faceCW, vCW);
            directionCW = CMegaminx::eCW;
            if (!fMega.IsSouthEquatorVertex(nextCW))
            {
               // wrong direction, go in other direction
               nextCW = fMega.NextCounterCWVertex(faceCW, vCW);
               directionCW = CMegaminx::eCounterCW;
            }
         }
         
         fMega.WriteComment("Step11 non-equator case");
         CTempRotate rotSouthPole(fMega, kSouthPoleFace, spCount, 
               CMegaminx::eCounterCW);
         CTempRotate rotCounterCW(fMega, faceCounterCW, 
                              counterCWCount, directionCounterCW);
         CTempRotate rotCW(fMega, faceCW, cwCount, directionCW);
         Step11BothEquators(nextCounterCW, nextCW);
      
      }
   }
}

void CSolver::Step11BothEquators(int vCounterCW, int vCW)
{
   // we will loft the colors of both vertices to the South Pole;
   // need to figure out which direction to rotate their faces,
   // and what rotation is needed for the South Pole to have the
   // lofted corners together.
   
   // pick two non-adjacent faces for lofting the vertices
   int faceCounterCW, faceCW;   // faces to rotate
   fMega.FindNonAdjacentSouthFaces(vCounterCW, vCW, 
         &faceCounterCW, &faceCW);   
   
   // figure out the direction to rotate each face, and which vertex 
   // the corner will loft to
   // We will position the CCW corner 1 vertex CW of the CW face,
   // and rotate the CW face to put the CW vertex next to the CCW 
   // vertex. The right face will then be the CW face.
   CMegaminx::Direction dCounterCW, dCW;   // directions to loft
   int loftedCounterCW1, loftedCW1;
   
   loftedCounterCW1 = fMega.NextCounterCWVertex(faceCounterCW, 
         vCounterCW);
   if (fMega.IsSouthPoleVertex(loftedCounterCW1))
   {
      dCounterCW = CMegaminx::eCounterCW;
   }
   else
   {
      // wrong direction, go back in other direction
      dCounterCW = CMegaminx::eCW;
      loftedCounterCW1 = fMega.NextCWVertex(faceCounterCW, 
         vCounterCW);
   }
   int cwClicks = 0;
   loftedCW1 = fMega.NextCWVertex(faceCW, vCW);
   if (fMega.IsSouthPoleVertex(loftedCW1))
   {
      dCW = CMegaminx::eCW;   // OK, at left edge of face
      cwClicks = 1;
   }
   else
   {
      // wrong direction, go two vertices in other direction
      dCW = CMegaminx::eCounterCW;
      loftedCW1 = fMega.NextCounterCWVertex(faceCW, vCW);
      loftedCW1 = fMega.NextCounterCWVertex(faceCW, loftedCW1);
      cwClicks = 2;
   }
   
   // now figure out the South Pole rotation
   // we want CCW to be on the left of CW
   // as a simplification we will always rotate the South Pole CCW
   int iCounterCW = -1, iCW = -1;
   for (int i = 0; i < 5; i++)
   {
      if (CMegaminx::kFaceVertices[kSouthPoleFace][i] == 
                        loftedCounterCW1)
         iCounterCW = i;
      else if (CMegaminx::kFaceVertices[kSouthPoleFace][i] == 
                        loftedCW1)
         iCW = i;
   }
   int distToRotate = (iCW - 1) - iCounterCW;
   if (distToRotate < 0)
      distToRotate += 5;
   if (distToRotate >= 5)
      distToRotate -= 5;
      
   // OK, now we are ready to rotate everything!
   int rightFace = faceCW;
   int leftFace = faceCW - 1;
   if (leftFace <= kSouthPoleFace)
      leftFace += 5;
   
   // rotate the corners into place
   fMega.WriteComment("Step11BothEquators lofting");
   CTempRotate loftCounterCW(fMega, faceCounterCW, 1, dCounterCW);
   CTempRotate southPoleRotate(fMega, kSouthPoleFace, 
            distToRotate, CMegaminx::eCounterCW);
   CTempRotate loftCW(fMega, faceCW, cwClicks, dCW);
   
   // do the corner swap   
   fMega.WriteComment("Step11BothEquators corner swap");
   DoRUU(leftFace, rightFace);
   DoRUU(leftFace, rightFace);
   fMega.Slice(kSouthPoleFace, CMegaminx::eCounterCW, 1);
   DoLUU(leftFace, rightFace);
   DoLUU(leftFace, rightFace);
   fMega.Slice(kSouthPoleFace, CMegaminx::eCW, 1);
}

#pragma mark === Verification Routines ===
//////////////////////////////////////////////////////////////////////
// Verification Routines
//////////////////////////////////////////////////////////////////////

// see online code archive
CMegaminxApp.cpp
// see online code archive
CMegaminx.cpp
#include "CMegaminx.h"
#include "CMegaminxApp.h"

#include 

/////////////////////////////////////////////////////////////////
// initialization of tables

const CMegaminx::vertex_t CMegaminx::kFaceVertices[13][5] =
{
   // dummy face for 0
   {0, 0, 0, 0, 0},
   
    // North Pole face
    {0, 1, 2, 3, 4},

    // Northern Equatorial faces
    {3, 2, 7, 12, 8},
    {2, 1, 6, 11, 7},
    {1, 0, 5, 10, 6},
    {0, 4, 9, 14, 5},
    {4, 3, 8, 13, 9},
    
    // South Pole face
    {19, 18, 17, 16, 15},
    
    // Southern Equatorial faces
    {19, 15, 10, 5, 14},
    {18, 19, 14, 9, 13},
    {17, 18, 13, 8, 12},
    {16, 17, 12, 7, 11},
    {15, 16, 11, 6, 10}
    
};

const CMegaminx::face_t CMegaminx::kCornerFaces[20][3] = 
{
   // North Pole
   {1, 5, 4},
   {1, 4, 3},
   {1, 3, 2},
   {1, 2, 6},
   {1, 6, 5},
   
   // Northern Equatorial
   {4, 5, 8},
   {3, 4, 12},
   {2, 3, 11},
   {2, 10, 6},
   {5, 6, 9},
   
   // Southern Equatorial
   {4, 8, 12},
   {3, 12, 11},
   {2, 11, 10},
   {6, 10, 9},
   {5, 9, 8},
   
   // South Pole
   {7, 12, 8},
   {7, 11, 12},
   {7, 10, 11},
   {7, 9, 10},
   {7, 8, 9}
};

// list of adjacent face numbers, indexed by face number.
// each item lists the faces adjacent to this one, 
// in counterclockwise order as viewed from above this face.
// This list must be coordinated with the vertex list so that
// face[1] touches vertices [0] and [1].
const CMegaminx::face_t CMegaminx::kAdjacentFaces[13][5] =
{
   {0, 0, 0, 0, 0},   // dummy for face 0
   
    {4, 3, 2, 6, 5},
    {1, 3, 11, 10, 6},
    {1, 4, 12, 11, 2},
    {1, 5, 8, 12, 3},
    {1, 6, 9, 8, 4},
    {1, 2, 10, 9, 5},
    
    {9, 10, 11, 12, 8},
    {7, 12, 4, 5, 9},
    {7, 8, 5, 6, 10},
    {7, 9, 6, 2, 11},
    {7, 10, 2, 3, 12},
    {7, 11, 3, 4, 8}
};

const CMegaminx::face_t CMegaminx::kFaceBelow[20] =
{5, 4, 3, 2, 6, 8, 12, 11, 10, 9, 8, 12, 11, 10, 9, 0, 0, 0, 0, 0};
const CMegaminx::face_t CMegaminx::kFaceAbove[20] =
{0, 0, 0, 0, 0, 4, 3, 2, 6, 5, 4, 3, 2, 6, 5, 12, 11, 10, 9, 8};

const CMegaminx::face_t CMegaminx::kFaceDownRight[13] = 
{0, 0, 10, 11, 12, 8, 9, 0, 0, 0, 0, 0, 0};
const CMegaminx::face_t CMegaminx::kFaceDownLeft[13] =
{0, 0, 11, 12, 8, 9, 10, 0, 0, 0, 0, 0, 0};
const CMegaminx::face_t CMegaminx::kFaceUpRight[13] =
{0, 0, 0, 0, 0, 0, 0, 0, 4, 5, 6, 2, 3}; 
const CMegaminx::face_t CMegaminx::kFaceUpLeft[13] =
{0, 0, 0, 0, 0, 0, 0, 0, 5, 6, 2, 3, 4}; 

// list of North Pole edges
const  CMegaminx::face_t CMegaminx::kNorthPoleEdgeN[kNumNorthPoleEdges] = 
{1, 1, 1, 1, 1};
const CMegaminx::face_t CMegaminx::kNorthPoleEdgeS[kNumNorthPoleEdges] = 
{2, 3, 4, 5, 6};

// list of North Equator edges.
const CMegaminx::face_t CMegaminx::kNorthEqEdgeL[kNumNorthEqEdges] = 
{2, 3, 4, 5, 6};
const CMegaminx::face_t CMegaminx::kNorthEqEdgeR[kNumNorthEqEdges] =
{6, 2, 3, 4, 5};

// list of middle equatorial edges. Ordered in two arrays,
// the first giving the south face and the second the corresponding
// north face. For even indices the edge is below and right of the
// north face, for odd indices it is below and to the left.
const CMegaminx::face_t CMegaminx::kMiddleEqEdgeN[kNumMiddleEqEdges] = 
{5, 4, 4, 3, 3, 2, 2, 6, 6, 5};
const CMegaminx::face_t CMegaminx::kMiddleEqEdgeS[kNumMiddleEqEdges] =
{8, 8, 12, 12, 11, 11, 10, 10, 9, 9};

// list of Southern Equator edges
const CMegaminx::face_t CMegaminx::kSouthEqEdgeL[kNumSouthEqEdges] = 
{8, 9, 10, 11, 12};
const CMegaminx::face_t CMegaminx::kSouthEqEdgeR[kNumSouthEqEdges] =
{12, 8, 9, 10, 11};

// list of South Pole edges
const CMegaminx::face_t CMegaminx::kSouthPoleEdgeN[kNumSouthPoleEdges] =
{8, 9, 10, 11, 12};
const CMegaminx::face_t CMegaminx::kSouthPoleEdgeS[kNumSouthPoleEdges] =
{7, 7, 7, 7, 7};


//////////////////////////////////////////////////////////////////////

CMegaminx::CMegaminx(const string& testNumberString)
{
   // clear all facelets
    std::memset(fEdgeFacelets, 0, sizeof(fEdgeFacelets));
    std::memset(fCornerFacelets, 0, sizeof(fCornerFacelets));

   // open correct rotations file
   string rotationsName = string("rotations") + 
                     testNumberString + ".txt";
   fRotationsStream.open(rotationsName.c_str());
   if (!fRotationsStream.is_open())
   {
      CMegaminxApp::SayFileError(rotationsName);
      return;
   }
}

CMegaminx::~CMegaminx()
{
   fRotationsStream.close();
}
   
void CMegaminx::LoadCornerFacelet(face_t faceNumber1, face_t faceNumber2,
                     face_t faceNumber3, color_t colorNumber)
{
   assert(1 <= faceNumber1 && faceNumber1 <= 12);
   assert(1 <= faceNumber2 && faceNumber2 <= 12);
   assert(1 <= faceNumber3 && faceNumber3 <= 12);
   
   if (faceNumber2 < faceNumber3)
      fCornerFacelets[faceNumber1][faceNumber2][faceNumber3] 
         = colorNumber;
   else
      fCornerFacelets[faceNumber1][faceNumber3][faceNumber2] 
         = colorNumber;
   
}

                     
void CMegaminx::LoadEdgeFacelet(face_t faceNumber1, face_t faceNumber2,
                     color_t colorNumber)
{
   assert(1 <= faceNumber1 && faceNumber1 <= 12);
   assert(1 <= faceNumber2 && faceNumber2 <= 12);

   fEdgeFacelets[faceNumber1][faceNumber2] = colorNumber;
}

void CMegaminx::SliceImp(CMegaminx::face_t faceNumber, 
            Direction direction)
{
    short *pFaceletColors1[5], *pFaceletColors2[5],
            *pFaceletColors3[5];   // pointers to colors to move, listed CCW
    int i;
    
    // rotate the edge facelets
    for (i = 0; i < 5; i++)
    {
        int adj = kAdjacentFaces[faceNumber][i];
        pFaceletColors1[i] = &fEdgeFacelets[adj][faceNumber];
                     // adjacent face
        pFaceletColors2[i] = &fEdgeFacelets[faceNumber][adj];
                     // this face
    }
    RotateFacelets(pFaceletColors1, direction);
    RotateFacelets(pFaceletColors2, direction);

    // rotate the corner facelets
    for (i = 0; i < 5; i++)
    {
        int adjRight = 
                     kAdjacentFaces[faceNumber][(i == 0) ? 4 : i - 1];
        int adjLeft = kAdjacentFaces[faceNumber][i];
        int low, high;
        
        low = (adjRight < adjLeft) ? adjRight : adjLeft;
        high = (adjRight > adjLeft) ? adjRight : adjLeft;
        pFaceletColors1[i] = 
                  &fCornerFacelets[faceNumber][low][high];   // this face
        
        low = (faceNumber < adjLeft) ? faceNumber : adjLeft;
        high = (faceNumber > adjLeft) ? faceNumber : adjLeft;
        pFaceletColors2[i] = 
                  &fCornerFacelets[adjRight][low][high];   // right face
        
        low = (faceNumber < adjRight) ? faceNumber : adjRight;
        high = (faceNumber > adjRight) ? faceNumber : adjRight;
        pFaceletColors3[i] = 
                  &fCornerFacelets[adjLeft][low][high];   // left face
    }
    RotateFacelets(pFaceletColors1, direction);
    RotateFacelets(pFaceletColors2, direction);
    RotateFacelets(pFaceletColors3, direction);
    
    // write out this rotation to the file
    fRotationsStream << faceNumber << ",";
   fRotationsStream << ((direction == eCW) ? '+' : '-');
   fRotationsStream << std::endl;
}

void CMegaminx::Slice(face_t faceNumber, Direction direction, 
                     int clicks)
{
   assert(clicks >= 0);
   for (int i = 0; i < clicks; i++)
      SliceImp(faceNumber, direction);
}

bool CMegaminx::IsSolved()
{
   bool bSolved = true;
   for (int i = 1; i <= 12; i++)
   {
      int rightColor = CorrectColor(i);
      for (int j = 1; j <= 12; j++)
      {
         // check edges
         bSolved = bSolved && (fEdgeFacelets[i][j] == 0 || 
               fEdgeFacelets[i][j]== rightColor);
            
         // check corners
         for (int k = j + 1; k <= 12; k++)
         {
            bSolved = bSolved && (fCornerFacelets[i][j][k] == 0 ||
                  fCornerFacelets[i][j][k] == rightColor);
         }
      }
   }
   return bSolved;
}

void CMegaminx::RotateFacelets(short **ppColor, Direction direction)
{
    // rotate a list of 5 facelet colors
    // the pList is an array of 5 pointer to the color entries
    // in either fEdgeFacelets or fCornerFacelets, in counterclockwise
    // order. For CCW direction we shift the array right, and
    // for CW direction we shift it left.
    short saveColor = 0;
    int i;
    if (direction == eCounterCW)
    {
        // shift right
       saveColor = **(ppColor + 4);
        for (i = 3; i >= 0; i--)
            **(ppColor + i + 1) = **(ppColor + i);
        **(ppColor + 0) = saveColor;
    }
    else
    {
        // shift left
       saveColor = **(ppColor + 0);
        for (i = 0; i < 4; i++)
            **(ppColor + i) = **(ppColor + i + 1);
        **(ppColor + 4) = saveColor;
    }
}

bool CMegaminx::IsCornerCorrectlyPlaced(vertex_t vertex)
{
   // get the actual colors and the correct colors;
   // the item is correctly placed if these lists are
   // rotations of each other.
   int f0, f1, f2;
   int actualColors[5];
   int correctColors[3];
   
   f0 = kCornerFaces[vertex][0];
   f1 = kCornerFaces[vertex][1];
   f2 = kCornerFaces[vertex][2];
   actualColors[0] = actualColors[3] = 
            CornerFaceletColor(f0, f1, f2);
   actualColors[1] = actualColors[4] = 
            CornerFaceletColor(f1, f2, f0);
   actualColors[2] = CornerFaceletColor( f2, f0, f1);
   correctColors[0] = kCornerFaces[vertex][0];
   correctColors[1] = kCornerFaces[vertex][1];
   correctColors[2] = kCornerFaces[vertex][2];
   if (correctColors[0] > 6)
      correctColors[0] -= 6;
   if (correctColors[1] > 6)
      correctColors[1] -= 6;
   if (correctColors[2] > 6)
      correctColors[2] -= 6;
      
   bool bHaveMatch = false;
   for (int i = 0; (i < 3) && !bHaveMatch; i++)
   {
      bHaveMatch = true;
      for (int j = 0; j< 3; j++)
      {
         if (actualColors[i+ j] != correctColors[j])
            bHaveMatch = false;
      }
   }
   
   return bHaveMatch;
}

bool CMegaminx::IsCornerCorrect(vertex_t vertex)
{
   int f0 = kCornerFaces[vertex][0];
   int f1 = kCornerFaces[vertex][1];
   int f2 = kCornerFaces[vertex][2];
   
   bool bOK =    
            CornerFaceletColor(f0, f1, f2) == CorrectColor(f0) &&
            CornerFaceletColor(f1, f2, f0) == CorrectColor(f1) &&
            CornerFaceletColor(f2, f0, f1) == CorrectColor(f2);
            
   return bOK;
}

CMegaminx::vertex_t 
      CMegaminx::FacesToVertex(CMegaminx::face_t f0, 
            CMegaminx::face_t f1, CMegaminx::face_t f2)
{
   // find the lowest face number, then search the table of corner faces
   // for a match. It is an error if we don't find a match.
   int holdFace = 0;
   
   if (f1 < f0)
   {
      holdFace = f0;
      f0 = f1;
      f1 = holdFace;
   }
   if (f2 < f0)
   {
      holdFace = f0;
      f0 = f2;
      f2 = holdFace;
   }
   
   for (int i = 0; i < 20; i++)
   {
      if (f0 == kCornerFaces[i][0])
      {
         int trialFace1 = kCornerFaces[i][1];
         int trialFace2 = kCornerFaces[i][2];
         if ( (f1 == trialFace1 && f2 == trialFace2) ||
             (f1 == trialFace2 && f2 == trialFace1))
         {
            return i;
         }
      }
   }
   
   // trouble, did not find a match
   ::SysBeep(1);
   assert(false);
   return 0;
}

CMegaminx::vertex_t CMegaminx::CorrectSouthernVertex(CMegaminx::vertex_t vertex)
{
   // find where v1 should be;
   // first read out its current colors, then 
   // figure its correct faces
   int oldf0, oldf1, oldf2;   // old face numbers
   int c0, c1, c2;                     // corresponding current colors
   int newf0, newf1, newf2;   // new face numbers
   oldf0 = kCornerFaces[vertex][0];
   oldf1 = kCornerFaces[vertex][1];
   oldf2 = kCornerFaces[vertex][2];
   c0 = CornerFaceletColor(oldf0, oldf1, oldf2);
   c1 = CornerFaceletColor(oldf1, oldf2, oldf0);
   c2 = CornerFaceletColor( oldf2, oldf0, oldf1);
   
   // in general we can find the face numbers by adding 6
   // to each color; however for Southern Equatorial
   // vertices there is one color that should not have 6
   // added, and that is the "non-contiguous" color.
   newf0 = c0 + 6;
   newf1 = c1 + 6;
   newf2 = c2 + 6;
   if (c0 != 1 && c1 != 1 && c2 != 1)
   {
      // not pole, so correct one face
      if (std::abs(newf0 - newf1) == 1 || 
               std::abs(newf0 - newf1) == 4)
         newf2 -= 6;
      else if (std::abs(newf1 - newf2) == 1 || 
                        std::abs(newf1 - newf2) == 4)
         newf0 -= 6;
      else
         newf1 -= 6;
   }
   return FacesToVertex(newf0, newf1, newf2);
}

   
CMegaminx::vertex_t CMegaminx::CornerHavingColors(CMegaminx::color_t c0, 
                  CMegaminx::color_t c1, CMegaminx::color_t c2)
{
   int desiredColors[5];
   desiredColors[0] = desiredColors[3] = c0;
   desiredColors[1] = desiredColors[4] = c1;
   desiredColors[2] = c2;
   int trialVertex;
   for (trialVertex = 0; trialVertex < 20; trialVertex++)
   {
      // get the actual colors and the correct colors;
      // the item is correctly placed if these lists are
      // rotations of each other.
      int f0, f1, f2;
      f0 = kCornerFaces[trialVertex][0];
      f1 = kCornerFaces[trialVertex][1];
      f2 = kCornerFaces[trialVertex][2];
      int trialColors[3];
      trialColors[0] = CornerFaceletColor(f0, f1, f2);
      trialColors[1] = CornerFaceletColor(f1, f2, f0);
      trialColors[2] = CornerFaceletColor(f2, f0, f1);

      bool bHaveMatch = false;
      for (int i = 0; (i < 3) && !bHaveMatch; i++)
      {
         bHaveMatch = true;
         for (int j = 0; j< 3; j++)
         {
            if (desiredColors[i+ j] != trialColors[j])
               bHaveMatch = false;
         }
      }
      
      if (bHaveMatch)
         break;
   }

   return trialVertex;
}

CMegaminx::vertex_t CMegaminx::NextCounterCWVertex(CMegaminx::face_t faceNumber, 
            CMegaminx::vertex_t vertexNumber)
{
   for (int i = 0; i < 5; i++)
   {
      if (kFaceVertices[faceNumber][i] == vertexNumber)
         return kFaceVertices[faceNumber][(i == 4) ? 0 : i + 1];
   }
   
   ::SysBeep(1);   // trouble, vertex not on face
   assert(false);
   return -1;
}

CMegaminx::vertex_t CMegaminx::NextCWVertex(CMegaminx::face_t faceNumber, 
                  CMegaminx::face_t vertexNumber)
{
   for (int i = 0; i < 5; i++)
   {
      if (kFaceVertices[faceNumber][i] == vertexNumber)
         return kFaceVertices[faceNumber][(i == 0) ? 4 : i - 1];
   }
   
   ::SysBeep(1);   // trouble, vertex not on face
   assert(false);
   return -1;

}

void CMegaminx::FindNonAdjacentSouthFaces(CMegaminx::vertex_t v1,
               CMegaminx::vertex_t v2, 
               CMegaminx::face_t *pf1, CMegaminx::face_t *pf2)
{
   int f1[2], f2[2];   // candidate faces
   
   f1[0] = kCornerFaces[v1][1];
   f1[1] = kCornerFaces[v1][2];
   f2[0] = kCornerFaces[v2][1];
   f2[1] = kCornerFaces[v2][2];
   
   for (int i = 0; i < 2; i++)
   {
      for (int j = 0; j < 2; j++)
      {
         int dist = f1[i] - f2[j];
         if (dist < 0)
            dist = -dist;
         if (dist == 2 || dist == 3)
         {
            *pf1 = f1[i];
            *pf2 = f2[j];
            return;
         }
      }
   }
   
   ::SysBeep(1);   // trouble, couldn't find suitable faces
   assert(false);
}

#ifndef NDEBUG
void CMegaminx::WriteComment(const char *pComment)
{
    fRotationsStream << "* " << pComment << std::endl;
}
#else
void CMegaminx::WriteComment(const char * /* pComment */)
{
   // nothing
}
#endif

bool CMegaminx::EdgeHasColors(CMegaminx::face_t f0, CMegaminx::face_t f1, 
               CMegaminx::color_t c0, CMegaminx::color_t c1)
{
   int actualc0 = fEdgeFacelets[f0][f1];
   int actualc1 = fEdgeFacelets[f1][f0];
   bool bMatches = ((actualc0 == c0) && (actualc1 == c1)) ||
               ((actualc0 == c1) && (actualc1 == c0));
   return bMatches;
}

#pragma mark === CTempRotate ===
//////////////////////////////////////////////////////////////////////
CTempRotate::CTempRotate(CMegaminx& rMega, CMegaminx::face_t faceNumber, 
            int clicks, CMegaminx::Direction direction) :
fMega(rMega),
fFaceNumber(faceNumber),
fClicks(clicks),
fDirection(direction)
{
   assert(fClicks >= 0);
   fMega.WriteComment("CTempRotate ctor");
   fMega.Slice(fFaceNumber, direction, fClicks);
}

CTempRotate::~CTempRotate()
{
   fMega.WriteComment("CTempRotate dtor");
   fMega.Slice(fFaceNumber, 
         fDirection == CMegaminx::eCW ? 
               CMegaminx::eCounterCW : CMegaminx::eCW, 
         fClicks);
}

CMegaminxApp.h

// see online code archive
CMegaminx.h
//////////////////////////////////////////////////////////////////////
//
// The CMegaminx class holds the state of the Megaminx. There's only
// one operation for changing state, the Slice function. This class
// also handles writing out the rotations files; this placement is 
// somewhat arbitrary, but is useful because it ensures that changing
// the Megaminx state will always cause the correct movements to be
// written out.
//
//////////////////////////////////////////////////////////////////////

#pragma once

#include 
#include 
using std::string;

class CMegaminx
{
public:
   /////////////////////////////////////////////////////////////////
   // various types and tables describing the Megaminx
   
   // enum for rotation direction; always measured looking
   // down on a face.
   // We also use this for an orientation of a corner; if
   // the color number increase CCW we call it CCW, and if
   // they increase CW we call it CW.
   enum Direction
   {
      eCounterCW = 1,
      eCW = 2
   };
   
   // typedefs for face number, color number, vertex number
   typedef int face_t;
   typedef int color_t;
   typedef int vertex_t;
   
   // vertices are numbered 0-19; these equates give the ranges
   static const int kNumVertices = 20;
   static const vertex_t kFirstNorthPoleVertex = 0;
   static const vertex_t kLastNorthPoleVertex = 4;
   static const vertex_t kFirstNorthEqVertex = 5;
   static const vertex_t kLastNorthEqVertex = 9;
   static const vertex_t kFirstSouthEqVertex = 10;
   static const vertex_t kLastSouthEqVertex =14;
   static const vertex_t kFirstSouthPoleVertex = 15;
   static const vertex_t kLastSouthPoleVertex = 19;
   
   // vertex numbers of each face, indexed 0 through 19,
   // counterclockwise looking at the face from outside
   static const vertex_t kFaceVertices[13][5];

   // list of all vertices and the adjoining faces. Faces are listed
   // in CCW order started with the lowest-numbered.
   static const face_t kCornerFaces[20][3];

   // list of adjacent face numbers, indexed by face number.
   // each item lists the faces adjacent to this one, 
   // in counterclockwise order as viewed from above this face.
   // This list must be coordinated with the vertex list so that
   // face[1] touches vertices [0] and [1].
   static const face_t kAdjacentFaces[13][5];
   
   // list of faces below or below left of a vertex, indexed
   // by vertex number. For North Equatorial vertices the face is
   // below (the vertex is its top vertex) and for North Pole
   // and South Equatorial vertices the face is below and
   // to the left (the vertix is its upper right vertex).
   static const face_t kFaceBelow[20];

   // list of faces above or above right of a vertex, indexed
   // by vertex number. For South Equatorial vertices the face is
   // above (the vertex is its bottom vertex) and for South Pole
   // and North Equatorial vertices the face is above and
   // to the right (the vertix is its lower left vertex).
   static const face_t kFaceAbove[20];
   
   // for equatorial faces, the faces above and below them.
   //
   // faces below and to left or right of given North Equatorial
   // face; indexed by face number
   static const face_t kFaceDownRight[13];
   static const face_t kFaceDownLeft[13];
   // faces above and to left or right of given South Equatorial 
   // face; indexed by face number
   static const face_t kFaceUpRight[13];
   static const face_t kFaceUpLeft[13];
   
   // list of North Pole edges
   static const int kNumNorthPoleEdges = 5;
   static const face_t kNorthPoleEdgeN[kNumNorthPoleEdges];
   static const face_t kNorthPoleEdgeS[kNumNorthPoleEdges];

   // list of North Equator edges.
   static const face_t kNumNorthEqEdges = 5;
   static const face_t kNorthEqEdgeL[kNumNorthEqEdges];
   static const face_t kNorthEqEdgeR[kNumNorthEqEdges];

   // list of middle equatorial edges. Ordered in two arrays,
   // the first giving the north face and the second the corresponding
   // south face. For even indices the edge is below and right of the
   // north face, for odd indices it is below and to the left.
   static const int kNumMiddleEqEdges = 10;
   static const face_t kMiddleEqEdgeN[kNumMiddleEqEdges];
   static const face_t kMiddleEqEdgeS[kNumMiddleEqEdges];

   // list of Southern Equator edges
   static const int kNumSouthEqEdges = 5;
   static const face_t kSouthEqEdgeL[kNumSouthEqEdges];
   static const face_t kSouthEqEdgeR[kNumSouthEqEdges];

   // list of South Pole edges
   static const int kNumSouthPoleEdges = 5;
   static const face_t kSouthPoleEdgeN[kNumSouthPoleEdges];
   static const face_t kSouthPoleEdgeS[kNumSouthPoleEdges];


   /////////////////////////////////////////////////////////////////
   // public functions
   
   CMegaminx(const string& testNumberString);
   ~CMegaminx();
   
   
   // load a corner facelet;
   // faceNumber1 is the face it is on (numbered 1..12),
   // faceNumber2 and faceNumber3 are neighboring faces,
   // and colorNumber is the facelet's color (numbered 1..6).
   void LoadCornerFacelet(face_t faceNumber1, face_t faceNumber2,
                     face_t faceNumber3, color_t colorNumber);
                     
   // similarly, load an edge facelet (no face 3 for these)
   void LoadEdgeFacelet(face_t faceNumber1, face_t faceNumber2,
                     color_t colorNumber);
                     
   // slice operation; rotate face one click in given direction;
   // changes our internal state and writes a line to
   // the rotations file.
   // This is a public function so that our helper classes
   // can get to it.
   void Slice(face_t faceNumber, Direction direction, int clicks);

   // check that the Megaminx is correctly solved
   bool IsSolved();
   
   // check whether a corner is correctly placed, based
   // on its colors. The first checks only placement, not 
   // orientation.
   bool IsCornerCorrectlyPlaced(vertex_t vertex);
   bool IsCornerCorrect(vertex_t vertex);
   
   // check whether an edge is correctly placed and positioned
   bool IsEdgeCorrect(face_t faceL, face_t faceR)
   { return (fEdgeFacelets[faceL][faceR] == CorrectColor(faceL) &&
            fEdgeFacelets[faceR][faceL] == CorrectColor(faceR));};
   
   
   // look up the vertex having these faces
   vertex_t FacesToVertex(face_t f0, face_t f1, face_t f2);
   
   // find correct location of the colors at a vertex,
   // assuming they should be in the Southern
   // half. Returns the correct vertex number.
   // We assume the colors actually belong in the
   // specified Southern half, so caller
   // must check this. "Southern" means South Pole
   // or South Equatorial.
   // Corners with same colors have opposite orientations
   // in the Northern and Southern halves.
   vertex_t CorrectSouthernVertex(vertex_t vertex);
   
   // find the corner having these colors in this order
   // (with rotations allowed). This means the corner that
   // is currently colored with these corners.
   color_t CornerHavingColors(color_t c0, color_t c1, color_t c2);
   
   // return facelet color of face f0 that borders f1 and f2
   color_t CornerFaceletColor(face_t f0, face_t f1, face_t f2)
      { if (f1 < f2) return fCornerFacelets[f0][f1][f2];
         else return fCornerFacelets[f0][f2][f1];};
         
   // return color of edge on f0 that borders f1
   color_t EdgeFaceletColor(face_t f0, face_t f1)
   { return fEdgeFacelets[f0][f1]; };
      
   // return correct color of solved Megaminx face
   static color_t CorrectColor(face_t faceNumber)
      { return (faceNumber <= 6) ? faceNumber : faceNumber - 6;};
   
   // find next vertex on a face
   static vertex_t NextCounterCWVertex(face_t faceNumber, vertex_t vertexNumber);
   static vertex_t NextCWVertex(face_t faceNumber, vertex_t vertexNumber);
   
   // find next or previous (numerically) South Equatorial faces
   static face_t NextSouthEqFace(face_t faceNumber)
      { return (faceNumber == 12) ? 8 : faceNumber + 1; };
   static face_t PrevSouthEqFace(face_t faceNumber)
      { return (faceNumber == 8) ? 12 : faceNumber - 1; };
   
   // find next or previous (numerically) North Equatorial faces
   static face_t NextNorthEqFace(face_t faceNumber)
      { return (faceNumber == 6) ? 2 : faceNumber + 1; };
   static face_t PrevNorthEqFace(face_t faceNumber)
      { return (faceNumber == 2) ? 6 : faceNumber - 1; };
   
   // tell which region a vertex is in
   static bool IsNorthPoleVertex(vertex_t vertexNumber)
      { return (vertexNumber <= 4);};
   static bool IsNorthEquatorVertex(vertex_t vertexNumber)
      { return (vertexNumber > 4 && vertexNumber <= 9);};
   static bool IsSouthEquatorVertex(vertex_t vertexNumber)
      { return (vertexNumber > 9 && vertexNumber <= 14);};
   static bool IsSouthPoleVertex(vertex_t vertexNumber)
      { return (vertexNumber > 14);};
      
   // tell which region a face is in
   static bool IsNorthPoleFace(face_t faceNumber)
      { return (faceNumber == 1); };
   static bool IsNorthEquatorFace(face_t faceNumber)
      { return (faceNumber > 1 && faceNumber <= 6); };
   static bool IsSouthEquatorFace(face_t faceNumber)
      { return (faceNumber > 6 && faceNumber <= 11); };
   static bool IsSouthPoleFace(face_t faceNumber)
      { return (faceNumber == 12); };
      
   // find non-adjacent South Equatorial faces holding
   // these vertices. This is useful for lofting because
   // we can rotate these two faces independently without
   // affected the other face's vertex.
   // The vertices v1 and v2 can be on the South Equator,
   // the South Pole, or a mixture; except that they cannot
   // be on the same vertical line (because they touch the
   // same faces then); the caller must detect this and not
   // call this routine in this case.
   static void FindNonAdjacentSouthFaces(vertex_t v1, 
            vertex_t v2, face_t *pf1, face_t *pf2);
      
   // write a comment line to the rotations file telling
   // what we are doing (debug only)
   void WriteComment(const char *pComment);
   
   // check whether an edge has the given colors (in either order)
   bool EdgeHasColors(face_t f0, face_t f1, color_t c0, 
            color_t c1);
      

private:

   /////////////////////////////////////////////////////////////////
   // used in implementation
   
   void SliceImp(face_t faceNumber, Direction direction);
            // slice one turn

   // utility for rotating part of a face
   static void RotateFacelets(short **ppColor, 
            Direction direction);

   

   /////////////////////////////////////////////////////////////////
   // member variables
   
   // colors for edge and corner facelets
   // colors are numbered 1 through 6; we use 0 for an invalid entry.
   //
   // indices are the face number (and so run from 1 through 12).
   // edge facelets are indexed by the two faces they touch, with
   // the first index being the face they are on.
   // corner facelets are indexed by the three faces they touch,
   // with the first index being the face they are on,
   // with second index < third index. 
   //
   // We allocate many more items than are actually valid.
   short fEdgeFacelets[13][13];
   short fCornerFacelets[13][13][13];

   // output stream for the answer
   std::ofstream fRotationsStream;

};

// class to temporarily rotate a face; when destructed,
// it rotates back in the other direction. The clicks
// can be 0, meaning no rotation.

class CTempRotate
{
public:
   CTempRotate(CMegaminx& rMega, CMegaminx::face_t faceNumber,
            int clicks, CMegaminx::Direction direction);
            
   ~CTempRotate();
private:
   CMegaminx& fMega;
   CMegaminx::face_t fFaceNumber;
   int fClicks;
   CMegaminx::Direction fDirection;
};

CSolver.h

//////////////////////////////////////////////////////////////////////
//
// This class contains all the algorithms for solving Megaminx.
//
//////////////////////////////////////////////////////////////////////

#pragma once

#include 
#include 
using std::string;

#include "CMegaminx.h"

class CCornerVisitor;
class CMegaminx;

class CSolver
{
public:
   CSolver(CMegaminx& rMega);
   ~CSolver();
   
   // solve the Megaminx and write out the solution
   void Solve();
   
   // call visitor   
   void VisitAllCorners(CCornerVisitor &aVisitor);
   
private:
   /////////////////////////////////////////////////////////////////
   // used in implementation
   
   // double operations from Meffert
   // RUU = R upper star upper star, and so on
   void DoLUU(CMegaminx::face_t leftFace, 
            CMegaminx::face_t rightFace);
   void DoRUU(CMegaminx::face_t leftFace, 
            CMegaminx::face_t rightFace);
   void DoRLL(CMegaminx::face_t leftFace, 
            CMegaminx::face_t rightFace);
   void DoLLL(CMegaminx::face_t leftFace, 
            CMegaminx::face_t rightFace);
   
   // distance along either the North or South pole vertices, measured
   // in the direction of increasing vertex number and wrapping around.
   // We use this when we are going to rotate in this direction.
   // Also: distance along an equator from one face to another.
   // This calculates (to - from) mod 5.
   int Distance(int from, int to)
   { int dist = to - from; if (dist < 0) dist += 5; return dist;};
   
   // this checks that the South half edges are an even permutation
   // of the solved position. It returns true if the permutation
   // is even and false if it is odd.
   bool CheckEdgeParity();
   static int ParityLookup(CMegaminx::color_t c0, 
            CMegaminx::color_t c1);
   
   // solution steps
   void Step3();
   void Step3Edges();
   CMegaminx::face_t Step3_4Drop(CMegaminx::color_t c0, 
                     CMegaminx::color_t c1);
   void Step3Corners();
   void Step4();
   void Step5();
   void Step5PlaceVertex(CMegaminx::vertex_t srcVertex, 
                     int destVertex);
   void Step5OrientVertex(int destVertex);
   void Step6();
   void Step6PlacePoleEdge(CMegaminx::face_t fromSFace, 
                  CMegaminx::face_t toEdgeIndex);
   void Step7();
   void Step7PlacePoleEdge(CMegaminx::face_t srcFaceN, 
                  CMegaminx::face_t destFaceL, 
                  CMegaminx::face_t destFaceR);
   void Step8();
   void Step8ReferenceEdge();
   void Step8SecondEdge();
   void Step8ThirdEdge();
   void Step8RestoreEquator();
   void Step8OrientFourFive();
   void Step9();
   void Step9EquatorAndPole(CMegaminx::vertex_t dst, 
                  CMegaminx::vertex_t src);
   void Step10();
   void Step11();
   void Step11BothEquators(CMegaminx::vertex_t vCounterCW, 
                  CMegaminx::vertex_t vCW);
   
   // verification steps (these run only in debug mode);
   // they check that various things are correctly positioned
   // at the end of step n, and assert if they are not.
   // Each step calls the preceding step, so all earlier
   // verifications are re-performed too.
   void Step3Verify();
   void Step4Verify();
   void Step5Verify();
   void Step6Verify();
   void Step7Verify();
   void Step8Verify();
   void Step9Verify();
   void Step10Verify();
   void Step11Verify();
   

   /////////////////////////////////////////////////////////////////
   // member variables
   CMegaminx& fMega;   // Megaminx being solved
};

// CCornerVisitor Class
class CCornerVisitor
{
public:
   CCornerVisitor() {};
   virtual ~CCornerVisitor() {};
   
   virtual void VisitCorner(int cornerIndex) = 0;
};