[PYTHON] Let's write a program to solve the 4x4x4 Rubik's Cube! 2. Algorithm

What is this article?

I am currently making a robot that solves the 4x4x4 Rubik's Cube (Rubik's Revenge) and is aiming for a world record. The biggest hurdle in making a robot was to implement an algorithm to solve a 4x4x4 cube in a realistic time and with as few steps as possible. If you look it up, you will find that there are few documents and ancestors about 4x4x4. I am writing this article, hoping that it will be one of such valuable materials. GitHub is here ** The content of this article is not complete. It may contain some inefficiencies. I will add it as needed if it is improved in the future. ** **

↓ Competition 4x4x4 Rubik's Cube and Competition 4x4x4 Rubik's Cube numbered for program production

The whole picture

This collection of articles consists of three articles in total.

1. Overview
2. Algorithm (this article)
3. Implementation

What to talk about in this article

In this article, I will explain in detail the Tsai's Algorithm that I talked about in the previous article.

Actual scramble

For the sake of clarity, this article will use real scrambling. The scramble used (white side is U side, green side is F side),

r2 b2 f2 d2 r2 b2 d f2 d' f2 d b' f' d' f2 r u f2 l d' rw2 fw2 u r' u' d2 fw2 f2 l uw2 d' l u2 fw' r uw2 u2 b l uw' d' rw uw2 b rw r

is. If you have a 4x4x4 Rubik's Cube, please read it while turning it. The state of the cube is as shown in the photo. When you see an image of cubes lined up, think of it as the orientation of this photo.

Phase 0

In Phase 0, you do the following: ** Bring all the center parts of R side and L side to R side or L side ** As an example, in the previous scramble, follow the steps below. rw l' uw r' rw d fw The state after turning is as shown in the photo.

You can see that there are only red or orange in the four center parts of the R and L sides. This is what we are aiming for this time. In the completed state, red and orange parts will be gathered on the R side and L side, respectively (depending on the orientation, of course, for convenience, white is the U side and green is the F side) In this phase, there are no restrictions on the rotation used, and you can rotate it freely. The rotations used are as follows (all types of rotations). r, r2, rw, rw2, l, l2, u, u2, uw, uw2, d, d2, f, f2, fw, fw2, b, b2

Phase 1

In Phase 1, you do the following: ** 1. Bring all the center parts of F side and B side to F side or B side ** ** 2. Separate high edge and low edge ** ** 3. Make the center state of the R and L sides one of the 12 states that can be processed in the future ** ** 4. Eliminate OLL parity ** There are many. Let's turn it with the example scramble for the time being. The procedure is as follows. Turn this step after Phase 0 is over. l2 d2 f rw f2 r2 b2 rw

At first glance, I think that the centers of the F side and B side, and the U side and D side are gathered in the same way as in Phase 0. This is the first goal to be achieved. Second, high and low edges can be a little confusing. It's amakudari, but if it looks like the photo, pair (stick) these two edges without using the inner layer 90 degree rotation (Uw, Rw, Fw). State) Cannot. In future operations, we will limit the use of 180 degree rotation only for inner layer rotation, so we will make it in a state where it can be solved even if that happens. Now, in the photo, the edges with the same color pair are on the same side and in the row. This is a bad situation. I want to avoid this situation. The third is the constraint that the rotation of R, L will not be used in the future (that is, it will be rotated 180 degrees when rotating the R or L surface). If you don't use the two types of rotation, `` `R, L, in short, the center may have a checkered pattern as shown in the photo, or only one face-to-face color may be mixed. Not aligned. Avoid this situation. The fourth is the avoidance of OLL parity, which is a phenomenon peculiar to 4x4x4. In order to eliminate OLL parity, it is essential to turn the inner layer 90 degrees. Therefore, OLL parity is avoided at this point. Specifically, it counts the number of inverted EOs (Edge Orientation), and if it is odd, it has OLL parity, and if it is even, it is not. The rotations used in Phase 1 are as follows. r, r2, rw, rw2, l, l2, u, u2, uw2, d, d2, f, f2, fw2, b, b2```

Phase 2

In Phase 2, you do the following: ** 1. Make a "row" in the center of the side ( F, R, B, L side) ** ** 2. Pair the edges located on the sides ** In the example scramble, follow the steps below. d l2 uw2 rw2 d f' uw2 b

The first goal is the constraint of not using `F, F'' rotation in the future. Make the pattern of the side center aligned or vertically the same color. The second goal is simply to pair the side-located edges (FR, BR, BL, FLedges). If you look at the photo, you can see that the edges at this position are aligned. The rotations used in Phase 2 are as follows.r2, rw2, l2, u, u2, uw2, d, d2, f, f2, fw2, b, b2```

Phase 3

In Phase 3, you do the following: ** 1. Complete 6 centers ** ** 2. Pair the remaining edges ** ** 3. Eliminate PLL parity ** In the example scramble, follow the steps below. l2 u l2 u rw2 d fw2 l2 u b2 rw2 At a glance, you can see that the puzzle is "3x3". This is called "reduction" in Speed Cube terminology. First, the center is complete. Second, all the edge pairing is done. The third is not obvious at first glance. The state of PLL parity, which is a two-point exchange of edges, cannot be resolved without turning the inner layer. In the future, we will arrange the puzzles only by turning the outer layer, so we will eliminate the PLL parity. The rotations used in Phase 3 are as follows. r2, rw2, l2, u, u2, uw2, d, d2, f2, fw2, b2

Phase 4

In Phase 4, you will: ** 1. Bring the stickers that should be on the U and D sides to the U or D side ** ** 2. Eliminate EO ** In the example scramble, follow the steps below. d l' f' d r' l' u2 f' d r b At a glance, you can see that there are only white (the color that finally comes to the U side) and yellow (the color that finally comes to the D side) on the U and D sides. This is the first goal to be achieved. The second is the elimination of EO. From now on, the final phase, Phase 5, will no longer use `` `R, L, F, Brotations (always use 180 degree rotations when turning these faces). Edge reversal (EO) cannot always be resolved without 90 degree rotation of two orthogonal planes. Therefore, EO will be eliminated now. The rotations used in Phase 4 are as follows.r, l, u, u2, d, d2, f, b```

Phase 5

This is the final phase. In Phase 5, you will finally ** complete the puzzle **. In the example scramble, follow the steps below. u r2 u l2 u2 l2 b2 u f2 u2 l2 b2 u' You can see that the puzzles are complete. The rotations used in Phase 5 are as follows. r2, l2, u, u2, d, d2, f2, b2

Summary

In this article, I introduced an algorithm for a computer to solve a 4x4x4 Rubik's cube based on Tsai's Algorithm. In the next article, I will introduce some rough guidelines for actually implementing this and tips on implementation.