Visual Basic 2010 (Console) Guide
Pocket Cube - Introduction

Introduction

This section outlines a basic program for solving the pocket cube. For simplicity, this has been done as a console program - it could be easily re-written as a Windows Forms program.

The approach that has been implemented here would not be possible without the excellent reference that has been produced by Jaap Scherphuis, Jaap's Puzzle Page. The page on the pocket cube as well as the pages on computer puzzling have proved essential to developing this program and others like it.

The aim of this section is to show how a working program can be produced to solve this puzzle as well as to provide hints as to how other puzzles could be solved using computer programs.

About The Pocket Cube

It is necessary to think a little about the nature of the puzzle we are solving before embarking on the program.

In the following image, the 3 visible faces have been labelled with letters. The letter F is used to represent the Front face. R represents the Right face and U is the Upper face.

pocket cube

A clockwise 90° turn of the Upper face is denoted with an F. F2 is used for a 180° turn and F' is used for an anticlockwise turn. Similarly turns of the other faces are represented with the letters R, R2, R' and U, U2, U'. When our program produces a solution to the puzzle in a given state, it will produce a move sequence using this notation which is familiar to people who follow written solutions to twisty puzzles.

Each of these 3 faces has an opposite face (F - Back, R - Left, U - Down). These faces will not play any part in our program - all positions are reachable on this puzzle with turns of only these 3 (adjacent) faces.

Representing Puzzle States

In order for our program to produce a solution to the puzzle, we need to have a method of representing the state of the puzzle. The following diagram shows the numbers we assign to each piece and position of the cube.

pocket cube

If you pick up a pocket cube and think about the effect of each of the 3 ways we are going to allow it to turn, you'll realise that piece 8 cannot move. That is what we want. The fixed position and orientation of this piece is important. It provides a reference for all of the other pieces and avoids us having to consider whether the cube is solved if we just turn it round.

We will need to keep track of the positions of pieces 1 to 7. There will 7! (7x6x5x4x3x2x1) different ways to arrange the positions of these pieces.

Each piece can be twisted even if it is in its home position. An untwisted piece is gets a 0, a clockwise twisted piece gets a 1 and a 2 is used for pieces which are twisted anticlockwise. This would normally lead to 3 different ways that the pieces can be oriented. However, there is a constraint on this puzzle. If we take the orientation of the pieces for any puzzzle state and add up the 0's, 1's and 2's, we will always get a number that divides exactly by 3. This reduces the ways that we can orient the puzzle pieces by a factor of 3 and means that we will have 36 unique ways to orient our pieces (we can always work out the orientation of the 7th piece by looking at the others).

Some Global Variables

' List of possible moves
Dim mvs() As String = {"F", "F2", "F'", "R", "R2", "R'", "U", "U2", "U'"}
' Permutation Helper Array - tells us the location of the piece that moves here after move F, R U
Dim mapPerm(,) As Integer = {{0, 1, 3, 7, 4, 5, 2, 6}, {0, 2, 6, 3, 4, 1, 5, 7}, {0, 4, 1, 2, 3, 5, 6, 7}}
Dim mapOri(,) As Integer = {{0, 0, 1, 2, 0, 0, 2, 1}, {0, 1, 2, 0, 0, 2, 1, 0}, {0, 0, 0, 0, 0, 0, 0, 0}}

The first variable here is simply a list of the labels we use for moves. They are now in an array (0-8) which allows us to use numbers or the turns in our programming logic. The second variable (mapPerm) is a two-dimensional array showing the order of the pieces after each of the 3 basic turns F, R & U. For example, an F turn does not move the piece in position 1 but the piece in position 2 will end up being whichever piece was in position 3. The last variable here (mapOri) lists the changes to orientation that occur to the pieces after they have moved to their new positions. It takes a while to work out these numbers for a puzzle. If you are good at rotating 3D shapes in your head, no problem. Otherwise, like me, you'll have to sit there messing with a cube until you can 'see' where the numbers come from.