# 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.