Revision as of 06:57, 10 January 2018

Notes on Tuple Representation of Rubiks Cube

Let's first explain what we mean when we talk about a tuple representation of a cube, and why this is useful.

Tuple Representation

A tuple representation means, we are representing one possible permutation of the Rubik's Cube using a tuple, ideally a tuple of N items arranged in some particular way.

Now, if we think about how a 3x3 Rubik's Cube or 4x4 Rubik's Revenge is mechanically constructed, we see that the cube consists of:

Rubik's Cube: 26 total (mechanical) pieces

8 corner pieces
12 edge pieces
6 center pieces

Rubik's Revenge: 56 total (mechanical) pieces

8 corner pieces
24 double-edge pieces (12 left-hand, 12 right-hand)
24 center pieces

However, it is important to note that we are not trying to find the minimal representation of the Rubik's Cube, we are simply trying to find a unique representation of a Rubik's Cube. Representing faces requires more information than representing pieces, but it is a lot simpler and accomplishes what we need:

The 3x3 Rubik's Cube has 9 squares on each face, and 6 faces, for a total of 36 squares.
The 4x4 Rubik's Revenge has 16 squares on each face, and 6 faces, for 96 total squares.

Now, if we were looking for a minimal representation, we would utilize the fact that some of these squares are innately linked (for example, the three faces representing a corner piece are always positioned in the same way relative to one another, even though they may move relative to the rest of the pieces on the cube).

However, we simply want a unique representation, so we can represent the state of any 3x3 Rubik's Cube using a 36-tuple, or the state of any 4x4 Rubik's Revenge using a 96-tuple.

Why A Tuple Representation

Finding a tuple representation enables us to study the properties of various move sequences and understand how the cube works.

For example, if we repeatedly apply any sequence of moves to a Rubik's Cube, eventually it will return back to the solved state. To predict how many times a sequence must be applied to a cube to return to the solved state, we can use techniques demonstrated by Donald Knuth in Volume 3 of The Art of Computer Programming (see AOCP) to derive a permutation algebra, factor permutations into cycles, and find the sequence length via the lcm of each cycle length.

Tuple representation: https://github.com/charlesreid1/rubiks-cycles/blob/master/tup.py

4x4 Rubiks Cube Representation

Flags

