Visual Basic 2010 (Console) Guide
Pocket 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.