To describe a chess game state, you don’t need to mention every chess piece’s details. Essentially, a chess piece is just a symbol. Ignoring appearance detail helps us to grab the game gist. Till now, a popular way to represent a Rubik’s cube state is the facelets expanding graph, like this:
By this way, you can’t tell which facelets are adjacent each other straightway, also it’s hard to imagine what the cube will change into after a twist applied. That because it comes from the appearance, but not the essential. Furtherly, as my preivous blog wrote, Rubik’s Cube solver programs who construct cube state from facelet color is clumsy. Rubik’s Cube is a game about cubes’s rotation and permutation (but not painting color), matrix is the most proper math tool here.
However, the fact revealed by this method is not easy to see through, and that is just what I will tell you in this blog.
Cube orientation representation
Let’s begin with a simple case, the 1-order Rubik’s cube, i.e. a single cube. How to restore a rotated cube to the original orientation, in a shorttest way? That’s just Cube Rotation Algebra’s topic. Now let’s symbolize them in a new way.
Recently, I found 2 lucky things, this is the first:
You will be familiar with this figure if you have read Cube Rotation Algebra. The lucky is that we have exact 24 modern Greek letters in total coincidentally.
I have explained cube rotation algebra in the preivous blog in details, now I just show you what the relationship looks like between Greek letters and colored cubes.
Mathematically, they can be defined in quaternions:
$$ \begin{aligned} & \alpha = 1 \\ & \beta = i \\ & \gamma = j \\ & \delta = k \\ & \epsilon = \sqrt{i} = \frac{\sqrt{2}}{2} + \frac{\sqrt{2}}{2} i \\ & … \\ & \omega = i\sqrt[-]{k} = \frac{\sqrt{2}}{2} i - \frac{\sqrt{2}}{2} j \end{aligned} $$
These 24 elements make up a group $O_{h}$, that means they are closed for multiplication, and the multiplication satisfys the associative law.
And this is the group multiplication table:
$ \begin{matrix} \times & \boldsymbol{\alpha} & \boldsymbol{\beta} & \boldsymbol{\gamma} & \boldsymbol{\delta} & \boldsymbol{\epsilon} & \boldsymbol{\zeta} & \boldsymbol{\eta} & \boldsymbol{\theta} & \boldsymbol{\iota} & \boldsymbol{\kappa} & \boldsymbol{\lambda} & \boldsymbol{\mu} & \boldsymbol{\nu} & \boldsymbol{\xi} & \boldsymbol{\omicron} & \boldsymbol{\pi} & \boldsymbol{\rho} & \boldsymbol{\sigma} & \boldsymbol{\tau} & \boldsymbol{\upsilon} & \boldsymbol{\phi} & \boldsymbol{\chi} & \boldsymbol{\psi} & \boldsymbol{\omega} \\ \boldsymbol{\alpha} & \alpha & \beta & \gamma & \delta & \epsilon & \zeta & \eta & \theta & \iota & \kappa & \lambda & \mu & \nu & \xi & \omicron & \pi & \rho & \sigma & \tau & \upsilon & \phi & \chi & \psi & \omega \\ \boldsymbol{\beta} & \beta & \alpha & \delta & \gamma & \theta & \chi & \omega & \epsilon & \phi & \psi & \pi & \omicron & \sigma & \rho & \mu & \lambda & \xi & \nu & \upsilon & \tau & \iota & \zeta & \kappa & \eta \\ \boldsymbol{\gamma} & \gamma & \delta & \alpha & \beta & \tau & \iota & \psi & \upsilon & \zeta & \omega & \mu & \lambda & \rho & \sigma & \pi & \omicron & \nu & \xi & \epsilon & \theta & \chi & \phi & \eta & \kappa \\ \boldsymbol{\delta} & \delta & \gamma & \beta & \alpha & \upsilon & \phi & \kappa & \tau & \chi & \eta & \omicron & \pi & \xi & \nu & \lambda & \mu & \sigma & \rho & \theta & \epsilon & \zeta & \iota & \omega & \psi \\ \boldsymbol{\epsilon} & \epsilon & \theta & \upsilon & \tau & \beta & \xi & \lambda & \alpha & \nu & \mu & \omega & \psi & \phi & \chi & \kappa & \eta & \zeta & \iota & \gamma & \delta & \sigma & \rho & \omicron & \pi \\ \boldsymbol{\zeta} & \zeta & \phi & \iota & \chi & \lambda & \gamma & \rho & \omicron & \alpha & \xi & \tau & \epsilon & \eta & \omega & \upsilon & \theta & \psi & \kappa & \mu & \pi & \delta & \beta & \nu & \sigma \\ \boldsymbol{\eta} & \eta & \psi & \omega & \kappa & \nu & \lambda & \delta & \rho & \pi & \alpha & \phi & \iota & \upsilon & \epsilon & \zeta & \chi & \tau & \theta & \sigma & \xi & \omicron & \mu & \gamma & \beta \\ \boldsymbol{\theta} & \theta & \epsilon & \tau & \upsilon & \alpha & \rho & \pi & \beta & \sigma & \omicron & \eta & \kappa & \iota & \zeta & \psi & \omega & \chi & \phi & \delta & \gamma & \nu & \xi & \mu & \lambda \\ \boldsymbol{\iota} & \iota & \chi & \zeta & \phi & \mu & \alpha & \nu & \pi & \gamma & \sigma & \epsilon & \tau & \psi & \kappa & \theta & \upsilon & \eta & \omega & \lambda & \omicron & \beta & \delta & \rho & \xi \\ \boldsymbol{\kappa} & \kappa & \omega & \psi & \eta & \xi & \omicron & \alpha & \sigma & \mu & \delta & \zeta & \chi & \epsilon & \upsilon & \phi & \iota & \theta & \tau & \rho & \nu & \lambda & \pi & \beta & \gamma \\ \boldsymbol{\lambda} & \lambda & \omicron & \pi & \mu & \phi & \omega & \tau & \zeta & \eta & \epsilon & \sigma & \nu & \delta & \beta & \xi & \rho & \gamma & \alpha & \iota & \chi & \kappa & \psi & \upsilon & \theta \\ \boldsymbol{\mu} & \mu & \pi & \omicron & \lambda & \chi & \kappa & \epsilon & \iota & \psi & \tau & \xi & \rho & \beta & \delta & \sigma & \nu & \alpha & \gamma & \zeta & \phi & \omega & \eta & \theta & \upsilon \\ \boldsymbol{\nu} & \nu & \rho & \xi & \sigma & \psi & \epsilon & \phi & \eta & \upsilon & \iota & \beta & \gamma & \omicron & \mu & \alpha & \delta & \lambda & \pi & \omega & \kappa & \theta & \tau & \zeta & \chi \\ \boldsymbol{\xi} & \xi & \sigma & \nu & \rho & \omega & \upsilon & \zeta & \kappa & \epsilon & \chi & \gamma & \beta & \lambda & \pi & \delta & \alpha & \omicron & \mu & \psi & \eta & \tau & \theta & \phi & \iota \\ \boldsymbol{\omicron} & \omicron & \lambda & \mu & \pi & \zeta & \psi & \theta & \phi & \kappa & \upsilon & \rho & \xi & \alpha & \gamma & \nu & \sigma & \beta & \delta & \chi & \iota & \eta & \omega & \epsilon & \tau \\ \boldsymbol{\pi} & \pi & \mu & \lambda & \omicron & \iota & \eta & \upsilon & \chi & \omega & \theta & \nu & \sigma & \gamma & \alpha & \rho & \xi & \delta & \beta & \phi & \zeta & \psi & \kappa & \tau & \epsilon \\ \boldsymbol{\rho} & \rho & \nu & \sigma & \xi & \eta & \tau & \chi & \psi & \theta & \zeta & \delta & \alpha & \pi & \lambda & \gamma & \beta & \mu & \omicron & \kappa & \omega & \upsilon & \epsilon & \iota & \phi \\ \boldsymbol{\sigma} & \sigma & \xi & \rho & \nu & \kappa & \theta & \iota & \omega & \tau & \phi & \alpha & \delta & \mu & \omicron & \beta & \gamma & \pi & \lambda & \eta & \psi & \epsilon & \upsilon & \chi & \zeta \\ \boldsymbol{\tau} & \tau & \upsilon & \theta & \epsilon & \delta & \sigma & \mu & \gamma & \rho & \lambda & \kappa & \eta & \chi & \phi & \omega & \psi & \iota & \zeta & \alpha & \beta & \xi & \nu & \pi & \omicron \\ \boldsymbol{\upsilon} & \upsilon & \tau & \epsilon & \theta & \gamma & \nu & \omicron & \delta & \xi & \pi & \psi & \omega & \zeta & \iota & \eta & \kappa & \phi & \chi & \beta & \alpha & \rho & \sigma & \lambda & \mu \\ \boldsymbol{\phi} & \phi & \zeta & \chi & \iota & \omicron & \beta & \sigma & \lambda & \delta & \nu & \theta & \upsilon & \kappa & \psi & \epsilon & \tau & \omega & \eta & \pi & \mu & \alpha & \gamma & \xi & \rho \\ \boldsymbol{\chi} & \chi & \iota & \phi & \zeta & \pi & \delta & \xi & \mu & \beta & \rho & \upsilon & \theta & \omega & \eta & \tau & \epsilon & \kappa & \psi & \omicron & \lambda & \gamma & \alpha & \sigma & \nu \\ \boldsymbol{\psi} & \psi & \eta & \kappa & \omega & \rho & \mu & \beta & \nu & \omicron & \gamma & \chi & \zeta & \theta & \tau & \iota & \phi & \epsilon & \upsilon & \xi & \sigma & \pi & \lambda & \alpha & \delta \\ \boldsymbol{\omega} & \omega & \kappa & \eta & \psi & \sigma & \pi & \gamma & \xi & \lambda & \beta & \iota & \phi & \tau & \theta & \chi & \zeta & \upsilon & \epsilon & \nu & \rho & \mu & \omicron & \delta & \alpha \end{matrix} $
This is the multiplication visualization:
Cubies’ position representation
In 3-order Rubik’s cube, we have $3^3-1=26$ cubies. And this is the second lucky thing: there are 26 Latin letters in total. So we can labeled 26 cubie positions by A-Z. It looks like this:
Mathematically, we define 26 one-hot vectors:
$$ \boldsymbol{A} = (\mathbf{1}, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0) \\ \boldsymbol{B} = (0, \mathbf{1}, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0) \\ \boldsymbol{C} = (0, 0, \mathbf{1}, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0) \\ … \\ \boldsymbol{Z} = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, \mathbf{1}) $$
This form is convenient for constructing matrices, e.g. a 26×26 identity matrix can be represented as:
$$ \begin{bmatrix} \boldsymbol{A}^T & \boldsymbol{B}^T & \boldsymbol{C}^T & … & \boldsymbol{X}^T & \boldsymbol{Y}^T & \boldsymbol{Z}^T \end{bmatrix}^T $$
Cube rotation and position permutation
Rotation causes displacement, it’s a kind of linear transformation. We can see this clearly in matrix. Take this simple example firstly:
We have 4 (2×2) boxes labeled by red A B C D, and we have 4 fixed cells labeled by black A B C D.
Before and after a 90° rotation, we record boxes’ position in a 4×4 table:
|
⇨ |
|
So this is the matrix’s meaning, every row tells us which cell the box is at.
$$ \alpha \begin{bmatrix} 1 & & & \\ & 1 & & \\ & & 1 & \\ & & &1 \end{bmatrix} \to \eta \begin{bmatrix} & 1 & & \\ & & & 1 \\ 1 & & & \\ & & 1 & \end{bmatrix} = \begin{bmatrix} & \eta & & \\ & & & \eta \\ \eta & & & \\ & & \eta & \end{bmatrix} $$
And plused an orientation scalar in Greek letters. (Why η? Try to look up what η stands for in the 24 knights figure.)
Now let’s extend 2×2 into 26×26:
For the matrix you see above, I arranged the cubies’ order as this:
A state matrix can be decomposed into 2 parts: orientations and position permutation. And position permutation is determined by orientations, so to present a Rubik’s cube state we only need to record a vector of orientation symbols. Mathematically, we have a state vector:
$$ S=o_i | _{i=1,…,26} $$
while
$$ o_i \in \left \{ \alpha, \beta, \gamma, …, \omega \right \} $$
then the state matrix is:
$$ mat(S)=diag(S) \cdot displace(o_i, P_i)^T|_{i=1,…,26} $$
$$ P_i = \boldsymbol{A}, \boldsymbol{B}, \boldsymbol{C}, …, \boldsymbol{Z} |_{\text{when } i=1,…,26} $$
while diag stands for diagonal matrix, displace is a position mapping by a specific orientation, from a one-hot position vector to another. This is the dispacement table:
$$ \begin{matrix} \text{displace} & \alpha & \beta & \gamma & … \\ \color{red} A & \boldsymbol{A} & \boldsymbol{G} & \boldsymbol{F} & … \\ \color{red} B & \boldsymbol{B} & \boldsymbol{H} & \boldsymbol{E} & … \\ \color{red} C & \boldsymbol{C} & \boldsymbol{E} & \boldsymbol{H} & … \\ … & & & & \end{matrix} $$
The whole table is 26×24, what shows here is a part, and you can imagine the rest.
Let’s take the top matrix in this blog (the tetris pattern) as an example:
$ \begin{aligned} & mat(\omicron, \lambda, \pi, \mu, \omicron, \lambda, \pi, \mu, \lambda, \omicron, \omicron, \lambda, \pi, \mu, \pi, \mu, \omicron, \mu, \lambda, \pi, \eta, \kappa, \iota, \zeta, \alpha, \alpha) \\ = & diag(\omicron, \lambda, \pi, \mu, \omicron, \lambda, \pi, \mu, \lambda, \omicron, \omicron, \lambda, \pi, \mu, \pi, \mu, \omicron, \mu, \lambda, \pi, \eta, \kappa, \iota, \zeta, \alpha, \alpha) \cdot \left [ F^T C^T B^T G^T H^T A^T D^T E^T O^T P^T S^T Q^T L^T K^T R^T T^T J^T N^T I^T M^T U^T V^T W^T X^T Y^T Z^T \right ] \end{aligned} $
For short, I will refer it as:
$$ \left \langle \omicron \lambda \pi \mu \omicron \lambda \pi \mu \lambda \omicron \omicron \lambda \pi \mu \pi \mu \omicron \mu \lambda \pi \eta \kappa \iota \zeta \alpha \alpha \right \rangle $$
State space capacity
3D object has 3 degrees of freedom in rotation, but the most convenient method to represent it is using 4 fields, i.e. quaternion. So a proper state space redundancy is necessary for the sake of calculation.
A valid 3-order Rubik’s cube’s total variation is:
$$ \frac{8! \times 3^8 \times 12! \times 2^{12}}{2 \times 2 \times 3} = 43252003274489856000 \approx 4.33 \times 10^{19} $$
If allowing disassembly, the number becomes twelve times larger:
$$ 8! \times 3^8 \times 12! \times 2^{12} = 519024039293878272000 \approx 5.19 \times 10^{20} $$
Besides that, representing a Rubik’s cube state in orientation vector ignores cubies’ position conflicting. The total variation is:
$$ 24^{20} = 4019988717840603673710821376 \approx 4.02 \times 10^{28} $$
(For equality, I ignored 6 axes cubies here.)
And above all these, the facet color scheme allow painting abitrary color in 6 kinds for every facet. Its total variation is:
$$ 6^{48} = 22452257707354557240087211123792674816 \approx 2.25 \times 10^{38} $$
As a Rubik’s cube computer implementation, I’m afraid the redundancy of this scheme is beyond necessary, and is waste and misleading.
Calculation of Rubik’s cube
Once we represent a Rubik’s cube state by a matrix, we can calculate it purely by algebra. This is an example to show what the Rubik’s cube multiplication looks like:
As all groups, Rubik’s cube multiplication obeys associative law, but is not exchangeable.
Rubik’s cube solver
Now, we see this significant fact: the Rubik’s cube solver problem is a matrix decomposition problem!
Specifically, we have 12 unit quarter twists in matrix form:
$$ \begin{aligned} & U = \left \langle \alpha \alpha \zeta \zeta \alpha \alpha \zeta \zeta \alpha \alpha \alpha \alpha \zeta \zeta \zeta \zeta \alpha \alpha \alpha \alpha \alpha \alpha \zeta \alpha \alpha \alpha \right \rangle \\ & U’ = \left \langle \alpha \alpha \iota \iota \alpha \alpha \iota \iota \alpha \alpha \alpha \alpha \iota \iota \iota \iota \alpha \alpha \alpha \alpha \alpha \alpha \iota \alpha \alpha \alpha \right \rangle \\ & D = \left \langle \iota \iota \alpha \alpha \iota \iota \alpha \alpha \iota \iota \iota \iota \alpha \alpha \alpha \alpha \alpha \alpha \alpha \alpha \alpha \alpha \alpha \iota \alpha \alpha \right \rangle \\ & D’ = \left \langle \zeta \zeta \alpha \alpha \zeta \zeta \alpha \alpha \zeta \zeta \zeta \zeta \alpha \alpha \alpha \alpha \alpha \alpha \alpha \alpha \alpha \alpha \alpha \zeta \alpha \alpha \right \rangle \\ & L = \left \langle \theta \alpha \theta \alpha \theta \alpha \theta \alpha \alpha \alpha \theta \alpha \alpha \alpha \theta \alpha \theta \alpha \alpha \theta \alpha \alpha \alpha \alpha \theta \alpha \right \rangle \\ & L’ = \left \langle \epsilon \alpha \epsilon \alpha \epsilon \alpha \epsilon \alpha \alpha \alpha \epsilon \alpha \alpha \alpha \epsilon \alpha \epsilon \alpha \alpha \epsilon \alpha \alpha \alpha \alpha \epsilon \alpha \right \rangle \\ & R = \left \langle \alpha \epsilon \alpha \epsilon \alpha \epsilon \alpha \epsilon \alpha \alpha \alpha \epsilon \alpha \alpha \alpha \epsilon \alpha \epsilon \alpha \epsilon \alpha \alpha \alpha \alpha \alpha \epsilon \right \rangle \\ & R’ = \left \langle \alpha \theta \alpha \theta \alpha \theta \alpha \theta \alpha \alpha \alpha \theta \alpha \alpha \alpha \theta \alpha \theta \alpha \theta \alpha \alpha \alpha \alpha \alpha \theta \right \rangle \\ & F = \left \langle \eta \eta \eta \eta \alpha \alpha \alpha \alpha \eta \alpha \alpha \alpha \eta \alpha \alpha \alpha \eta \eta \alpha \alpha \eta \alpha \alpha \alpha \alpha \alpha \right \rangle \\ & F’ = \left \langle \kappa \kappa \kappa \kappa \alpha \alpha \alpha \alpha \kappa \alpha \alpha \alpha \kappa \alpha \alpha \alpha \kappa \kappa \alpha \alpha \kappa \alpha \alpha \alpha \alpha \alpha \right \rangle \\ & B = \left \langle \alpha \alpha \alpha \alpha \kappa \kappa \kappa \kappa \alpha \kappa \alpha \alpha \alpha \kappa \alpha \alpha \alpha \alpha \kappa \kappa \alpha \kappa \alpha \alpha \alpha \alpha \right \rangle \\ & B’ = \left \langle \alpha \alpha \alpha \alpha \eta \eta \eta \eta \alpha \eta \alpha \alpha \alpha \eta \alpha \alpha \alpha \alpha \eta \eta \alpha \eta \alpha \alpha \alpha \alpha \right \rangle \\ \end{aligned} $$
To find a path from the solved state to an arbitrary state, is just finding a multiplication decomposition in unit twists for the specific state matrix.
We known that any 3-order Rubik’s cube state can be solved in 26 quarter twists in most[1]. But finding the shortest solution is still a pending problem. I hope the matrix representation can provide some new approaches for this problem. After all, linear algebra is a highly developed domain already.