2
$\begingroup$

I'm trying to make a Rubik's cube solver using Thistlethwaite's algorithm. I've already made a working program that solves the cube in 3~ minutes without the lookup tables.

I'll summarize the algorithm to save you time:

There are 4 groups, G0 is any scrambled cube and G4 is a solved cube. Each group has a goal that is reachable only using the legal moves of said group. To get from Gi to Gi+1 you can only use the moves from Gi. This way the cube is solved in groups which makes it easier to find a solution, and each group "contains" the group before it (in G2, G1 is already solved and so on). by limiting the moves of each group, the cube is assured to never un-solve any of the goals that it already reached.

the lookup tables are used as a way to prune the tree out of nodes that lead to "dead ends". if a node is further from a solution, it doesn't need to be checked.

My initial thought was to use a solved cube (G4) and run a BFS that indexes all the possible permutations based on a specific group and their rank (how close they are to a solution). for example G0->G1 can use all the moves, and only needs to worry about edge orientation.

The problem is, I can't just use a solved cube as a starting point, since there are many permutations were G1 would be satisfied besides the solved state.

I then thought about using the permutation of the edges together with the orientation of them to generate an index, but it still leads to the same problem that there isn't a single starting point.

How can I generate a table that tells me based on a position how close or far I am from a solution? (not from a solved cube state, but from a solved group state)

thanks in advance, I hope I was clear.

$\endgroup$

1 Answer 1

3
$\begingroup$

A BFS starting from the solved cube is the way to go. However, you don't use the complete cube but instead ignore all the aspects that are not affected by the current stage of the algorithm.

In the first stage, where the edge orientations get solved, the only aspect of the cube that you look at are those edge orientations. Ignore the corners, and think of all the edges as being identical pieces so that their permutation is irrelevant. Of course the edges still move around when a move is done, but you cannot distinguish one edge piece from another. Only their orientation matters, so you can still see whether an edge is flipped or not.

Do a BFS with such a simplified cube to build your pruning table. The state of the cube can be uniquely encoded into an 11-bit integer, where each bit is the orientation of an edge at some location on the cube. That integer is the index into your pruning table. The table will store the distance from solved for each state of this simplified cube. Each time the BFS encounters a cube state it has not seen before (the associated table entry has not yet been filled), it then stores the current distance from start into the table. It is basically generating a God's Algorithm table for this simplified cube.

You will need to define what the edge orientation is on your cube. It depends on which pair of opposite faces gets restricted in $G_1$. Let's say it is F and B. On the simplified edge-orientation-only cube any moves in G1=<U,D,R,L,F2,B2> do not flip any pieces (though they are still moved around). The moves F, B, F', and B' however will each not only move four edges around, they also flip those four moving edges. With this definition you can build your pruning table through a BFS search.

When you want to solve a normal cube, and use this pruning table to solve the first stage in the algorithm, you will need to be able to look up the normal cube in your pruning table. So you need to extract the edge-orientation-index from it. For any edge, imagine bringing it to its home location using only moves from $G_1$. Once it is in its home location you can easily tell if it is flipped or not by whether its colours match the face centres. Since the $G_1$ moves did not affect its orientation, you now know whether the edge is flipped even if it was not at its home location.
When you have determined the orientation of all the edges of your cube, you can set the simplified edge-orientation cube to that state, use the pruning table to find a solution for this stage, and then apply this solution to the original cube.

The other stages of the algorithm can be done in essentially the same way, generating one or more pruning tables using a simplified version of the cube that only encodes the aspects being solved in that stage. The most difficult aspect to encode into a pruning table index will be what happens to the corner permutation in the third stage.

For each stage you can either generate a single pruning table, so that solving that stage for a real cube is essentially a God's Algorithm set of table lookups, or you can use several pruning tables, in which case solving that stage will involve a search using those tables (i.e. IDA*, iterative deepening A* search).

I presume you have found the page on my website about the Thistlethwaite algorithm. Another page that might be helpful is the page about computer cubing which has brief descriptions of the techniques involved.

$\endgroup$
7
  • 1
    $\begingroup$ I hope the tag worked, I'm not familiar with this stackexchange, but I wanted to say thank you for your comment and explanation. I've managed to create the G0->G1 table for now and it boosted performance by a lot more than I expected (even just for G0-G1). I also wanted to say that I've been using your site for the past few weeks and it's great, it really is a treasure. I can tell you're passionate about this subject and it really shows. Is there a page about the maths involved in a rubik's cube? or any other articles you think would be relevant? $\endgroup$
    – itaysadeh
    Feb 10, 2021 at 16:20
  • $\begingroup$ @NULL Two pages of mine that you may like are Useful Mathematics and Group Theory for Puzzles. $\endgroup$ Feb 10, 2021 at 21:52
  • $\begingroup$ I noticed that in a search the G0-1 table actually makes it slower - the moves UBFD can only be solved after 4 moves for example, but the distance in the lookup table for it is 2. I realised this happened because, for example, the moves LFLUBD will override the previous distance of 4 with a 3, because up to the first U move the cube was in a solved stayed, so the first U move had a distance of 1, and a distance of 3 after the BD moves. The issue is, technically it might be correct? different permutations of the same ID can have different distances. Is this right? Could you share any insights? $\endgroup$
    – itaysadeh
    Feb 13, 2021 at 16:00
  • $\begingroup$ @NULL I do not understand what kind of search you are doing and what you mean with "different permutations of the same ID". You seem to be confusing the state of the cube with a move sequence. A particular edge orientation state can be reached by many cube sequences, but the pruning table should hold the smallest length of all possible move sequences, so that when you look up a state the value tells you that it takes at least that number of moves to solve the cube because it takes exactly that many moves to solve only the edge orientation.. $\endgroup$ Feb 13, 2021 at 16:34
  • 1
    $\begingroup$ @jennie There was a cube programming contest in which my implementation of the Thistlethwaite algorithm came third. Length of the program mattered, but my program is still fairly readable unlike most other entries. It contains a few tricks that may be hard to understand, especially in stage 3 of the algorithm, but overall it is a useful example to look at. $\endgroup$ Nov 24, 2021 at 21:34

You must log in to answer this question.

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