Algorithmically Solving a 2x2 Rubik's Cube

A 2x2 Rubik's Cube, has six colored sides (Blue, White, Orange, Yellow, Red, Green), each of which is subdivided into four sections. The exterior surface of the device consists of eight cube segments, one at each corner of the Rubik's Cube. Three colored faces are present on each of the eight corner segments. (Blue, White, Orange), (Blue, Orange, Yellow), (Blue. Yellow, Red), (Blue, Red, White), (Green, White, Orange), (Green, Orange, Yellow), (Green. Yellow, Red), and (Green, Red, White). In total there are 8$\times$3=24 faces on a Rubik's cube.

There are 8! possible permutations of the corner pieces. Any seven of the corner pieces can be rotated with respect to the eighth giving rise to $3^{7}$ possible positions. Moreover, for any given permutation, the 2x2 cube can be arbitrary oriented in twenty-four different ways, (one way for each face). The faces can therefore be permuted in 3,674,160 ways. \[\frac{8!\times3^{7}}{24} = 3,674,160\] The following image depicts all 24 faces of a 2x2 Rubik's cube.

Each of the faces can be uniquely identified given its color and its pairing with the other two colors on the same corner segment. For this algorithm I have labelled the Blue face of the corner segment containing a Blue face, White face, and Orange face as Face ID# = 0. Because the puzzle can be oriented as a whole such that any single face can occupy any one of twenty-four positions it is useful therefore to define an origin relative to which other positions can be in turn be defined. If you were to orient a 2x2 Rubik's cube such that Face ID# = 0 was on the top side and was in the back, left quadrant of this side then Face ID# = 0 could be said to occupy Position ID# = 0. The remaining Face ID#s and Position ID#s are assigned based on the solved state of the puzzle. In the puzzle's solved state the face ID# and the position ID# are the same, i.e. face one occupies position one and face two occupies position two etc. In the proceeding image each face was labeled with a number representing the Position ID# (which is the same as the Face ID#) of the face with respect to the origin.

Every permutation of a 2x2 Rubik's cube can be notated by an array where the index is the Position ID# and the value in that location is the Face ID#. The array for the solved state reads as {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23}

Any four co-planar corner sections can be rotated together as one of six 'sides' in either a clockwise or a counter-clockwise manner for a total of 6$\times$2=12 possible types of rotations. In this algorithm the rotations are intuitively labeled 1 through 12. Each rotation transforms the array in a unique way that is analogous to the act of physically rotating a side of the puzzle. If the puzzle began in a solved state and then a single rotation were performed then the resulting array would be modified to the following states corresponding to each of the twelve unique rotations:

(1) - Rotate Top CW:
{2, 0, 3, 1, 6, 7, 8, 9, 10, 11, 4, 5, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23}

(2) - Rotate Top CCW:
{1, 3, 0, 2, 10, 11, 4, 5, 6, 7, 8, 9, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23}

(3) - Rotate Bottom CCW:
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 18, 19, 12, 13, 14, 15, 16, 17, 22, 20, 23, 21}

(4) - Rotate Bottom CW:
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 14, 15, 16, 17, 18, 19, 12, 13, 21, 23, 20, 22}

(5) - Rotate Front CW:
{0, 1, 15, 7, 4, 5, 6, 20, 16, 8, 2, 11, 12, 13, 14, 21, 17, 9, 3, 19, 18, 10, 22, 23}

(6) - Rotate Front CCW:
{0, 1, 10, 18, 4, 5, 6, 3, 9, 17, 21, 11, 12, 13, 14, 2, 8, 16, 20, 19, 7, 15, 22, 23}

(7) - Rotate Right CW:
{0, 9, 2, 17, 3, 5, 6, 7, 8, 21, 18, 10, 1, 13, 14, 15, 16, 23, 19, 11, 20, 12, 22, 4}

(8) - Rotate Right CCW:
{0, 12, 2, 4, 23, 5, 6, 7, 8, 1, 11, 19, 21, 13, 14, 15, 16, 3, 10, 18, 20, 9, 22, 17}

(9) - Rotate Left CW:
{13, 1, 5, 3, 4, 22, 14, 6, 0, 9, 10, 11, 12, 20, 15, 7, 2, 17, 18, 19, 8, 21, 16, 23}

(10) - Rotate Left CCW:
{8, 1, 16, 3, 4, 2, 7, 15, 20, 9, 10, 11, 12, 0, 6, 14, 22, 17, 18, 19, 13, 21, 5, 23}

