The Rubik’s cube is a magical toy with a simple structure and endless variations. So how to simulate the endless transformation of the Rubik’s cube in a universal browser, and how to restore it? Let’s take a step-by-step look.
Rubik’s Cube abstraction
Those who have disassembled the Rubik’s cube may know that the internal structure of the rubik’s cube in reality contains a central axis, springs, screws and other mechanical devices. But when we just want to “simulate” it, we just need to grasp its most remarkable property — a 3x3x3 set of cubes:
The basic concept
The figure above illustrates the basic mental model of the Rubik’s cube. But it’s not enough to know that the pieces that make up a Rubik’s cube aren’t randomly placed. There are subtle differences between them:
- Blocks located at each corner of the rubik’s cube are called corner blocks, and each corner block has 3 colors. A cube has eight corners, so a Rubik’s cube also has eight corners.
- The blocks located on each edge of the Rubik’s cube are called edge blocks, and each edge block has 2 colors. A cube has 12 edges, so a Rubik’s cube also has 12 edges.
- The cube in the center of each surface is called the center block, each center block has only one color. A cube has six sides, so a Rubik’s cube also has six central blocks.
- The block in the center of the cube has no color and is of no practical use during rendering and restoration, so we can ignore this block.
If you add up the number of blocks, you get exactly 3^3 = 27 blocks. The only manipulation (or transformation) you can use with these blocks is rotation on different surfaces. So, how do we identify a rotation operation?
Imagine holding a Rubik’s cube “straight” in your hand. We define the side facing you as Front and the side facing away as Back. Similarly, we have Left/Right/Upper/Down to identify the rest of the faces. When you rotate a side, we use the shorthand for that side (F/B/L/R/U/D) to identify a 90 degree clockwise rotation on that side. A counterclockwise rotation is denoted by a notation like F’/U’. If you rotate it 180 degrees, you can write it in terms of R2 over U2. For the 5 operations in the figure below, if we specify the blue side as Front, the rotation sequence is F’ R’ L’ B’ F’ :
That’s all you need to know about the basic structure and transformation of the Cube. Next we need to consider this question: how to design a data structure to store the state of the Rubik’s cube and use a programming language to implement a rotation transformation?
The data structure
For those of you who like “object-oriented” abstractions, you can quickly imagine that you can design a Block base class for each Block, and then use classes like CornerBlock and EdgeBlock to abstract corner blocks and corner blocks. In each CornerBlock instance, you can store references to the CornerBlock to its three adjacent edges… Such a Cube object only needs to hold a reference to the central block to store the entire Cube based on the adjacency properties of each block instance.
The above implementation is very similar to a linked list in that it can implement the “given a block, find its adjacent blocks” operation O(1), but it is not difficult to find that it requires O(N) complexity to implement a “where is the block at a location” lookup operation, and the rotation operation based on it is not very intuitive. In contrast, a more “violent” approach is quite practical: simply create an array of 27 lengths and store the color information of each block.
Why is that possible? We know that arrays have O(1) time complexity for subscription-based access. If we locate each block of the rubik’s cube in a three-dimensional coordinate system, the spatial coordinates of each block can be uniquely mapped to the subscripts of the array. Further, we can set x, y and z to -1, 0 and 1 respectively to express the possible positions of a block in its direction. In this case, for example, a rotation of U defined above is exactly the rotation of all blocks with the Y-axis coordinate value of 1. This good property is very conducive to the realization of the rubik’s cube transformation operation.
Rotation transformation
After the agreement of the data structure, how do we achieve a rotation transformation of the Rubik’s cube? Maybe some of you will directly relate this operation to a fourth order transformation matrix in three dimensions. But by noting that each rotation is an integer multiple of 90 degrees, we can use mathematical properties to greatly simplify this operation:
When rotated 90 degrees, each corner block on the rotation plane rotates to the position of the “next” corner block on the face, as does the edge block. Thus, we can easily “move” a block to its new position by simply looping alternately at the “next” position of each block. But that’s not enough: for each block in its new position, it needs to “spin” the colors of its six faces once more to point it in the right direction. This is also an alternate assignment. Thus, a three-dimensional rotation operation around the center of a surface is decomposed into a translation operation and a rotation operation around the center of each block. With just over 30 lines of code, we can implement the core transformation mechanism of the Rubik’s cube:
rotate (center, clockwise = true) {
const axis = center.indexOf(1) + center.indexOf(- 1) + 1
// Fix y direction in right-handed coordinate system.
clockwise = center[1]! = =0? ! clockwise : clockwise// Fix directions whose faces are opposite to axis.
clockwise = center[axis] === 1? clockwise : ! clockwiselet cs = [[1.1], [1.- 1], [- 1.- 1], [- 1.1]] // corner coords
let es = [[0.1], [1.0], [0.- 1], [- 1.0]] // edge coords
const prepareCoord = coord= > coord.splice(axis, 0, center[axis])
cs.forEach(prepareCoord); es.forEach(prepareCoord)
if(! clockwise) { cs = cs.reverse(); es = es.reverse() }// Move each block to its new position
const rotateBlocks = ([a, b, c, d]) = > {
const set = (a, b) = > { for (let i = 0; i < 6; i++) a[i] = b[i] }
const tmp = []; set(tmp, a); set(a, d); set(d, c); set(c, b); set(b, tmp)
}
const colorsAt = coord= > this.getBlock(coord).colors
rotateBlocks(cs.map(colorsAt)); rotateBlocks(es.map(colorsAt))
// Adjust the spin orientation of each block
const swap = [
[[F, U, B, D], [L, F, R, B], [L, U, R, D]],
[[F, D, B, U], [F, L, B, R], [D, R, U, L]]
][clockwise ? 0 : 1][axis]
const rotateFaces = coord= > {
constblock = colorsAt(coord) ; [block[swap[1]], block[swap[2]], block[swap[3]], block[swap[0]]] =
[block[swap[0]], block[swap[1]], block[swap[2]], block[swap[3]]]
}
cs.forEach(rotateFaces); es.forEach(rotateFaces)
return this
}
Copy the codeThis implementation should not be too inefficient: in my browser, the above code supports 300,000 rotation transformations per second. Why do we care about performance here? In the Rubik’s cube scenario, there is a very different aspect, namely the validity and verification of states.
Those familiar with rubik’s cubes should know that it is not always possible to paint each cube in a different color. In the common business development world, data validity and validation can often be guaranteed through a type system. But for a scrambled Rubik’s cube, ensuring its solvability is a difficult mathematical problem. Therefore, when we save the rubik’s cube state, only by saving all the transformation steps from the initial state of the same six colors to the current state, can we ensure that the state must be solvable. Thus, there is an O(N) correlation between the cost of deserializing a Rubik’s cube state and the number of steps. Fortunately, a real rubik’s cube state is usually less than 100 moves, so the cost of sacrificing time complexity for data validity should be worth it. In addition, time travel between any state of the Rubik’s cube can be achieved very easily in this way: from the initial state to any historical state, a series of rotation diff operations between them can be superimposed. It’s a very solid mental model.
There is a special feature in the above implementation: when the coordinate axis is y, we perform an inverse operation for the rotation direction. This does not accord with intuitive at first glance, but behind it is coordinate system defined by the question: if you ever derived each block in clockwise transformation in the next place, then in the right hand coordinate system used in the high school textbooks and WebGL, y axis rotate when each piece of the next position, the exchange order with x axis and z axis is the opposite. On the contrary, in DirectX’s left hand coordinate system, the rotation can be exactly the same as the orientation of the coordinate system. As a simple coder, I do not know whether the symmetry behind this contains any profound mathematical principles, and hope that the mathematics leaders to solve their doubts.
So far, we have basically completed the design of the abstract and transform algorithm of the rubik’s cube state. But I believe many students may be more curious about this question: in the browser environment, how should we render the Rubik’s cube? Let’s take a look.
Rubik’s Cube rendering
In the world of the browser, where countless two-dimensional rectangles are used as typesetting primitions, rendering a three-dimensional object like a Rubik’s cube is not a matter of looking up a document and writing a few lines of glue code. Fortunately, we have WebGL and other 3D graphics libraries at our command (of course, those who are familiar with the style should be able to use CSS to render the Rubik’s cube, but my CSS is not very good).
WebGL rendering basics
Due to the simplicity of the rubik’s Cube mind model, rendering it does not require advanced graphics features such as textures, lighting and shadows, only the most basic geometric drawing features are sufficient. Because of this, I only use the fully native WebGL API to draw rubik’s cube here. Broadly speaking, the steps required to render a set of cubes such as a Rubik’s cube are as follows:
- Initializing shaders (compiling programs for GPU execution)
- Passing vertex and color data to buffer (operating on video memory)
- Set the Perspective matrix and mode-to-view transformation matrix for observation (passing variables to the GPU)
- call
drawElements或drawArrayTo render a frame
In the previous article, we designed the data structure using an array of length 27 to store a series of blocks from [-1, -1, -1] to [1, 1, 1]. In a triple for loop, the logic for drawing each block onto the screen one by one would look something like this:
It’s important to note that closer to the underlying code is not necessarily faster. For example, in my earliest implementation, I rendered 27 small blocks directly by looping through a 3D cube routine from (or copied from) MDN. For 27 cubes with fewer than a thousand vertices, the CPU usage for 60 frames of animation could run full. After locating, it is found that repeated interaction between CPU and GPU is a big no-no. Data transfer from CPU to GPU and the final call to GPU drawing API have high fixed overhead. Generally we need to limit the number of Draw calls to 20 in a frame, and using 27 Draw calls for 27 cubes is clearly an anti-pattern. After modifying the code to batch pass in all vertices at once and call drawElements once, you can achieve smooth 60-frame animation 🙂
Rotation animation implementation
After the basic rendering mechanism is implemented, the overall rotation effect of the Rubik’s cube can be realized by matrix multiplication of the mode-visual matrix. The mode-view matrix will be computed for each vertex in parallel by the GPU in the vertex shader to obtain the gl_Position position after the vertex transformation. But for the rotation of a single face, we chose to compute the vertex position in the CPU and pass it into the vertex buffer. This is directly related to the realization principle of rubik’s Cube rotation animation:
- In the process of rotation of a certain surface, the data model of rubik’s cube does not change, but only changes the position of affected vertices.
- At the end of the rotation, we call what we implemented above
rotateAPI to “instantaneously rotate” the cube’s data model and then draw one more frame.
We first need to design the Render API to render a frame. Considering that the rubik’s cube may rotate a certain surface to a certain extent during drawing, the stateless rendering API interface looks like:
render (rX = 0, rY = 0, moveFace = null, moveAngle = 0) {
if (!this.gl) throw new Error('Missing WebGL context! ')
this.buffer = getBuffer(this.gl, this.blocks, moveFace, moveAngle)
renderFrame(this.gl, this.programInfo, this.buffer, rX, rY)
}
Copy the codeFor rotation of a single face, we can use the browser’s requestAnimationFrame API for basic timing control. A rotation that calls animate returns a Promise to resolve at the end of a single rotation, which is implemented as follows:
animate (move = null, duration = 500) {
if (move && move.length === 0) return Promise.resolve()
if(! move ||this.__ANIMATING) throw new Error('Unable to animate! ')
this.__ANIMATING = true
let k = move.includes("'")?1 : - 1
if (/B|D|L/.test(move)) k = k * - 1
const beginTime = +new Date(a)return new Promise((resolve, reject) = > {
const tick = (a)= > {
const diff = +new Date() - beginTime
const percentage = diff / duration
const face = move.replace("'".' ')
if (percentage < 1) {
this.render(this.rX, this.rY, face, 90 * percentage * k)
window.requestAnimationFrame(tick)
} else {
this.move(move)
this.render(this.rX, this.rY, null.0)
this.__ANIMATING = false
resolve()
}
}
window.requestAnimationFrame(tick)
})
}
Copy the codeContinuous rotation realization
After a single rotation is implemented, how do you support consecutive multiple rotations? Spirit can be lazy, lazy idea, I have been no changes made to the above function logic of naturalization transformation, only need to add the following lines at the entrance of the function, can make support incoming array as a parameter to recursively calls itself, and in the incoming continuous animation array length to 1 as exports of recursion, can easily realize the continuous animation effects:
if (Array.isArray(move) && move.length > 1) {
const lastMove = move.pop()
// Return the recursive Promise
return this.animate(move).then((a)= > this.animate(lastMove))
} else if (move.length === 1) move = move[0] // Continue with existing logic
Copy the codeAt this point, an experiencable Rubik’s cube is basically running in a browser. But that’s not our final goal: How do we automatically undo a Rubik’s cube?
Reduction of the Rubik’s cube
The reduction algorithm of the Rubik’s cube has been deeply studied in the academic circle. The computer can solve the Rubik’s cube in any state within 20 steps, and there are mature wheels that can be directly called. However, as a former Rubik’s cube amateur (in high school), the author is more concerned with “how to simulate my own operation to restore the Rubik’s cube”, so here we are going to introduce the simple and easy to understand CFOP layer first algorithm.
Before we begin, it is important to emphasize a concept mentioned earlier: the relative positions of the central blocks of the Rubik’s cube do not change during rotation. The diagram below:
Therefore, when the Rubik’s cube rotates, we only need to pay attention to whether the corner block and edge block are in the same position. In THE CFOP layer preemption method, the steps of relocating all corner blocks and edge blocks are divided into four successive steps:
- Restore the bottom four edges to create a “cross”.
- Group restore all corner blocks and edge blocks of bottom and second layer.
- Adjust the top block orientation to ensure that the top surface of the same color.
- Adjust the order of the top block to complete the whole solution.
Let’s take a look at what happened at each step.
The underlying cross
This step is arguably the simplest and most difficult. Our goal here is to restore the four bottom edges like this:
For a completely scrambled Rubik’s cube, each target edge block may appear in either position in two different orientations. Why are there two orientations? See the picture below:
This is the simplest case, in which a direct R2 rotation can bring the red and white edges back into place. But it’s also perfectly legal to:
In this case, due to the different orientation of the edge block, the required steps are completely different. In general, however, there is a limit to the number of possible locations of the edges needed to form a cross. After disassembling and classifying all possible scenarios, it is not difficult to use greedy strategies to match:
- Each time you find an edge block needed to form a cross, work out a series of steps to move it to the target position.
- On the premise of not affecting other cross edge block, it is put back to its position, and then the next edge block is searched.
This simplest strategy is very similar to the algorithm used in parsing with 1 forward symbol, but there is no need to backtrack. The implementation mechanism can be abstracted as follows:
solveCross () {
const clonedCube = new Cube(null.this.cube.moves)
const moveSteps = []
while (true) {
const lostEdgeCoords = findCrossCoords(clonedCube)
if(! lostEdgeCoords.length)break
moveSteps.push(solveCrossEdge(clonedCube, lostEdgeCoords[0))}return moveSteps
}
Copy the codeThe implementation principle is not complicated, and the cost is that too small local optimization leads to more redundant steps. If two or more edge blocks are observed at the same time and put together, the efficiency is obviously improved (and the difficulty is also increased). By comparison, a top rubik’s cube player can cross in seven steps, but this algorithm takes around 20 — but that’s the point, so don’t be too harsh.
At the bottom of the two layers
The goal here is to complete the return of all blocks in the bottom two layers, based on the completion of the bottom cross. Our goal is to achieve a state like this:
In this step, we use the concepts of Slot and Pair as the basic elements of the restore. An edge and an Angle between adjacent crosses form a Slot, and the two target blocks corresponding to them are called a Pair. In this step, we only need to repeat four times to put the Pair into Slot. The simplest operation might look something like this:
The image above puts the top Pair into the blue and red Slot. In this step, each edge block and corner block has a different position and orientation, similar to the previous case for solving the cross. If they are all at the top level, then we can use existing matching rules to implement matching; If they are in other slots, we recursively perform the “unwinding pairs from other slots” algorithm until the pairs are all at the top level.
The reduction algorithm for this step is very similar to the steps below, which are described later.
Top color and top order
After completing the reduction of the first two layers, the last thing we need to deal with is the top 8 edge blocks and corner blocks. The first step is the same color of the top surface. Adjust each block to the correct direction to achieve the same color of the top surface (white is generally used as the bottom surface, and yellow is the top surface according to the convention) :
Then there is the adjustment of the top order. In this step, on the premise of not changing the orientation of edges and angles, change their arrangement order, and finally complete the restoration of the whole Rubik’s cube:
There are a lot of rubik’s cube formula rules available for matching in the reduction steps from the first two layers to the top layer. How do you apply these ready-made rules to a reduction algorithm? We can use them in a rules-driven way.
Rule-driven design
Those of you who know compilation know that parsing can be done by writing a series of syntax rules. We also have a lot of rules to use in rubik’s Cube. The matching part of a rule might look something like this:
In the process of the same color of the top surface, the top surface that meets the above “pattern” can be restored by the steps of U L U ‘r ‘u L ‘u ‘r. Similarly, when restoring the top-level order, the rules match like this:
The top-level state satisfying this rule can be solved by the steps defined by the rule: R2 U’ R’ U’ R U R U’ R. In this way, the logic of the rule can be completely decoupled from the code logic into configurable JSON-formatted data just by matching the rule and performing the operation. A rule format used to restore the first two layers looks like this:
{
match: { [E]: topEdge(COLOR_F, E), [SE]: SE_D_AS_F },
moves: "U (R U' R')"
}
Copy the codeThe top-level rule format of the same color is as follows:
{
match: { [NW]: L, [NE]: R, [SE]: R, [SW]: L },
moves: "R U R' U R U' R' U R U U R'"
}
Copy the codeThe regular format of the top order is as follows:
{
match: { [N]: W, [W]: [E], [E]: N },
moves: "R R U' R' U' R U R U R U' R"
}
Copy the codeNW/E/SE here is the author’s implementation based on the nine-grid, east, west, north and south orientation of the shorthand. After the automatic matching and application of rules are realized, the implementation of the last three steps in CFOP is basically the same, and the main work is focused on some rotation-related mapping processing.
Self-testing of rules
There are hundreds of rules that need to be matched throughout the restore process. With so many rules, how do you make sure they are correct? In TDD test-driven development, developers need to write a variety of complex test cases to achieve coverage of code logic. But in the rubik’s cube realm, I discovered a much more elegant property: any rule itself is its own test case! Like this rule:
{
match: { [N]: W, [W]: [E], [E]: N },
moves: "R R U' R' U' R U R U R U' R"
}
Copy the codeSimply enter the original state of the rubik’s cube in reverse order for each of the moves steps to verify that the rules match and that the Rubik’s cube can be restored based on that rule. This property makes it easy to write simple code like the following that automatically verifies the correctness of each input rule:
const flip = moves= > moves.map(x= > x.length > 1 ? x[0] : x + "'").reverse()
OLL.forEach(rule= > {
const rMoves = flip(rule.moves)
const cube = new Cube(null, rMoves)
if (
matchOrientationRule(cube, rule) &&
isOrientationSolved(cube.move(rule.moves))
) {
console.log('OLL test pass', rule.id)
} else console.error('Error OLL rule match', rule.id)
})
Copy the codeOn the basis of this self-testing rule matching algorithm, all steps of solving the rubik’s cube are thus calculated 🙂
Results and postscript
After more than half a month of spare time, the author realized a very small rubik’s cube solution simulator Freecube. It supports the rendering and solving of the third-order Rubik’s cube state step by step, and also provides the API of rotation and solving for reuse. Because it doesn’t use any third party dependencies and uses all sorts of lean “tricks”, it is kept within 10KB of compression. Welcome to GitHub XD
Freecube was created in many places: cafes, bullet trains, buses and even dinner tables. Even in situations where you can’t write code, you can use tablet writing to design it. It was inspired by @Youngdro’s amazing guitar chord algorithm blog post, plus thanks to the guru’s Pointers and someone’s XD review of the README document