Smallest Rubik's cube state representation

Question

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

Answer 1

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.