(11) - Rotate Back CW:
{11, 19, 2, 3, 12, 4, 1, 7, 8, 9, 10, 23, 13, 5, 0, 15, 16, 17, 18, 22, 20, 21, 6, 14}

(12) - Rotate Back CCW:
{14, 6, 2, 3, 5, 13, 22, 7, 8, 9, 10, 0, 4, 12, 23, 15, 16, 17, 18, 1, 20, 21, 19, 11}

The following image depicts these rotations with numbered gray arrows.

For the purpose of this algorithm, the puzzle is considered to be in an unsolved state if Face ID# = 0 does not occupy Position ID# = 0 even if for each side of the puzzle, the four constituent faces share the same color. This is a trivial limitation and is addressed by first orienting Face ID# = 0 into Position ID# = 0 at the beginning of the algorithm.

If the puzzle is in an unsolved state and Face ID# = 0 occupies Position ID# = 0 then the Face ID# of between four and twenty-one of the faces will not occupy a position with the same Position ID# as the Face #ID. The following two images represent the same permutation labelled according to its Face ID#s and then by its Position ID#s.

When a side is rotated, 4$\times$3=12 faces move at the same time. This can be seen from the following image that depicts the groupings of three faces corresponding to each corner segment.

Consider, for example, that if rotation 1 is immediately followed by rotation 4 then the entire puzzle will have been rotated about a single axis but afterwards each face will still be relatively situated with respect to other faces in the same manner as before the two rotations. A consecutive pair of rotations with this property is a Frame Shift. A complete list of Frame Shifts is: (1,4), (2,3), (5,6), (7,10), (8,9), (11, 12)

The Algorithm

Step 1.) Begin by orienting the puzzle such that Face ID# = 0 occupies Position ID# = 0 using frame shifts. No more than three Frame Shifts will be required.

Step 2.) Preserve Face ID# = 0 in Position ID# = 0 and move Face ID# = 1 to Position ID# = 1

Step 3.) Preserve the previous position changes for Face ID# = 0 and 1 while moving Face ID# = 2 to Position ID# = 2

Step 4.) Preserve the previous position changes for Face ID# = 0,1 and 2 while moving Face ID# = 3 to Position ID# = 3

The puzzle is now half solved.

Step 5.) Preserve the previous position changes for Face ID# = 0,1,2 and 3 while moving Face ID# = 12 to Position ID# = 12

Step 6.) Preserve the previous position changes for Face ID# = 0,1,2,3 and 12 while moving Face ID# = 13 to Position ID# = 13

Step 7.) Preserve the previous position changes for Face ID# = 0,1,2,3,12 and 13 while moving Face ID# = 11 to Position ID# = 15

If Face ID# 16 is in Position ID# 16 then use this rotation sequence:
(2, 8, 5, 1, 10, 5, 3, 6, 2, 6, 8, 5, 1, 5, 3, 6) *16 rotations*

If Face ID# 17 is in Position ID# 16 then use this rotation sequence:
(8, 1, 5, 3, 9, 2, 6, 8, 1, 5, 3, 9, 2, 6, 8, 1, 5, 3, 9, 2, 6, 2, 8, 5, 1, 10, 5, 3, 6, 2, 6, 8, 5, 1, 5, 3, 6) *37 rotations*

If Face ID# 18 is in Position ID# 16 then use this rotation sequence:
(8, 6, 1, 7, 5, 3, 12, 2, 8, 5, 1, 5, 3, 6, 10) *15 rotations*

If Face ID# 20 is in Position ID# 16 then use this rotation sequence:
(2, 6, 8, 5, 1, 5, 3, 6, 9, 5, 4, 6, 2, 6, 7, 1) *16 rotations*

If Face ID# 21 is in Position ID# 16 then use this rotation sequence:
(8, 1, 5, 3, 9, 2, 6, 8, 1, 5, 3, 9, 2, 6, 8, 1, 5, 3, 9, 2, 6) *21 rotations*


If you find rotation sequences that perform the same purpose as the five above, but in fewer steps, please let me know in the comments section.

How to calculate Pi

$\pi$ is an irrational number: it cannot be expressed as the quotent of two integers. Furthermore the decimal representation of an irrational number does not terminate and does not consist of a repeating sequence. How can such a number ever be fully communicated? The informational content of an irrational number is infinite, therefore the number must be represented indirectly as with an expression.

