I want to implement a 2x2 optimal solver with SymCoords

[Herbert Kociemba]

No I actually never used it. 2x2x2 has so few states that symmetry reduction seemed overkill to me.

 

[Renslay]

No I actually never used it. 2x2x2 has so few states that symmetry reduction seemed overkill to me.

It might be overkill, but it's a good practice/learning for me.

However, I think I'm gonna return to the original definition of the orientations; and for applying symmetries I actually implement a general cube state multiplier. The rotation and mirror symmetric states will be pre-defined, so a specific symmetric case of a state A will actually be calculated as S*A*S', where S is one of the 6 (5 without id) pre-defined symmetry.

This way there is not really a difference between the two orientation definitions, however the original is easier to read from the stickers directly.

 

[Renslay]

I have another question in the meantime: what about inverses and inverse symmetries? Can we consider the family of S*A'*S' cases as well? Would that be just as easy to implement and consider when one generate the symmetric cases of A (so there will be 12 cases instead of 6)? Would that reduce the final table by another factor of 2, approximately?

 

[Herbert Kociemba]

I have not enough insight to say definitely that this will not work. But at least I see problems. For example I see no way how a corner orientation alone can be "inverted". Inversion always depends on the corner permutation. So I think it may only be possible to reduce the whole set of 7!3^6 different positions by the 12 smmetries/antisymmetries where each element has information about its permutation and orientation.

 

[Renslay]

Finally managed to implement the apply_symmetry() function. For the permutations, all of them are quite simple (conjugate with the relevant permutation that describes the symmetry).

But it's a bit trickier when we want to apply this to an entire cube, with permutations and orientations. Since I use the original definition for orientation (U/D reference stickers), at the end of the apply_symmetry() I had to swap 1s to 2s and 2s to 1s when the symmetry was a mirror symmetry.

In short:
if S symmetry is a cube state defining a rotation along the DBL-UFR axis:
B = S * A * S'
if S symmetry is a cube state defining a mirror symmetry (e.g., mirroring along the BL-FR plane):
B = S * A * S'
B.o = (3 - B.o) % 3

The reason for this is because S represents the mirror cube case, which changes clockwise (1) rotations to counter-clockwise (2), and vice-versa.

Technically, we should do this:
C1 = I * S // I represents the solved cube state
C1.o = (3 - C1.o) % 3 // we are in the "mirror dimension"; corner orientations are mirrored (0->0, 1->2, 2->1)
C2 = C1 * A // apply A in the "mirror dimension"
B = C2 * S' // this brings us back to the "normal world"
B.o = (3 - B.o) % 3 // the reverse of the orientation mirroring (0->0, 1->2, 2->1)

But the bold part is unnecessary, because at that point all of our corner orientations are 0 (the first step is also unnecessary for obvious reasons).

With an example:
Imagine A is such a state that it rotates the UFL corner clockwise: its orientation is 1.
What we expect is that it's BL-FR mirror case is when the UBR corner is twisted counter-clockwise (2).

S brings the UBR corner to the UFL place.
Applying A changes it's orientation to 1.
S' brings back the corner from UBL to UBR.
The last step swaps it's orientation from 1 to 2.

 

[Renslay]

I tested it, and I got the followings:

A = Converter.scramble2cube("R F' U2")
solver = Solver()
for sym in range(6):
    B = Symmetry.apply(A, sym)
    solution = solver.solve(B)
    print(solution)

# RESULTS:
U2 F R' (3 turns)  # id
F2 R U' (3 turns)  # CW rotation sym
R2 U F' (3 turns)  # CCW rotation sym
U2 R' F (3 turns)  # BL-FR mirror sym
F2 U' R (3 turns)  # DB-UF mirror sym
R2 F' U (3 turns)  # DL-UR mirror sym

Seems to be working! \o/

 

[Renslay]

Oooookay, I think I have a working distance table where the table size is the number of permutation representations * cube orientations. More precisely, there are 870 individual permutation representations. Slightly more than 7!/6 = 840, but less than 900, as predicted.

Out of the 7! = 5040 total permutation cases, there are:
4884 cases with no symmetries (or you can say 1 symmetry... the id),
138 cases with 2 symmetries,
16 cases with 3 symmetries,
2 cases with 6 symmetries.