@@ Line 1: / Line 1: @@
-=4x4 Rubiks Cube Representation=
+=Notes on Tuple Representation of Rubiks Cube=
-==Types of Pieces==
+Let's first explain what we mean when we talk about a tuple representation of a cube, and why this is useful.
-To represent the 4x4 cube as a permutation, so that we can move toward a permutation algebra for 4x4 Rubiks Cubes, we have to think about the cube as being composed of three separate types of pieces:
+==Tuple Representation==
-* 8 corner pieces, 3 orientations each
+A tuple representation means, we are representing one possible permutation of the Rubik's Cube using a tuple, ideally a tuple of N items arranged in some particular way.
-* 24 squares, 6 of each color in groups of 4
-* 12 left dedge pieces, 12 right dedge pieces
-(Note: dedge = double edge)
+Now, if we think about how a 3x3 Rubik's Cube or 4x4 Rubik's Revenge is mechanically constructed, we see that the cube consists of:
-While we can think about the 24 center squares and 24 dedge pieces as being as simple to represent as two 24-tuples, the 8 corner pieces require a bit more care.
+Rubik's Cube: 26 total (mechanical) pieces
-We might think of representing the corners using an integer to indicate which of the 8 corner pieces a piece is, and a second tuple that would represent the orientation of each corner piece, with 0, 1, 2 labeling some predetermined (but ultimately arbitrary) scheme of corner orientations. Thus, a solved cube might be represented as:
+* 8 corner pieces
+* 12 edge pieces
+* 6 center pieces
-(1 2 3 4 5 6 7 8) (0 0 0 0 0 0 0 0)
+Rubik's Revenge: 56 total (mechanical) pieces
-while a cube with corners mixed up might look something like:
+* 8 corner pieces
+* 24 double-edge pieces (12 left-hand, 12 right-hand)
+* 24 center pieces
-(2 1 4 3 8 7 5 6) (1 2 2 0 1 0 2 2)
+However, it is important to note that we are ''not'' trying to find the minimal representation of the Rubik's Cube, we are simply trying to find a ''unique'' representation of a Rubik's Cube. Representing faces requires more information than representing pieces, but it is a lot simpler and accomplishes what we need:
-The difficulty is that one tuple has a single integer per item (no repeats), while the other can have any number per item (with repeats).
+* The 3x3 Rubik's Cube has 9 squares on each face, and 6 faces, for a total of 36 squares.
+* The 4x4 Rubik's Revenge has 16 squares on each face, and 6 faces, for 96 total squares.
-Instead, what we'll do is waste some space, and make the tuple representation longer, to simplify the representation.
+Now, if we were looking for a ''minimal'' representation, we would utilize the fact that some of these squares are innately linked (for example, the three faces representing a corner piece are always positioned in the same way relative to one another, even though they may move relative to the rest of the pieces on the cube).
-Consider a single corner - the white, red, green corner. This corner can be represented using a 3-tuple, with a letter for each face:
+However, we simply want a ''unique'' representation, so we can represent the state of any 3x3 Rubik's Cube using a 36-tuple, or the state of any 4x4 Rubik's Revenge using a 96-tuple.
-(W R G) (G W R) (R G W)
+==Why A Tuple Representation==
-So an alternative representation of the corners is to use a 3-tuple for each corner, with the orientation specified by which of the three-tuples represents the corner.
+Finding a tuple representation enables us to study the properties of various move sequences and understand how the cube works.
-==Specifying Cube State==
+For example, if we repeatedly apply any sequence of moves to a Rubik's Cube, eventually it will return back to the solved state. To predict how many times a sequence must be applied to a cube to return to the solved state, we can use techniques demonstrated by Donald Knuth in Volume 3 of [[AOCP|The Art of Computer Programming]] (see [[AOCP]]) to derive a permutation algebra, factor permutations into cycles, and find the sequence length via the lcm of each cycle length.
-We must specify an order for our tuple to represent the cube state. We define the following arbitrary ordering:
+See also: https://github.com/charlesreid1/rubiks-cycles
-===Specifying Corners===
+Tuple representation: https://github.com/charlesreid1/rubiks-cycles/blob/master/tup.py
-The '''corners''' are labeled by the tuple first. Each corner is represented by three slots, which are the three colors of the cube specified in clockwise order, starting with the upper or downward face. Thus, WRG means the upper face is white, then the face to the bottom right is red, then the face to the bottom left is green.
+=4x4 Rubiks Cube Representation=
-It is easiest to orient the cube as U = WHITE, F = GREEN, R = RED.
-(Note that 6 colors map to 6 integers. We'll define a color map below.)
-===Specifying Centers===
-The centers are specified for each face in the order FRBLUD. Each of the six faces has four slots to specify the colors of the four center squares.
-On each face, the order of the four corners is specified in the order: NW, NE, SE, SW
-===Specifying Dedges===
-The first four dedges we specify are the dedges along the upper face. Each dedge has both colors specified. The upper face U is specified first. Thus, on a solved cube, these dedges would be represented by the tuple WGO WRG WBR WOB.
-The second four dedges we specify are the dedges along the downward face. Again, the color on each of the two faces of each dedge is specified. The downward face D is specified first. On a solved cube, these dedges are represented by YOG YGR YRB YBO.
-The last four dedges connect the FRBL faces. We specify dedges by specifying the two colors of the dedge piece closes to U first, then closest to D. The order of edges proceeds by connecting corners 1 (white-green-orange) and 5 (yellow-orange-green). The first of the four face dedges is between FL or green and orange on the solved cube, so is specified by GOGO. Next dedge is between FR or green and red on the solved cube, so RGRG. And so on.
-===Final Tuple===
-A final tuple representation of a solved cube, therefore, is:
-WGO WRG WBR WOB YOG YGR YRB YGBO GGGG RRRR BBBB OOOO WWWW YYYY WGWG WRWR WBWB WOWO YGYG YRYR YBYB YOYO GOGO RGRG BRBR OBOB
 =Flags=

Rubiks Cube/Tuple: Difference between revisions

From charlesreid1