1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ Some good information that I wasn't aware of before but I am a bit puzzled in how I would go about defining and generating those 96 tetrad states. :P Although what you've written is informative, I do find some of it puzzling... no pun intended haha $\endgroup$ Commented Apr 8, 2021 at 20:35
  • $\begingroup$ @zardoss Have you already done any of the other phases of Thistlethwaite? How do you "define and generate" the states for those phases, and what difficulty are you having with these tetrads that is not present in those? $\endgroup$ Commented Apr 8, 2021 at 20:55
  • $\begingroup$ Hi there, I have fully implemented the necessary checks for each stage of the algorithm. If I were to leave solve the cube using this method, it would most definitely find the solution but of course slowly as it does not have the pruning table for G2 to G3... I'm currently checking for the corners being in their tetrads by checking if specific corner Facelets are specific colors. It's quite a manual process but if it helps, I am able to share that. I am unable to think of a way to apply to same logic when generating all tetrad states for a pruning table. @Jaap Scherphuis $\endgroup$ Commented Apr 9, 2021 at 18:16
  • $\begingroup$ But have you done pruning tables for any of the other stages? I am trying to understand whether you are having trouble with pruning tables in general or if there something specific about these tetrads that is difficult for you. For example, the pruning table in stage 2 for separating the edges for the equator slice from the U/D edges is very similar to separating the corners into their tetrads in stage 3. @zardoss $\endgroup$ Commented Apr 9, 2021 at 18:26
  • $\begingroup$ I currently have one for G2 to G3 which is a basic version of what's required... It has distance values for all corner permutations with the M/S slice permutation arrangements. So 40,320*70 values. However, since there are 96 different tetrad cube substates that are considered as fulfilling G3 requirements, I need to generate those 96 states and set their distance values to 0 in that table. Although unorthodox, I went about the e slice edges for the G1 to G2 table a bit differently. I did a long way of getting the lexicographical order for those substates (Still, it works). $\endgroup$ Commented Apr 9, 2021 at 18:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .