Contact

HTA (Human Thistlethwaite Algorithm)

From TA to HTA

In 1980, Morwen Bernard Thistlethwaite developed a unique algorithm (in terms of computer algorithm) for solving the 3x3x3 Rubik's cube. Thistlethwaite's algorithm (TA) is solving the puzzle in 4 steps, and its uniqueness lies in that unlike other known methods back then, the goal of each step is not to solve several pieces but rather the reduction of possible moves (see Rubik's cube notation).

All possible moves (18 in total) of outer layers are allowed in the first step. In the second step, F/F' and B/B' moves are not permitted anymore, only F2/F2' and B2/B2' are allowed. Third step is forbidding R/R' and L/L' moves. In the fourth step it is only possible to keep solving using the double moves (6 in total) such as U2, B2 etc.

Consider a set of all allowed moves M. Then for the first step M₁ we can write M₁ = {U,D,R,L,F,B} (because U U = U2 = U2' and U2 U = U'). For the next steps we will get M₂ = {U,D,R,L,F2,B2}, M₃ = {U,D,R2,L2,F2,B2} and finally M₄ = {U2,D2,R2,L2,F2,B2}. It can be seen that the elements/moves of a set M_n+1 form a subset of M_n for n = 1,2,3. Inner layer moves are combinations of outer layer moves with a subsequent cube rotation, thus we won't take them into further consideration. Individual steps of TA can be schematically depicted as follows:

Verbal description of the goal of each step is as follows:

• edge orientation
• corner orientation, putting edges into E slice
• getting corners into tetrads, even permutation of corners, putting edges into M and S slices
• cube solution

While there are more than 43·10¹⁸ puzzle combinations/states before the first step of TA, there are only less than 1·10⁶ of them before the fourth step. More specifically, there are 2 048 states in the first step for a cube to be solvable in the next step. For the second, third and fourth step there are 1 082 565, 29 400 and 663 552 of such states/algorithms (in terms of cubing algorithm). Even though such a number of algorithms is impractical for humans, TA is very suitable for computers.

M. B. Thistlethwaite himself proved that for the first step the maximum number of moves required is 7, and for the next steps it is 13, 15 and 17, respectively. Therefore, TA solves the cube in a maximum of 52 moves. Later an optimal solution for each step was found: 7, 10, 13, 15 - so 45 moves in total. Average number of moves for optimal TA is 31.3.

What makes TA interesting (among others) is a fact that we can look at each of its step as being a specific puzzle because in the next steps we can not scramble what has been already achieved in the previous steps. In other methods, usually we have to scramble something already being solved in order to continue solving further pieces.

In 2002, Ryan Heise was thinking how could people solve a cube using the TA method. In 2003 he described the HTA (Human Thistlethwaite Algorithm), which is a version of TA suitable for humans.

Since we will often refer to a face or a layer, the difference between these two terms is illustrated on the following two simulators:

top face		top layer

HTA: step 1, move set {U,D,R,L,F,B}

This step is sometimes called an edge orientation and is probably the most difficult step for beginners. It can be profitable to think of two opposite colors as being only one color. Opposite colors on the simulators below are red and orange, blue and green, yellow and white.

In order to orient the edges correctly, we must first know if an edge has a good orientation or if it has a bad orientation. When considering fixed cube orientation (i.e. don't do x, y nor z moves) and only a move set {U,D,R,L,F2,B2}, then a correctly oriented edge is the one which can be placed to its position without being incorrectly oriented (of course you don't have to do that physically, it is sufficient to imagine needed moves in your head). In other words, a correctly oriented edge is the one for which an insertion to its position with a correct orientation requires an even number of F/F' and B/B' moves (if that sum is an odd number then it is an incorrectly oriented edge). There is always an even number of incorrectly oriented edges on a cube.

This step is the only one in which we can change an edge orientation from good to bad and vice versa. Let's demonstrate what an F (also F' and B/B') move does from an edge orientation point of view. Note that this move is omitted in the next step of HTA. Gray-colored pieces on the simulator aren't important as of now.

We can see that an F move changes the orientation of 4 edges in a turning layer because after this move it is not possible to place either edge to the correct position with a correct orientation using only a move set {U,D,R,L,F2,B2}. However, if we execute F2 instead of F in the beginning position of the simulator, edge orientation won't change (try to solve the edges back using only a move set {U,D,R,L,F2,B2} and fixed cube orientation; one such solution is U L2 D R2 B2 U L2 R2). An F' move again changes the orientation of 4 edges. You can simulate the B/B2/B' moves by executing a y2 rotation first followed by a given move - B and B' changes the orientation of 4 edges in a turning layer, B2 = B2' doesn't.

On the next simulator we see (without a need to make any cube rotation) that an edge at the UF position is incorrectly oriented (because we can imagine red center as an orange one, and yellow center as a white one - then the edge is placed at its position but with an incorrect orientation), an edge at the UB position is correctly oriented (because an edge color in the top face is the same as a center color in the top face (when considering that red center is orange center)).

There are few tricks how to recognize when an edge is incorrectly oriented. I know only one of them (you don't need to remember it but if you do, you will find out faster whether an edge is correctly oriented or not): if an edge located in the top or bottom layer has a sticker corresponding to a color of the top or bottom center, and this sticker is facing up or down (i.e. not facing towards you, away from you, left or right), then it's an edge with a correct orientation.

Most of the time there will be at least 4 incorrectly oriented edges at the beginning. It may be useful to insert 4 incorrectly oriented edges to the front or back layer immediately, and orient them subsequently. An advantage of such procedure is that we don't have to determine and remember the orientation of all 12 edges at once, we only have to do that for 8 remaining edges. Edge orientation is shown in the following example.

The trick mentioned above implies that an edge at the UR position is incorrectly oriented (if you don't want to remember the trick it is sufficient for this edge to imagine a U move in your head and red center as an orange one - then the edge is at its position but oriented incorrectly), by a move [1] we are placing it to the front layer. Edge at the UR position is incorrectly oriented, therefore we are placing it to the front layer by a move [2]. However, by doing so an incorrectly oriented edge (now at the UL position) has been taken out of that layer. Incorrectly oriented edge at the UL position is being placed to the front layer by a move [3]. Without any cube rotation the trick implies that an edge at the DR position is also incorrectly oriented. It is being inserted to the front layer by a move [4]. Edge at the DR position is incorrectly oriented, thus it is being placed to the front layer by a move [5]. Then move [6] is correctly orienting the edges in the front layer. At this moment it is convenient to find out the orientation of all remaining edges (meaning the edges in the back and middle layer). Other incorrectly oriented edges are located at the UR, UL, DR positions (for middle layer), BR, BD, BL (for back layer). By a move [7] we are placing an incorrectly oriented edge to the BU position, but at the same time another incorrectly oriented edge to the FU position. By a move [8] we are correctly orienting the edges in the back layer. Now there are only 2 incorrectly oriented edges on a cube at the FU and DR positions. In case of only 2 incorrectly oriented edges, insert one of them to the front or back layer (done due to an edge at the FU position). Next, change the orientation of edges in that layer; see move [9] - meaning that 3 correctly oriented and 1 incorrectly oriented edges will become 3 incorrectly oriented and 1 correctly oriented edges. By a move [10] we are inserting the last incorrectly oriented edge from DR position to the front layer, then all edges are being correctly oriented by a move [11].

HTA: step 2, move set {U,D,R,L,F2,B2}

This step is also known as a Domino reduction due to its similarity with the Rubik's domino. While in TA this step is solved in one stage, in HTA it is solved in two stages: first place the edges belonging to the top or bottom layer to these layers, then orient corners in these layers. Consequently, top and bottom faces will consist of two opposite colors only.

Edges

Similarly to the previous step, we don't have to distinguish between opposite colors now. Intuitively insert the edges to the top layer first, followed by the bottom layer. Cube rotations x2, y2 and z2 don't affect anything from the allowed-moves point of view.

Edges at the RF and LF positions will be placed to the top layer, that is happening in moves [1-3]. Cube rotation is made in move [4] in order to start placing edges to the current top layer. An edge from the LF position is being inserted to the top layer (moves [5-7]) without affecting edges in the bottom layer. Finally, an edge from the RF position is being placed to the top layer (moves [8-10]).

Corners

Similarly to the edges, in case of corners we don't also need to distinguish between opposite colors at this stage. Cube rotations mentioned above apply to corners as well.

For the first two examples: by a move [1] a misoriented corner from bottom layer is being oriented. Setup move [2] is used to place that corner to the same layer (i.e. right or left one) in which another initially misoriented corner is. 2 initially misoriented corners are being swapped in move [3]. Remaining two moves are inverse to moves [1-2] and they are used to orient misoriented corner initially located in top layer.

In the third example, any incorrectly oriented corner is being inserted to the bottom layer by a move [1]. Although we can't get an initial state of two previous cases, at least we can orient a corner at the DRF position after move [2] - see moves [3-7] which can be also found in the first example. After move [7] we could continue by L2 D' U' for example, and that state would be converted to the second example.

From examples it is clear that we are trying to orient two corners at once - one from the bottom and the other from top layer. If both corners can't be oriented simultaneously (i.e. when only 3 corners (and sometimes 6 corners as well) are incorrectly oriented at the beginning), then orient at least 1 corner while leaving the other one still incorrectly oriented. Afterwards apply the technique from the first two examples above to orient 2 corners at once.

HTA: step 3, move set {U,D,R2,L2,F2,B2}

Unlike TA, in HTA we will solve this step in two stages again. First a corner permutation will be done in stage 1, followed by an edge orientation in stage 2. A so-called 3-axis edge orientation is meant by an edge orientation in this step because until now a so-called 2-axis edge orientation has been made so far (1-axis edge orientation has been made in step 1, 2-axis edge orientation has been made in step 2). Essential, however not necessarily sufficient, goal is to get opposite colors not only in the top and bottom face but also in the front and back as well as right and left face. We can encounter a step designation Half Turn Reduction (HTR), also known as a double moves reduction or a 180 degree turns reduction.

Corner permutation

Start by intuitive separation of corners - insert corners belonging to the top layer to that layer (in this stage we will distinguish between opposite colors so e.g. red and orange are two different colors). It means that corners belonging to the bottom layer will be located in that layer. There are several cases how corners can be mutually permuted. In one of them a diagonal swap of two corners in both the top and bottom layer is needed.

For all the other corner permutation cases we can use at most two applications of the following algorithm (and setup moves). Suppose that corners are solved and we want to swap only those at the URF and URB positions (the simulator is offering a view from below).

Both mentioned corners are being inserted to the bottom layer in the first move. Wanted corner is being placed to required URB position in moves [2-3]. However, current corners at the URB and DLF positions can't be easily paired up and inserted back to the top layer so that the corners at the top right positions would be swapped as a final consequence. Therefore the positions of both mentioned corners are being swapped in moves [4-6]. By a move [7], given corners are being paired up again. Corners of interest are being inserted back to the top layer in moves [8-9]. We can notice that also diagonal corners at the DRF and DLB positions have been swapped as a side effect to the swap of adjacent corners at the URF and URB positions. For completeness' sake the remaining corner permutation cases and their solutions are illustrated below (if your case is missing then make an x2 rotation and/or U/D moves).

It's not necessary to solve corners relative to centers in this stage. Instead, it's sufficient to get a state in which all 3 colors on each corner correspond to a color of the center or a color of opposite center (except for the case in which a diagonal swap of 2 corners is needed in only one layer). From now on, the corners are solvable using a move set {U2,D2,R2,L2,F2,B2}.

Edge orientation

A so-called 3-axis edge orientation applies to an edge whose both colors correspond to a color of the center or a color of opposite center. Consequently, such edges will be solvable in the next step using a move set {U2,D2,R2,L2,F2,B2}.

There is an even number of incorrectly oriented edges in the top and bottom layer when considering the concept of 3-axis edge orientation. On the simulator below, these edges are at the UF, UR, UB, UL, DF and DR positions.

An M2' move will help us to orient all 4 edges located in this middle (between left and right) layer. By moves [1-2] we are placing incorrectly oriented edges to the DF and DB positions. By moves [3-4] we are correctly orienting 4 edges which were located in the middle layer after move [2]. Now there are incorrectly oriented edges at the UR and DF positions. Similarly to the first step of HTA we can make 4 incorrectly oriented edges out of 2 incorrectly oriented edges. We do this by placing both incorrectly oriented edges to either top or bottom layer (move [5]) so that it is possible to turn the top or bottom (bottom in our case) layer in order to insert two correctly oriented edges to the DF and DB positions (or UF and UB positions in case of turning the top layer) which will become incorrectly oriented after an M2' move. Move [7] is changing the orientation of edges in the middle layer - from 1 bad and 3 good ones as being before move [6] to 3 bad and 1 good edges. Move [8] is inverse to move [6] and is orienting some edges in the bottom layer. Now incorrectly oriented edges are at the UF, UR, UB and DL positions. By a move [9] an incorrectly oriented edge from the UR position is being placed to the DR position. By a move [10] 2 incorrectly oriented edges are being placed to the DF and DB positions. All edges in top layer are being oriented in move [11], all edges in bottom layer are being oriented in move [12].

From now on, the edges (thus a whole cube) are solvable using a move set {U2,D2,R2,L2,F2,B2}.

HTA: step 4, move set {U2,D2,R2,L2,F2,B2}

The last step of HTA will be done in two stages again (unlike TA for which only one stage is enough) - first we will solve corners and then we will permute/solve edges.

Solving the corners is intuitive. When you solve corners in one layer, corners in the second layer will be automatically solved as well. For edges it is convenient to know 2 following algorithms.

We can use them in cases in which we want to swap 4 edges; check out the following 2 simulators.

We see that by the first move we get a state in which 3 unsolved edges are at the UF, UR and UB positions, while 4^th unsolved edge is at the DL position. The meaning of moves [2-4] is to get a state in which it is needed to swap edges at the following positions: UF with UB, and RF with RB.

We can also use them in cases in which we want to solve 3 edges in the middle layer.

We can already solve that state. Solve the Rubik's cube as shown on the last simulator with commentary.

We are starting with corners in front layer; see moves [1-3]. By a move [4] we are solving corners relative to centers. If there are more than 6 unsolved stickers on 3 adjacent faces (the condition is met for front, top and right face, among others), it is advantageous to execute M2 E2 S2 (see moves [5-7]) in order to solve several edges. You don't need to remember this trick - you can continue without it but in this specific scenario it makes a solving faster. Move [8] is a setup move. Now edges can be swapped at the positions UF with UB, and RF with RB (moves [9-14]). Then an inverse move (move [15]) to move [8] is executed. Move [16] is a setup move. Now edges can be swapped at the positions DF with DB, and RF with RB (or a cube rotation can be made in order to swap edges at the positions UF with UB, and RF with RB, just like in the previous case). Edges are being swapped in moves [17-22]. Move [23] is a setup move. The rest of the puzzle is being solved by moves [24-27].

Similar methods

In 1992, Herbert Kociemba published a new computer algorithm. Simply said, Kociemba's algorithm combines first two steps of Thistlethwaite's algorithm into one step (called phase 1) and remaining two steps of TA into phase 2. Kociemba's two-phase algorithm, being based on Thistlethwaite's algorithm, is the result of an expansion of computer hardware to some extent because due to the lack of memory and low-performance processors of computers back then, 4 steps couldn't be combined into 2 phases already in 1980. Phase 1 of Kociemba's algorithm requires 12 moves at most, phase 2 requires 18 moves at most.

Regarding human solving, the most similar method (that I know of) to the Human Thistlethwaite Algorithm method is the 3-Color Method (see also a brief method description) which had been developed and used already in 1980 by Michael Feather. The 3-Color Method is therefore more than 20 years younger than HTA.

The page was graphically improved by Michael Feather.