Teaching Kids Programming: Videos on Data Structures and Algorithms
Given a 3×3 Rubik Cube, how many Permutations does it have (solvable)?
There are 6 cores (the pieces in the middle) which don’t change and if we break the rubik cube, these pieces are fixed.
There are 12 edge pieces (two colors) and 8 corner pieces (three colors).
To install the edge pieces without considering the colors is:
which is 12! (factorial)
To assemble the corner pieces, similar idea without considering the colors is:
which is 8! (factorial).
For each edge pieces, we can flip it (two permutations), for each corner pieces, we can twist it three times. And thus, the total number of states that we can re-assemble a 3×3 rubik’s cube is:
This is the number of permutations that we can re-assemble the 3×3 rubik cube, however, not all of them can be solvable (can be obtained from a solvable state).
For the last corner cube, we can only have 1 solvable state – thus 1/3 of them is solvable.
For the last edge pixel, we can only 1 out of 2 have solvable state (we can’t just simply flip them).
And we can’t simply swap any two edge pieces without affecting other pieces, thus only 1/2 is solvable.
And that is (one twelvth) is solvable from all states:
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Teaching Kids Programming - Greedy/Simulation Algorithm to Validate Stack Sequences
Next Post: Teaching Kids Programming - Counting the Number of Squares and Rectangles of a NxN Rubik Cube