# Visual Basic 2010 (Console) GuidePocket Cube - God's Algorithm

## Introduction

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. Like before, we will only be storing the number of moves that it took to generate the position (the distance).

By separating out the creation of our permutation and orientation tables, and by creating the transition tables, we have made this stage much easier than if we hadn't.

We will need one additional global variable,

```' God's Algorithm Table Dim bigtable(5039, 728) As Byte```

Notice the numbers. For each of the 5040 permutations, there are 729 possible orientations. We will work out how many moves it takes to reach these states on the pocket cube. Multiply these two numbers together and we get the number of distinct positions for the puzzle as a whole (counting both permutation and orientation). That figure comes to 3,674,160.

## Exploring Permutation & Orientation Combined

```'Explore Permutation & Orientation Combined Sub ExploreAll(ByVal p As Integer, ByVal o As Integer)    Dim len As Byte = bigtable(p, o)    Dim mv As Integer = 0    For i As Integer = 0 To 8       If bigtable(perm(p, i), ori(o, i)) = 50 Then          bigtable(perm(p, i), ori(o, i)) = len + 1       End If    Next End Sub```

This time we can use our transition tables. This means that the indexes are no longer being calculated over and over again. This reduces execution time considerably.

## Creating The Monster Table

This is our final table to set up before we can acutally use the data to solve the puzzle. We need to use nested loops this time.

```' Create The Monster Table - Permutation & Orientation Combined Sub CreateMonsterTable()    For i As Integer = 0 To 5039       For j As Integer = 0 To 728          bigtable(i, j) = 50       Next    Next    Console.WriteLine("Calculating Big Tables")    Console.WriteLine("**********************")    Console.WriteLine()    bigtable(0, 0) = 0    Dim len As Integer = 0    Dim c As Integer = 0    Dim tot As Integer = 0    Do       c = 0       For p As Integer = 0 To 5039          For o As Integer = 0 To 728             If bigtable(p, o) = len Then                c = c + 1                ExploreAll(p, o)             End If          Next       Next       Console.WriteLine("Depth: {0} Positions: {1}", len, c)       tot = tot + c       len = len + 1    Loop While c > 0    Console.WriteLine("Finished. {0} unique positions.", tot) End Sub```

## Testing

We can test the program again at this stage. Change the Sub Main so that it reads,

```CreatePermTables() CreateOrientationTables() CreateMonsterTable() Console.ReadLine()```

The last table should be output at the end. The numbers should read,

```Calculating Big Tables ********************** Depth: 0 Positions: 1 Depth: 1 Positions: 9 Depth: 2 Positions: 54 Depth: 3 Positions: 321 Depth: 4 Positions: 1847 Depth: 5 Positions: 9992 Depth: 6 Positions: 50136 Depth: 7 Positions: 227536 Depth: 8 Positions: 870072 Depth: 9 Positions: 1887748 Depth: 10 Positions: 623800 Depth: 11 Positions: 2644 Depth: 12 Positions: 0 Finished. 3674160 unique positions.```

At this point, I always check my calculations against the ones listed for the puzzle on Jaap's Puzzle Page. We have only written out the numbers in face turn metric. We have treated 180° turns as a single turn rather than as 2.