A convenient way to represent $\pi$ is with an infinite series. When the terms of an infinite series are added together they can converge to a single value or they can diverge by increasing to infinity or by oscillating within a range of values. For the purposes of representing $\pi$ we need to use a convergent infinite sequence.

The Nilakantha Series is easy to understand and easy to calculate but converges to $\pi$ slowly. \[ \pi = 3 +\frac{4}{2\times3\times4} -\frac{4}{4\times5\times6} +\frac{4}{6\times7\times8} -\frac{4}{8\times9\times10}\cdots \] The Nilakantha Series can be expressed in sigma notation as: \[\pi = 3+\displaystyle\sum_{k=1}^{\infty} \frac{4(-1)^{k-1}}{2k\times (2k+1) \times (2k+2)} \] \[\pi = 3+4\displaystyle\sum_{k=1}^{\infty} \frac{(-1)^{k-1}}{8k^{3}+12k^{2}+4k} \] The Chudnovsky Series is more complex but converges to $\pi$ quickly. \[\frac{1}{\pi} = 12\displaystyle\sum_{k=1}^{\infty}\frac{(-1)^{k}(6k)!(13591409+545140134k)}{(3k)!(k!)^{3}640320^{3k}640320^{\frac{3}{2}}}\] This blog will demonstrate how to calculate the Chudnovsky series in C++ and will attempt to do so with sufficient detail such that any motivated novice can understand the process. The Chudnovsky series can be reformulated to allow for a more convenient calculation.
\[\frac{1}{\pi} = 12\displaystyle\sum_{k=1}^{\infty}\frac{(-1)^{k}(6k)!(13591409+545140134k)}{(3k)!(k!)^{3}640320^{3k}640320^{\frac{3}{2}}}\] \[\frac{1}{\pi} = \frac{12}{640320^{\frac{3}{2}}}\displaystyle\sum_{k=1}^{\infty}\frac{(-1)^{k}(6k)!(13591409+545140134k)}{(3k)!(k!)^{3}640320^{3k}}\] \[\frac{1}{\pi} = \frac{12}{640320^{1}\times640320^{\frac{1}{2}}}\displaystyle\sum_{k=1}^{\infty}\frac{(-1)^{k}(6k)!(13591409+545140134k)}{(3k)!(k!)^{3}640320^{3k}}\] \[\frac{1}{\pi} = \frac{12}{640320\times\sqrt{640320}}\displaystyle\sum_{k=1}^{\infty}\frac{(-1)^{k}(6k)!(13591409+545140134k)}{(3k)!(k!)^{3}640320^{3k}}\] \[\frac{1}{\pi} = \frac{12}{12\times53360\times\sqrt{64\times10005}}\displaystyle\sum_{k=1}^{\infty}\frac{(-1)^{k}(6k)!(13591409+545140134k)}{(3k)!(k!)^{3}640320^{3k}}\] \[\frac{1}{\pi} = \frac{1}{53360\times8\times\sqrt{10005}}\displaystyle\sum_{k=1}^{\infty}\frac{(-1)^{k}(6k)!(13591409+545140134k)}{(3k)!(k!)^{3}640320^{3k}}\] \[\frac{1}{\pi} = \frac{1}{426880\sqrt{10005}}\displaystyle\sum_{k=1}^{\infty}\frac{(-1)^{k}(6k)!(13591409+545140134k)}{(3k)!(k!)^{3}640320^{3k}}\] \[\frac{1}{\pi} = \frac{1}{426880\sqrt{10005}}\displaystyle\sum_{k=1}^{\infty}\frac{(-1)^{k}(6k)!13591409}{(3k)!(k!)^{3}640320^{3k}}+\frac{(-1)^{k}(6k)!545140134k}{(3k)!(k!)^{3}640320^{3k}}\] \[a = \frac{(-1)^{k}(6k)!}{(3k)!(k!)^{3}640320^{3k}}\] \[b = \frac{(-1)^{k}(6k)!k}{(3k)!(k!)^{3}640320^{3k}}\] \[b = a\times k\] \[\frac{1}{\pi} = \frac{1}{426880\sqrt{10005}}\displaystyle\sum_{k=1}^{\infty}13591409a+545140134b\] \[\frac{1}{\pi} = \displaystyle\sum_{k=1}^{\infty}\frac{13591409a+545140134b}{426880\sqrt{10005}}\] \[\pi = \displaystyle\sum_{k=1}^{\infty}\frac{426880\sqrt{10005}}{13591409a+545140134b}\] At this point the series has a favorable form where knowing a allows b to be quickly calculated. This is further improved by finding a multiple such that a_k can be calculated quickly from a_(k-1). \[\frac{a_k}{a_{(k-1)}}=\frac{(-1)^{k}(6k)!}{(3k)!(k!)^{3}640320^{3k}}\div\frac{(-1)^{k-1}(6(k-1))!}{(3(k-1))!((k-1)!)^{3}640320^{3(k-1)}}\] \[\frac{a_k}{a_{(k-1)}}=\frac{(-1)^{k}(6k)!}{(3k)!(k!)^{3}640320^{3k}}\times\frac{(3(k-1))!((k-1)!)^{3}640320^{3(k-1)}}{(-1)^{k-1}(6(k-1))!}\] \[\frac{a_k}{a_{(k-1)}}=\frac{(-1)^{k}(6k)!(3(k-1))!((k-1)!)^{3}640320^{3(k-1)}}{(-1)^{k-1}(6(k-1))!(3k)!(k!)^{3}640320^{3k}}\] \[\frac{a_k}{a_{(k-1)}}=\frac{(-1)^{k}(6k)!(3k-3)!((k-1)!)^{3}640320^{3k-3}}{(-1)^{k}(-1)^{-1}(6k-6)!(3k)!(k!)^{3}640320^{3k}}\] \[\frac{a_k}{a_{(k-1)}}=\frac{(6k)!(3k-3)!((k-1)!)^{3}640320^{3k}640320^{-3}}{(-1)^{-1}(6k-6)!(3k)!(k!)^{3}640320^{3k}}\] \[\frac{a_k}{a_{(k-1)}}=\frac{-1(6k)!(3k-3)!((k-1)!)^{3}640320^{-3}}{(6k-6)!(3k)!(k\times(k-1)!)^{3}}\] \[\frac{a_k}{a_{(k-1)}}=\frac{-1(6k)(6k-1)(6k-2)(6k-3)(6k-4)(6k-5)(6k-6)!(3k-3)!((k-1)!)^{3}}{(6k-6)!(3k)(3k-1)(3k-2)(3k-3)!k^{3}((k-1)!)^{3}640320^{3}}\] \[\frac{a_k}{a_{(k-1)}}=\frac{-6k(6k-1)(6k-2)(6k-3)(6k-4)(6k-5)}{3k(3k-1)(3k-2)k^{3}640320^{3}}\] \[\frac{a_k}{a_{(k-1)}}=\frac{-2(6k-1)(2)(3k-1)(3)(2k-1)(2)(3k-2)(6k-5)}{(3k-1)(3k-2)k^{3}640320^{3}}\] \[\frac{a_k}{a_{(k-1)}}=\frac{-24(6k-1)(2k-1)(6k-5)}{k^{3}640320^{3}}\] Here is a basic implementation of the algorithm in C++. The code is free to use on an as is basis. No attribution is required if you use it. No warranty of any kind is implied.

