- Joined
- Jun 7, 2013

- Messages
- 1,232

- Likes
- 257

- Location
- Portland, OR, USA

- WCA
- 2013BROT01

- YouTube
- chree55

Thread starter
#1

After a random chain of thoughts I had last night, the question just occured to me: If I wanted to store a digital representation of every single possible cube state, how much space would that take up? This naturally led to the question: what is the most efficient way to store any single cube state in a digital format? I don't think that I came up with "The" answer, but I knocked out a few ideas. I searched the forums for a better answer and found none. I hope y'all can help out.

My first instinct was to just look at a scramble picture like we get from TNoodle, which is just a picture of where the stickers wind up after the scramble. TNoodle spits out the familiar (and easy to read) layout. 6 faces with 9 stickers each in a "T" shape, 54 stickers total. I could just as easily imagine a 1x54 grid of colors, where each segment of the grid is assigned to a particular sticker on the cube. To store that digitally, I can assign each color a value, then create an array or string with the sticker colors encoded in sequence. Since there are 6 possible colors for each sticker, I would need a minimum of 3 bits to say what color was asigned to any one sticker.

Ok... but technically, I don't need to store the center stickers. I can just as easily write a decoder that assumes the 6 center stickers never change, and we can just ignore it. That removes 1 sticker per face that we need to store.

To cut it down further, I can make one big assumption: the cube is always solvable. For a solvable cube, if I know the location and values for 11 edges, we know that we can derive the location and orientation of the 12th edge. Same goes for when we know the state of 7 of 8 corners. In my decoder, I could program it to figure out the last pieces and calculate their orientation. This eliminates the need to store the values for 2 edge stickers and 3 corner stickers, 5 total. So...

Then I decided to take a different approach. What if, instead, only want to code the properties of each piece? There are many fewer total Pieces than Stickers, so it'll probably be more efficient.

Instead we'll just store the permutation and orientation of each piece. As far as the "Array" is concerned, we can imagine the first value stored is the location of the WBO corner. The next value is for WBR, then WGO, etc. The order that you store the pieces is arbitrary, as long as your decoder knows which values are assigned to which pieces. Then we assign each location a value, so UBL is "0", UBR is "1", UFL is "2", etc. Once again, the actual value is arbitrary, we just need 1 unique value for each unique location.

There are 8 corners with 8 possible permutations: 3 bits each.

Each corner has 3 possible orientations: 2 bits each.

12 edges with 12 possible locations: 4 bits each.

And each edge has 2 possible permutations: just 1 more bit each.

(Edit: Just realized that's really just 5 bits per piece)

So:

Quite a jump. And like before, we can ignore the last edge and corner, and just program the decoder to calculate the permutation and orientation based on the state of the rest of the cube.

So I'm down to 90 bits per cube. If I wanted to use this "code" to store every single possible cube state, such that I could program a decoder to pluck out any one of them and give me a visual representation of cube state... store all 4.3 quintillion states would cost 387 quintillion bits... or at 8 bits per bytes, 48ish quintillion bytes, so something like 48 million petabytes.

I haven't even bothered to do the exact calculation on this because I'm positive that there has to be a more efficient way of encoding a cube state.

I'm sure SOMEone has thought about this before. Thoughts?

My first instinct was to just look at a scramble picture like we get from TNoodle, which is just a picture of where the stickers wind up after the scramble. TNoodle spits out the familiar (and easy to read) layout. 6 faces with 9 stickers each in a "T" shape, 54 stickers total. I could just as easily imagine a 1x54 grid of colors, where each segment of the grid is assigned to a particular sticker on the cube. To store that digitally, I can assign each color a value, then create an array or string with the sticker colors encoded in sequence. Since there are 6 possible colors for each sticker, I would need a minimum of 3 bits to say what color was asigned to any one sticker.

**6 faces * 9 stickers per face * 3 bits per sticker = 162 bits per cube state**Ok... but technically, I don't need to store the center stickers. I can just as easily write a decoder that assumes the 6 center stickers never change, and we can just ignore it. That removes 1 sticker per face that we need to store.

**6 faces * 8 stickers per face * 3 bits per sticker = 138 bits per cube state**To cut it down further, I can make one big assumption: the cube is always solvable. For a solvable cube, if I know the location and values for 11 edges, we know that we can derive the location and orientation of the 12th edge. Same goes for when we know the state of 7 of 8 corners. In my decoder, I could program it to figure out the last pieces and calculate their orientation. This eliminates the need to store the values for 2 edge stickers and 3 corner stickers, 5 total. So...

**((6 faces * 8 stickers per face) - 5 stickers) * 3 bits per sticker = 123 bits per cube**Then I decided to take a different approach. What if, instead, only want to code the properties of each piece? There are many fewer total Pieces than Stickers, so it'll probably be more efficient.

Instead we'll just store the permutation and orientation of each piece. As far as the "Array" is concerned, we can imagine the first value stored is the location of the WBO corner. The next value is for WBR, then WGO, etc. The order that you store the pieces is arbitrary, as long as your decoder knows which values are assigned to which pieces. Then we assign each location a value, so UBL is "0", UBR is "1", UFL is "2", etc. Once again, the actual value is arbitrary, we just need 1 unique value for each unique location.

There are 8 corners with 8 possible permutations: 3 bits each.

Each corner has 3 possible orientations: 2 bits each.

12 edges with 12 possible locations: 4 bits each.

And each edge has 2 possible permutations: just 1 more bit each.

(Edit: Just realized that's really just 5 bits per piece)

So:

**8 corners * (3 bits per permutation + 2 bits per orientation) + 12 edges * (4 bits per permutation + 1 bit per orientation) = 100 bits per cube state**Quite a jump. And like before, we can ignore the last edge and corner, and just program the decoder to calculate the permutation and orientation based on the state of the rest of the cube.

**7 corners * (3 bits per permutation + 2 bits per orientation) + 11 edges * (4 bits per permutation + 1 bit per orientation) = 90 bits per cube state**So I'm down to 90 bits per cube. If I wanted to use this "code" to store every single possible cube state, such that I could program a decoder to pluck out any one of them and give me a visual representation of cube state... store all 4.3 quintillion states would cost 387 quintillion bits... or at 8 bits per bytes, 48ish quintillion bytes, so something like 48 million petabytes.

I haven't even bothered to do the exact calculation on this because I'm positive that there has to be a more efficient way of encoding a cube state.

I'm sure SOMEone has thought about this before. Thoughts?

Last edited: Feb 10, 2016