chikaku

且听风吟

永远是深夜有多好｡
github
email
HomeArchives

Calculation of the Number of States for a 3x3 Rubik's Cube

#魔方#数学443
AI Translation
This post is translated from Chinese into English through AI.View Original
AI-generated summary
The discussion revolves around calculating the total number of possible states for a standard 3x3 Rubik's Cube, often referred to as "God's Number." The cube consists of six faces, eight corner pieces, and twelve edge pieces. **Corner Piece States:** - There are 8 corner positions, contributing to a state count of \(8!\). - Each corner has three color orientations, but due to fixed relative positions, the effective orientations are \(3^7\) (the last corner's color is determined by the first seven). - Thus, the total states for corners are \(8! \times 3^7\). **Edge Piece States:** - There are 12 edge positions, contributing to a state count of \(12!\). - Each edge has two color orientations, leading to \(2^{11}\) (the last edge's color is fixed). - Therefore, the total states for edges are \(12! \times 2^{11}\). **Total State Count:** - The naive multiplication of corner and edge states includes impossible configurations, specifically those that involve swapping two corners or edges without altering others. - To account for this, the total state count must be divided by 2, resulting in the final formula: \[ \frac{1}{2} \times 8! \times 3^7 \times 12! \times 2^{11} = 43,252,003,274,489,856,000 \] This calculation provides the total number of distinct configurations for a 3x3 Rubik's Cube.

A few days ago, during a meal with colleagues, we discussed "How many moves are needed to restore a Rubik's Cube from any state?" (God's Number), which led to a question about how to calculate the total number of possible states of a Rubik's Cube. At that time, the consideration was quite rough, so I revisited the topic and looked up some information to record it here.

Calculation of the Number of States of a Rubik's Cube#

image image

This is a 3D diagram and an unfolded diagram of a standard Rubik's Cube. There are a total of six faces, which means six center pieces (the center pieces do not rotate, so their state does not need to be considered), eight corner pieces (each with three colored faces), and twelve edge pieces (each with two colored faces).

Number of States for Corner Pieces#

There are eight positions for the corner pieces, so the number of positional states is 8!8! Each corner piece has three colored faces, but the number of color states is not 3!3! Considering the corner piece in the lower left corner of the unfolded diagram, the clockwise relative order of the three colored faces is fixed as: [Green, Red, Yellow]. It is impossible to have the arrangement: [Yellow, Red, Green] under any rotation (even if the cube is disassembled and reassembled). Therefore, each corner piece has only three color states: ABC, CAB, BCA.

We also need to consider that the states of the corner pieces affect each other. Once the positions and colors of the seven corner pieces are fixed, the color of the eighth corner piece is determined. In other words, it is impossible to change the color state of the eighth corner piece without modifying the states of the other seven corner pieces. Thus, the number of color states for the last corner piece is 11, and the total number of states for the corner pieces is (8∗3)∗(7∗3)...(2∗3)∗(1∗1)=8!∗37(8*3) * (7*3) ... (2*3) * (1*1) = 8! * 3_{}^{7}

Number of States for Edge Pieces#

The analysis is similar to that of the corner pieces. There are a total of twelve positions, so the number of positional states is 12!12! The color states have only two options: AB and BA, and the color of the last edge piece is fixed. Therefore, the total number of states for the edge pieces is 12!∗21112! * 2_{}^{11}

Total Number of States#

Now we have the number of states for the corner pieces and the edge pieces, but directly multiplying these results will include some impossible states.

First, it is important to clarify: it is impossible to swap the positions of two corner pieces (or two edge pieces) without modifying the states of the other pieces, because when twisting the cube, the twisting is done by face, and the rotation of each piece affects the surrounding pieces.

Assuming we normally twist the cube to a legal state s1=...AB...s1 = ...AB... where ABAB represents the positional states of two corner pieces (or two edge pieces), it is clearly impossible to have s1flip=...BA...s1_{flip} = ...BA... which results from merely flipping the positions of ABAB without modifying the states of the other pieces. However, the total states obtained from direct multiplication actually include a collection of each legal state and its flipped state:

{s1,s2,..,sn,s1flip,s2flip,..,snflip}\left \{ s1, s2, .., sn, s1_{flip}, s2_{flip}, .., sn_{flip} \right \}

Thus, when calculating the total number of states, we must also divide by 22, resulting in:

1/2∗8!∗37∗12!∗211=432520032744898560001/2 * 8! * 3_{}^{7} * 12! * 2_{}^{11} = 43252003274489856000

Reference: calculating-the-number-of-permutations-of-the-rubiks-cube

Loading...
Ownership of this post data is guaranteed by blockchain and smart contracts to the creator alone.