7

I'm trying to determine what is the fewest number of bits I need to represent the state of a Rubik's cube. (EDIT: I am assuming the cube is a valid Rubik's cube that has not been altered and only valid rotations have been performed. I am also assuming the faces are solid, uniform colors. I am not concerned with center cubelet rotations.)

For the corners, I need to know which of the 8 corners (3 bits) it is, it's rotation (3 options -> 2 bits) and location (6 sides -> 3 bits).

For the edges I need to know which of the 12 (4 bits), rotation (2 options -> 1 bit) and location (6 sides -> 3 bits).

If I specify the location based on the middle color, I don't have to track the middle pieces at all I don't think, since everything will be relative to the centers.

Corners: 8 x (3b + 2b + 3b) = 64 bits
Edges: 12 x (3b + 1b + 3b) = 84 bits
Total: 148 bits

Another way would be to have a predetermined order in an array of 20 (first 8 are corners, last 12 are edges). Each would have to know what piece (5 bits) and rotation (2 bits for corners, 1 bit for edges).

Corners: 8 x (3b + 2b) = 40 bits
Edges: 12 x (4b + 1b) = 60 bits
Total: 100 bits

If you know 7 of the 8 corners, you can deduce the last one. Same for the edges...

Corners: 7 x (3b + 2b) = 35 bits
Edges: 11 x (4b + 1b) = 55 bits
Total: 90 bits

Is there a way to further reduce this?

EDITED: I found a website that shows how to represent a cube state, but I'm not sure how many bits it would take to use this method. The actual website appears to be down, but the internet archive has it here: https://web.archive.org/web/20190706141807/http://kociemba.org/cube.htm

  • Title corrected. Not sure what happened there. – J Price Dec 27 '19 at 23:04
  • 1
    If you have a cube with designs on the faces instead of just colours you have another (6 centres) x (4 rotations). – James McLeod Dec 28 '19 at 2:47
  • 1
    You can only deduce the last piece if you know it's a valid cube. Your calculation will fail if Mr. Gremlin flipped over one of your pieces--you know what but not it's orientation. – Loren Pechtel Dec 28 '19 at 3:29
  • I didn't specify that I'm not concerned with the rotation of the cubelet faces, but this is implied by calling it a "Rubik's cube" which is uniform colors on all cubelet sides. I am also assuming the cube is valid and does have a solution. If a piece was flipped or otherwise moved or rotated, the cube would probably not be solvable. I am concerned with unmodified cubes only. Thank you for your comments. – J Price Dec 29 '19 at 4:18
8

You can encode the 8! possible permutations of the corners in 16 bits, and the 12! possible permutations in 29 bits, by numbering the permutations from 1 to 8! (or 1 to 12!), and storing the number. I found a description for how to make this encoding efficient here, using a Lehmer code.

In an analogous manner, you can pack the 3^8=6561 orientations of the corners into 13 bits (I assume one wants to be able to store "invalid" cubes). The 2^12 orientations of the edges will require 12 bits, there is no way to reduce this. In total, this gives

 16 + 29 + 13 + 12 = 70 bits

This is only one bit more than theoretically possible: the pidgeon hole principle shows you cannot reduce the total number of bits below

log_2(8! * 12! * 3^8 * 2^12) = 68.814 ... 

which means 69 bits is the theoretically smallest value, which can be achieved by encoding all the four groups of permutations into one 69 bit value.

Note: if one wants to store only "valid" permutations of the cube, there are 3^7 valid corner orientations, 2^11 valid edge orientations, and only 8!/2 valid corner permutations, which gives

log_2(8!/2 * 12! * 3^7 * 2^11) = 65.22 ... 

So for this case, 66 bits is the smallest possible value.

|improve this answer|||||
  • Your calculations and Herbert Kociemba's agree except that Herbert use 3^7 instead of 3^8 for the corner orientations. This is exactly the info I needed. Thank you. – J Price Dec 29 '19 at 4:14
  • 1
    @JPrice: thanks, see my edit. – Doc Brown Dec 29 '19 at 10:08
  • Pity that it doesn't fit into an uint64_t... – cmaster - reinstate monica Dec 29 '19 at 11:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.