🟦🟩🟥🟧🟨⬜
I am only considering the traditional 3x3 rubik's cube using the quarter-turn metric.
[ ] parser of human readable move notation [X] define move format [ ] parse reduced moveset [ ] parse standard moveset [ ] binary formats [ ] binary format for moves (with extra codepoints) [ ] parser for binary moves [ ] binary format for states [ ] visualize the cube [ ] print state [ ] animate moves [ ] interactive animation [ ] solver [ ] implement layer by layer solving [ ] implement corners then sides solving [ ] can we generalize algorithms from code to data? like condition+action notation? [ ] theory [ ] is there a meaningful distance function between two states? [ ] is there a smooth tradeoff between the upper bound of nessary moves and the complexity of the algorithm used (solving speed vs learning difficulty) [ ] radix tree of all optimal solutions? How large is the tree, and how small can it be for non-optimal solutions [ ] is permutation parity at all interesting to a human solver?
Consider the standard(?) move notation. Because this is a notation for humans, it includes a bit of redundancy/ancillary information.
In terms of actual state transitions there are only twelve (6*2): each face (6) can be rotated clockwise or anti-clockwise (2). However, a human solver can manipulate the cube in semi-transitional ways, and by combining state transitions with non-transitional movements. These semi- and non-transitional moves are important for both animation and humans attempting to implement an algorithm in the physical world.
Does our internal format only care about transitional data, or do we care about animation and how a human would parse an algorithm? Many parts of the notation are equivalent if we don't care about animation. Perhaps there's a need for multiple binary formats?
r == Rwa priori. probably a holdover from competing standardsR2 == RR == R'R'trivially, but the animation forR2is ambiguousR' == RRRhowever, not in terms of solution length or animation. We probably don't want to consider these as equivalentl == Rx'Lower-case letters exist to reduce rotations, but are not equivalent in terms of animationsxyzare entirely non-transitionalM == RL'x' == r'R == Rr'again the animation is not equivalent, but also it's not clear to me that every human solver would treat these as equivalent. Personally I would user'R(but I'm not a speed cuber so idk).
There is also a difference of opinion based around the quarter-turn and half-turn metric. There isn't even a concensus even about how to count moves because of this.
Since most of my questions are theoretical/mathematical rather I will only be considering true state transitions, which means that there are only twelve transitions. However, the parser should correctly handle the extended notation (wide moves and rotations change the basis of future moves). When (if) I get around to animating the transitions, I'll use a free camera, or the cross-view of the cube so that 'rotations' aren't so important.
So to summarize:
- I only care about 12 'moves' which in a human-readable notation I will denote with
UDRLFBudrlfb, whereUis a clockwise transition of the top face anduis an anti-clockwise rotation of the top face. - The parser will have two modes. The first handles this reduced moveset, and the second will handle the standard notation, producing the equivalent moves within the reduced moveset.
- note: postel's law
Since we only need to represent 12 moves and n ∈ N: 12 != 2^n, we have some extra code points that we could use. For example we could use 4 extra code points (for a total of 16) and encode each item in 4 bits.
Since it's intended in the future to implement a solver kind of thing, perhaps the other bits could represent other kinds of data for the solver. For example, procedure definitions (imagine forth).
I don't know if this will have any algorithmic use, but it's pleasing to me that U and u should be represented as binary complements.
picked bit assignment based on rotating around U axis and (original*5) mod 16
0 0000 U
1 0001 F
2 0010
3 0011 f
4 0100
5 0101 L
6 0110
7 0111 r
8 1000 D
9 1001 B
10 1010
11 1011 b
12 1100
13 1101 R
14 1110
15 1111 l
Does the order of the faces make it any easier or harder to represent rotations?
Using a bit board, the color of each sticker takes 3 bits * 8 per face (the center isn't needed b/c it's stationary). with 6 faces the bit board must be 3bits86 = 144bits.
Using separate arrays for edges and corners, we need
- 12*5bits for the index, orientation, and position of edges
- 8*5bits for the index and position of corners
- for a totall of 100 bits or 2*64bits
Clearly (to me), using separate arrays is "better" because it is a more efficient representation, but it still isn't ideal. Using the "ideal" representation, every combination of bits represents a valid cube. It is also the smallest possible representation.
In this case, given that there are 43,252,003,274,489,856,000 valid combinations, the ideal representation takes ~65.22 bits. Problematically, there is no deterministic way to show that a valid move or even the current position of any given cubie is easy to compute given this representation.
A sequence of moves can be seen as equivalent to the state that is created when that sequence is applied to a solved cube. In this sense, the effects of an arbitrarily long move sequence can always be represented in a fixed length. This is probably equivalent to a hash or modulus operation, and the equivalence is similarly irreversable.
I'm imagining the solver as defining 'conditions' and 'procedures', then repeatedly applying procedures to the cube until either the cube is solved, or no more procedures can be applied. The binary encod
Considering that the cube has 24 possible rotations (each face), and that algorithms may be mirrored, there is 48x symmetry that should be accounted for in patterns and algorithms.
What if we consider each state as a point in space, then a move sequence is a vector between states. This does not work because algorithms do not compose, and so do not behave like vectors
I had hoped against hope that the commonly talked about number of combinations (4.3*10^19 == ~65.22bits) did not account for the 12 orbits, so that we could accommodate the entire representation in 64 bits, which would be lovely.