The general scheme of building algorithms on the example of the Rubik's Cube

Perhaps many of the readers tried to assemble a 3 × 3 Rubik's cube on their own, but after many unsuccessful attempts, they either threw out this activity or looked for a ready-made solution. The purpose of this article is to show with the example of the Rubik's Cube that finding a solution to any (from the class of the solved) problems independently, is a completely doable task for everyone, if you follow a certain set of rules. This solution was obtained by me in 10 hours, plus of this algorithm that it does not require memorizing complex combinations and to train for a long time - it is enough to assemble in this way only a few times.

So, consider one of the possible solutions. Below, under each item, a rough estimate of the computational complexity (Cn) of this subtask is given (based on the search time for the solution, which is directly proportional to the total number of combinations of possible moves):

1. We study the construction (the initial conditions of the problem) - we understand that the vertices of the Rubik's cube, the lateral and central faces are not “mixed”, which means the task can be divided into at least three subtasks of the assembly:

1. tops
2. central faces
3. side faces

Another thing that needs to be understood from the design: the position of all the colors on the sides of the assembled cube relative to each other is strictly fixed (make sure of this yourself).

Of course, the statement of the problem and its splitting into parts is also a task, therefore some “intellectual complexity” also corresponds to this item, but there is no uniform assessment criterion for it, so we skip it.
')
2. Putting the first side (red-bottom).

C2 ~ 2

3. Select the assembled side as a reference point for searching the algorithms for assembling the remaining vertices (belonging to the red side). We are looking for all possible invariant operators (Tx) with respect to this point that are capable of “shuffling” the remaining uncollected faces in every possible way.

As a result, out of the whole set, depending on their “action”, I selected 4 main operators:

1. Tv - "vertical"
   
   C3.1 ~ 3
2. Tg - "horizontal"
   
   C3.2 ~ 3
3. Tf - Flip
   
   C3.3 ~ 2
4. Ttw90 - "turn 90"
   
   C3.4 ~ 0

Note: all the above operators do not require “memorization”, it is enough to understand how they work - follow the trajectory of the red faces.

4. The question arises: Why do we need all these operators, if by themselves they do not give an unambiguous rule for placing them in vertices? The fact is that the mechanical system of the Rubik's cube has complex internal connections, and the solution requires a lengthy sequential search, which is much easier to perform (analytically) on the basis of the operators defined in Section 3:

1. Rearrange two adjacent corner faces
   Tv-Ttw90-Tf-Tg
   
   S4.1 ~ 4
2. Rotate two adjacent corner faces
   Tv-Tg-Tg-Ttw90-Tg
   
   S4.2 ~ 5

The data of the two above-defined "manipulations" are enough to place all the angular faces in places.

5. Restoring the central edges to places (independently).

C5 ~ 2

6. The final stage - the arrangement of the side faces. All you need is one operator:

1. Ts - "side"
   
   C6.1 ~ 3

I suggest the reader to independently figure out how on the basis of this operator it is possible to “complete the puzzle” - complexity C6 ~ 2.

In conclusion, we calculate the total “complexity” in terms of O-estimates, for a given solution of the algorithm, this is the maximum complexity of the subtasks of all the used subtasks for a complete solution of the general problem: O (C1) + O (C2) + ... = MAX {C1, C2, ...}.
Total, "complexity" of the general solution of the "problem" of the Rubik's cube in this way was ~ 5.

It remains to be clarified that there is a “subtask complexity” - this value is directly proportional to the number of all enumerations of possible solutions taking into account all conditions (symmetry, ...), for example, in case of turning any face 180 degrees, it does not make sense when searching for a solution , turn it right there for another 180 degrees.

Thus, for the construction of the algorithm is necessary:

1. Split the task, based on its features, into as many independent subtasks as possible.
2. Determine the starting point for each subtask for which a solution is sought (in the example of the Rubik's cube it was a red face)
3. Similarly, for each subtask to build a complete set of operators (“shuffling”), with the help of which a conditional search of all sorts of solutions will be carried out.
4. Determine the search conditions (to exclude "symmetric duplicates").

All the rest will be done by a computer for you - the harder it is, the longer the search will be performed.