Visual Basic 2010 (Console) Guide
Pocket Cube - Indexing

Introduction

In order to solve the puzzle, our program is first going to calculate the number of turns required to reach each different permutation (order of pieces) and each different orientation. This, as you will see later, is sufficient to allow us to calculate solutions to any position. The problem we have to counter is how to store this information.

We have 5040 permutations to store and 729 orientations to store (see last page) and all we want to store is a number - how many turns it took to get there.

Permutations ( Positions Of The Pieces )

If we have 4 items that can each be in one of 4 positions. We can represent the positions and pieces using numbers.

We can use an array to store which piece is in which position. Since arrays are assumed to begin with an index of zero, that has been added to the declaration.

Dim solvedPieces() as Byte = { 0, 1, 2, 3, 4 }

When the pieces are solved, the numbers are in the correct order and match up with their index in the array.

If the first two pieces swap around, the array becomes,

{ 0, 2, 1, 3, 4 }

This is the best way to represent the position when we want to manipulate the order (perform a move on the puzzle). It's not very efficient when it comes to storage though. This is when it becomes useful to have a way of converting each permutation into a single integer.

A great method for doing this is based on the factorial number system.

A reminder of the place value table for the decimal number system - it shows the number 47395. Each column's place value is 10. The highest digit allowable in any column is a 9.

10000000100000010000010000100010010Units
00047395

In the factorial number system, each column's place value is n! The highest digit allowed in a column is determined by n. The highest number that can be represented is determined by the number of columns. With n columns, the largest number would be n! -1

7!6!5!4!3!2!1!0!
76543210

If 4 pieces can be arranged into 4 positions and all permutations are possible, the number of positions is 4!. If each position were assigned a number, with 0 going for the solved position, then the factorial number system should be perfect to do this.

The following table shows how each of those 24 permutations can be mapped to a single integer. The first four columns show the permutation. For the next column, look at the first number in the permutation, count how many times you find a smaller number to its right. This process is also done for the second and third numbers in the permutation. The factorial number for the permutation is calculated by multiplying the numbers in columns 1,2 & 3 by their place values working left to right on the chart (n-1!, n-2!,..., 1), in this case 6, 2 and 1.

Permutation123Index
12340000
12430011
13240102
13420113
14230204
14320215
21341006
21431017
23141108
23411119
241312010
243112111
312420012
314220113
321421014
324121115
341222016
342122117
412330018
413230119
421331020
423131121
431232022
432132123

Pseudocode for this kind of conversion can be found on , Jaap's Puzzle Page. Here are some Visual Basic functions that do the same job.

' Converts a permutation to an integer 0 to n!-1
Function PermutationToIndex(ByVal perm As Byte(), ByVal n As Integer) As Integer
   Dim t As Integer = 0
   For i As Integer = 1 To n - 1
      t = t * (n - i + 1)
      For j As Integer = i + 1 To n
         If perm(i) > perm(j) Then t = t + 1
      Next
   Next
   Return t
End Function

' Converts an integer to a permutation array of size n
Function IndexToPermutation(ByVal idx As Integer, ByVal n As Integer) As Byte()
   Dim position(n) As Byte
   Dim t As Integer = idx
   position(n) = 1
   For i As Integer = n - 1 To 1 Step -1
      position(i) = 1 + (t Mod (n - i + 1))
      t = t \ (n - i + 1)
      For j As Integer = i + 1 To n
         If position(j) >= position(i) Then position(j) = position(j) + 1
      Next
   Next
   Return position
End Function

Orientations

The way to represent orientations is a little easier to understand. If you use 0 for a correctly oriented piece and 1 for a twisted piece then you can also store orientations in an array. A four-piece puzzle where each piece can be flipped or not would have something like,

Dim solvedOrientations() as Byte = { 0, 0, 0, 0, 0 }

The number of different ways the pieces can be oriented is vn where v is the number of orientations and n is the number of pieces.

When there are two possible orientations, you could take each position as a place in a binary number, 1010 when pieces 1 and 3 are flipped. Each way of orienting the pieces would have its own number.

On a pocket cube we have 3 orientations, solved (0), clockwise twist (1), anticlockwise twist(2). Our number won't be binary, it will be ternary.

One thing that often happens with twisty puzzles is that there are constraints on the types of position that can actually be reached. Each turn affects lots of pieces changing their position and their orientation. On a pocket cube, this means that the number of distinct orientations is limited to vn-1. Knowing the orientations of the other pieces, we can always work out the last. The constraint on the pocket cube is that the total twist of the cubes (add up the orientations) must be 0 or divide exactly by 3. Or, total twist mod v = 0.

Jaap has the algorithms for orientations too, with or with the constraint. This is a Visual Basic version with the mod v twist constraint.

' Converts array of orientations to integer - zero twist constraint
Function OrientationToIdx(ByVal oris() As Byte, ByVal n As Integer, ByVal v As Integer) As Integer
   Dim t As Integer = 0
   For i As Integer = 1 To n - 1
      t = t * v
      t = t + oris(i)
   Next
   Return t
End Function

' Converts an integer to orientations
Function IdxToOrientation(ByVal idx As Integer, ByVal n As Integer, ByVal v As Integer) As Byte()
   Dim s As Integer = 0
   Dim t As Integer = idx
   Dim oris(n) As Byte
   For i As Integer = n - 1 To 1 Step -1
      oris(i) = t Mod v
      s = s - oris(i)
      If s < 0 Then s = s + v
      t = t \ v
   Next
   oris(n) = s
   Return oris
End Function