The last two cases are the id permutation; and the permutation where all the corners are diagonally swapped (except DLB and URF).

To double check that my new, reduced sym distance table works, I went through all possible cube states, and checked whenever the two distances agreed: the original table with the original raw coordinates, and the new table with the sym distances. They agreed everywhere.

Since this was the last piece in the puzzle so to speak, soon I can wrap up the entire thing! I will write a detailed explanation on everything on github, with the code attached.

Some extra notes:
- I keep the construction of the original distance table (size of 7!*3^6). The reduced sym distance table is constructed from that.
- I also have move tables with raw coordinates: sizes are 7!*9 and 3^6*9 for permutation and orientation, respectively. Unlike the sym distance table, these are not stored but constructed on the fly (the extra runtime is negligible).
- I will further reduce the size of the sym distance table by storing modulo 3 distances, and 5 such values will be stored in one byte. This means the entire table has the size of (870*3^6) / 5 = 126846 bytes (less than 127 KB!)
- Generating the distance table(s) requires like 20 seconds in Python. This could be optimized further, but I won't do it. 20s is acceptable when the whole table will be stored as a file anyway.

 

[Herbert Kociemba]

Sound as if you make progress! Storing 5 values instead of 4 in a byte is just for fun I think . The saved memory is not very inpressive in absolute values (just some KB).

 

[Renslay]

Sound as if you make progress! Storing 5 values instead of 4 in a byte is just for fun I think . The saved memory is not very inpressive in absolute values (just some KB).

The whole 2x2 sym table is just for fun, I did it because I wanted to do it, not because it's necessary in anyway. A full distance table is good enough on it's own, even with full blown distance values (without the mod 3 trick), as my first software iteration shows.

It was more about the journey itself, finally I understand how sym coordinates work and able to demonstrate it with a working software.

And I cannot stress this enough: you provided an awful lot of help! I am honored and grateful

 

[Renslay]

Sound as if you make progress! Storing 5 values instead of 4 in a byte is just for fun I think . The saved memory is not very inpressive in absolute values (just some KB).

I have another question. The entire purpose of the move tables is that I have the permutation and orientation “neighbours” pre-computed. Forgetting sym coords for a minute, if I have a cube state (x,o) with permutation and orientation raw coordinates, I can ask which move would bring the cube closer to the solves state. I DON’T have to “reconstruct” the cube (get the x-th permutation and o-th orientation), apply a turn to get the new permutation and orientation, calculate their (x*, o*) coordinate, and ask the distance of the cube according to said coordinates. INSTEAD, x* and o* can be get directly from the move tables.

