Updated Rubik's Cube Robot software 3. Solution search
What is this article?
I am currently developing a robot that solves a 2x2x2 Rubik's cube. This is a collection of commentary articles on the robot program.
I used to write an article collection represented by the article here, but since this time the software has been significantly updated so I will introduce a new program. think.
The corresponding code is available at here.
Related articles
"Let's make a robot that solves the Rubik's cube!"
Updated software for Rubik's Cube Robot
- Basic function
- Pre-calculation
- Solution search (this article)
- Status recognition
- Machine operation (Python)
- Machine operation (Arduino)
- Main processing
This time, we will introduce `` `solver.py``` as a solution search.
Import basic functions
Import the functions introduced in Basic Functions
from basic_functions import *
Global variables
Variables and arrays placed globally.
'''Read array'''
''' Load arrays '''
with open('cp_cost.csv', mode='r') as f:
cp_cost = [int(i) for i in f.readline().replace('\n', '').split(',')]
with open('co_cost.csv', mode='r') as f:
co_cost = [int(i) for i in f.readline().replace('\n', '').split(',')]
cp_trans = []
with open('cp_trans.csv', mode='r') as f:
for line in map(str.strip, f):
cp_trans.append([int(i) for i in line.replace('\n', '').split(',')])
co_trans = []
with open('co_trans.csv', mode='r') as f:
for line in map(str.strip, f):
co_trans.append([int(i) for i in line.replace('\n', '').split(',')])
neary_solved_idx = []
with open('neary_solved_idx.csv', mode='r') as f:
for line in map(str.strip, f):
neary_solved_idx.append([int(i) for i in line.replace('\n', '').split(',')])
neary_solved_solution = []
with open('neary_solved_solution.csv', mode='r') as f:
for line in map(str.strip, f):
if line.replace('\n', '') == '':
neary_solved_solution.append([])
else:
neary_solved_solution.append([int(i) for i in line.replace('\n', '').split(',')])
len_neary_solved = len(neary_solved_idx)
solution = []
solved_cp_idx = 0
solved_co_idx = 0
The operation of pruning and turning the puzzle, and the state of being ready in a little while are read from the CSV file.
Also, the `` `solution``` array is used for the solution search, and the solution is stored in this array by adding / deleting elements here.
Make a puzzle state array from the color states
This is a bit complicated. Manually list the colors in each part of the puzzle and their order (the order in which the colors appear when you look at the parts clockwise from diagonally above), and search for the matching parts one by one. To go.
It is an error if all the colors do not appear in 4 colors, the same parts appear multiple times, or there are parts that do not fit into any of the part candidates. The error handling here was quite troublesome.
'''Create a puzzle state array from color information'''
''' Create CO and CP arrays from the colors of stickers '''
def create_arr(colors):
#Check if all colors appear 4 each
for i in j2color:
cnt = 0
for j in colors:
if i in j:
cnt += j.count(i)
if cnt != 4:
return -1, -1
cp = [-1 for _ in range(8)]
co = [-1 for _ in range(8)]
set_parts_color = [set(i) for i in parts_color]
#Fill CP and CO one by one
for i in range(8):
tmp = []
for j in range(3):
tmp.append(colors[parts_place[i][j][0]][parts_place[i][j][1]])
tmp1 = 'w' if 'w' in tmp else 'y'
co[i] = tmp.index(tmp1)
if not set(tmp) in set_parts_color:
return -1, -1
cp[i] = set_parts_color.index(set(tmp))
tmp2 = list(set(range(7)) - set(cp))
if tmp2:
tmp2 = tmp2[0]
for i in range(7):
if cp[i] > tmp2:
cp[i] -= 1
return cp, co
I'm sorry to use a lot of meaningless variable names. It's hard to think of variable names, but I'll tell you hard about myself in the past.
Find the distance from the state of the puzzle to the solution
Since it is used for pruning during the search, it is necessary to know the distance from the state of the puzzle to the solution.
'''Returns the distance from that state to the solution'''
''' Returns the distance between the state and the solved state '''
def distance(cp_idx, co_idx):
#Returns the maximum value of each minimum cost when only CP and CO are aligned
return max(cp_cost[cp_idx], co_cost[co_idx])
This function returns the maximum values of "minimum cost for aligning only CP" and "minimum cost for aligning only CO". This number is the same as or less than the cost of actually aligning both CP and CO, isn't it? Assuming that the value returned by the distance function is $ h (cp, co) $ and the actual cost is $ h ^ * (cp, co) $
about it. At this time, it is said that it is ** acceptable **, and the shortest procedure can always be searched.
Turn the puzzle
The act of turning the puzzle is done at the index level. In other words, instead of creating an array of puzzles and replacing them, you can just look at the table using the numbers that represent the state of the puzzle. Use the table created in the previous Pre-calculation.
'''Use the transition table to change the state of the puzzle'''
''' Change the state using transition tables '''
def move(cp_idx, co_idx, twist):
return cp_trans[cp_idx][twist], co_trans[co_idx][twist]
Where `co_trans``` and `cp_trans``` are arrays that represent the transition. about this,
Transition array[State number before rotation][Rotation number] ==Status number after rotation
is. Make a transition at each of CP and CO.
Binary search
The binary search is used to search the array that enumerates the "states that can be aligned at low cost and their solutions" created by Precomputation.
This array is sorted by the combined value of CP and CO ($ cp \ times2187 + co $: where 2187 is the maximum value of CO + 1). However, this key is not represented as a continuous integer, and it is difficult to find the desired number from this key.
Therefore, we use a binary search. Binary search is the number of calculations of $ \ log_2N $ (where the bottom 2 is often omitted), strictly speaking, a loop, to find the desired element in a sorted array of $ N $ elements. I'm done. If you look at it normally, you can imagine that it is overwhelmingly fast considering that it requires a maximum of $ N $ loops. As an example, let's look at the value of $ \ log N $ at $ N = 100, 100000, 1000000000 = 10 ^ 2, 10 ^ 5, 10 ^ 9 $.
As $ N $ grows, a tremendous difference appears.
'''Binary search'''
''' Binary search '''
def bin_search(num):
#Binary search neary_Find the desired index in solved
l = 0
r = len_neary_solved
while r - l > 1:
c = (l + r) // 2
if neary_solved_idx[c][0] == num:
return c
elif neary_solved_idx[c][0] > num:
r = c
else:
l = c
if r == len_neary_solved:
return -1
if num == neary_solved_idx[l][0]:
return l
elif num == neary_solved_idx[r][0]:
return r
else:
return -1
Depth-first search
Depth-first search (strictly speaking, it may be a little different) is used in the contents of IDA * search, which is the main body of solution search. Depth-first search can be written neatly by implementing it recursively, so I implemented it recursively. Basically, use the functions introduced so far to rotate, calculate the cost, and then call yourself again. At this time, just add / delete elements (rotation numbers) to the `solution``` array placed in the global variable, and when they are aligned (when ``` True``` is returned) The `solution``` array is the solution. This is the neat point of recursion.
'''Depth-first search'''
''' Depth-first search '''
def search(cp_idx, co_idx, depth, mode):
global solution
#Use rotation in the direction orthogonal to the last hand
twist_idx_lst = [range(6, 12), range(6), range(12)]
for twist in twist_idx_lst[mode]:
#Rotate the puzzle
cost = cost_lst[twist]
n_cp_idx, n_co_idx = move(cp_idx, co_idx, twist)
#Update remaining depth
n_depth = depth - cost - grip_cost
#Calculate the value to use for the next recursion
n_mode = twist // 6
n_dis = distance(n_cp_idx, n_co_idx)
if n_dis > n_depth:
continue
#Add elements to the global procedure array
solution.append(twist)
#If you are in a state where you can get it at a low cost calculated in advance
if n_dis <= neary_solved_depth <= n_depth:
tmp = bin_search(n_cp_idx * 2187 + n_co_idx)
if tmp >= 0 and neary_solved_solution[tmp][0] // 6 != solution[-1] // 6:
solution.extend(neary_solved_solution[tmp])
return True, grip_cost + neary_solved_idx[tmp][1]
#Search for the next depth
tmp, ans_cost = search(n_cp_idx, n_co_idx, n_depth, n_mode)
if tmp:
return True, ans_cost
#If no solution is found, pop the element from the global procedure array
solution.pop()
return False, -1
IDA * Search
It's finally Honmaru. That said, the IDA * search is not a complicated implementation, as it only performs a depth-first search many times while increasing the maximum depth.
If it is in the "ready" state before the search, it will not be searched. When searching, the depth-first search is performed while increasing `` `depth``` in order from 1. When a solution is found, the search is aborted and the solution (converted to facilitate the next process) is returned.
''' IDA*search'''
''' IDA* algorithm '''
def solver(colors):
global solution
#Find CP and CO indexes
cp, co = create_arr(colors)
if cp == -1 or co == -1:
return -1, -1
cp_idx = cp2idx(cp)
co_idx = co2idx(co)
#If you already know the answer before exploring
if distance(cp_idx, co_idx) <= neary_solved_depth:
tmp = bin_search(cp_idx * 2187 + co_idx)
if tmp >= 0:
return [twist_lst[i] for i in neary_solved_solution[tmp]], neary_solved_idx[tmp][1]
res_cost = 0
# IDA*
for depth in range(1, 34):
solution = []
tmp, cost = search(cp_idx, co_idx, depth, 2)
if tmp:
res_cost = depth + cost
break
if solution == []:
return -1, res_cost
return [twist_lst[i] for i in solution], res_cost
Summary
This time, I explained the solution search program, which is the most interesting (I feel) of this robot. I think the method described here can be used to solve various other puzzles. I hope it will be helpful for those who want to solve puzzles.
Recommended Posts