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.
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.
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.
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
)
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
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
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'.
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
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.
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.
Recommended Posts