Does TRP put edges in different orbits?

[jgouly]

I'm a bit confused by search2. How does it achieve: "1. Orient corresponding low and high edges the same way. Make sure that the number of misoriented edges is a multiple of 4. (Instead of requiring that all edges are oriented correctly, we require only that a low edge and its corresponding high edge be oriented the same way: both correctly or both incorrectly.) " (Taken from http://cubezzz.dyndns.org/drupal/?q=node/view/73#comment-2588) I think this text means that the pairs of edges have to be in different orbits.

All I can see from Centres2.java is that it cares about 'parity' and flips parity on slice moves. I don't see any mention of orbits.

[cs0x7f]

Yes, it means the pairs of edges have to be in different orbits. However, in this implementation, I do not filter or pruning edge states during phase 2 search. Instead, only centers and the parity of all 24 edges are solved in boolean search2(int ct, int rl, int maxl, int lm, int depth); After search2, I directly check whether edges have been correctly oriented, which is done at https://github.com/cs0x7f/TPR-4x4x4-Solver/blob/master/src/Search.java#L387 .

There're two main reasons why I do not use a pruning table for edges in this step. Firstly, the probability of a random state that have oriented edges (the pairs of edges are in different orbits and the number of flipped edges is even) is about (12! 12! 2^12 / 2 / 2) / (24! / 2), which is only about 1/1320. Secondly, I did not find an appropriate coordinate to efficiently handle "edge orientation." The simplest way I found is to define low/high edges. In this way, the size of the coordinate will be (24!/12!/12!/2) = 1352078, which is much larger than 1320 (and therefore the coordinate is too inefficient). And since there are 2048 different ways to define low/high edges, 2048 different step2 search should be performed for each solved step1 state, which is also not appropriate.

[jgouly]

Thanks for the reply!

Can you give a 'simple' explanation of how symmetry works in solvers?

[cs0x7f]

Well, for 3x3x3 cube, the equivalence of state A and state B is defined as A = S^-1 B S (as introduced in http://kociemba.org/math/symmetries.htm) For 4x4x4 cube, the definition of symmetry is the same as 3x3x3. The only difference is that the calculation can be simplified, since S^-1 gH == gH is established for most of subgroup H and coset gH during reduction procedure. Then, the equivalence of two coordinates can be simplified as aH = bH * S, which is equivalent to the direct cube rotation.

[jgouly]

Thanks, I will have a read of that page. I'm still learning about this group theory stuff (never studied it).

[jgouly]

Can you explain a bit how you actually 'use' this symmetry in the code? The code in https://github.com/cs0x7f/TPR-4x4x4-Solver/blob/master/src/Edge3.java seems pretty complex.