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.
10000000 | 1000000 | 100000 | 10000 | 1000 | 100 | 10 | Units |
---|---|---|---|---|---|---|---|
0 | 0 | 0 | 4 | 7 | 3 | 9 | 5 |
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! |
---|---|---|---|---|---|---|---|
7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
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.
Permutation | 1 | 2 | 3 | Index | |||
---|---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 0 | 0 | 0 | 0 |
1 | 2 | 4 | 3 | 0 | 0 | 1 | 1 |
1 | 3 | 2 | 4 | 0 | 1 | 0 | 2 |
1 | 3 | 4 | 2 | 0 | 1 | 1 | 3 |
1 | 4 | 2 | 3 | 0 | 2 | 0 | 4 |
1 | 4 | 3 | 2 | 0 | 2 | 1 | 5 |
2 | 1 | 3 | 4 | 1 | 0 | 0 | 6 |
2 | 1 | 4 | 3 | 1 | 0 | 1 | 7 |
2 | 3 | 1 | 4 | 1 | 1 | 0 | 8 |
2 | 3 | 4 | 1 | 1 | 1 | 1 | 9 |
2 | 4 | 1 | 3 | 1 | 2 | 0 | 10 |
2 | 4 | 3 | 1 | 1 | 2 | 1 | 11 |
3 | 1 | 2 | 4 | 2 | 0 | 0 | 12 |
3 | 1 | 4 | 2 | 2 | 0 | 1 | 13 |
3 | 2 | 1 | 4 | 2 | 1 | 0 | 14 |
3 | 2 | 4 | 1 | 2 | 1 | 1 | 15 |
3 | 4 | 1 | 2 | 2 | 2 | 0 | 16 |
3 | 4 | 2 | 1 | 2 | 2 | 1 | 17 |
4 | 1 | 2 | 3 | 3 | 0 | 0 | 18 |
4 | 1 | 3 | 2 | 3 | 0 | 1 | 19 |
4 | 2 | 1 | 3 | 3 | 1 | 0 | 20 |
4 | 2 | 3 | 1 | 3 | 1 | 1 | 21 |
4 | 3 | 1 | 2 | 3 | 2 | 0 | 22 |
4 | 3 | 2 | 1 | 3 | 2 | 1 | 23 |
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