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.