4
$\begingroup$

https://www.jaapsch.net/puzzles/thistle.htm

I'm trying to generate 29400 ($8C4^2 * 6$) indices for each one of the cube states in G2.

$8C4^2$ = 4900 is for solving the corner and edge pieces (forming the 2 corner tetrads and getting the remaining 8 edges into their slices). Then, because of 90-degree left and right face turns, an extra factor of 2 is added due to states with uneven parity. To that, an extra factor of 3 is added which is explained here in a different question which gives all 29400 states.

I've only managed to generate $8C4^2 * 2$ = 9800 states so far (missing an extra factor of 3)

Once the corner tetrads are formed, it's possible to calculate the factor of 3: it's explained here, and the gist of it is that if for example the two tetrads are split to an even and an uneven tetrad like this: (0,2,4,6) (1,3,5,7) then for every permutation of the even tetrad, the uneven tetrad will be in one of 4! = 24 permutations (and vice versa). After solving 5 corners (e.g the entire even tetrad and the first corner in the uneven tetrad) the 3 remaining pieces can be in any one of the 3! = 6 permutations which gives the 2 * 3 = 6 factor (2 for parity).

This works, but only if the 2 tetrads are formed, so it's only relevant to $4!^2$ = 576 states (or 1 of the 8C4 states). The additional factor of 3 in G2 also applies to cube states where the tetrads aren't formed yet.

One work-around is splitting the two corner tetrads into 4 pairs instead, which gives 8C4 * (8C2 * 6C2 * 4C2 * 2C2) * 2 = 352800 unique states instead of 29400, which is less than 8C4 * 8! * 2 but still more than $8C4^2$ * 6.

Is it possible to assign each one of the 29400 cube states in G2 a unique index? I haven't found any implementation of the algorithm that does it yet.

Edit: The issue described in the comments was that the corner permutation had a relation of perm[position] = piece_ind instead of perm[piece_ind] = position

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

This is actually much easier than it looks. You can simply use any consistent method for separating the the tetrad pieces. By consistent I mean that if two stage 3 positions can be brought to a stage 4 position by the same set of moves, then the two positions get the same tetrad twist number. Note however that you don't need to figure out what those moves are, as long as you permute any two such positions in the same way.

Suppose for example that you have labelled the corners so that the pieces belonging to one tetrad are odd, the other are even, as in your example. If the current state of the cube is stored as an array, and the part with the eight corners contains 4, 1, 6, 5, 2, 3, 7, 0. You can simply extract the even numbers in order from left to right to get 4, 6, 2, 0, leaving 1, 5, 3, 7 for the odd tetrad. Put the corners in their tetrads in that order. Then use those for determining the tetrad twist.

I once wrote a Thistlethwaite solver for a coding contest. Here is my code. It is not very readable, since brevity was one of the judging criteria, but it does exactly what I describe above. Then 5 pieces are solved using a method equivalent to applying only half turns, and the permutation of the final 3 corner pieces is encoded as a number 0-5 to represent the tetrad twist and permutation parity.

For completeness I'll describe a nice way to think about this tetrad twist factor 3. Look at the 4 corners that belong in the U face. There are two from each tetrad. Whatever half-turn moves you do, these four pieces will always lie in the same plane - either together in a single face, or in one of the planes diagonally through the cube (e.g. UFL,UBR,DFL,DBR or UFR,DFL,UBR,DBL etc). So once you know the position of one pair, the position of the other pair is constrained. There are 6 ways to choose two out of four objects, so of the 6 places the other pair might be, only 2 are possible in the square group. This is the factor 3 from this phase. You can think of each tetrad having a U/D axis, going through the centre of the face containing its U-pair of corners through to the opposite face. The two tetrads need to have their U/D axes aligned.

Improve this answer
$\endgroup$
7
  • $\begingroup$ I've followed your answer, when I extract the corners from the original permutation into a new array while keeping the relative order (e.g 3 1 0 5 4 6 7 2->0 3 4 1 6 5 2 7) as you described, and solve the even tetrad I get all 4! permutations in the odd tetrad. But, after solving 1 of the corners in the odd tetrad an additional corner is always solved which only gives me 2 out of the 6 permutations (e.g after solving 1: 0 1 2 3 4 x 6 x). What am I missing? It makes sense because once the tetrads are formed only half twists are applied (so only 1/3 of the perms are reachable like in G3) $\endgroup$
    – itaysadeh
    Commented Apr 15, 2021 at 10:33
  • $\begingroup$ I forgot to mention, for a solved cube the corner permutation would be 0 1 2 3 4 5 6 7 $\endgroup$
    – itaysadeh
    Commented Apr 15, 2021 at 15:59
  • $\begingroup$ @itaysadeh Can you tell me what pieces the numbers 0-7 refer to in your implementation, so that I know how the moves permute them? (e.g. 0=URF, 1=UFL,...) $\endgroup$
    – Jaap Scherphuis
    Commented Apr 15, 2021 at 16:02
  • $\begingroup$ I don't store the indices by position, instead I assigned a unique index for each combination of 3 colours. A permutation of 0 1 2 3 4 5 6 7 means that all the pieces are solved. This is the order I used to get 0 1 2 3 4 5 6 7 for a solved state: ULB ULF DLF DLB DRB DRF URF URB. I used (U2/L2/B2) to solve ULB, then (D2/F2) to solve DLF and (R2) to solve DRB. To solve ULF I used the 3 move sequences you mentioned in your other reply. $\endgroup$
    – itaysadeh
    Commented Apr 15, 2021 at 16:15
  • $\begingroup$ After some testing, the (1, 3) and (5, 7) pairs are formed after solving the even tetrad, not the single piece from the odd tetrad. Once that happens all half twist moves will keep these pairs no matter what which causes the problem. Ex: before solving the even tetrad: 0 1 4 7 2 3 6 5, after: 0 1 2 3 4 7 6 5 or before: 0 5 4 3 2 7 6 1, after: 0 5 2 7 4 3 6 1 $\endgroup$
    – itaysadeh
    Commented Apr 15, 2021 at 18:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.