Rubik's Cube Encoding
If you don’t care about making legal moves to arrive at a position, I think it’d be easy to come up with schemes for encoding information in a Rubik’s cube. It’s probably simplest to start with schemes that only encode values in the 20 movable cubes.
For example: starting with all cubes in their solved position, you could change the rotation of a cube (i.e. the piece is in the correct location, but the stickers are facing the wrong way) to indicate a 1 or keep the cube in it’s solved rotation to indicate a 0. Then you decide an order in which to check the cubes, and you can encode 20 bits of data.
If you only work with 10 cubes, say the white face, the orange-green edge and the orange-blue edge, you could encode a wider range of values per cube. Solved position is 0, rotated is 1, and swapped with the cube across from it (e.g. green-white swaps with green-yellow) is -1. That gives 10 trits, which is about 4 bits less than the first system, but it shows that we can come up with various rules to assign values to cubes.
I think it takes 13 trits to exceed the capacity of 20 bits, so you’d need to find a ruleset improves on what we have so far by 3 more cubes.
Another possibility is to go back to rotating the 20 movable cubes, but say the 12 edges (which have only 2 possible states) represent binary values as before, but the corners (which have 3 rotations) represent ternary values. Then you have 12 bits plus 8 trits, which is about 24 bits, but this kind of thing seems horrifying and wrong.
If you do care about making legal moves, it’s more difficult.
The first simple encoding method I can think of is to only use one face and to only care about the color of the sticker, not if each cube is actually in it’s solved position. So on the white face of the cube, white stickers get a value of 1 and any other color sticker get’s a value of 0, and of course you ignore the center cube, so you get 8 bits to work with.
Expanding this beyond one face gets into the problem that cubes never rotate or change position in isolation. Using the “sticker-color-only” method, I think it is impossible to set arbitrarily set bits on both the white and yellow faces.
There might be a solution that involves tracking pairs, which would probably mean we can get 10 bits. Maybe you can scale this problem down by only considering corner pieces and investigating what would be involved in tracking pairs of swapped corner cubes.
A more fruitful approach is probably to work within the patterns that occur naturally. Instead of examining the limitations to rotating and positioning cubes arbitrarily, you could examine all of the states possible in the orientation of last layer and permutation of last layer stages and come up with rules to assign values based on the states. Or, I use the Roux method to solve, so I might investigate the patterns that occur regularly when using that method and see how they could be used to encode values.
Yeah… developing an encoding method that considers legal moves should probably start by enumerating the kinds of manipulations that can occur, and then looking at those manipulations for opportunities to set bits (or trits).