Visual Basic 2010 (Console) Guide
Pocket Cube - Building Tables

Permutations

In this section we are going to add code to calculate some tables that will be used for solving. We will deal with permutations first.

We will need 2 global variables, both arrays. The first array is going to store the number of moves it took our program to arrive at this position. The second variable is a 2-dimensional array. For each of the positions, it will store the position that is reached by each of the 9 possible moves (0-8). This will help us greatly in later stages, not just by making the program easier to follow, but also in reducing execution time when solving.

' Pruning table for permutations
Dim prune1(5039) As Byte
' Transition Table For Permutations
Dim perm(5039, 8) As Integer

Next we need a procedure that, given a starting point, will tell us all of the positions that are one move away from that point.

' Explore all permutations within one turn of given position
Sub ExplorePerm(ByVal pos As Integer)
   Dim len As Byte = prune1(pos)
   Dim mv As Integer = 0
   Dim tempPos As Integer = pos
   For i As Integer = 0 To 2
      ' repeat turns
      For j As Integer = 0 To 2
         mv = (i * 3) + j
         tempPos = DoPermMap(tempPos, i)
         perm(pos, mv) = tempPos
         If prune1(tempPos) = 50 Then
            prune1(tempPos) = len + 1
         End If
      Next
      tempPos = pos
   Next
End Sub

The next procedure will set up the initialise values for the global variables and then make calls to our exisiting functions to calculate the values described above.

' Create The Permutation Table
Sub CreatePermTables()
   For i As Integer = 1 To 5039
      prune1(i) = 50
   Next
   prune1(0) = 0
   Console.WriteLine("Calculating Permutation Tables")
   Console.WriteLine("******************************")
   Console.WriteLine()
   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
         If prune1(p) = len Then
            c = c + 1
            ExplorePerm(p)
         End If
      Next
      Console.WriteLine("Depth: {0} Positions: {1}", len, c)
      tot = tot + c
      len = len + 1
   Loop While c > 0
   Console.WriteLine("Finished. {0} unique permutations.", tot)
End Sub

The starting value of 50 is used for the tables since it is a number much larger than the total number of moves required to solve the puzzle. An alternative to using a positive integer is to use a data type that supports negative integers and store the unvisited positions as -1.

Orientations

Code for the orientations is very similar. Because the main work is done by our indexing and turn functions, this part doesn't change a lot.

Global Variables

' Pruning Table For Orientations
Dim prune2(728) As Integer
' Transition Table For Orientations
Dim ori(728, 8) As Integer

Explore Orientations

' Explore all orientations within one turn of given position
Sub ExploreOrientation(ByVal pos As Integer)
   Dim len As Byte = prune2(pos)
   Dim mv As Integer = 0
   Dim tempPos As Integer = pos
   For i As Integer = 0 To 2
      ' repeat turns
      For j As Integer = 0 To 2
         mv = (i * 3) + j
         tempPos = DoOrientationMap(tempPos, i)
         ori(pos, mv) = tempPos
         If prune2(tempPos) = 50 Then
            prune2(tempPos) = len + 1
         End If
      Next
      tempPos = pos
   Next
End Sub

Create Table

' Create The Orienation Table
Sub CreateOrientationTables()
   For i As Integer = 1 To 728
      prune2(i) = 50
   Next
   Console.WriteLine("Calculating Orientation Tables")
   Console.WriteLine("******************************")
   Console.WriteLine()
   Dim len As Integer = 0
   Dim c As Integer = 0
   prune2(0) = 0
   Dim tot As Integer = 0
   Do
      c = 0
         For p As Integer = 0 To 728
         If prune2(p) = len Then
            c = c + 1
            ExploreOrientation(p)
         End If
         Next
      Console.WriteLine("Depth: {0} Positions: {1}", len, c)
      tot = tot + c
      len = len + 1
   Loop While c > 0
   Console.WriteLine("Finished. {0} unique orientations.", tot)
End Sub

Testing The Program

There is enough code now to test that the program is working. Add the following lines to the Sub Main, save and execute the program.

CreatePermTables()
CreateOrientationTables()
Console.ReadLine()

You should get the following output,

Calculating Permutation Tables
******************************
Depth: 0 Positions: 1
Depth: 1 Positions: 9
Depth: 2 Positions: 54
Depth: 3 Positions: 297
Depth: 4 Positions: 1233
Depth: 5 Positions: 2157
Depth: 6 Positions: 1244
Depth: 7 Positions: 45
Depth: 8 Positions: 0
Finished. 5040 unique permutations.

Calculating Orientation Tables
******************************

Depth: 0 Positions: 1
Depth: 1 Positions: 2
Depth: 2 Positions: 12
Depth: 3 Positions: 64
Depth: 4 Positions: 274
Depth: 5 Positions: 336
Depth: 6 Positions: 40
Depth: 7 Positions: 0
Finished. 729 unique orientations.