Jun 02 Challenge

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
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))

// 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
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))

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

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

// 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;
&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
&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].
{
{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();
}

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;

}

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++)
{
// this face
}
RotateFacelets(pFaceletColors1, direction);
RotateFacelets(pFaceletColors2, direction);

// rotate the corner facelets
for (i = 0; i < 5; i++)
{
kAdjacentFaces[faceNumber][(i == 0) ? 4 : i - 1];
int low, high;

pFaceletColors1[i] =
&fCornerFacelets[faceNumber][low][high];   // this face

pFaceletColors2[i] =

pFaceletColors3[i] =
}
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;

}

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].

// 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();

// 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).
face_t faceNumber3, color_t colorNumber);

// similarly, load an edge facelet (no face 3 for these)
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.
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;
};
```

Community Search:
MacTech Search:

Notion 2.1.9 - A unified workspace for m...
Notion is the unified workspace for modern teams. Features: Integration with Slack Documents Wikis Tasks More guests: invite up to 10 collaborators, friends & family to your pages Page... Read more
Spotify 1.2.0.1165 - Stream music, creat...
Spotify is a streaming music service that gives you on-demand access to millions of songs. Whether you like driving rock, silky R&B, or grandiose classical music, Spotify's massive catalogue puts... Read more
Thunderbird 102.5.1 - Email client from...
As of July 2012, Thunderbird has transitioned to a new governance model, with new features being developed by the broader free software and open source community, and security fixes and improvements... Read more
Pinegrow 7.03 - Mockup and design web pa...
Pinegrow (was Pinegrow Web Designer) is desktop app that lets you mockup and design webpages faster with multi-page editing, CSS and LESS styling, and smart components for Bootstrap, Foundation,... Read more
Adobe After Effects 2022 23.1 - Create p...
The new, more connected Adobe After Effects can make the impossible possible. Get powerful new features like a Live 3D Pipeline that brings CINEMA 4D scenes in as layers - without intermediate... Read more
SteerMouse 5.6.7 - Powerful third-party...
SteerMouse is an advanced driver for USB and Bluetooth mice. SteerMouse can assign various functions to buttons that Apple's software does not allow, including double-clicks, modifier clicks,... Read more
Wireshark 4.0.2 - Network protocol analy...
Wireshark is one of the world's foremost network protocol analyzers, and is the standard in many parts of the industry. It is the continuation of a project that started in 1998. Hundreds of... Read more
Adobe Premiere Pro 2022 23.1 - Digital v...
Adobe Premiere Pro is available as part of Adobe Creative Cloud for as little as \$54.99/month. The price on display is a price for annual by-monthly plan for Adobe Premiere Pro only. Adobe Premiere... Read more
1Password is a password manager that uniquely brings you both security and convenience. It is the only program that provides anti-phishing protection and goes beyond password management by adding Web... Read more
FotoMagico 6.3 - Powerful slideshow crea...
FotoMagico lets you create professional slideshows from your photos and music with just a few, simple mouse clicks. It sports a very clean and intuitive yet powerful user interface. High image... Read more

## Latest Forum Discussions

Hello gentle readers, and welcome to the SwitchArcade Round-Up for December 8th, 2022. Today is Thursday, and that usually means an absolute deluge of new releases on the eShop. But the year is winding down, so we’ve only got ten or so to look at... | Read more »
‘Awaken Legends: Idle RPG’ Celebrates th...
Awaken Legends: Idle RPG is adding its first update since the game was soft-launched in November, letting players get their hands on a new hero “Hera Valen". Players can also look forward to the Covenant of the Dark Knight event and the Wishing Well... | Read more »
‘Horizon Chase 2’ Japan World Tour Expan...
Horizon Chase 2 () from Aquiris is getting a major expansion today on Apple Arcade. The Japan World Tour expansion brings in 11 new races across 9 cities and it should be rolling out now as of this writing. I expect it to be available worldwide... | Read more »
Dark Fantasy Visual Novel ‘The 13th Mont...
Originally announced for release in August, The 13th Month from Japanese developer Kobayashimaru and publisher Kodansha released on PC via Steam worldwide this month. The dark fantasy visual novel that reimagines the classic Sleeping Beauty tale, is... | Read more »
Tom Clancey’s The Divison Resurgence ann...
Ubisoft has announced the latest Live Test dates for Tom Clancy’s The Division Resurgence, the hotly anticipated mobile entry in the Divison series. Starting December 8th and ending on the 22nd, the test will offer a huge amount of content for the... | Read more »
‘Easy Come Easy Golf’ New Update Adds St...
Easy Come Easy Golf () from Clap Hanz is one of my favorite games on Apple Arcade. It has been updated quite a bit since launch bringing in new modes and improvements. It recently launched on Nintendo Switch as well. | Read more »
Out Now: ‘Magic vs Metal’, ‘Suzerain’, ‘...
Each and every day new mobile games are hitting the App Store, and so each week we put together a big old list of all the best new releases of the past seven days. Back in the day the App Store would showcase the same games for a week, and then... | Read more »
Hello gentle readers, and welcome to the SwitchArcade Round-Up for December 7th, 2022. Today can be accurately described as Mikhail Madness, with a whopping four reviews from our pal-est of pals. Football Manager 2023 Touch, Wobbledogs, Soccer Story... | Read more »
Alchemy Stars celebrates 1 and a half ye...
It has been one and a half years since Alchemy Stars launched, and Level Infinite is celebrating in style with a host of new content. There will be a new story mission and even a store to explore, and a whole new mode for those budding idol... | Read more »
Fighting Game ‘Art of Fighting 2’ ACA Ne...
Last week, side-scrolling shooter Pulstar hit mobile platforms as the newest ACA NeoGeo series release from Hamster and SNK. Read Shaun’s review of it here. Today, fighting game Art of Fighting 2 has launched on iOS and Android. Art of Fighting 2... | Read more »

## Price Scanner via MacPrices.net

New! Details on Verizon’s Christmas/Holiday p...
Verizon is offering discounts on iPhones, Apple Watch models, and iPads with specific promo codes as part of their Christmas/Holiday 2022 offerings. Codes are valid when adding a new line of service... Read more
Apple MagSafe accessories are back on Holiday...
Amazon has Apple MagSafe Chargers and Apple’s MagSafe Battery on sale for up to 24% off MSRP again as part of their Christmas/Holiday sale. Shipping is free, and all models are in stock: – MagSafe... Read more
13″ M2 MacBook Airs on sale again for the low...
Amazon has 13″ MacBook Airs with M2 CPUs in stock today and on sale for \$150 off MSRP as part of their Christmas/Holiday Sale, prices start at \$1049. Shipping is free. They are the lowest prices... Read more
Get an Apple 16″ MacBook Pro for \$400 off MSR...
16″ MacBook Pros with Apple’s M1 Pro CPUs are in stock and on sale today at B&H Photo for \$300-\$400 off Apple’s MSRP for a limited time. Prices start at \$2099 for M1 Pro models with 512GB or 1TB... Read more
Holiday clearance sale! Previous-generation A...
Amazon has 2nd generation 32GB and 64GB 4K Apple TVs with Siri remotes and 32GB Apple TV HDs on clearance sale for \$80-\$90 off original MSRP. Shipping is free, and delivery is available in time for... Read more
Christmas sale at Verizon: Apple AirPods Pro...
Verizon has first-generation Apple AirPods Pro on sale for \$159.99 on their online store as part of their continuing Christmas/Holiday sale. Their price is \$90 off Apple’s original MSRP, and it’s the... Read more
New Christmas/New Years promo at Xfinity Mobi...
Switch to Xfinity Mobile and open a new line of service, and take \$400 off the price of a new iPhone, no trade-in required, through January 10, 2023. The \$400 is applied to your account as credits... Read more
Apple iPad Smart Keyboard Folio prices drop u...
Apple iPad Smart Keyboard Folio prices have dropped up to \$60 off MSRP at Amazon and Walmart as part of their Christmas/Holiday sales. These are the cheapest prices currently available for these iPad... Read more
Today is the final day for Xfinity Mobile’s \$...
If you switch to Xfinity Mobile and open a new line of service, they will take \$500 off the price of a new iPhone, no trade-in required. This is the best no trade-in Cyber Monday Apple iPhone 14 deal... Read more
Amazon restocks 10.2″ 64GB 9th-generation iPa...
Amazon has Apple’s 9th generation 10.2″ 64GB WiFi iPads (Silver) in stock and on sale for \$269.99 shipped as part of their Christmas/Holiday Sale. Their price is \$60 off Apple’s MSRP. Free delivery... Read more

## Jobs Board

*Apple* Systems Administrator - JAMF - Activ...
…Administration **Duties and Responsibilities** + Configure and maintain the client's Apple Device Management (ADM) solution. The current solution is JAMF supporting Read more
Cashier - *Apple* Blossom Mall - JCPenney (...
Cashier - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Blossom Mall Read more
Omnichannel Associate - *Apple* Blossom Mal...
Omnichannel Associate - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Read more
Sephora Beauty Advisor - *Apple* Blossom Ma...
Sephora Beauty Advisor - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Read more
Operations Associate - *Apple* Blossom Mall...
Operations Associate - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Read more