Kozenba’s two-stage algorithm
- Public id: Rand_cs
This article specifically introduces a specific rubik’s cube reduction algorithm – Koxianba’s two-stage algorithm, part of the relevant content in the previous chapter, mainly the direction of the definition of that piece, not to see the suggestion to look at:
Two-stage, as the name suggests, problem solving is divided into two steps, with one goal completed and then the final recovery. A telling metaphor for the two-stage algorithm is that solving a Rubik’s cube is like a boat trying to reach a fixed destination on a vast ocean. The two-stage algorithm is to first let the boat to a fixed special water area, and then to the final destination, which is obviously much easier than directly looking for the destination.
Figurative to figurative is abstract, but let’s look at it concretely.
First, an overview
In order to facilitate the narration and avoid confusion, we define the randomly disrupted Rubik’s cube as the random state or initial state, the states in the special water area as the target state, and the destination as the restore state.
The initial state can be viewed as a function ofU, R, F, D, L, BThe composition of these six fundamental rotations, and the group generated by these six rotations is denoted as
.
The target state defined by Kosemba is generated by the combination of U, D, L2, R2, F2, B2, The same notes for G1 = ⟨ U, D, L2, R2, F2, B2 ⟩ G_1 = \ langle U, D, L2, R2, F2, B2 \ rangleG1 = ⟨ U, D, L2, R2, F2, B2 ⟩.
ⅰ Properties of target state
Remember from the previous article how we defined direction when counting states? Let’s review again:
-
The edge has two states, flip is 0 and flip is 1. Only the rotation of F and B layers can change the direction.
-
The Angle block has three states: untwisted is represented by 0, clockwise is represented by 1, and counterclockwise is represented by 2. Only U, D layer rotation does not change the direction of the Angle block.
The target state is generated by six rotations U, D, L2, R2, F2, B2, which do not change the direction of the corner block and the edge block. Because no matter how it rotates, the U plane or D plane owned by the corner block is always in the U plane or D plane, so the direction remains the same. The direction of the edge block will not change, because only the rotation of F and B will cause the change of the direction of the edge block, and the continuous rotation of F2 twice, flipping and then reversing the edge block is equivalent to unflipping, so the direction of the edge block will not change. These six rotations also do not bring the middle block to U or D, so the middle block can only be in the middle.
Therefore, the nature of the target state is summarized as follows:
- The direction of edge block and corner block remains unchanged, that is, the sum of their direction values is 0.
- The middle block in the restore state is in the middle
ⅱ Search algorithm
Kosemba’s two-stage algorithm uses the IDA* algorithm, or iteratively deepened search algorithm, and IDA* algorithm is used in both stages.
IDA*, there’s another A* algorithm that you’re probably not familiar with, and there’s nothing mysterious about it, but just A little bit. A star is A generalized search with heuristic functions. IDA* is a deep search with depth limits and heuristic functions. So far, detailed explanation please baidu CSDN.
In general, wide search can find the shortest path, deep search can not, IDA* although the use of deep search, but it has a depth limit, also can find the shortest path. Let’s say I search at depth 1, I don’t find it, I search again at depth 2, and so on, I get the shortest path.
Therefore, the corresponding shortest path can be obtained in both stages, and the goal of each stage can be achieved with the minimum number of steps, but will the combined solution be optimal?
And the answer is no, because the optimal solution for phase two is relative to phase one, for example
Both stages are optimal, just like the distance obtained by method 1 above, but the two stages together are obviously not the shortest distance, and the shortest line segment between two points should be method 4.
So how do we solve this, how do we get a better or even optimal solution? Also as shown in the figure above, we deepen the search depth of the first stage. Although the path of the first stage is longer, the second stage may find shorter paths, so that their combined edges may be better. In this way, the optimal solution can always be found step by step. That is to say, Kozenba’s two-stage algorithm may not find the optimal solution in a single search, but it will be able to find the optimal solution as long as it is given time. But for Kozenba algorithm is not used to find the optimal solution, the purpose is to find a group of relatively optimal solution in a short time.
For Koxianba’s two-stage algorithm should have a very intuitive basic understanding of it, if it is not clear, and then for magic friends to give a very graphic example. The CFOP reduction formula we generally use, F2L should be OLL and PLL, right? If we normally follow the FORMULA of CFOP, the optimal solution is obtained in these stages, and the sum of them is relatively optimal. But if we take a few more steps in F2L, it’s possible to jump O or even jump P, which saves a lot of subsequent rotation steps and gives us a better solution.
The above example of the shortest line between two points, metaphorically, the actual situation is a bit different, said in front of the two stage algorithm is a special water as the boat first, then to the destination, but in some cases the shortest path may simply not passed through the waters, if or specially waters, nature also won’t get the optimal solution. Does that conflict with the above? No, the restore state is actually one of the target states, right? So if you solve stage one and you find that you’ve already restored, the steps required for stage two go down to zero, then that’s the optimal solution. It’s like finishing F2L to find out that jump O and P have been restored.
Ok, so that’s a summary of Kozenba’s two-stage algorithm, which should be easy to understand. Here is the algorithm details, a lot of interested friends can see, not interested in rubik’s cube to understand this step is probably enough.
But learn computer, on the rubik’s cube reduction algorithm is still worth a look. The number of states of the Rubik’s cube is much larger than that of the eight digits. Moreover, the Rubik’s cube is square and has many special properties that can be used to optimize the algorithm. Let’s take a look at the following:
Define rubik’s cube
Ⅰ block level
To define a Rubik’s cube, the basic elements, such as diagonal block and edge block, can be numbered as follows:
The code is shown as follows:
typedef enum {URF,UFL,ULB,UBR,DFR,DLF,DBL,DRB} Corner;
typedef enum {UR,UF,UL,UB,DR,DF,DL,DB,FR,FL,BL,BR} Edge;
Copy the codeOnce the diagonal edges are numbered, a Rubik’s cube can be defined in terms of blocks:
struct corner_o
{ Corner c; / / Angle block
char o; / / direction
};
struct edge_o
{ Edge e; // Edge blocks, i.e. edges
char o; // Block direction
};
struct CubieCube// a rubik's cube state {
struct corner_o co[8]. / / 8 block edges
struct edge_o eo[12]. / / Angle of 12 pieces
};
Copy the codeHow to store the rubik’s cube state? For example, co[URF]={URF,0}co[URF] = \{URF,0\}co[URF]={URF,0} indicates that the URF block stored at the location of URF is 0. Co [URF]={UFL,1}co[URF] ={UFL,1 \}co[URF]={UFL,1} indicates that the UFL block stored at the URF location is 0.
The same is true of the edge block, and as we said at the beginning of canto, we don’t have to worry about the center block, which remains stationary as a reference frame. Thus, we can use the CubieCube structure to represent a Rubik’s cube state and define a Rubik’s cube.
ⅱ Coordinate Hierarchy (Index)
This name is a literal translation from the English name. This level simply means that we need to encode/hash the rubik’s cube state and assign a unique number to each state to identify it, which is mainly used as the index of transformation table and pruning table. Of course, it is impossible to actually code the different complete states of the Rubik’s cube, there are too many to be practical. But the rubik’s cube part status code, a state of complete rubik’s cube has eight Angle blocks, 12 block edges and their direction, and the algorithm is to split them, such as some pieces of the location of the edges, Angle position, Angle block, block edges, etc., to encode their hash, this number will be small lot.
Therefore, encoding is mainly for two indicators of position and direction, and the following three encoding methods are mainly used:
(1) the direction
Directions are divided into corner block direction and edge block direction, which are similar. Here, for example, corner block direction is used. Suppose that there is an arrangement of corner blocks with direction as shown below:
The first line represents the position, and the second line represents the corner block stored at the position and its direction, encoded using the following method:
It should be intuitive and easy to understand, because when the orientation of the seven corner blocks is determined, the direction of the last corner block is also determined, so there is no need to code the direction of the last corner block. The code is as follows:
short int idx_co = 0; // Corner orientation index
for (Corner c = URF; c < DRB; c++)
idx_co = 3 * idx_co + co[c].o;
Copy the code(2) are arranged
During is usually used for location change arrangement number, we may use a variety of arrangement, such as the arrangement of eight Angle blocks, six side arrangement and so on, these are part of the rubik’s cube of state, said we need to encode, the permutation encoding method has a name called cantor, also directly look at an example to illustrate the cantor expand this kind of coding way, Suppose 8 corner blocks are arranged as follows:
The first line represents the position, and the second line represents the corner block placed on the corresponding position. From the label, we know that our block is divided into sizes: URF
Specific coding:
This formula corresponds to the third line above, which should be easy to understand without explanation. The code description is as follows:
int idx_cp = 0; // Corner position index
for (int i = DRB; i > URF; i--){
int s = 0;
for (int j = i - 1; i >= DRF; j--)
if(co[j] > co[i]) s++;
idx_cp = (idx_cp + s) * i;
}
Copy the code(3) combination
For location change can sometimes be used in combination, combination need to code number, we would use in phase one on the middle tier 4 block edges of a composite number coding, stage a target state requirements in the middle tier edge block in the middle tier, so calculate phase one state of edge block position we just think about all the four edges of the middle layer, There are 12×11×10×9=1188012\times11\times10\times9 =1188012 ×11×10×9=11880 states, but there is no position requirement between the four edges of the middle layer, so we have to divide by their own position arrangement 4! = 244! = 244! =24, a total of 495 states, and this is a combination number C124C^4_{12}C124, we need to code the 495 states:
The first line represents the position and the second line represents the stored blocks. Only the positions of the four blocks in the middle layer are considered, namely FR FL BL BRFR\ FL BL\ BRFR FL BL BR. Since the four blocks in the middle layer have no position requirements, they are replaced by X to indicate that they are the same. The third line shows how many combinations X corresponds to, and the second line illustrates how to code:
The above encoding method should be easy to understand, in order to line, look at the code:
int idx_slice = 0, x = 0 // The middle layer 4 block state encoding
for(int i = BR; i >= UR; i--) // From back to front
if(edge[i] >= FR && edge[i] <= BR) // Check if there are 4 edges in the middle layer
idx_slice += c_nk(11 - j, x + 1) //c_nk is the combined value of n choose k
x += 1 //x + 1, x is the second value in parentheses above
Copy the codeI’m directly using the number of combinations, so I’m going to write a function ahead of time to find the number of combinations, n choose k, and if k>nk>nk>n is equal to 0, I’m just going to write the function. The above code can also be expressed as the sum of the other eight combinations, so you can try it out for yourself.
The above is the coding process, the coordinate hierarchy representation of the Rubik’s cube, that is, part of the state of the Rubik’s cube is transformed into a specific number to represent it. The coding method is not unique, but reasonable. We should also need a reverse process, from coding to the actual Rubik’s cube state, so that the above two levels of definition can be converted to each other, I won’t repeat here, it is basically the reverse process.
Define rotation
ⅰ Position Change
{0,1,2,3}\{0,1,2,3}\{0,1,2,3}\{0,1,2,3}\{0,1,2,3}\
int a[4] = {0.1.2.3};
int b[4] = {1.2.3.0};
int c[4] = {};
Copy the codeAn array is a data structure that has two elements, one is the location of the index and the other is the element, both of which are equally important, but we tend to ignore the use of the index.
What does this array b represent? Of course you can represent a permutation, 1 for bit 0, 2 for bit 1, 3 for bit 2, and 0 for bit 3.
This is just general knowledge. What else does it mean? That in itself represents a transformation, which means that the 0 element is replaced by the 1 element, the 1 element is replaced by the 2 element, the 2 element is replaced by the 3 element, and the 3 element is replaced by the 0 element. For example, the element of position 0 is replaced by the element of position 1, which can be written as a[0]=a[1] A [0]=a[1] A [0]=a[1].
So given a permutation, it is not only an permutation, but also a transformation, because there is an order in the permutation itself. From the perspective of an array, there is an implicit subscript to indicate the position of the elements, and a transformation operation can be explained by the change of the order of an element.
In particular, if the number of elements the range of subscripts is equal to the range of elements, then it’s very easy to define closed transformations on them. For example, the number of elements is 4, so the range of the subscripts is 0 and 3, and the values of the elements themselves are also 0 and 3. In this case, it is convenient to define the change operation. For example, if you perform the transformation B on the permutation A, the result will be stored in the permutation C.
for(int i = 0; i < 4; i++)
c[i] = a[b[i]];
Copy the codeSo the summary is that if you give a permutation, if you want to think of it as a transformation, then not only do the subscripts represent positions, but their elements also represent positions. B [2] = 3 indicates that the element in position 2 is replaced by the element in position 3.
After understanding the above, the definition of the rotation of the Rubik’s cube will be easily solved. There is no need for any new data structure. The state of the rubik’s cube defined in the previous section can be transformed, but we can interpret it differently when different needs are met.
ⅱ Direction Change
A location stores not only the block itself, but also the direction of the block. The block can be viewed from the above alternative perspective, but the direction is not.
For example, if you operate F in state A, as mentioned earlier, the rotation operation can also be regarded as a state. Let’s call F operation B and the result ab. Let’s take the position URF as an example.
F rotates so that the elements in the URF slot are replaced by the elements in the UFL slot, which can be written as
O ≠a.co[UFL].oab.co[URF].o \neq a.co[UFL].oab.co[URF].o=a.co[UFL].o, F The element in the UFL position moves to the URF position and twists clockwise, so for F rotation, the direction should change as follows:
It’s a little bit convoluted here, so you can actually take a Rubik’s cube and do a little bit of a simulation, and it should be physically very understandable, but it’s basically written in programming language and it’s a little bit convoluted.
ⅲ Basic rotation
So we should be able to write down the definition of fundamental rotation very easily. Let’s take an example F:
const cubieCube basicMoveF = {{{UFL,1}, // The URF slot element is replaced by the UFL slot element, and the clockwise twist, direction increment 1
{DLF,2},{ULB,0},{UBR,0},{URF,2},{DFR,1},{DBL,0},{DRB,0}},
{{UR,0},{FL,1},{UL,0},{UB,0},{DR,0},{FR,1},
{DL,0},{DB,0},{UF,1},{DF,1},{BL,0},{BR,0}}};
Copy the codeⅳ Rotation function
Rotation is divided into corner block rotation and edge block rotation, so the code is as follows:
CubieCube cubeMove(CubieCube cc, int m){ // apply rotation m on cc
CubieCube ccRet;
cornerMultiply(&cc, &basicMove[m], &ccRet); //basicMove is an array of basic rotations, elements of which are basic rotations as in the previous section
edgeMultiply(&cc, &basicMove[m], &ccRet);
return ccRet;
};
Copy the codeThis function is the encapsulation of angular block rotation and angular block rotation function, taking the angular block rotation function as an example:
void cornerMultiply(const CubieCube *a, const CubieCube *b, CubieCube *ab){
for (Corner crn = URF; crn <= DRB; crn++){
ab->co[crn].c = a->co[b->co[crn].c].c; / / Angle block
ab->co[crn].o = (a->co[b->co[crn].c].o + b->co[crn].o) % 3 // Angle block direction
/ * * * * * * * * * * * * * * * * * * * * * /}}Copy the codeUnlike Kozenba’s source program, the original program also deals with mirroring and so on, which I’ll leave out here and talk about later. The way I’ve described it is to think of A as a state of the Rubik’s cube, and b as a transformation, but you can also think of A as a transformation, and then AB is equivalent to a compound operation, the same thing, just from a different perspective.
Ⅴ rotating table
Rotation in the program will often be used, each time to do a transformation operation is too time-consuming, we need to build the rotation table, as long as the first run the program to establish the table, the subsequent rotation operation directly to look up the table.
There are many rotation tables, depending on which coordinates are used to represent the rubik’s cube state. Take the corner block direction as an example:
unsigned short int twistMove[Ntwist][Nmove]; //Ntwist=3^7-1, Nmove=18
Copy the codeHere we use the coordinate hierarchy defined by the Rubik’s cube state as an index. As an example, twistMove[a][U]=btwistMove[a][U] =btwistMove[a][U] =b, indicating that state A, U operation, get state B. A and B are two numbers, which respectively uniquely identify the corner block direction state of the Rubik’s cube.
This two-dimensional array is also easy to initialize, looking directly at the code:
void initTwistMoveTable(a){ // Initializes the corner block rotation table
CubieCube a, b;
int i,j,m;
for (int i = 0; i < NTWIST; i++){// Enumerates direction states
CubieCube a = twist2cube(i); // Coordinate level -> block level
for (int j = U; j <= B; j++){ //6 basic rotations
for(int k = 0; k < 3; k++){ // The three directions of basic rotation, such as U,U2 and U', correspond to 90°, 180° and 270° respectively
cornerMultiply(&a, &basicCubeMove[j], &b);
twistMoveTable[i][j * 3 + k] = get_twist(b); // Change the state from block level -> coordinate level
}
cornerMultiply(&a, &basicCubeMove[j], &b); // Return to the original state}}}Copy the codeFour, symmetry
Rubik’s cube is a highly symmetrical object, and we can use symmetry to reduce the overhead in time and space.
There are four basic cases of symmetry, original state, only color change, only position change, mirror image.
They’re all equivalent, and if we can solve one of them, we can solve the others, just by adding the corresponding symmetry change to the solution.
Let’s look at an example of different colors at the same position and see how the original state changes to get an equivalent state:
If A(A rotation sequence) operation is performed on the restored rubik’s cube, the following states can be obtained:
To obtain an equivalent state, perform the following operations: restore the state by rotating 90° counterclockwise about the UD axis, then by operating A, and finally by rotating 90° clockwise about the UD axis.
Do you have any association with this? Is it similar to the similar transformation of matrix? Some reduction algorithms save the Rubik’s cube in the form of matrix, and the rubik’s cube transformation is the corresponding matrix transformation.
ⅰ Symmetric transformation
① Basic transformation
Some of the above equivalent forms are obtained by symmetry transformation. There are 48 transformation forms for each state plus itself, and generally there are 48 equivalent forms for each state, which are all composed of four “fundamental symmetries” :
- S_U4: Rotate 90° around the axis UD, 4 kinds
- S_F2: Rotate 180° around the FD axis, two kinds
- S_URF3: Rotate 120° around the URF corner block, 3 kinds
- S_LR2: mirroring of LR layer, two kinds
=484\times2\times3\times2=484×2×3×2=48 kinds
I will not draw a graph to show the specific rotation (alas, mainly because the 3D mapping of transformation is too difficult, I tried, the effect is not good, sorry). Since it is a transformation operation, the symmetric transformation can still be represented by the block level of the state. Specifically, let’s look at the definition of the four basic symmetric transformation. And that should give you an idea of how it works.
const CubieCube basicSymCube[4] =
{
{{{URF,1},{DFR,2},{DLF,1},{UFL,2},{UBR,2},{DRB,1},{DBL,2},{ULB,1}},
{{UF,1},{FR,0},{DF,1},{FL,0},{UB,1},{BR,0},
{DB,1},{BL,0},{UR,1},{DR,1},{DL,1},{UL,1}}},//S_URF3
{{{DLF,0},{DFR,0},{DRB,0},{DBL,0},{UFL,0},{URF,0},{UBR,0},{ULB,0}},
{{DL,0},{DF,0},{DR,0},{DB,0},{UL,0},{UF,0},
{UR,0},{UB,0},{FL,0},{FR,0},{BR,0},{BL,0}}},//S_F2
{{{UBR,0},{URF,0},{UFL,0},{ULB,0},{DRB,0},{DFR,0},{DLF,0},{DBL,0}},
{{UB,0},{UR,0},{UF,0},{UL,0},{DB,0},{DR,0},
{DF,0},{DL,0},{BR,1},{FR,1},{FL,1},{BL,1}}},//S_U4
{{{UFL,3},{URF,3},{UBR,3},{ULB,3},{DLF,3},{DFR,3},{DRB,3},{DBL,3}},
{{UL,0},{UF,0},{UR,0},{UB,0},{DL,0},{DF,0},
{DR,0},{DB,0},{FL,0},{FR,0},{BR,0},{BL,0}}} //S_LR2
};
Copy the codeThe 48 symmetric transformations are also easy to initialize, with four for loops and the multiply function called to compound the results into the symCube[48] array, so we don’t need to repeat operations here.
Pay attention to the above mirror transformation. Add 3 to all changes in corner block direction, that is to say, the corner block direction of the mirror is [3,5][3,5].
(2) the inverse transformation
So we’ve done two symmetric transformations in order to get the equivalent state, and these two transformations are inverse to each other, which is called inverse in group theory, and we need to find the inverse transformation for each of these symmetric transformations.
How do I get the corresponding inverse transformation? In group theory, the composition of two elements that inverse each other is equal to the identity, which is the equivalent of the multiplication of two reciprocal numbers multiplied by one, whereas in rubik’s cube, the reduction of states is the identity which is that one. So all we have to do is compound 48 transformations in pairs to see if the result reaches the reduced state.
init inv_idx[48] - 1; // Initialize to -1, representing the inverse of each symmetric transformation
for(i = 0; i < 48; i++){
for(j = 0; j < 48; j++){
CubieCube cc = multiply(symCube[i], symCube[j]); // The two transformations are multiplied
if (cc == identity) // If the result is equal to the unitary restore state
inv_idx[i] = j; // The inverse of the symmetric transformation I is j}}Copy the codeⅡ equivalent
For the 48 kinds of symmetric transformation operations mentioned above, we denoted them as S[48]S[48]S[48], which is also the array symCube[48]. If there are two states A and B, If there is A = S BS [I] – [I] 1 A = S [I] [I] BS ^ {1} A = S BS [I] – [I], [I] is S – 1 AS [I] = BS [I] ^ {1} AS [I] = [I] – 1 BS AS [I] = B, we see A, B are equivalent. This kind of writing is not like the matrix similar transformation is exactly the same, essentially are interlinked, so really want to learn math ah.
Since they are equivalent, we can set these equivalent states together, that is to say, we classify the states like the following:
\begin{array}{1} 0&A0&A1&A2&… \\ 1&B0&B1&B2&… \\ 2&C0&C1&C2&… \ \… &… &… &… &… \end{array}
Therefore, for each state, we only need to record which set (row number) it belongs to and which symmetric transformation (column number) it uses. Such a set is called equivalence class. This saves a lot of space and time because there is less information stored and less state space to search for. In Kozenba’s two-stage algorithm, the UD axis is not moving, so only 16 symmetric transformations are used.
Add a state that belongs to the equivalence class Y and use the symmetric transformation I, then we can use the new coordinate Y ×16+iy\times16 +iy ×16+ I to describe the original state. But not every equivalence class has 16 different states, that is to say, not every state has 16 different symmetric states. For example, there are equivalence classes y and symmetric transformations I, j, y×16+iy\times16+iy×16+ I and y×16+jy\times16+jy×16+j are possible to describe the same state.
The key question is how do we know which coordinate is in which equivalence class, which symmetric transformation is used? To look directly at pseudo-code analysis:
init idx2class[Nindex] - 1 // initialize to -1, which equivalence class idx belongs to
init idx2sym[Nindex] - 1 // initialize to -1, which symmetric transformation idx uses
init class2rep[NCLASS] - 1 // Initialize to -1, the representation of the equivalence class
classidx = 0; // Equivalence class label
CubieCube cc = get_cube(); // Get the block-level representation of the initial rubik's cube state
for(idx = 0; idx < Nindex; i++){ // Coordinate hierarchy representation of the state of part of the Rubik's cube, such as Angle block direction Nindex = Ntwist = 2187
if(idx2class[idx] == - 1) {// Not yet filled
idx2class[idx] = classidx; / / fill
idx2sym[idx] = 0; // The first element of the equivalence class uses the symmetric transformation of the first type 0
class2rep[classidx] = idx; // The representation in the equivalence class is the one with the smallest idx
}
else
continue; // Already filled, skipped
/** The first element in the equivalence class is handled above, where the 16 symmetric transformations are applied directly to the other elements **/
for(sym = 0; sym < 16; sym++){
idx_new = idxSymTable[idx][sym]; Sym = idx_new; // sym = idx_new
if(idx2class[idx_new] == - 1){
idx2class[idx_new] = classidx;
idx2sym[idx_new] = sym;
}
}
classidx++; // After completing the current equivalence class, add one to prepare the next one
}
Copy the codeⅲ table of symmetric transformation
The above code has been used, similar to the previous rotation table, symmetric transformation, rotation is a transformation operation, rotation has a rotation table, symmetric transformation must also have the corresponding transformation table. For example, define the following table:
int moveSymTable[NMOVE][16]; // Do S[I]*m*S[I]^-1 for each rotation m
int twistSymTable[NTWIST][16]; // Twist S[I]*twist*S[I]^-1
Copy the codeThe specific initialization operation and rotation table are both based on the compound operation of states, illustrated by the symmetrical transformation table in the direction of corner blocks:
void initTwistConjugate(a){
CubieCube cc,ccSym,ccTmp;
int i,j;
for (int i = 0; i < NTWIST; i++){ cc = twist2cube(i);// Coordinate level to block edge level
for (int j = 0; j <16; j++){
cornerMultiply(&symCube[i], &cc, &ccTmp); //S[i]*cc
cornerMultiply(&ccTmp, &symCube[inv_idx[i]], &ccSym); //S[i]*cc*S[i]^-1
twistSymTable[i][j] = get_twist(ccSym); // The result is converted to the coordinate level}}}Copy the codeThe source program uses the word conjugate (conjugate), but I’ll use Sym directly to explain it, which I think might be more intuitive.
Five, the pruning
Pruning, which should be the core of Koxianba’s two-stage algorithm, combines all the data structures previously defined to build a new lookup table, the pruning table, which stores information on the minimum number of steps to the target state (stage 1) or restore state (stage 2). If the number of steps is greater than the number left to take, cut backtracking.
There may be multiple pruning tables for two stages, and each stage should select the largest number as the minimum number of steps needed to reach the target/restore state. For example, if Table 1 tells me that there are at least 5 more steps needed to reach the target state in the current state, and Table 2 tells me that there are at least 6 more steps needed, 6 is taken as the minimum number of steps needed. It is easy to understand, right? Table 1 and Table 2 respectively describe some states of the Rubik’s cube, and the target state is achieved only when all the states of each part reach the target state. Therefore, the largest state should be selected. This is also the h(n), h(n), h(n) * from IDA.
ⅰ Establishment of pruning table
Can the pruning table show the minimum number of steps to the target state? Isn’t it amazing? There’s nothing magical about it, just the result of a violent search. Set the depth of the target state as 0, and then perform 18 rotation operations on the target state to obtain the depth of the state node of the first layer as 1. Rotate each state of the first layer to obtain the depth of the state node of the second layer as 2………. See the following pseudo-code:
init pruneTable1[Nindex] - 1 // Initialize all elements to -1
depth = 0 // Initial depth is 0
pruneTable[0] = 0; // This is the target state, so the depth/required steps is 0
done = 1; // An initial state is filled in
while done < Nindex: // The form has not been completed
for i = 0 to Nindex - 1
if pruneTable[i] == depth
for each m in Nmove // Perform 18 rotation operations for each state
index = moveTable[i][m] // Use the rotation table to get the state coordinates after rotation
ifpruneTable[index] ! =- 1 // If you have not already filled out the form, complete it
pruneTable[index] = depth + 1 // Add 1 to the depth of the table
done++
depth++ // The depth is increased by 1
Copy the codeIn essence, it is a wide search, but the form and we usually see the framework may not be the same, this form takes a little time but saves space without storing nodes like the common wide search framework, the number of states of the Rubik’s cube is a lot, we want to use a more space-saving form.
ⅱ Storage Skills
If we know how far the initial state is from the target state, and then every step we take, we’re either going to increase by 1, or we’re going to stay the same, or we’re going to decrease by 1, all three of those things, then we can figure out how far we are from the target state after rotation. So in the pruning table we only need 2 bits to store the actual distance mod 3. According to the distance of the current state, and according to the mod3 value found in the pruning table, we can calculate the distance between the state after rotation and the target state. This greatly reduces the use of space.
But the key is how far is it from the initial state to the target state? You might say, look up tables, look up tables is fine, but remember, prune tables don’t store actual distances anymore, they store mod3 distances that only use 2 bits. So what to do? Let’s go straight to the pseudo-code analysis solution:
int get_depth_phase1(CubieCube cc){
index = get_index(cc); // Get the coordinates of the initial state
depth_mod3 = pruneTable[index]; // Mod3 distance from the initial state to the target state
depth = 0; // initialize 0
whileindex ! = SOLVED:// If the target state is not reached, loop
if(depth_mod3 == 0) depth_mod3 = 3; //mod3 = 0, multiple of table 3, set to 3
for each m in Nmove // For each rotation
index_new = moveTable[index][m];
if (pruneTable[index1] == depth_mod3 - 1) // If the distance is closer after rotation
depth++; // The actual distance is increased by 1
index = index1; // Update the coordinate index value
depth_mod3--; //mod3 distance minus 1
break; // Find an example target to rotate closer and break out of the loop
return depth;
}
Copy the codeAccording to the pseudo-code, we can see the general meaning, because what we check out from the pruning table is the mod3 distance, so the mod3 distance decreases continuously from 3 to 0, and the actual distance increases continuously from 0 until it reaches the target state. Since each time we update the two distance values, we will get closer to the target state after rotation, so the final actual distance depth must be the minimum steps needed to get from the initial state to the target state. This seems to have solved the Rubik’s cube all over, but in fact it is not, because index is only the coordinate index of the partial state of the Rubik’s cube, so the value calculated by this function is only used as an initial index.
6. Stage 1
ⅰ Coordinates used
Phase ONE uses three coordinates:
twist, Angle block direction, value range
flip, edge direction, value range
slice, the selection state of the 4 edges of the middle layer, and the value range
I don’t say the first two, very familiar, the third coordinate level at the same time. If you think about the properties of the target state in phase 1, the first two coordinates are to solve the orientation problem. The target state of the first stage does not have high requirements for the position of the block edge. It only requires the block belonging to the middle level to stay in the middle level, and it is not required to stay at home, as long as it is in the middle level. The third coordinate is to solve the position problem.
ⅱ Coordinate optimization
Instead of actually defining slice, this coordinate is slice_sorted, which is an enhanced version of Slice. Does slice not consider the position of the four edges in the middle layer? If so, it is slice_sorted. Value range: [0,11879][0,11879][0,11879]. But of course we still use slice, which is the indicator of stage 1. That is, we divide slice_sorted by 24. Why bother to define slice directly? Because phase two also uses this slice_sorted coordinate, so I’ll do that for the sake of uniformity, but of course, as long as you don’t confuse yourself, it doesn’t matter which coordinate you use, or even some other coordinate.
This coordinate is neither a combination nor a permutation. How do you code it? Times11 \times10\times9=\frac{A^{12}_{12}}{C^4_{12}}12×11×10×9=C124A1212, So this coordinate can also be represented by permutations and combinations of codes.
Coordinate merge/index calculation
Flip slice, flipslice=2048×slice+flipflipslice=2048 \times slice+ flipflipSlice =2048×slice+flip Value range of [0, (2048 x 495-1)] [0, (2048 \ times495-1)] [0, (2048 x 495-1)].
However, due to symmetry, flipslice can be replaced by CLASsidx and syM, whose values are [0,64429][0, 64429], [0,15][0,15][0,15] [0,15][0,15]. 64430×16>2048×49564430\times16 >2048 \times 49564430×16>2048×495, which shows that there are not 16 different symmetric states in every equivalence class.
Classidx, sym and twist combine into a coordinate, let’s call it sym_flipslice_twist, Value range [0,64430 x 2187−1][0,64430\times2187-1][0,64430 x 2187−1] this coordinate is the index of the stage 1 prune table.
Sym_flipslice_twist =2187× classidX +twistSymTable[twist][sym]sym\_flipslice\_twist =2187 \times classidx+ TwistSymTable [twist][sym]sym_flipslice_twist=2187× CLASsidx +twistSymTable[twist][sym] There’s no reason why coshimba does it this way, or it doesn’t have to do it this way, but it’s just an index value, a hash value, as long as it can be separated from one another.
ⅳ Search algorithm
The search algorithm uses IDA*, not to mention the pseudo-code:
main: / / main thread
CubieCube cc = get_cube(); // Get the input rubik's cube
dist = get_depth_phase1(cc); // Get the minimum number of steps required for phase 1
twist = get_twist(cc); // Get the coordinate twist
flip = get_flip(cc); // get the coordinate flip
slice_sorted = get_slice_sorted(cc); // Get the coordinates slice_sorted
for(togo1 = dist; togo1 <= 20; i++) //IDA* limits the depth of the search to a point that cannot exceed togo1
search1(twist, flip, slice_sorted, dist, togo1); // Stage 1 search
Copy the codevoid search1(twist, flip, slice_sorted, dist, togo1){ / / deep search
if(togo1 == 0) // Phase 1 has been resolved
Search2 ()**/ search2()**/
else{
for each permitted m in MOVE{ // For every rotation allowed
flip_new = flipMoveTable[flip][m]; // Get a new flip
twist_new = twistMoveTable[twist][m]; // Get new Twist
slice_sorted_new = sliceSortedMoveTable[slice_sorted][m]; // Get the new slice_sorted
flipslice = 2048 * slice_sorted_new / 24 + flip_new; // Calculate the flipslice, slice_sorted by 24
classidx = flipslice2class[flipslice]; // Which equivalence class flipslice belongs to
sym = flipslice2sym[flipslice]; // Record which symmetry transform is used
sym_flipslice_twist = 2187 * classidx + twistSymTable[twist][sym]; // Calculate index
dist_new_mod3 = get_flipslice_twist_depth3(sym_flipslice_twist); // Get mod3 distance from prune table
dist_new = get_real_dist(dist_new_mod3); // Mod3 distance to actual distance
if (dist_new > togo1) // The minimum number of steps required is greater than the allowable number of steps
continue;
maneuver1.append(m); // Make a choice and m adds the rotation sequence of the solution
search1(twist_new, flip_new, slice_new, dist_new, togo1 - 1); // Next level of search
maneuver1.pop(); // Undo selection, try sibling or backtrace}}}Copy the code7. Stage 2
ⅰ Coordinates used
corners, Angle block array, 8, value range
ud_edges, the edges of layer U and layer D are arranged, 8, and the value range is 8
slice_sorted, the edges of the middle layer are arranged, 4, and the value range is
Now we are in the target state of stage I, and all the edges of edge blocks have good directions. We only need to solve the problem of their positions. Therefore, these three coordinates are permutation numbers, and the coordinates can be established according to the permutation number coding.
Coordinate merge/index calculation
Coners ranges from [0,40319][0, 40319][0,40319]. Due to symmetry, it can be replaced by CLASSIDX and SYM. The value ranges are [0,2767][0, 2767][0,2767] respectively. [0,15][0,15][0,15] 2768 equivalence classes, also because there are not 16 different states in each equivalence class, so 2768×16>403202768\times16>403202768×16>40320
The CLASsidx, SYm, and UD_edges combine into one coordinate, tentatively called sym_corners_ud_edges, Value range [0,40320 x 2768−1][0,40320\times2768-1][0,40320 x 2768−1] this coordinate is the index of the prune table of stage 2. Sym_corners_ud_edges =40320× CLASsidx +ud_edgesSymTable[UD_edges][sym]sym\_corners\_ud\_edges =40320 \times classidx+ Ud \ _edgesSymTable [ud \ _edges] [sym] sym_corners_ud_edges = 40320 x classidx + ud_edgesSymTable [ud_edges] [sym]
Corners and slice_sorted are grouped into another coordinate, named “corners_slice_sorted”. The values range from [0,40320×24−1][0,40320\times24-1][0,40320×24−1]. This coordinate is the index of another pruning table for stage 2. Corners_slice_sorted = 24 x corners + slice_sortedcorners \ _slice \ \ _sorted = 24 times Corners + slice \ _sortedcorners_slice_sorted = 24 x + slice_sorted corners
ⅲ Search algorithm
void search2(corners, ud_edges, slice_sorted, dist, togo2){ // Search the frame
if(togo2 == 0) // Phase 2 has been resolved
maneuver = maneuver1 + maneuver2; // Combine the two-stage solution
if(len(maneuver) < shortest)
shortest = len(maneuver) // Record the length of the shortest solution
else{
for each permitted m in MOVE{ // For every rotation allowed
corners_new = cornersMoveTable[corners][m]; // Get the rotated corners
ud_edges_new = ud_edgesMoveTable[ud_edges][m]; // Obtain the rotated UD_edges
slice_sorted_new = sliceSortedMoveTable[slice_sorted][m]; // Get rotated slice_sorted
classidx = corner2classidx[corners_new]; // Get the representative of corners
sym = corner2sym[corners_new]; // Get the symmetry transform used
sym_corners_ud_edges = 40320 * classidx + ud_edgesSymTable[ud_edges][sym]; // Calculate index
corners_slice_sorted = 24 * corners + slice_sorted; // Calculate index
dist_new_mod3 = get_corners_ud_edges_depth3(sym_flipslice_twist); // Check the pruning table to get the mod3 distance after rotation
dist_new = get_real_dist(dist_new_mod3); // Mod3 distance is converted to actual distance
another_dist = corners_slice_sorted_pruneTable[corners_slice_sorted] // Select * from pruning table
if(max(dist_new, another_dist) >= togo2) // Two distance indicators, if the largest one is greater than the allowed number of steps, prune
continue;
maneuver.append(m); // Make a choice, m adds the solution in stage two
seach2(corners_new, ud_edges_new, slice2_new, dist_new, togo2 - 1); // Search for the underlying node
maneuver.pop(); // Undo selection, try sibling or backtrace}}}Copy the codeViii. Improve and supplement
Kozenba’s two-stage algorithm has been combed through from beginning to end, and now let’s look at the parts that are omitted or simply skipped
ⅰ Improvement stage I
void search1(twist, flip, slice, dist, togo1){ / / deep search
if(togo1 == 0) {// Phase 1 has been resolved
/*** Calculate the parameters required in stage 2 ***/
corners = get_corners(cc); // Get the corners coordinates of the initial state
for m in maneuver1 // Update the corners by turning the corners according to the solution in stage 1
corners = cornersMoveTable[corners][m];
// Calculate the maximum number of steps allowed in stage 2. The length of the current optimal solution minus the number of steps taken in stage 1, and the number of steps used in stage 2 should not exceed 11-1=10
// The number of steps in stage 2 drops rapidly, usually no more than 9
togo2_limit = min(shortest - len(maneuver1), 10);
corners_slice_sorted = 24 * corners + slice_sorted; // Calculate index
if(corner_slice_sorted_pruneTable[corners_slice_sorted] >= togo2_limit) // check the table for pruning
return
ud_edges = get_ud_edges(cc); // Obtain the ud_edges coordinates of the initial state
for m in maneuver1 // Rotate to update the UD_edges according to the solution in stage 1
ud_edges = ud_edgesMoveTable[ud_edges][m];
dist2 = get_depth_phase2(corners, ud_edges);
for(togo2 = dist2; togo2 <= togo2_limit; togo2++) // Deep search with limited steps, IDA*
search2(corners, ud_edges, slice, dist2, togo2)
}
Copy the codeⅱ Allowable rotation
A lot of the previous code said all 18 rotations allowed. What does that mean? For example, if I use L for this step, I should not use {L,L2,L3}\{L, L2,L3} {L,L2,L3}\{L, L2,L3} {L,L2,L3} for the next rotation, because there is always a shorter rotation sequence that can be used instead. For example LL=L2, LL2=L3, LL3=0, L2L3=LLL=L2, \ LL2=L3, \ LL3=0, \ L2L3=LLL=L2, LL2=L3, LL3=0, L2L3=L. So {L, L2, L3} \ {L, L2, L3 \} {L, L2, L3} should not be used behind the {L, L2, L3} \ {L, L2, L3 \} {L, L2, L3}.
For example, FR≠RFFR\neq RFFR=RF, but the two relative layers of rotation meet the commutation law, such as LR=RLLR=RLLR=RL, so if L rotation can be followed by R rotation, So you have to forbid rotations of class R followed by rotations of class L.
In addition, each stage has limited rotation, especially in stage 2, only {U,D,L2,R2,F2,B2}\{U,D,L2,R2,F2,B2}{U,D,L2,R2,F2,B2}
In stage 1, if dist=0 AND togo1≠0dist =0 \ \ AND \ \ togo1 \neq 0dist=0 AND togo1=0, it means that sub-optimal solutions should be sought in stage 1 to achieve a better overall solution. At this time, even in phase one, but we ban the use of {U1, U2, U3, D1, D2, D3, L2, R2, F2, B2} \ {U1, U2, U3, D1, D2, D3, L2, R2, F2, B2 \} {U1, U2, U3, D1, D2, D3, L2, R2, F2, B2}, This is the rotation used in stage two, but we forbid it. Why is that? For example, a rotation sequence M can make the initial state reach the target state, then MU, MR2 and other rotation sequences can also make the initial state reach the target state. However, such suboptimal solution of stage I cannot help us find a better solution.
The inverse element of state/transformation
I don’t know what to call it, so I’m just going to use a mathematical term, but we’ve done the inverse of a symmetric transformation, and here we’re going to do the inverse of a Rubik’s cube or the inverse of a normal transformation. The implementation here is different from the symmetric transformation where the verification is done in pairs. Let’s look at the code directly:
CubieCube inverse_cubiecube(CubieCube cc){
CubieCube inv;
for(Edge edg = UR; edg <= BR; edg++)// Edge position
inv.eo[cc.eo[edg].e].e = edg;
for(Edge edg = UR; edg <= BR; edg++)// Edge direction
inv.eo[edg].o = cc.eo[inv.eo[edg].e].o;
for(Corner crn = URF; crn <= DRB; crn++)// Corner block position
inv.co[cc.co[crn].c].c = crn;
for(Corner crn = URF; crn <= DRB; crn++)// Angle block direction
inv.co[crn].o = (3 - cc.co[ccInv.co[crn].c].o) % 3 // The direction of the corner block should change
}
Copy the codeThere are a little bit more inside, do not get dizzy, simulate how the change should be very well understood. Tell me why the direction of the edges doesn’t change, but the direction of the corner blocks does. The reason is related to the Angle block has three directions and the definition of the block edge. For the Angle block, if we only look at it from the Angle of torsion and untorsion, the direction of the Angle block does not change. We can simply substitute several numbers to try, and the function of the last formula is to make 1 change 2,2 change 1, 0 or 0. If you still don’t know, you can invert one cube and see how the edges of the cube change according to the direction definition.
ⅳ. Angle block direction problem during compound transformation/rotation
Due to the addition of mirror transform, the direction of diagonal block is redefined, and the value range of mirror direction is [3,5][3,5][3,5]. Here, the clockwise twist becomes 5, and the counterclockwise twist becomes 4. Here, I see the relevant information at home and abroad has not pointed out, but according to the actual code operation, the result of the simulation of the Rubik’s cube rotation should be like this.
The corner_multiply function is used to handle changes in the position and direction of the corner blocks during the transformation. The corner_multiply function is used to handle changes in the position and direction of the corner blocks during the transformation.
void cornerMultiply(const CubieCube *a, const CubieCube *b, CubieCube *ab){
for (Corner crn = URF; crn <= DRB; crn++){
ab->co[crn].c = a->co[b->co[crn].c].c; // The corner block position changes
char oriA = a->co[b->co[crn].c].o; // The original direction
char oriB = b->co[crn].o); // How does the direction change
/*** * discuss ***/ respectively according to normal or mirror
if (oriA < 3 && oriB < 3) {//a and B are in the normal state
ori = oriA + oriB;
if (ori >= 3) ori -= 3; // The result is normal
}else if (oriA < 3 && oriB >= 3) {// B is in the mirror state
ori = oriA + oriB;
if (ori >= 6) ori-=3; // Result Mirror status
}else if (oriA >= 3 && oriB < 3) {// A is in the mirror state
ori = oriA - oriB;
if (ori < 3) ori += 3; // Result Mirror status
}else if (oriA >= 3 && oriB >= 3) {// BOTH a and B are in mirror state
ori = oriA - oriB;
if (ori < 0) ori += 3; // The result is normal}}}Copy the codeMirror state normal, mirror state normal, mirror state, mirror state, mirror state, mirror state, mirror state mirror change is the same thing as going back so it’s normal state, it should make a lot of sense.
The main thing is that the above for the different cases of oriA and oriB plus or minus and the end result ori plus or minus 3 can be confusing, hey, confusing but I’m not going to go into details, mainly because it’s really hard to say in this direction, and the best way to figure it out is with a simple mirror transform, Let’s simulate the normal transformation, and then take a physical Rubik’s cube as a reference, and see if that’s the case. To elaborate on the simulation operation, most of the content is the displacement operation in the discrete, repetitive and boring, so don’t say, interested in their own simulation.
V multi-threaded multi-direction search to improve efficiency
You can use multi-threaded parallel search, which is not searching the same situation in the same direction multiple times, but searching in different directions. For example, search for other axial directions, search for inversion. In addition, axial search means to perform S_URF3 symmetric transformation on the Rubik’s cube before searching (not necessarily rotating around THE URF3 Angle, but otherwise). Similarly, to search for inverse state is to perform inverse transformation on the Rubik’s cube first.
Remember what transformation you used in the beginning, and then invert the solution that you got after the search to get the original solution. Experimental results show that the efficiency of three different combinations of axial and contravariant transformations is the highest when six threads are opened.
Ix. Closing reference
That’s what Kozenba’s two-stage algorithm looks like, basically covering all the hard points. Generally speaking, the core of the algorithm lies in the construction of various data structures, to create a variety of tables, especially the establishment of the pruning table, directly affect the search performance and the merits of the solution.
This article refers to the foreign language materials, interested can go to see the original materials
kociemba.org/cube.htm, Kosen… In the Python version, the parts are very clear.
www.jaapsch.net/puzzles/, abroad…
www.cube20.org, announced that the number of God is 20 of a website, there is also a two-stage algorithm on the source code and the corresponding PDF explanation, read through the understanding should become a god, I insist after reading almost did not back in the past, interested in stronger can try.
En.wikipedia.org/wiki/Optima…
www.speedsolving.com/wiki/index….
Ruwix.com/the-rubiks-… Also a very good site, there are all kinds of theories there are online programs and so on
The Diameter of The Rubik’s Cube Group Is Twenty, The most influential paper in The field, concludes that The number of God Is 20 and worth a look.
And some do not give out, the above is a some people think that a good web site resources, want to see the original theoretical explanation can go and see, all is in English, in the domestic side of information literature did too little, almost no, next bucai, render also hope to do a little, there is something wrong in the same also please correct me criticism. Some websites and resources are the need for a ladder, no friends can reply to the rubik’s cube in the background, I put some of the above source code and procedures in it, easy to download.
This article to the about section of the first two stages algorithm is here, families first usually can not get the optimal solution of the algorithm, is there any algorithm can get the optimal solution every time, the answer is yes, god is a piece of time also mentioned algorithm — Krof ‘s algorithm, nothing mysterious, is based on the division of the first two stages algorithm implementation, Now that you understand the two-stage algorithm, it should make a lot of sense, and we’ll talk about it in the next video.
Finally, talk about a little bit of digressions, for the two-stage algorithm, in fact, the two-stage algorithm not only in the computer field rubik’s cube field can give us inspiration, usually life and learning is also helpful, how to say that sentence, first set a small goal, step by step to solve. Remember that vivid metaphor on the cover of the article about the two-stage algorithm? Aimlessly sailing to the other shore that is far away, it is better to go to specific waters to complete one goal after another, and finally successfully reach the other shore. Although may not get the optimal solution, but life this road who can go straight? As long as you work hard, strive for each stage of life to get the corresponding optimal solution, combined to get a better solution that is also very good, right?