Let's write a program to solve the Rubik's Cube (Part 2: IDA * Search)

Introduction

This article is the 17th day article of Speedcubing Advent Calendar 2019. [Series] Let's write a program to solve the Rubik's Cube (Part 1) We will continue.

In the first part, I created a class that expresses the state / operation of the Rubik's cube and wrote a method to operate the state. Now that you can rotate the cube programmatically, let's proceed with the search.

In the second part, we will search by brute force, so we will not be able to find the solution of the Rubik's cube in any state yet, but small puzzles such as Pyraminx and 2x2x2 cubes can also be solved by this method.

environment

As for the environment, Python 3.6 or higher is the same as the first part.

Continuing from the first part, a Colaboratory notebook version of the code that appears below I also prepared, so if you click [Open in Play Ground] and proceed while executing in order, you will not need to build an environment and it will be easier.

Solve the Rubik's Cube by brute force

The Rubik's Cube has about 4.3 * 10 ^ 19 states, and the shortest number of moves is about 18 on average. It is known to be completed in 20 hands in the worst case (c.f. https://www.cube20.org/).

Brute force is a scale that cannot be matched in a realistic time, but first, let's write a program to solve the Rubik's cube by brute force, and improve based on that.

Breadth-first search uses too much memory due to the huge number of states in the Rubik's cube. To brute force the Rubik's Cube, [Iterative Deepening Depth-First Search](https://ja.wikipedia.org/wiki/%E5%8F%8D%E5%BE%A9%E6%B7%B1% E5% 8C% 96% E6% B7% B1% E3% 81% 95% E5% 84% AA% E5% 85% 88% E6% 8E% A2% E7% B4% A2) can be used. This is a method of repeating a depth-first search (depth-constrained search) with a limit on the search depth (solution length) by gradually increasing the limit depth.

Function to determine the completion status

First, I have to write a function to judge whether the state that appears in the search process is a completed state. If all of EO, CO, EP, and CP are complete, it means that the product is complete, so I wrote a function to judge that.

def is_solved(state):
    return (state.eo == [0] * 12  #All EOs are available
            and state.co == [0] * 8  #All CO is available
            and state.ep == list(range(12))  #All EPs are available
            and state.cp == list(range(8))  #All CPs are available
            )

A function that returns whether the operation can be used as the next move

Write a function that refers to the previous move and returns whether the operation can be used as the next move.

In a simple case, it is not possible to rotate the same surface continuously. (Such as R'R2) Besides, ʻU D U is the same as ʻU2 D, so it's bad. To avoid this, when turning face-to-face continuously, fix the order in the dictionary order of face names (like D U order is good, but ʻU D` order is not).

inv_face = {
    "U": "D",
    "D": "U",
    "L": "R",
    "R": "L",
    "F": "B",
    "B": "F"
}

def is_move_available(prev_move, move):
    """
Determine if the operation can be used as the next move by considering the previous move
    -Do not rotate the same surface continuously(e.g. R'R2 is not possible)
    -Fix the order when turning face-to-face(e.g.D U is good, but U D is not)
    """
    if prev_move is None:
        return True  #Any operation is possible for the first move
    prev_face = prev_move[0]  #The surface turned one side
    if prev_face == move[0]:
        return False #Same side is not possible
    if inv_face[prev_face] == move[0]:
        return prev_face < move[0] #When face-to-face, dictionary order is acceptable
    return True

Implementation of iterative deepening depth-first search

I wrote it like this. start_search calls the implementation of depth-limited search, starting from 0 moves and gradually increasing the number of moves, and returns it when it finds a solution. The argument depth of depth_limited_search represents the remaining depth, and while reducing this, the search proceeds recursively so that when depth = 0, the number of steps currently being searched is reached.

Prepare one stack to manage the solution (procedure) you are thinking about. If you push the operation when entering the next node in the process of searching and pop it when exiting, the solution currently being searched will always be in this stack, and it is not necessary to have a solution for each state.

class Search:
    def __init__(self):
        self.current_solution = []  #Stack to put the procedure you are searching for

    def depth_limited_search(self, state, depth):
        if depth == 0 and is_solved(state):
            # is_If solved is True, it is completed, so it returns True because the solution was found.
            # depth==0 is not required, but depth>You don't have to call the decision function every time because you already know that 0 has no solution
            return True
        if depth == 0:  #Returns False if the solution is not found after reaching depth 0
            return False

        # depth=Continue searching until 0
        prev_move = self.current_solution[-1] if self.current_solution else None  #1 front operation
        for move_name in move_names:
            if not is_move_available(prev_move, move_name):
                continue
            self.current_solution.append(move_name)
            if self.depth_limited_search(state.apply_move(moves[move_name]), depth - 1):
                return True
            self.current_solution.pop()

    def start_search(self, state, max_length=20):
        for depth in range(0, max_length):  #Repeat the depth-limited search while gradually increasing the number of steps from 0
            print(f"# Start searching length {depth}")
            if self.depth_limited_search(state, depth):
                #If a solution is found, return it at that point
                return " ".join(self.current_solution)
        return None

Try performing an iterative deepening depth-first search

In this implementation, we can't find a solution for ordinary random scrambling in a realistic time, so let's give it a suitable 6-hand scramble. The solution was found in 34 seconds. Naturally, the solution is to turn the scramble in the opposite direction.

import time
scramble = "R U R' F2 D2 L"
scrambled_state = scamble2state(scramble)
search = Search()
start = time.time()
solution = search.start_search(scrambled_state)
print(f"Finished! ({time.time() - start:.2f} sec.)")
if solution:
  print(f"Solution: {solution}.")
else:
  print("Solution not found.")
Finished! (34.11 sec.)
Solution: L' D2 F2 R U' R'.

Speeding up by pruning (IDA * search)

Pruning is a technique for speeding up the search. With your prior knowledge of the Rubik's Cube, you can round up more and more if you find it meaningless to explore further. This knowledgeable iterative deepening depth search is called an IDA * search (c.f. https://en.wikipedia.org/wiki/Iterative_deepening_A *).

For example, what if you didn't have any of the parts you had at depth = 1 (1 move left)? Try manually pulling the Rubik's Cube from the finished state. With one move left, if you don't have at least four corners and eight edges, you won't be able to do it with your next move. Therefore, it is meaningless to proceed with the search for the next move, depth = 0.

Similarly, when depth = 2 (2 moves left), all corners may be broken (eg LR), but if you don't have 4 edges, you'll have 2 moves left. There is no possibility of doing it.

With depth = 3 (3 moves left), if you don't have at least 2 edges at that point, you won't be able to complete with 3 moves left.

Let's implement pruning using this knowledge.

def count_solved_corners(state):
    """
Count the number of aligned corners
    """
    return sum([state.cp[i] == i and state.co[i] == 0 for i in range(8)])


def count_solved_edges(state):
    """
Count the number of aligned edges
    """
    return sum([state.ep[i] == i and state.eo[i] == 0 for i in range(12)])


def prune(depth, state):
    """
Returns True if it makes no sense to proceed with the search further
    """
    if depth == 1 and (count_solved_corners(state) < 4 or count_solved_edges(state) < 8):
        #If there are less than 4 corners aligned with the remaining 1 hand, or if there are less than 8 aligned edges, they will no longer be aligned.
        return True
    if depth == 2 and count_solved_edges(state) < 4:
        #If there are less than 4 edges aligned with the remaining 2 hands, they will not be aligned anymore
        return True
    if depth == 3 and count_solved_edges(state) < 2:
        #If there are less than 2 edges that are aligned with the remaining 3 hands, they will not be aligned anymore
        return True
    return False
class Search:
    def __init__(self):
        self.current_solution = []

    def depth_limited_search(self, state, depth):
        if depth == 0 and is_solved(state):
            return True
        if depth == 0:
            return False

        #Pruning(Only the addition of these two lines has changed)
        if prune(depth, state):
            return False

        prev_move = self.current_solution[-1] if self.current_solution else None  #1 front operation
        for move_name in move_names:
            if not is_move_available(prev_move, move_name):
                continue
            self.current_solution.append(move_name)
            if self.depth_limited_search(state.apply_move(moves[move_name]), depth - 1):
                return True
            self.current_solution.pop()

    def start_search(self, state, max_length=20):
        for depth in range(0, max_length):
            print(f"# Start searching length {depth}")
            if self.depth_limited_search(state, depth):
                return " ".join(self.current_solution)
        return None

Exploration time when pruning

Searching that took 34 seconds is now less than 1 second. As you can see, pruning is very powerful.

scramble = "R U R' F2 D2 L"
scrambled_state = scamble2state(scramble)
search = Search()
start = time.time()
solution = search.start_search(scrambled_state)
print(f"Finished! ({time.time() - start:.2f} sec.)")
if solution:
  print(f"Solution: {solution}.")
else:
  print("Solution not found.")
Finished! (0.21 sec.)
Solution: L' D2 F2 R U' R'.

With this alone, small puzzles such as Pyraminx and 2x2x2 cubes can be solved in a realistic amount of time. Some enthusiasts may want to explore a portion of the Rubik's cube (such as a crossing procedure or a procedure for aligning 2x2x3 blocks), but if it's short, this is the way to go. It is possible to search for multiple types of solutions by modifying the search so that the search continues instead of returning immediately after finding the first solution.

Next Notice: State Indexing + Two-Phase-Algorithm

I wrote a program to solve the Rubik's cube by brute force, and I was able to speed it up a little by pruning, but it is far from finding a solution in a short time from any state.

Two-Phase-Algorithm is widely used as an algorithm to find the suboptimal solution of the Rubik's cube in a realistic time. The Rubik's Cube solution is broken down into two phases, each of which is brute force.

In Phase 1, you can move the Rubik's Cube freely and bring it to a state where it can be completed with just the movement of <U, D, R2, L2, F2, B2>. In Phase2, we will use only the movements of <U, D, R2, L2, F2, B2> to bring it to completion.

Phase 1 is the worst 12 moves, about 10 moves, Phase 2 can be completed in 18 moves at worst, about 13-14 moves (c.f. http://kociemba.org/math/symmetric.htm).

The deeper the search depth (procedure length), the more exponentially the search range increases, so it takes about 18 moves to brute force without dividing the phase, while 10 moves and 13 moves. It will be faster if you divide it into searches.

It is important that the Two-Phase-Algorithm is properly decomposed into two phases and divided into two steps that require less effort, but it is also important that the number of states in each phase is increased by dividing the phase into two. The number of states can be reduced, the state can be indexed and a state transition table can be created in advance, and the table for pruning can also be calculated in advance. In the implementation of the second part, an instance of the State class is created every time the search is performed, and that part is actually slow. You can improve that by indexing the state.

Another feature is that if you take the time to search, you can get closer to the optimal solution. The implementation of Two-Phase-Algorithm will be left in the second part.

References

Recommended Posts

Let's write a program to solve the Rubik's Cube (Part 2: IDA * Search)
Let's write a program to solve the 4x4x4 Rubik's Cube! 2. Algorithm
Let's write a program to solve the 4x4x4 Rubik's Cube! 3. Implementation
Write a program to solve the 4x4x4 Rubik's Cube! 1. Overview
How to make a program to solve Rubik's Cube starting from PC Koshien 2014 Floppy Cube
Write a python program to find the editing distance [python] [Levenshtein distance]
Let's make a robot that solves the Rubik's Cube! 2 Algorithm
Let's make a robot that solves the Rubik's Cube! 3 Software
Let's make a robot that solves the Rubik's Cube! 1 Overview
Let's write a simple simulation program for the "Monty Hall problem"
I made a program to solve (hint) Saizeriya's spot the difference
Try to write a program that abuses the program and sends 100 emails
Various comments to write in the program
Let's write a Python program and run it
How to write a GUI using the maya command
I want to write in Python! (2) Let's write a test
I tried to solve the soma cube with python
A program to write Lattice Hinge with Rhinoceros with Python
How to use the Rubik's Cube solver library "kociemba"
To write a test in Go, first design the interface
I didn't want to write the AWS key in the program
Let's search from the procession
How to start the program
[Note] Let's try to predict the amount of electricity used! (Part 1)
I wanted to solve the ABC164 A ~ D problem with Python
Write a script to calculate the distance with Elasticsearch 5 system painless
Solve the subset sum problem with a full search in Python
Let's modify the computer Go program CgfGoBan to support multiple program languages
[Python] A program that rotates the contents of the list to the left