[PYTHON] Let's make a robot that solves the Rubik's Cube! 2 Algorithm

What is this article?

This article is serialized ** Let's make a robot that solves the Rubik's cube! It is a part of the article collection called **. Click here for the whole picture

1. Overview
2. Algorithm (this article)
3. Software (unpublished)
4. Hardware (unpublished)

GitHub is here.

I also created a video with the same content as this article.

Click here for a video collection about this article collection.

Contents of this article

This time, I will explain the algorithm of the program that outputs the shortest procedure (for the robot) for solving the 2x2x2 Rubik's cube. The algorithm introduces "breadth-first search" and "IDA *". Before that, let's briefly touch on the idea of full search.

What is "total search" to be considered this time?

Full search is literally a ** method of searching all patterns **. For a 2x2x2 Rubik's cube, if you turn {U, U', U2, F, F', F2, R, R', R2} from a certain state, check everything, and if not, check before. It is a search method such as turning and checking all {U, U', U2, F, F', F2, R, R', R2} for all patterns (strictly, 2 steps). There are 6 steps each to search after the eyes, but I will talk about that later). The U, F, and R that appear here are called rotation symbols. Please see the overview for details.

Now, let's draw a little figure here. In this way, if the state of the cube is represented by a circle (node) and turning a hand from that state is represented by a stick (side), repeating turning all the hands that can be searched from a certain state and this tree A diagram like this corresponds. In the figure, it was skipped, but in the case of 2x2x2, for each state,

• The first move is {U, U', U2, F, F', F2, R, R', R2} 9 moves
• From the second move onward, if the previous move is any of {X, X', X2}, {U, U', U2, F, F', F2, R, R', R2} \ 6 moves of {X, X', X2} (\ is the symbol of the difference set)

Since you can turn this much, you will have 9 sides from the first node (root) and 6 sides from each of the nodes other than the first.

In addition, the number of steps to be searched after the second move is reduced, for example, if you turn X X', it is the same as not turning anything, if you turn XX, it is the same as X2, if you turn X X2, it is the same as X'. In addition, if two hands of the same type of rotation symbols are lined up, it will always be canceled out or replaced with another rotation symbol.

Breadth-first search

"** Breadth-first search " is a typical method of full search along with " Depth-first search **". The nodes in the previous figure are intentionally numbered for the sake of explanation here. As you can see (?) The order of examining each node is different between depth-first search and breadth-first search. Let's briefly explain each.

Breadth-first search

Breadth-first search is shown in the figure 1->1.1->1.2->1.3->...1.9->1.1.1->1.1.2->...1.1.6->1.2.1->1.2.2->...1.3.1->...1.1.1.1->... It is a search method to search. what the hell? I think, so let's add an arrow to the previous figure. That's right, it's a search that gradually becomes deeper. In terms of the numbers in the figure, the number of L.M.N to be searched will gradually increase. In other words, the more you move from the beginning, the later you will be searched.

This search method is often used to ** find the shortest path **. This is because, if "the more hands you turn, the later you will be searched", then "if you can reach a solution in a short amount of time, the search will be terminated when you find it."

If you want to know more, I recommend the article here.

Depth-first search

The search order of the depth-first search is as follows. 1->1.1->1.1.1->1.1.1.1->...1.2->1.2.1->1.2.1.1->...1.2.2->1.2.2.1->... Let's also put a figure. Depth-first search is a search method that searches to the deepest (longest) part for the time being, and if it fails, returns to one shallower place (try changing the last hand turned to another hand). is. In other words, when examining a node with the last number N, such as L.M.N for each depth, the node with L.M. (N-1 or less) has already been examined.

This search method is relatively easy to implement, may finish faster than breadth-first search (if you are looking for a non-optimal solution (non-shortest procedure)), and uses relatively little memory, so I want to do a full search for the time being. I often use it when.

For more information, we recommend here and here.

Solve the Rubik's cube with breadth-first search

This time I want to find the shortest number of steps, so I use breadth-first search. Let's implement it for the time being. If you can't read Python here, just read the comments and listen to them.

from collections import deque
from copy import deepcopy
from time import time

move_candidate = ["U", "U2", "U'", "F", "F2", "F'", "R", "R2", "R'"] #Candidates for rotation

#Cube class Not essential in this article(I will explain in detail in the software section)
class Cube:
    def __init__(self):
        self.Co = [0, 0, 0, 0, 0, 0, 0]
        self.Cp = [0, 1, 2, 3, 4, 5, 6]
        self.Moves = []

    #Rotation processing CP
    def move_cp(self, num):
        surface = [[0, 1, 2, 3], [2, 3, 4, 5], [3, 1, 5, 6]]
        replace = [[2, 0, 3, 1], [3, 2, 1, 0], [1, 3, 0, 2]]
        idx = num // 3
        res = Cube()
        res.Cp = [i for i in self.Cp]
        for i, j in zip(surface[idx], replace[num % 3]):
            res.Cp[i] = self.Cp[surface[idx][j]]
        res.Moves = [i for i in self.Moves]
        res.Moves.append(num)
        return res

    #Rotation processing CO
    def move_co(self, num):
        surface = [[0, 1, 2, 3], [2, 3, 4, 5], [3, 1, 5, 6]]
        replace = [[2, 0, 3, 1], [3, 2, 1, 0], [1, 3, 0, 2]]
        pls = [2, 1, 1, 2]
        idx = num // 3
        res = Cube()
        res.Co = [i for i in self.Co]
        for i, j in zip(surface[idx], replace[num % 3]):
            res.Co[i] = self.Co[surface[idx][j]]
        if num // 3 != 0 and num % 3 != 1:
            for i in range(4):
                res.Co[surface[idx][i]] += pls[i]
                res.Co[surface[idx][i]] %= 3
        res.Moves = [i for i in self.Moves]
        res.Moves.append(num)
        return res

    #Actually change the state array of the puzzle according to the rotation number
    def move(self, num):
        res = Cube()
        res.Co = self.move_co(num).Co
        res.Cp = self.move_cp(num).Cp
        res.Moves = [i for i in self.Moves]
        res.Moves.append(num)
        return res

    #Convert rotation number to rotation symbol
    def num2moves(self):
        res = ''
        for i in self.Moves:
            res += move_candidate[i] + ' '
        return res
    
    #Create a unique number from the cp array
    def cp2i(self):
        res = 0
        marked = set([])
        for i in range(7):
            res += fac[6 - i] * len(set(range(self.Cp[i])) - marked)
            marked.add(self.Cp[i])
        return res
    
    #Create a unique number from the co array
    def co2i(self):
        res = 0
        for i in self.Co:
            res *= 3
            res += i
        return res

#Puzzle state(R U R' U')3(This 3 is R U R' U'Means that you turned 3 times)State turned
#Start from a mess of puzzles and explore until they are complete
puzzle = Cube()
#CP is an abbreviation for Corner Permutation. Represents the position of corner parts.
puzzle.Cp = [1, 0, 2, 5, 4, 3, 6]
#CO is an abbreviation for Corner Orientation. Indicates the orientation of corner parts.
puzzle.Co = [2, 1, 0, 0, 0, 0, 0]

#The state of the puzzle in the solved state
solved = Cube()
solved.Cp = [0, 1, 2, 3, 4, 5, 6]
solved.Co = [0, 0, 0, 0, 0, 0, 0]

#measurement of time
strt = time()

#Breadth-first search
que = deque([puzzle])
while que:
    #Remove state from queue
    status = que.popleft()

    #L the number of the last step_Put it in mov
    l_mov = -1 if not status.Moves else status.Moves[-1]

    #List of steps to turn next
    t = (l_mov // 3) * 3
    lst = set(range(9)) - set([t, t + 1, t + 2])
    for mov in lst:
        #Actually move the puzzle
        n_status = status.move(mov)

        #I found the answer!
        if n_status.Cp == solved.Cp and n_status.Co == solved.Co:
            print(n_status.num2moves())
            print(time() - strt, 'Seconds')
            exit()
        
        #If no answer is found, add the state to the queue
        que.append(n_status)

It's been a bit long, but the main subject is just under the last 30 lines. Other than that, it is a class for expressing cubes. I will talk in detail in the software section.

In this program, scramble the image ((RUR'U') 3, 3 means to do RUR'U' 3 times, this move is also called 3sexy because RUR'U' is called sexy move) , Measuring the time.

Let's see the execution result.

F R F2 R2 U2 R F'
2.8320679664611816 seconds

First of all, the solution isn't 3sexy (that's right, 2x2x2 cubes can be solved with up to 11 moves). And it's been taking a long time. To find the cause of this, let's introduce the concept of ** complexity ** instead of going to the Amazon's hinterland.

Computational complexity

Simply put, it's the number of times the loop goes around. $ O (number) $ I will write it as. Also, in this case, the length of the solution (= depth of search) is important, so other constant multiples are ignored.

The loop that goes around in breadth-first search is a while statement. This turns as many times as the number in the que, so the amount of calculation is $ O (number of states in \ mathrm {que}) $ It will be. Let's calculate. First, there are 9 edges growing from the first node. And after depth 2 (2nd move), 6 sides grow from each node. Therefore, if the depth is $ N $, the amount of calculation of this program is O(9\times 6^{N-1}) is. By the way, this scramble seems to have been solved with 7 hands. Let's substitute $ N = 7 $. O(9\times 6^6)=O(4.2\times10^5) This time, the amount of calculation has slowed down, probably because each process is heavy. By the way, 2x2x2 cubes can be arranged with a maximum of 11 hands (God's number), so let's substitute $ N = 11 $ as well. O(9\times 6^{10})=O(5.4\times10^8) Not like that. This won't end almost forever! !! Therefore, ** pruning ** is introduced to speed up the process.

Pruning

Pruning means that when you search to a certain depth, if you know that ** you cannot reach a solution (the cubes are not aligned) ** even if you proceed with the search as it is, the search is terminated at that point.

This time, the shortest number of steps when ignoring CO (Corner Orientation, orientation of corner parts) and aligning only CP (Corner Permutation, position of corner parts), and the shortest number of steps when ignoring CP and aligning only CO Calculate the two in advance, and prun the branches the moment you find that either CP or CO is not within 11 moves (God's number). I think it will be a mess, so let's put a photo as an example. The left is the state where only CP is prepared, and the right is the state where only CO is prepared. For details, see the software section.

The breadth-first search of the previous program is as follows.

inf = 100
fac = [1]
for i in range(1, 8):
    fac.append(fac[-1] * i)

#Create a CP sequence for pruning by breadth-first search
cp = [inf for _ in range(fac[7])]
cp_solved = Cube()
cp_solved.Cp = solved.Cp
cp[cp_solved.cp2i()] = 0
que = deque([cp_solved])
while len(que):
    status = que.popleft()
    num = len(status.Moves)
    l_mov = status.Moves[-1] if num else -1
    t = (l_mov // 3) * 3
    lst = set(range(9)) - set([t, t + 1, t + 2])
    for mov in lst:
        n_status = status.move_cp(mov)
        n_idx = n_status.cp2i()
        if cp[n_idx] == inf:
            cp[n_idx] = num + 1
            que.append(n_status)

#Create a CO sequence for pruning by breadth-first search
co = [inf for _ in range(3 ** 7)]
co_solved = Cube()
co_solved.Co = solved.Co
co[co_solved.co2i()] = 0
que = deque([co_solved])
while len(que):
    status = que.popleft()
    num = len(status.Moves)
    l_mov = status.Moves[-1] if num else -1
    t = (l_mov // 3) * 3
    lst = set(range(9)) - set([t, t + 1, t + 2])
    for mov in lst:
        n_status = status.move_co(mov)
        n_idx = n_status.co2i()
        if co[n_idx] == inf:
            co[n_idx] = num + 1
            que.append(n_status)
print('Preprocessing', time() - strt, 's')

#Breadth-first search
que = deque([puzzle])
while que:
    #Remove state from queue
    status = que.popleft()

    #L the number of the last step_Put it in mov
    l_mov = status.Moves[-1] if len(status.Moves) else -1

    #List of steps to turn next
    t = (l_mov // 3) * 3
    lst = set(range(9)) - set([t, t + 1, t + 2])
    for mov in lst:
        #Actually move the puzzle
        n_status = status.move(mov)

        #I found the answer!
        if n_status.Cp == solved.Cp and n_status.Co == solved.Co:
            print(n_status.num2moves())
            print('The entire', time() - strt, 'Seconds')
            exit()
        elif len(n_status.Moves) + max(cp[n_status.cp2i()], co[n_status.co2i()]) < 11:
            #If you don't find the answer, add a state to the queue You're pruning with elif here
            que.append(n_status)

Let's see the result of this execution.

Preprocessing 0.433823823928833 s
F R F2 R2 U2 R F'
Overall 2.1692698001861572 seconds

Oh, it's a little faster. But it's still a bit late ... I'd like to aim for less than a second. And the memory usage is also moderate and severe. Even this pruned program seems to use about 4.3GB of memory. That's where IDA * comes in.

IDA* IDA * stands for Iterative Deepening A *. The specific content is described in detail in the article here, so I will omit it in my article, but personally in this article I will quote the content that I thought was the easiest to understand.

In one word, IDA * is "repeat a depth-first search (DFS) with a limited maximum depth while increasing the depth". The mechanism of IDA * is to forget the node once searched. If you forget the node, you can free up memory, right?

In other words, if the content is to solve the Rubik's cube this time, the depth (number of steps) will be investigated from 1 to 11, and ** depth-first search ** will be performed within that depth range. Also, if you search to the end at a depth of $ N-1 $ and no solution is found, forget everything you searched for. Then search again at a depth of $ N $. At first glance it's inefficient, but it works surprisingly well.

I mentioned above that depth-first search does not always find the optimal solution. But IDA * guarantees that no solution exists up to a depth of $ N-1 $ when examining the depth of $ N $. In other words, if a solution is found at a depth of $ N $, that is the optimal solution. He also mentioned that depth-first search uses relatively little memory. IDA * uses this depth-first search to significantly reduce memory usage.

Let's implement it. I will borrow up to the pruning of the previous program and rewrite after that.

# IDA*
for depth in range(1, 12):
    stack = [puzzle]
    while stack:
        #Get the state off the stack. This time it is a depth-first search, so it is not popleft
        status = stack.pop()

        #L the number of the last step_Put it in mov
        l_mov = status.Moves[-1] if len(status.Moves) else -1

        #List of steps to turn next
        t = (l_mov // 3) * 3
        lst = set(range(9)) - set([t, t + 1, t + 2])
        for mov in lst:
            #Actually move the puzzle
            n_status = status.move(mov)

            #I found the answer!
            if len(n_status.Moves) == depth - 1 and n_status.Cp == solved.Cp and n_status.Co == solved.Co:
                print(n_status.num2moves())
                print('The entire', time() - strt, 'Seconds')
                exit()
            elif len(n_status.Moves) + max(cp[n_status.cp2i()], co[n_status.co2i()]) < depth:
                #If you don't find the answer, add a state to the stack You're pruning with elif here
                stack.append(n_status)

The only thing that changed a while ago was the addition of a depth for statement and the fact that que became a stack. Queues and stacks are not covered in this article, so please refer to the articles here.

Well, how about the result.

Preprocessing 0.352100133895874 s
F R' U2 R2 F2 R' F'
Overall 0.36607813835144043 seconds

Explosive speed ...! !! Memory usage was only 93MB. It's the best IDA *.

It was pointed out that further memory savings can be expected by writing the depth-first search recursively and managing the list of rotation numbers (rotation symbols) currently being investigated as one stack. We won't cover this here as it will change the implementation significantly and it is desirable to make some class changes. In the software section, we will introduce a program that reflects this point.

Also, if the number of divisions is large, such as 3x3x3 instead of 2x2x2, it will take time to find a solution with IDA * alone, so it is common to use a two-phase algorithm.

Summary

Thank you for reading this far. I tried to write the algorithm for solving the Rubik's cube as simply as possible (although I can't explain IDA *, which is the first algorithm I learned about making this robot this time, so easily (and I). I'm not very familiar with it), so I broke it quite a bit). If you like algorithms, why not start Rubik's Cube? And if you like Rubik's Cube, why not start studying algorithms?