Visual C# 2005 Guide
Floppy Cube Project - God's Algorithm

God's Algorithm

In cubing, the term, God's Algorithm is used to refer to a method of solving a puzzle using the shortest possible sequence of moves for any given position. In practical terms, we are looking for a table of unique positions and the sequences of moves (or algorithms) that generate them. Each entry is the optimal (shortest) method of generating that state. When the number of positions for a puzzle is relatively small, it is easy to perform the calculation on a computer. Fortunately, the floppy cube is one such puzzle.

Data Representation

Our solution is not based on having a computer turn an actual puzzle and then look at it to say what state it is in. We are looking to represent the puzzle in an abstract way. This means storing key information about the puzzle.

Representing Cube States

floppy cube turns

We can represent the positions of the corners using the letters a-d as shown in the diagram above.

The edges don't move, but we need to keep track of their orientations. We can use a 0 to represent a correctly oriented edge and a 1 to represent the incorrectly flipped edges.

A string of the corner positions followed by a string of edge states ab, bc, cd, da would give us a solved puzzle string of,

abcd0000

As a global variable this would be,

// solved positions
private static string solvedPosition = "abcd0000";

Turns

floppy cube turns

The diagram shows the possible turns on the floppy cube. We can represent each turn with the numbers 0 to 3 in the same order as the diagram. A sequence of turns can be stored as a string of these characters.

The effect of each turn would be to reorder the string of positions and edge states from above. Using our solved corner position (abcd) as a reference, the position of each corner after each of the 4 turns can be represented with the following table,

Turnabcd
01023
10213
20312
33120

Meaning that, when you do turn 0, the piece at position 1 goes to position 0, 1 to 0. 2 and 3 stay where they were. This can be a 2d integer array as follows,

// transition table for position changes
private static int[,] mapPositions = { { 1, 0, 2, 3 }, { 0, 2, 1, 3 },
{ 0, 1, 3, 2 }, { 3, 1, 2, 0 } };

Move Table

Each time we find a new position, we need to store it. We can use a Dictionary to do that. We can use the generic List structure to store all of the unique postions ar each depth. We'll assume no more than 14 turns to start with - we can adjust this number up or down when we have executed the program.

// dictionary to store moves
private static Dictionary<string,string> moveTable = new Dictionary<string,string>();
// list to store moves at each depth
private static List<string>[] positionsAtDepth = new List<string>[15];