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

J Price
  • 89
  • 5
  • 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 02: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 03: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 04:18

1 Answers1

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.

Doc Brown
  • 199,015
  • 33
  • 367
  • 565
  • Your calculations and [Herbert Kociemba's](https://web.archive.org/web/20190616141551fw_/http://kociemba.org/math/coordlevel.htm) 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 04:14
  • Pity that it doesn't fit into an `uint64_t`... – cmaster - reinstate monica Dec 29 '19 at 11:27