However, with sym coords I cannot avoid to “reconstruct” the cube. If I have the raw coordinates (x,o), I can ask for the sym coords ((y,s),o). For the next step, I have to “reconstruct” the cube, so I can apply the inverse of s to get the new orientation o’, and bring the cube to ((y,id),o’) state (and then I can ask the distance of this this cube in the reduced distance table using y and o').

I can still use the move tables to ask for the raw coordinates of the neighbours, but I’m no longer avoiding a “reconstruction” step. A cube with sym coords y and o has a neighbour with coordinates y* and o'*, not o*.
How can you go from o to o’* without applying calculations on permutations and orientations directly? Do I have to build yet another table that has a size of 3^6*6, which gives me o' given a raw orientation coordinate o and a sym s?

(If I have to reconstruct a cube, I might as well drop the move tables anyway. I know for the 2x2 these are all irrelevant, but I want to go with the "efficient" way anyway.)

EDIT - okay, for generating the distance table move tables are important, so I won't drop them.

 

[Herbert Kociemba]

However, with sym coords I cannot avoid to “reconstruct” the cube. If I have the raw coordinates (x,o), I can ask for the sym coords ((y,s),o). For the next step, I have to “reconstruct” the cube, so I can apply the inverse of s to get the new orientation o’, and bring the cube to ((y,id),o’) state

I do not exactly understand the problem you have. But eventually you do not use "move" tables for the conjugation with the symmetries for the orientations. So you should have some twodimensional array a[0..3^6-1,0..5] where you have precomputed for each orientation o and each symmetry s your o'. This should be completely independent of the the permutations or you made something wrong with the way you defined the orientations.

 

[Renslay]

I do not exactly understand the problem you have. But eventually you do not use "move" tables for the conjugation with the symmetries for the orientations. So you should have some twodimensional array a[0..3^6-1,0..5] where you have precomputed for each orientation o and each symmetry s your o'. This should be completely independent of the the permutations or you made something wrong with the way you defined the orientations.

So, without sym coords, these are the steps of the main algorithm that looks for a solution:

1. Start with a given cube, calculate its raw coordinates (x,o).

2. Look up the distance at position (x,o), which is D[x*N+o], where N is the number of orientations, 3^6.

3. Look at all the move-neighbours (x*,o*). x* can be looked up at the permutation move table M. For example, M[x,U2] gives the U2 neighbour of permutation x.
o* can be fetched similarly.

4. Get the different distances for each (x*,o*).

5. select the raw coordinates with the smaller distance, continue the search from here.



Now, here is how I do the same with sym coords:



1. Start with a given cube, calculate its raw coordinates (x,o).

2. get the sym coord of x, which is (y,s)

3. construct a cube state C with permutation and orientation (X, O) which has raw coordinates (x,o).
C actually contains 2 vectors of 2*7 elements.

4. apply the inverse of s, which calculates C’ = S_inv*C*S, following cube multiplication rules for getting new permutation and orientation vectors (with new raw coordinates (x',o')). C’ has the sym coords ((y,id),o’), but we are only interested on the orientation o' of this new cube state (y is already known).

5. Look at the distance value of (y,o’).

6. get the move-neighbours of (x,o), and calculate their distances in a similar way that step 2.-5. here. The rest of the steps are similar.



What bothers me is step 3.-4. I think this is what should I do instead:



1. Start with a given cube, calculate its raw coordinates (x,o).

2. Get the sym coord of x, which is (y,s)

3. From a pre-computed table (o,s) -> o’, get the modified orientation o’. (Which is the conjugate s_inv * o * s on an orientation alone. Is this independent of the permutations? So, for cube C with different permutations but the same orientation, s_inv * C * s would yield the same o’ ? It's 4am here so I'm a bit tired to think it through...)

The rest of the steps are similar: get the move-neighbours and fetch their distances after transforming their raw coordinates to sym coords.



My question previously was about the construction of such (o,s)->o' table. But if I understand it correctly, this is exactly what you suggest.

 

[Renslay]

So you should have some twodimensional array a[0..3^6-1,0..5] where you have precomputed for each orientation o and each symmetry s your o'. This should be completely independent of the the permutations or you made something wrong with the way you defined the orientations.

Now here is the thing I don't understand.

Let's see the cube state after an F move. I have 4 corners that are still well oriented (there are four 0s in the orientation vector: all corners at the back positions).
If I apply a CW rotational symmetry, it means I conjugate the cube with a diagonal axis rotation. It is the same as if I rotate the cube along this axis, apply an F, and then rotate back.
The resulted cube is the same as if I did an R move, and the resulted orientation vector has still four 0s (though at different vector positions).

Now, let's see a different scramble. I do a U F turn. The orientation vector is the same as before. Four 0s, all at the same positions as we see in the case of the F cube.
But if I conjugate with the axis-rotation, the result is the same as if I did a F R. The conjugated orientation vector is different, I only have two well-oriented corners!

So I don't understand your statement above: the result of o' = (o, s) depends on the permutation!

My orientation vector is defined in such a way that the i-th element of the vector shows the orientation at corner position i.
For example, an F move on a solved cube or an F move on a <U, F2, R2> scrambled cube would yield the same orientation vector.

 

[Herbert Kociemba]

Since I only did the work for the standard corner orientation on 3x3x3 (where this works fine) there are two possibilies:

1. The approach does not work with the new orientation system I suggested , then I also would be interested why not.
2. You did not find the right approach yet, then I hope we can solve this together.

Let's see the cube state after an F move. I have 4 corners that are still well oriented (there are four 0s in the orientation vector: all corners at the back positions).

Why 4 corners in the back? The DLB corner is not part of the orientation vector in the way I think of it.

Now, let's see a different scramble. I do a U F turn. The orientation vector is the same as before. Four 0s, all at the same positions as we see in the case of the F cube.

I do not understand this. The U turn changes the orientation of the ULB and UBR corner, so only the DRB corner stays 0.
Or are you talking about the "standard" corner orientation definition? Then the axis rotation you propose is forbidden. You may only apply the 16 symmetries which fix the UD-axis here.

 

[Renslay]

Since I only did the work for the standard corner orientation on 3x3x3 (where this works fine) there are two possibilies:

1. The approach does not work with the new orientation system I suggested , then I also would be interested why not.
2. You did not find the right approach yet, then I hope we can solve this together.

Why 4 corners in the back? The DLB corner is not part of the orientation vector in the way I think of it.

My mistake. I meant 3 correctly oriented corners. DLB is not stored in any way.

I do not understand this. The U turn changes the orientation of the ULB and UBR corner, so only the DRB corner stays 0.
Or are you talking about the "standard" corner orientation definition? Then the axis rotation you propose is forbidden. You may only apply the 16 symmetries which fix the UD-axis here.

Yes, at one point I went back to the standard orientation definition, U/D sides as references for U/D stickers.
None of the symmetries work generally, i.e., for any s symmetry, I can find c1 = (x1,o) and c2 = (x2,o) such that conjugating with s gives c1' and c2' cubes with different orientations.

EDIT: mirroring along the BL-FR plane seems to work. I guess this is the only one (and id) within the 6 symmetries that's part of the 16 symmetries you mentioned.

Should I go back to the more symmetric corner orientation definition? My problem with that is that it's hard to see and test the orientations of different cube states.

 

[Herbert Kociemba]

You definitely have to use the new orientation system to make the conjugation work. Maybe for testing it is easier to use this alternative reference system you found yourself instead of the method with the circles i described.

 

[Renslay]

You definitely have to use the new orientation system to make the conjugation work. Maybe for testing it is easier to use this alternative reference system you found yourself instead of the method with the circles i described.

Thank you! I need a short mental break before I return to the new orientation system and test it.

I need the alternative reference system anyway, because the user can define a cube by setting the sticker colors; and I have to build a permutation and an orientation vector from that.

Maybe for testing I'll build a method that converts from one orientation system to another (with a given permutation of course).

 

[Herbert Kociemba]

that converts from one orientation system to another (with a given permutation of course).

Should be easy. At each corner position you just have to add some number mod 3.

 

[Renslay]

Should be easy. At each corner position you just have to add some number mod 3.

I am happy to confirm that with the new orientation definition, the system works. \o/

The orientation is defined by the moves (for example, the U turn has the move cycle URF -> +2 -> FLU -> +1 -> ULB -> +1 -> RUB -> +2 -> URF).

But I also needed a method to define the orientation by the stickers only, and I came up with the following solution:

The reference sides/stickers are ULB, RUB, URF, FLU, DRB, DFR, DLF (almost like the old definition, except for UBR and UFL).
Each cube has a reference sticker (its first letter), and each position has a reference side (also the first letter).
The orientation of a corner c at position p is determined by their references' relative state.
If they are matching, the orientation (the p-th number in the vector) is 0.
If the corner's reference sticker is twisted clockwise compared to the position's reference side, the orientation is 1.
Counter-clockwise case means an orientation number 2.
For example, after an F2 turn, at position DFR sits the corner FLU, and we compare sticker F to side D at this position.
Since it's twisted clockwise, the orientation is 1, which is the 5th position (DRF's position) in the orientation vector.

This is almost exactly what we discussed before; I just needed to realize that instead of UBR I have to use RUB. For the corner itself, I have to keep an eye on its R sticker. Similarly, at the RUB position I have to use the R side as reference. Similar changes to UFL; but for all the other corners and places the old definition is equivalent.

The rest came naturally from this.

 

[Herbert Kociemba]

Nice. So compared to the standard definition you just have to add +1 mod 3 for the UBR position and +2 mod 3 for the UFL position, the other orientations are the same.