Rubiks Cube: Computer Simulation
Articles —> Rubiks Cube: Computer Simulation
The Rubik's Cube should need little introduction. The puzzle itself consists of six sides, each with nine cells holding a color, rotations of the sizes allow one to both scramble and solve the puzzle. Introduced in 1974 the puzzle gained worldwide attention for both it difficulty as a puzzle as well as its colorful simplicity.
Modeling the Rubik's Cube computationally allows one to both visualize the cube as well as inspect solutions. At first thought, a graph data structure seemed appropriate to computationally model the Rubik's cube: each cell having four non-diagonal neighbors. However, a graph becomes complex when rotations get involved. An alternative is to use reality as the guide: what better way to model the Rubik's Cube than to model it as a true cube, with each cell having coordinates (and in this case, a surface normal to both differentiate between same coordinate cells on adjacent sides and as well as for 3-dimensional rendering). In this case, I arbitrarily chose the coordinates for each axis as -1, 0, and 1, centering the cube at the x,y,z origin.
The model may become more apparent with some code. Below are two classes written in java. The first class represents a 3-dimensional value (vector, point) that will be used for the location and surface normal. The second class represents a colored cell on the cube, and contains its location, surface normal, and color (here defined as an int)
/** * Simple 3 double value wrapper class that can represent data in three dimensions. * @author G Cope * */ public final class Tuple3d { public final double x; public final double y; public final double z; /** * Constructs a new tuple based upon int values. * @param x * @param y * @param z */ public Tuple3d(int x, int y, int z){ this((double)x, (double)y, (double)z); } /** * Constructs a new Tuple3d. * @param x * @param y * @param z */ public Tuple3d(double x, double y, double z){ this.x = x; this.y = y; this.z = z; } /** * Constructs a new Tuple3d object based upon the parameter. object. * @param p */ public Tuple3d(Tuple3d p){ this(p.x, p.y, p.z); } }
/** * Class used to represent a colored cell on a Rubik's Cube. * @author G Cope * */ public class Cell{ /* * Colors */ public static final int RED = 0; public static final int GREEN = 1; public static final int WHITE = 2; public static final int BLUE = 3; public static final int ORANGE = 4; public static final int YELLOW = 5; private final int color; private Tuple3d location; private Tuple3d normal; /** * Constructs a new cell with location, a surface normal norm, and color. * @param loc * @param norm * @param color one of RED, GREEN, ...ORANGE, YELLOW. */ public Cell(Tuple3d loc, Tuple3d norm, int color){ this.location = loc; this.normal = norm; this.color = color; } /** * Deep copies the parameter node. * @param node */ public Cell(Cell node){ this(new Tuple3d(node.location.x, node.location.y, node.location.z), new Tuple3d(node.normal.x, node.normal.y, node.normal.z), node.color); } /** * Retrieves the color value. * @return */ public int getColor(){ return color; } /** * Sets the location * @param p */ public void setLocation(Tuple3d p){ this.location = p; } /** * Retrieves the location. * @return */ public Tuple3d getLocation(){ return location; } /** * Sets the normal * @param v */ public void setNormal(Tuple3d v){ normal = v; } /** * Retrieves the normal. * @return */ public Tuple3d getNormal(){ return normal; } }
Next there are two goals to generate a cube ready to be played with.
- Construct the Rubik's Cube. This can simply be a solved cube with the appropriate cells of colors, locations, and normals.
- Capability to rotate (or pivot) the sides around the axis. This allows one to solve (or scramble) the cube.
One way in which we can address both of these goals is to construct a way to rotate the cells around an axis. This allows us to build by iteratively generating the same side followed by any necessary rotation into place. It also allows us to make a move in that we can choose all cells that are a part of the move followed by rotation to their next location. The utility methods below provides the math for the rotation around the axis, which the rotateCell method can use to rotate a cell around an axis. Note that in order to maintain our arbitrary x,y,z locations of 1, 0, -1, the methods below round the values into an int - this helps constrain the location values rather than being subject to floating point math errors which - if present - could make determining cell locations inaccurate.
/** * Rotates around the Z axis by radians * @param p1 * @param radians * @return */ public static Tuple3d rotateZAxis(Tuple3d p1, double radians){ int x = (int)Math.round(p1.x * Math.cos(radians) - p1.y * Math.sin(radians)); int y = (int)Math.round(p1.x * Math.sin(radians) + p1.y * Math.cos(radians)); int z = (int)p1.z; return new Tuple3d(x, y, z); } /** * Rotates around the X axis by radians * @param p1 * @param radians * @return */ public static Tuple3d rotateXAxis(Tuple3d p1, double radians){ int x = (int)p1.x; int y = (int)Math.round(p1.y * Math.cos(radians) - p1.z * Math.sin(radians)); int z = (int)Math.round(p1.y * Math.sin(radians) + p1.z * Math.cos(radians)); return new Tuple3d(x, y, z); } /** * Rotates the Tuple3d around the Y axis by radians. * @param p1 * @param radians * @return */ public static Tuple3d rotateYAxis(Tuple3d p1, double radians){ int x = (int)Math.round(p1.z * Math.sin(radians) + p1.x * Math.cos(radians)); int y = (int)p1.y; int z = (int)Math.round(p1.z * Math.cos(radians) - p1.x * Math.sin(radians)); return new Tuple3d(x, y, z); } public static final int X_AXIS = 1; public static final int Y_AXIS = 2; public static final int Z_AXIS = 3; public static void rotateNode(Cell n, int axis, double radians){ switch(axis){ case Rotator.X_AXIS: n.setLocation(rotateXAxis(n.getLocation(), radians)); n.setNormal(rotateXAxis(n.getNormal(), radians)); break; case Rotator.Y_AXIS: n.setLocation(rotateYAxis(n.getLocation(), radians)); n.setNormal(rotateYAxis(n.getNormal(), radians)); break; case Rotator.Z_AXIS: n.setLocation(rotateZAxis(n.getLocation(), radians)); n.setNormal(rotateZAxis(n.getNormal(), radians)); break; } }
Now onto to achieve our two goals above. First, to generate a solved Rubik's Cube we can, for each side, generate cells located at front face locations, then rotate the cells to their respective face of the Cube. The code below loops over each side, constructs the cells at a default location, and proceeds to rotate the cells based upon their final location.
Cell[] cube = new Cell[54]; for ( int i = 0; i < 6; i++ ){ List<Cell> list = new ArrayList<Cell>(); //initialize as front face for ( int j = -1; j <=1; j++ ){ for ( int k = -1; k <= 1; k++ ){ list.add(new Cell(new Tuple3d(j, k, 1), new Tuple3d(0,0,1), i)); } } switch(i){ case 1://bottom for (Cell n : list ){ rotateNode(n, Rotator.X_AXIS, Math.PI / 2); } break; case 2://back for (Cell n : list ){ rotateNode(n, Rotator.X_AXIS, Math.PI ); } break; case 3://top for (Cell n : list ){ rotateNode(n, Rotator.X_AXIS, -Math.PI / 2); } break; case 4://left for (Cell n : list ){ rotateNode(n, Rotator.Y_AXIS, -Math.PI / 2); } break; case 5://right for (Cell n : list ){ rotateNode(n, Rotator.Y_AXIS, Math.PI / 2); } break; } for ( int j = 0; j < 9; j++ ){ cube[i*9 + j] = list.get(j); } }
Our second goal is to tackle side rotations. We first must find each cell that needs to be moved, then rotate around the appropriate axis. For example, assuming we are looking at the front face of the cube (z = 1): to rotate all nodes on the left side pivot up, we can locate the nodes with an x value of -1, and then rotate by 90 degrees (for a sanity check, an assertion is added to verify the correct number of cells is selected).
//get all candidates List<Cell> cells = new ArrayList<Cell>(); for ( Cell n : cube.getCells() ){ if ( n.getLocation().x == -1 ){ cells.add(n); } } assert cells.size() == 21 : "Number to rotate is innacurate " + toString(); for ( Cell n : cells ){ rotateNode(n, X_AXIS, Math.PI / 2); }
A similar technique can be made for each of the other valid moves of the Rubik's cube. All of the code for these moves is beyond the scope of this article, suffice it to say I organized each as its own class implementing an interface - this organization lets me map a constant representing the move to the appropriate class, letting me make the appropriate move simply with a constant value.
Of course, the Rubik's Cube is a visual puzzle, and thus computational representation may be fun and useful to help calculate solutions, a way to visualize the cube is virtually a necessity. Coming up, I visualize the cube in both 2 and 3 dimensions.
Comments
- Pronab Pal - March, 2, 2018
where is Rotator class ? Can I execute the code -could you please share the whole code so that I can run and understand your article better .
Thanks