What is the most efficient way to store a cube in memory?

[minime12358]

Hi, I was wondering what the most efficient way to store a cube in memory. I put a new thread in as I thought it would be more than one response.

Looking at the number of cube positions, the optimal should be something like 65, I forget what exactly.

I currently have the best at 100 bits for practical use:
Edges: 4 bits each position for permutation and 1 bit for orientation * 12 = 60
Corners: 3 bits each position for permutation 2 bits for orientation * 12 = 40
= 100
Although you do not need the final piece for edges/corner, so you could subtract 10. You also don't need need the permutation of a second edge, so you could subtract 4.
= 86
This of course is still 21 from optimal. Any ideas?

 

[blah]

However many bits your machine needs to store 43_252_003_274_489_856_000. Nothing practical about that, but it *is* the most efficient way to store it, I think.

 

[qqwref]

If you're storing piece-by-piece, you could use numbers from 1-24, and once you have gotten rid of at least 8 possible positions (so 16 remaining) you can use only 4 bits to store the rest, and so on. So the idea is that instead of storing your edge orientation (or whatever) as the index out of the list of possibilities - if a piece can have (1, 3, 4, 8, 11, 12, 18, 22), just as an example, then you need only 3 bits to represent which one it is, and all you have to write down is which number the one you want is in that list.

So to store the edges this way there are 24/22/20/18/16/14/12/10/8/6/2 possibilities, (the 2 is for EO) which uses 5+5+5+5+4+4+4+4+3+3+1 = 43 bits, and to store the corners there are 24/21/18/15/12/9/6 possibilities, which uses 5+5+5+4+4+4+3 = 30 bits, for a total of 73.


You could also separately store orientation and permutation. EO is obviously 11 bits, and CO has 3^7 possibilities so you'll need at least 12 bits for that (it shouldn't be hard to retrieve CO from a bit-optimal storage method). Then storing the permutations as above, the edges have 12/11/10/9/8/7/6/5/4/3 possibilities so you need 4+4+4+4+3+3+3+3+2+2 = 32 bits, and the corners have 8/7/6/5/4/3/2 so you need 3+3+3+3+2+2 = 16 bits, for a total of 71. Surprisingly this is even more efficient.

 

[minime12358]

Oh wow thanks! I am going to start using something like that. then

 

[cuBerBruce]

You can convert the corner permutation to a number from 0 to 40320-1 (16 bits), and edge permutation into a number from 0 to 479001600-1 (29 bits). If you really need to use minimal bits, it's possible to eliminate one bit from one of these numbers because of the permutation parity constraint between the corners and the edges. This is talked about in the Cube Explorer documentation as well as this page on Jaap's web site.

I would say you probably don't need to be concerned too much about storing the positions near optimally unless your program needs to store a lot of positions. If you store near optimally, you may need to do extra work to calculate the effects of moves on a cube position, for example. In my programs, I will typically use both a "cubie level" representation of the cube and a "numeric" representation where the cube is stored near optimally. Of course, you need to have routines to convert both directions between the two representations. The cubie level is nice for performing manipulations on the cubes, while the numeric representation is convenient for storing lots of positions in memory.

My cubie level representation uses 8 bytes to store information about the 8 corner positions, and 12 bytes store information about the 12 edge positions. The "numeric" representation would use a 4-byte integer to store edge permutation, and three 2-byte integers to store corner permutation, corner orientation, and edge orientation. As all the bits aren't used in this numeric representation, further packing is possible if there is some reason to do it.