I'm currently creating a Rubik's Cube Solver and am having some difficulty generating pruning tables. Pruning tables contain information that is used to prune search tree branches, exponentially speeding up the search process for solving algorithms when searching for a solution.
How can I generate a pruning table for all corner sub-states using only double turns for my Rubik's Cube Solver? There are allegedly 96 sub-states the corners can be permutated in belonging within their tetrads... I have a function that identifies which corners are in which tetrad but when applying a double turn, the result is technically the same! Any help, advice, recommendations are greatly appreciated.
p.s. not interested in another solving method besides Thistlethwaite's at the moment. I am implementing all solving methods, it's just Thistlethwaite's algorithms turn.
The idea of phase 3 of Thistlethwaite's algorithm is to produce a cube position that is solvable with half turns only. For that you need to know what corner permutations are possible with half turns, and that is trickier than it seems.
The obvious restriction is that the corners are split into two orbits, which I call tetrads because they are arranged like tetrahedra. The pieces at locations URF, ULB, DLF, DRB can be permuted by half turns, but will never be intermingled with the pieces of the other tetrad locations UFL, UBR, DFR, DBL. So one aspect of phase 3 of the algorithm is to put the corner pieces into their correct tetrads. This reduces the number of states that the cube can have by a factor of $\binom{8}{4} = \frac{8!}{4!4!} = 70$.
The two tetrads cannot be individually permuted using half turns only. In fact, once the permutation of one tetrad is given, only $\frac16$ of the permutations of the other tetrad are solvable by half turns. The factor $2$ of this is due to permutation parity - every half turn consists of two swaps so is an even permutation which means the corner permutation must be even to be solvable. The factor $3$ is more elusive. I have called it tetrad twist, which is a bit misleading, but it does in a way encapsulate how one tetrad is oriented with respect to the other, and only one way is solvable with half turns.
One way to look at it is as follows. 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 an 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.
Here is another way to see it. It is easy to solve one tetrad using half turns, as any two corners of a tetrad can be swapped with a single move. The sequence R2F2R2U2 swaps only URF-ULB, DLF-DRB, so it moves one tetrad with respect to the other. Using this (and its rotations F2U2F2R2 and U2R2U2F2), it is easy to solve one piece of the second tetrad. If the position you started with is in the square group, then the other three corner pieces of the second tetrad will be solved automatically. Note that 3 pieces normally have 3!=6 possible permutations, but only one of these is possible in the square group. This is a combination of the parity restriction and this elusive tetrad orientation.
Now you know where it comes from, you still need to get a way to associate some twist number to any random position in phase 3 in a consistent manner so that you can use it as an index into your phase 3 pruning table. With consistent I mean this: Suppose some position p in phase 3 can be completely solved with the some move sequence, say abcd. Let q be the phase 3 position that is completely solved by the moves abcd R2. Then p and q must have the same twist number, because it takes the same moves to get it to a square group position. One conceptually simple method is to simply do what I described in the previous paragraph. For any phase 3 cube position, temporarily solve 5 of the corner pieces and encode the permutation of the remaining 3 pieces to represent the combined tetrad twist and permutation parity of that original position.