Preface and Acknowledgements
This section introduces the project, its purpose, and acknowledges contributions from mentors and collaborators.
Rubiks Cube Simulation and Solver Challenges
This section discusses the main challenges faced when simulating a Rubik's Cube in Unity and developing an algorithmic solver.
public static byte[] duplicate(byte[] original)
{
byte[] copy = new byte[original.Length];
for(int i = 0; i < original.Length; i++)
{
copy[i] = original[i];
}
return copy;
}
Unity Game Engine Rendering and Animation
This section explains how 3D objects are rendered, how animations are handled, and performance considerations in Unity.
public void initiateAnimation(Vector3 centerOfRoation, Vector3 axisOfRotation, float animationLength)
{
animationAxisCenter = centerOfRoation;
animationAxis = axisOfRotation;
maxAnimationTime = animationLength;
if ((transform.position != goalLocation) || (transform.position == centerOfRoation))
{
startAnimation();
}
else
{
jumpToRenderLocation();
}
}
public void jumpToRenderLocation()
{
transform.position = goalLocation;
transform.eulerAngles = new Vector3(goalOrientation.x, goalOrientation.y, goalOrientation.z);
}
public void runAnimation()
{
float animationAngle = (90 / maxAnimationTime) * Time.deltaTime;
transform.RotateAround(animationAxisCenter, animationAxis, animationAngle);
}
Code Representation of 3D Objects
This section details how Rubik’s Cube pieces are represented in code, including object hierarchies, transforms, and rotations.
/*
INDEX MAP
Red side White side Blue side
|0 |1 |2 | |8 |9 |10| |16|17|18|
|3 |x |4 | |11|x |12| |19|x |20|
|5 |6 |7 | |13|14|15| |21|22|23|
Green side Yellow side Orange side
|24|25|26| |32|33|34| |40|41|42|
|27|x |28| |35|x |36| |43|x |44|
|29|30|31| |37|38|39| |45|46|47|
PIECE MAP
Corners
White Side Yellow Side
|0 |x |1 | |4 |x |5 |
|x |x |x | |x |x |x |
|2 |x |3 | |6 |x |7 |
Edges
White Side Yellow Side
|x |9 |x | |x |13|x |
|8 |x |10| |12|x |14|
|x |11|x | |x |15|x |
Red Side Orange Side
|x |11|x | |x |9 |x |
|16|x |17| |18|x |19|
|x |13|x | |x |15|x |
COLOR MAP
Red = 0 White = 1 Blue = 2
Green = 3 Yellow = 4 Orange = 5
Counter Clockwise
Red = 6 White = 7 Blue = 8
Green = 9 Yellow = 10 Orange = 11
*/
public static byte[] getSolvedByteCube()
{
byte[] solvedByteCube = new byte[48];
//Red Side
solvedByteCube[0] = 0;
solvedByteCube[1] = 0;
solvedByteCube[2] = 0;
solvedByteCube[3] = 0;
solvedByteCube[4] = 0;
solvedByteCube[5] = 0;
solvedByteCube[6] = 0;
solvedByteCube[7] = 0;
//White Side
solvedByteCube[8] = 1;
solvedByteCube[9] = 1;
solvedByteCube[10] = 1;
solvedByteCube[11] = 1;
solvedByteCube[12] = 1;
solvedByteCube[13] = 1;
solvedByteCube[14] = 1;
solvedByteCube[15] = 1;
//Blue Side
solvedByteCube[16] = 2;
solvedByteCube[17] = 2;
solvedByteCube[18] = 2;
solvedByteCube[19] = 2;
solvedByteCube[20] = 2;
solvedByteCube[21] = 2;
solvedByteCube[22] = 2;
solvedByteCube[23] = 2;
//Green Side
solvedByteCube[24] = 3;
solvedByteCube[25] = 3;
solvedByteCube[26] = 3;
solvedByteCube[27] = 3;
solvedByteCube[28] = 3;
solvedByteCube[29] = 3;
solvedByteCube[30] = 3;
solvedByteCube[31] = 3;
//Yellow Side
solvedByteCube[32] = 4;
solvedByteCube[33] = 4;
solvedByteCube[34] = 4;
solvedByteCube[35] = 4;
solvedByteCube[36] = 4;
solvedByteCube[37] = 4;
solvedByteCube[38] = 4;
solvedByteCube[39] = 4;
//YOrange Side
solvedByteCube[40] = 5;
solvedByteCube[41] = 5;
solvedByteCube[42] = 5;
solvedByteCube[43] = 5;
solvedByteCube[44] = 5;
solvedByteCube[45] = 5;
solvedByteCube[46] = 5;
solvedByteCube[47] = 5;
return solvedByteCube;
}
How to Solve A Rubiks Cube
This section outlines how humans first learn simple methods for solving a Rubik’s Cube.
Programmatic Approach
This section describes the overall coding strategy for coding a program to utilize the simple methods to solve the a Rubik’s Cube.
public static byte[] generateGoalCube(byte[] byteCube, byte[] targetData, byte[] maybeSolved, byte[] alreadySolved, byte stage)
{
byte[] newGoalCube = RubiksByteCube.getEmptyCube(100);
byte[] preSolved = new byte[] { 100 };
if (maybeSolved != null)
{
preSolved = new byte[maybeSolved.Length];
}
for (int i = 0; i < preSolved.Length; i++) { preSolved[i] = 100; }
if (maybeSolved != null)
{
for (int i = 0; i < maybeSolved.Length; i++)
{
byte[] index = ByteCubeAnalyzer.getPieceIndexes(maybeSolved[i]);
if (maybeSolved[i] == targetData[0])
{
preSolved[i] = maybeSolved[i];
// Debug.Log("Target Piece " + preSolved[i] + " added Goal");
continue;
}
//Debug.Log("Checking colors at : " + index[0] + ", " + index[1]);
if (ByteCubeAnalyzer.pieceIsCorrect(byteCube, maybeSolved[i]))
{
//Debug.Log("Piece " + maybeSolved[i] + " in correct Location");
preSolved[i] = maybeSolved[i];
}
}
}
if (maybeSolved == null)
{
byte[] emptyIndex = new byte[] { 100 };
emptyIndex = checkForMidPoints(byteCube, newGoalCube, targetData, stage, emptyIndex);
}
for (int i = 0; i < preSolved.Length; i++)
{
if (preSolved[i] != 100)
{
byte[] index = ByteCubeAnalyzer.getPieceIndexes(preSolved[i]);
if (preSolved[i] == targetData[0])
{
index = checkForMidPoints(byteCube, newGoalCube, targetData, stage, index);
}
if (index != null)
{
for (int k = 0; k < index.Length; k++)
{
newGoalCube[index[k]] = ByteCubeAnalyzer.correctColorAtIndex(index[k]);
//Debug.Log("Value " + newGoalCube[index[k]] + " added to goal index of " + index[k]);
}
}
}
}
if (alreadySolved != null)
{
for (int i = 0; i < alreadySolved.Length; i++)
{
if (alreadySolved[i] != 100)
{
byte[] index = ByteCubeAnalyzer.getPieceIndexes(alreadySolved[i]);
for (int k = 0; k < index.Length; k++)
{
newGoalCube[index[k]] = ByteCubeAnalyzer.correctColorAtIndex(index[k]);
//Debug.Log("Value " + newGoalCube[index[k]] + " added to goal index of " + index[k]);
}
}
}
}
return newGoalCube;
}
Setting the Stage
This section covers how the concept of 'stages' is implented in my code for breaking up the solve into multiple, less complicated steps.
public static byte[] getYellowCrossGoalCube(byte[] byteCube, byte[] targetData, byte stage)
{
byte[] maybeSolved = new byte[4] { 12, 13, 14, 15 };
byte[] alreadySolved = null;
return generateGoalCube(byteCube, targetData, maybeSolved, alreadySolved, stage);
}
public static byte[] getYellowSideGoalCube(byte[] byteCube, byte[] targetData, byte stage)
{
byte[] maybeSolved = new byte[4] { 4, 5, 6, 7 };
byte[] alreadySolved = new byte[4] { 12, 13, 14, 15 };
return generateGoalCube(byteCube, targetData, maybeSolved, alreadySolved, stage);
}
public static byte[] getMidGoalCube(byte[] byteCube, byte[] targetData, byte stage)
{
byte[] maybeSolved = new byte[4] { 16, 17, 18, 19 };
byte[] alreadySolved = new byte[8] { 12, 13, 14, 15, 4, 5, 6, 7 };
return generateGoalCube(byteCube, targetData, maybeSolved, alreadySolved, stage);
}
public static byte[] getWhiteCrossGoalCube(byte[] byteCube, byte[] targetData, byte stage)
{
byte[] maybeSolved = null;
byte[] alreadySolved = new byte[12] { 12, 13, 14, 15, 4, 5, 6, 7, 16, 17, 18, 19 };
return generateGoalCube(byteCube, targetData, maybeSolved, alreadySolved, stage);
}
public static byte[] getWhiteCrossAndEdgesGoalCube(byte[] byteCube, byte[] targetData, byte stage)
{
byte[] maybeSolved = null;
byte[] alreadySolved = new byte[12] { 12, 13, 14, 15, 4, 5, 6, 7, 16, 17, 18, 19 };
return generateGoalCube(byteCube, targetData, maybeSolved, alreadySolved, stage);
}
public static byte[] getWhiteCornersGoalCube(byte[] byteCube, byte[] targetData, byte stage)
{
byte[] maybeSolved = null;
byte[] alreadySolved = new byte[16] { 12, 13, 14, 15, 4, 5, 6, 7, 16, 17, 18, 19, 8, 9, 10, 11 };
return generateGoalCube(byteCube, targetData, maybeSolved, alreadySolved, stage);
}
public static bool yellowCrossComplete(byte[] goalCube)
{
byte[] byteCheck = new byte[8] { 33, 35, 36, 38, 6, 33, 30, 46 };
return rawByteCheck(goalCube, byteCheck);
}
public static bool yellowSideComplete(byte[] goalCube)
{
byte[] byteCheck = new byte[20] { 33, 35, 36, 38, 6, 33, 30, 46, 5, 6, 7, 21, 22, 23, 45, 46, 47, 29, 30, 31 };
return rawByteCheck(goalCube, byteCheck);
}
public static bool midCubeComplete(byte[] goalCube)
{
byte[] byteCheck = new byte[28] { 33, 35, 36, 38, 6, 33, 30, 46, 5, 6, 7, 21, 22, 23, 45, 46, 47, 29, 30, 31, 3, 4, 19, 20, 43, 44, 27, 28 };
return rawByteCheck(goalCube, byteCheck);
}
public static bool whiteCrossComplete(byte[] goalCube)
{
byte[] byteCheck = new byte[32] { 33, 35, 36, 38, 6, 33, 30, 46, 5, 6, 7, 21, 22, 23, 45, 46, 47, 29, 30, 31, 3, 4, 19, 20, 43, 44, 27, 28,9,11,12,14 };
return rawByteCheck(goalCube, byteCheck);
}
public static bool whiteCrossAndEdgesComplete(byte[] goalCube)
{
byte[] byteCheck = new byte[36] { 33, 35, 36, 38, 6, 33, 30, 46, 5, 6, 7, 21, 22, 23, 45, 46, 47, 29, 30, 31, 3, 4, 19, 20, 43, 44, 27, 28, 9, 11, 12, 14, 1, 17, 41, 25 };
return rawByteCheck(goalCube, byteCheck);
}
public static bool cubeComplete (byte[] goalCube)
{
byte[] byteCheck = new byte[48] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47 };
return rawByteCheck(goalCube, byteCheck);
}
Search Algorithms
This section explains the general concept of search algorithms such as BFS, DFS, or heuristic-based methods. Then it delves into how search algorithms are used in the solver.
public MoveSet getGuidedByteMovesFast(byte[] baseByteCube, byte stage, bool fullSolve = true)
{
byte[] returnCube = RubiksByteCube.duplicate(baseByteCube);
byte[] thoughtCube = RubiksByteCube.duplicate(baseByteCube);
int iterations = 0;
bool solutionFound = false;
byte[] guidedByteMoves = new byte[1] { 100 };
while (!StageDecider.cubeComplete(thoughtCube))
{
iterations++;
if (iterations > 50) { break; }
stage = StageDecider.getCurrentStage(thoughtCube, 100);
calculations = 0;
byte[] targetData = TargetManager.getTarget(thoughtCube, stage);
Debug.Log("No targets found");
if (targetData[0] == 100) { return new MoveSet(ByteMove.getNullMoves(1)); }
Debug.Log("Target : " + targetData[0] + " Target Location: " + targetData[1]);
byte[] goalCube = StageDecider.getCurrentGoalCube(thoughtCube, stage, targetData);
string goalString = "|";
for (int i = 0; i < goalCube.Length; i++)
{
if (goalCube[i] != 100)
{
goalString += i + ": " + goalCube[i] + " |";
}
}
Debug.Log(goalString);
int maxDepth = 0;
int forceMove = -1;
byte[] potentialMoves = MoveManager.getPossibleMoves(thoughtCube, stage, targetData, out maxDepth, out forceMove);
Debug.Log("Max moves: " + maxDepth);
Debug.Log("Potential moves: " + ByteMove.byteMovesToString(potentialMoves));
currentMovePool = potentialMoves;
byte[] newBranch = ByteMove.getNullMoves(maxDepth);
byte[] newMoves = new byte[1] { 100 };
solutionFound = false;
newMoves = getBestGuidedByteBranchFast(thoughtCube, stage, goalCube, potentialMoves, targetData, newBranch, 100, 1, 0, maxDepth, forceMove, out solutionFound, out returnCube, true);
if (!solutionFound) { break; }
guidedByteMoves = ByteMove.combineMoveSets(guidedByteMoves, newMoves);
Debug.Log("Current Moves: " + ByteMove.byteMovesToString(guidedByteMoves));
if (!fullSolve) { break; }
thoughtCube = RubiksByteCube.duplicate(returnCube);
}
if (solutionFound)
{
Debug.Log("Stage: " + stage);
Debug.Log(ByteMove.byteMovesToString(guidedByteMoves));
Debug.Log("Total Moves: " + guidedByteMoves.Length);
Debug.Log("Cleaning Moves...");
guidedByteMoves = ByteMove.removeRedundantMoves(guidedByteMoves);
Debug.Log(ByteMove.byteMovesToString(guidedByteMoves));
Debug.Log("Total Moves: " + guidedByteMoves.Length);
MoveSet calculatedMoveSet = new MoveSet(guidedByteMoves);
return calculatedMoveSet;
}
else
{
Debug.Log("Solution not found: " + ByteConverter.byteMoveString(guidedByteMoves));
Debug.Log("Stage: " + stage);
Debug.Log(ByteMove.byteMovesToString(guidedByteMoves));
return new MoveSet(ByteMove.getNullMoves(1));
}
}
public byte[] getBestGuidedByteBranchFast(byte[] thoughtByteCube, byte stage, byte[] goalCube, byte[] potentialMoves, byte[] targetData, byte[] currentBranch, byte byteBranchBase, byte repeated, byte calculationDepth, int maxDepth, int forceMove, out bool solutionFound, out byte[] returnCube, bool firstLoop = false)
{
//Debug.Log("Force Move: " + forceMove);
if ((calculationDepth < maxDepth) || (calculations > maxCalculations))
{
//Debug.Log("Current Branch: " + ByteMove.byteMovesToString(currentBranch));
potentialMoves = ByteMoveDecider.removeRedundants(thoughtByteCube, currentMovePool, byteBranchBase, repeated, forceMove, targetData);
//Debug.Log("Moves to consider: " + ByteMove.byteMovesToString(potentialMoves));
if (forceMove >= 0)
{
if (targetData[1] != 52) { forceMove++; }
else { forceMove = 0; }
if (forceMove >= currentMovePool.Length) { forceMove = 0; }
}
if (forceMove >= 0) { calculations++; }
else { calculations += potentialMoves.Length; }
if (calculations >= maxCalculations)
{
returnCube = RubiksByteCube.duplicate(thoughtByteCube);
solutionFound = false;
return currentBranch;
}
byte[][] duplicateCubes = new byte[potentialMoves.Length][];
bool[] solved = new bool[potentialMoves.Length];
byte[][] newBranches = new byte[potentialMoves.Length][];
for (int i = 0; i < potentialMoves.Length; i++)
{
newBranches[i] = DuplicateThis.array(currentBranch);
newBranches[i][calculationDepth] = potentialMoves[i];
duplicateCubes[i] = RubiksByteCube.duplicate(thoughtByteCube);
ByteCubeTurner.turn(duplicateCubes[i], potentialMoves[i]);
solved[i] = StageDecider.cubeMatchesGoal(duplicateCubes[i], goalCube);
if (solved[i])
{
returnCube = RubiksByteCube.duplicate(duplicateCubes[i]);
solutionFound = true;
return newBranches[i];
}
}
//byte[][] newBaseBranches = ByteMoveDecider.initiateNewGuidedBranch(thoughtByteCube, goalCube, potentialMoves, currentBranch, calculationDepth, out organizedMoves, out solved, out duplicateCubes);
calculationDepth++;
byte[] bestBranch = new byte[1] { 100 };
byte[] chosenBestCube = new byte[1] { 100 };
bool foundASolution = false;
if (firstLoop)
{
Parallel.For(0, newBranches.Length, i =>
{
if (byteBranchBase == potentialMoves[i]) { repeated++; }
else { repeated = 1; }
bool cubeSolved = false;
byte[] bestCube = new byte[1] { 100 };
newBranches[i] = getBestGuidedByteBranchFast(duplicateCubes[i], stage, goalCube, currentMovePool, targetData, newBranches[i], newBranches[i][calculationDepth - 1], repeated, calculationDepth, maxDepth, forceMove, out cubeSolved, out bestCube);
if (cubeSolved)
{
foundASolution = true;
chosenBestCube = bestCube;
bestBranch = newBranches[i];
return;
}
});
}
else
{
for (int i = 0; i < potentialMoves.Length; i++)
{
if (byteBranchBase == potentialMoves[i]) { repeated++; }
else { repeated = 1; }
bool cubeSolved = false;
byte[] bestCube = new byte[1] { 100 };
newBranches[i] = getBestGuidedByteBranchFast(duplicateCubes[i], stage, goalCube, currentMovePool, targetData, newBranches[i], newBranches[i][calculationDepth - 1], repeated, calculationDepth, maxDepth, forceMove, out cubeSolved, out bestCube);
if (cubeSolved)
{
foundASolution = true;
chosenBestCube = bestCube;
bestBranch = newBranches[i];
break;
}
}
}
solutionFound = foundASolution;
if (solutionFound)
{
returnCube = RubiksByteCube.duplicate(chosenBestCube);
}
else
{
returnCube = RubiksByteCube.duplicate(thoughtByteCube);
}
return bestBranch;
}
returnCube = RubiksByteCube.duplicate(thoughtByteCube);
solutionFound = false;
return currentBranch;
}
Bringing it All Together
This section demonstrates how each aspect of the code works together to make the solver function. Staging -> Search -> Turn Sequencing -> Actual Turns -> Render Updates
public static byte getCurrentStage(byte[] byteCube, byte totalStages)
{
for (int i = 0; i < totalStages; i++)
{
if (stageComplete(byteCube, (byte)i)) { continue; }
else { return (byte)i; }
}
return totalStages;
}
public static bool stageComplete(byte[] byteCube, byte stage)
{
switch (stage)
{
case 0:
return yellowCrossComplete(byteCube);
case 1:
return yellowSideComplete(byteCube);
case 2:
return midCubeComplete(byteCube);
case 3:
return whiteCrossComplete(byteCube);
case 4:
return whiteCrossAndEdgesComplete(byteCube);
case 5:
return cubeComplete(byteCube);
default:
return false;
}
}
public static byte[] getCurrentGoalCube(byte[] byteCube, byte stage, byte[] targetData)
{
switch(stage)
{
case 0:
return getYellowCrossGoalCube(byteCube, targetData, stage);
case 1:
return getYellowSideGoalCube(byteCube, targetData, stage);
case 2:
return getMidGoalCube(byteCube, targetData, stage);
case 3:
return getWhiteCrossGoalCube(byteCube, targetData, stage);
case 4:
return getWhiteCrossAndEdgesGoalCube(byteCube, targetData, stage);
case 5:
return getWhiteCornersGoalCube(byteCube, targetData, stage);
default:
return null;
}
}
Potential Improvements
This section highlights possible future enhancements, such as optimizing cube representation in code, search algorithm architecture, and search algorithm execution.
public static byte[] removeRedundantMoves(byte[] moves)
{
int newLength = 0;
byte[] moveDuplicate = new byte[moves.Length];
byte previous = 100;
byte repeat = 1;
for (int i = 0; i < moves.Length; i++)
{
moveDuplicate[i] = moves[i];
if ((moves[i] < 0) ||(moves[i] > 11)) { continue; }
if (moves[i] == previous) { repeat++; }
else { repeat = 1; }
if (moves[i] == getOpposite(previous))
{
if (i > 0) { moveDuplicate[i - 1] = 100; }
moveDuplicate[i] = 100;
newLength --;
previous = 100;
continue;
}
if (repeat >=3)
{
moveDuplicate[i] = getOpposite(moves[i]);
moveDuplicate[i - 1] = 100;
moveDuplicate[i - 2] = 100;
newLength --;
previous = getOpposite(moves[i]);
continue;
}
newLength++;
previous = moves[i];
}
byte[] cleanedList = new byte[newLength];
int j = 0;
for (int i = 0; i < moveDuplicate.Length; i++)
{
if ((moveDuplicate[i] >= 0) && (moveDuplicate[i] <= 11))
{
cleanedList[j] = moveDuplicate[i];
j++;
if (j >= cleanedList.Length) { break; }
}
}
return cleanedList;
}
On the Horizon
This section looks at additional plans for the cube solver such as additional UI features like a cube-painter and custom colorization.