void chudnovsky (void)
{

long double const const_A = 13591409.0;
long double const const_B = 545140134.0;
long double const const_C = 640320.0;
long double const const_D = 426880.0;
long double const const_E = 10005.0;
long double squareRoot = 0;
long double c_Cubed = pow(const_C, 3); // 262537412640768000
long double numerator = 0;
long double denominator = 0;
long double piAprx = 0;
long double alpha = 1; // at k = 0
long double alpha_Sigma = 1;
long double beta_Sigma = 0; // at k = 0
int iterations = 1;

squareRoot = sqrt(const_E);
numerator = squareRoot*const_D;
denominator = (alpha_Sigma*const_A) + (beta_Sigma*const_B);
piAprx = numerator/denominator;
std::cout << "at k = 0, piAprx = " << std::setprecision(16) << piAprx << std::endl << std::endl;

for (long double k = 1; k <= iterations; k++)
{
// this starts calculating the series from k = 1

alpha *= -24*(6*k-1)*(2*k-1)*(6*k-5)/(pow(k,3)*c_Cubed);

alpha_Sigma += alpha;

beta_Sigma += alpha*k;

}
denominator = (alpha_Sigma*const_A) + (beta_Sigma*const_B);

piAprx = numerator/denominator;
std::cout << "at k = " << iterations << " piAprx = " << std::setprecision(16) << piAprx << std::endl << std::endl;

}