1.
Introduction
This blog describes two findings related to the structure of the state space graph of the
3×3×3 Rubik cube puzzle.
In addition to
the above, the method of cube representation and the "direction value mappings" are new.
“Rubik cube” here means the 3×3×3 Rubik cube. There are Rubik
cubes of other dimensions but they are not discussed here.
2.
Background
The Rubik cube puzzle has around 4.3×1019
possible states. Finding the optimal sequence of moves to go to the “Goal
state” from a random state is an unsolved problem. (Here the optimality is with
respect to the number of moves in the sequence)
The
Idea: In a graph like the n-dimensional hypercube,
it is easy to find the optimal path from one node to another, however large the
graph may be, since we know the structure
of the graph. Likewise if we know the structure
of the state space Graph of the Rubik cube puzzle, we could find optimal
solutions to any configuration of the Rubik cube. The findings described below are discovered while trying to understand the structure of the
state space graph of the Rubik cube puzzle.
3.
Terminology
State
Space Graph: The set of all states a puzzle can go
into as vertices, and the edges connecting nodes that are one “move” apart,
form the state space graph of a puzzle.
The
Puzzle Finding a sequence of moves to go from a
random state to the Goal state constitutes an instance of the Rubik cube
puzzle.
Vertex
Transitive graph A graph G in which for every pair
of vertices v1, v2, there is some automorphism f: V(G) → V(G) such that f(v1) =
v2.
OR
Informally, no
vertex can be distinguished from any other based on the vertices and edges
surrounding it
OR
No node is
different from any other in terms of distance distribution of nodes.
4.
Cube Description
The Rubik cube is a cube shaped object. The
cube can be seen as a stack of three layers when seen from any of the 6 faces.
Any layer can be rotated in clockwise or anti-clockwise direction while keeping
the other two layers in their positions. When a move is made, the cube changes
its state.
The Rubik cube is composed of 12 edge
cubelets and 8 corner cubelets and 6 centre cubelets. Each edge cubelet
contains 2 faces(colors) and each corner cubelet contains 3 faces(colors). The
centre cubelets contain just one face. The color of the centre cubelet
describes the color of a face. The colors (9 on each face) of the cubelets on
the 6 faces of the Rubik cube describe a state of the Rubik cube. Alternatively
a state of Rubik cube can also be described as in the next section.
In general, the Rubik cubes available in
market have the below six colours:
Blue opposite to green
Pink opposite to red
White/black opposite yellow
5.
Mathematical Representation
Number of Edge cubelets in the Rubik cube
is 12. Each of these can be present in any of the 12 positions. So we can number
the edge cubelets 0 to 11 and the edge positions 0 to 11. In any postion an
edge cubelet can be positioned in 2 ways(directions). These directions can be
numbered 0, and 1.
Number of Corner cubelets in the Rubik cube
is 8. Each of these can be there in any of the 8 positions. So we number the
corner cubelets 0 to 7 and the corner positions 0 to 7. In any position a
corner cubelet can be positioned in 3 ways (directions). These directions can
be numbered 0, 1, and 2.
Position
matrix
Edge cubelet position values 0… 11
Corner cubelet positon values 0… 7
Edge cubelet direction values 0, 1
Corner cubelet direction values 0, 1, 2
A cube state can be declared with the
following data structure.
Struct state{
Int Edge_pos[12];
Int edge_dir [12];
Int corner_pos[8];
Int corner_dir[8];
}
6.
Direction mappings
In the Rubik cube, any two opposite faces
form a layer pair. The six faces of the cube can be divided into 3 layer pairs.
These 3 layer pairs can be numbered 0, 1, and 2.
So we have,
6 faces – 6 layers
3 layer pairs
1.
Moves:
There are 12 moves: each of the 6 layers
can be rotated in two directions. 1) axis of rotation pointing into the cube
and 2)axis of rotation pointing out of the cube
Layer
colors & layer pairs: opposite faces form a
layer pair
Blue-green 0
Yellow-white 1
Red-pink 2
2.
Edge cubelet direction value mapping
When a move is made, the new direction
value of an edge cubelet is obtained by the below method:
Direction value 0 changes to 1 upon a move
Direction value 1 changes to 0 upon a move
3.
Corner cubelet direction value
mapping
When a move is made we can find the new
direction value of a corner cubelet using the below mapping:
(current_corner_dir_value,
current_layer_pair of the move) ->
new_corner_dir_value
(0, 0)->0 (1, 0)->2 (2,0)->1
(0, 1)->2 (1, 1)->1 (2,1)->0
(0, 2)->1 (1, 2)->0 (2,2)->2
This mapping too is an important new
finding.
7.
More Cube Mathematics
1)
The Difference function
The "difference" of two Rubik
cube configurations s1, s2 can be defined to be the config "diff"
which has the same relative placement of cubelets(relative to the Goal node) in
it, as s2 is relative to s1.
OR
The sequence of moves needed to go from s2
to s1 is same as the sequence of moves needed to go from "diff" to
Goal node.
A program was written for this, and was
found to give correct results.
2)
The mid-point concept*
The author has also contemplated the
concept of finding a configuration/node that is at equal distance from two
given configurations*(not yet finalized).
8.
Structure of the state space
graph
In the Rubik cube, from any state, 12 moves
are possible. These 12 moves correspond to: each of the 6 layers can be rotated
by 90 degrees in two directions – (1) axis of rotation pointing into the cube
and (2) axis of rotation pointing out of the cube.
Because there are 12 moves possible from
any state, the degree of the graph is 12(viz 12 neighbors for any state or
node) (On the other hand we can see this as 12 egdes connected to each vertex).
The state space graph is a vertex transitive graph, because no node is
different from any other in terms of distance distribution of nodes.
Total number of vertices in the graph is
understood to be: (12! × 212 × 8! × 38) ÷ (12)
1)
Finding_1- The State Space
Graph Contains 4-d hypercubes as elements.
When we move only a pair of opposite faces(layers)
in the cube, while keeping the middle face(layer) in its position, we traverse
16 states. These 16 states form a 4-d hyper cube. And since there are 3 layer
pairs, we see three 4-d hypercubes projecting out of each node in the graph.
Every node is connected to three 4-d
hypercubes. No two of these hypercubes have more than one node in common. These
three hypercubes can be associated to the three layer pairs as pink-red
hypercube, yellow-white hypercube and blue-green hypercube.
2)
Finding_2 - The State Space
Graph Contains “cubes” of 4-d hypercubes
In a 4-d hypercube each node has exactly
one farthest node (i.e. node at distance 4). So from a node in the graph, go to
the farthest nodes in the three hypercubes connected to it, from those three
nodes do the same process again. When we do this we see that we traverse a “cube”
of 4-d hyper cubes i.e., each “edge” of the “cube” is a 4-d hypercube.
9.
Conclusion
This is not a complete solution in itself,
but possibly a step forward to understand the structure of the graph. The
ultimate goal would be to understand the structure of the state space Graph
such that a program (based on the structure of the Graph) running on a PC (the
intention here is that our program should be efficient enough to run on a
normal PC and give the result in reasonable amount of time e.g an hour in the
worst case; and not require a super computer) gives out the optimal solutions
to a random instance of the Rubik cube puzzle.
Probably the next interesting thing would
be to find how the “cubes” are connected.
10.
Appendix A: A 4-d Hypercube
11.
Appendix D: Total Possible
States
4 different programs can be written to
confirm that the total number of nodes in the state space graph is : (12! × 212
× 8! × 38) ÷ (12)
These programs are basically exhaustive
generation of: 1) edge cube let position values 2) edge cubelet direction
values 3) corner cubelet position values 4) corner cubelet direction values
Comments
Post a Comment