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 a collection of articles 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.

"Let's make a robot that solves the Rubik's cube!"

"Updated software for Rubik's Cube Robot"

Basic function (this article)
Pre-calculation
Solution search
State recognition
Machine operation (Python)
Machine operation (Arduino)
Main processing

This time, I will introduce `` `basic_functions.py``` as a basic function edition.

Function to rotate the puzzle

Learn how to keep the puzzle as an array and how to implement the process of rotating the puzzle.

'''Function to rotate the cube'''
''' Functions for twisting cube '''

#Rotation processing CP
# Rotate CP
def move_cp(cp, arr):
    #Replace parts using surface and replace arrays
    surface = [[3, 1, 7, 5], [1, 0, 6, 7], [0, 2, 4, 6], [2, 3, 5, 4]]
    replace = [[3, 0, 1, 2], [2, 3, 0, 1], [1, 2, 3, 0]]
    res = [i for i in cp]
    for i, j in zip(surface[arr[0]], replace[-(arr[1] + 1)]):
        res[surface[arr[0]][j]] = cp[i]
    return res

#Rotation processing CO
# Rotate CO
def move_co(co, arr):
    #After replacing the parts using the surface and replace arrays, the pls array is used to reproduce the change in CO when rotated 90 degrees.
    surface = [[3, 1, 7, 5], [1, 0, 6, 7], [0, 2, 4, 6], [2, 3, 5, 4]]
    replace = [[3, 0, 1, 2], [2, 3, 0, 1], [1, 2, 3, 0]]
    pls = [2, 1, 2, 1]
    res = [i for i in co]
    for i, j in zip(surface[arr[0]], replace[-(arr[1] + 1)]):
        res[surface[arr[0]][j]] = co[i]
    if arr[1] != -2:
        for i in range(4):
            res[surface[arr[0]][i]] += pls[i]
            res[surface[arr[0]][i]] %= 3
    return res

The 2x2x2 Rubik's Cube (colored purses) has eight parts of one type as shown in the figure. iOS の画像(26).jpg It wouldn't be great if you had this puzzle state in a color arrangement, for example, but it uses a lot of memory and is awkward above all. Therefore, we will keep the puzzle state in two arrays.

CP (Corner Permutation) array showing the order of each part
CO (Corner Orientation) array showing the orientation of each part

There are two types. Each is represented by an array with 8 elements. Since there are 8 parts, the elements of the CP array are `0, 1, 2, 3, 4, 5, 6, 7`, and there are 3 types of orientation of each part, so the CO array The elements are 0, 1, 2.

The introduced function basically expresses the ** rotation ** action of the puzzle by ** replacement ** of the array. Regarding the CO arrangement, the orientation of the parts changes depending on how the puzzle is turned, so there is additional processing.

State indexing

It's not very good to keep the puzzles in an array at all times. It takes a long time to process and consumes memory. Therefore, in the next article (pre-calculation), we will associate a unique value for each puzzle state. I will explain the ** function that connects arrays and values **, which is very useful at this time.

'''Array indexing'''
''' Indexing'''

#Create a unique number from the cp array
# Return the number of CP
def cp2idx(cp):
    #Indexed by factorial
    res = 0
    for i in range(8):
        cnt = cp[i]
        for j in cp[:i]:
            if j < cp[i]:
                cnt -= 1
        res += fac[7 - i] * cnt
    return res

#Create a unique number from the co array
# Return the number of CO
def co2idx(co):
    #Indexed in ternary. The state is uniquely determined by looking at the 7 parts
    res = 0
    for i in co[:7]:
        res *= 3
        res += i
    return res

#Create a cp array from a unique number
# Return the array of CP
def idx2cp(cp_idx):
    #Factorial to array conversion
    res = [-1 for _ in range(8)]
    for i in range(8):
        candidate = cp_idx // fac[7 - i]
        marked = [True for _ in range(i)]
        for _ in range(8):
            for j, k in enumerate(res[:i]):
                if k <= candidate and marked[j]:
                    candidate += 1
                    marked[j] = False
        res[i] = candidate
        cp_idx %= fac[7 - i]
    return res

#Create a co array from a unique number
# Return the array of CO
def idx2co(co_idx):
    #Conversion from ternary to array
    res = [0 for _ in range(8)]
    for i in range(7):
        res[6 - i] = co_idx % 3
        co_idx //= 3
    res[7] = (3 - sum(res) % 3) % 3
    return res

For indexing, the factorial number is used because the CP array can be numbered in a permutation. The CO array considers the array itself as a 7-digit decimal number and converts it to a decimal number.

For the calculation of factorial number, I just implemented what is written on the site of here.

You may be wondering about the indexing of CO arrays, "Why do you consider it as a 7-digit ternary number even though the number of elements is 8?" As long as the CO of the puzzle is aligned, you can see the state of the remaining one part by looking at the seven parts. That's why a 7-digit ternary number is sufficient.

Frequently used constants

The constants and arrays that are often used in multiple programs are written together.

'''constant'''
''' Constants '''

#Factorial value
fac = [1]
for i in range(1, 9):
    fac.append(fac[-1] * i)

#Frequently used values and arrays
grip_cost = 1
j2color = ['g', 'b', 'r', 'o', 'y', 'w']
dic = {'w':'white', 'g':'green', 'r':'red', 'b':'blue', 'o':'magenta', 'y':'yellow'}
parts_color = [['w', 'o', 'b'], ['w', 'b', 'r'], ['w', 'g', 'o'], ['w', 'r', 'g'], ['y', 'o', 'g'], ['y', 'g', 'r'], ['y', 'b', 'o'], ['y', 'r', 'b']]
parts_place = [[[0, 2], [2, 0], [2, 7]], [[0, 3], [2, 6], [2, 5]], [[1, 2], [2, 2], [2, 1]], [[1, 3], [2, 4], [2, 3]], [[4, 2], [3, 1], [3, 2]], [[4, 3], [3, 3], [3, 4]], [[5, 2], [3, 7], [3, 0]], [[5, 3], [3, 5], [3, 6]]]
twist_lst = [[[0, -1]], [[0, -2]], [[2, -1]], [[0, -1], [2, -1]], [[0, -2], [2, -1]], [[0, -1], [2, -2]], [[1, -1]], [[1, -2]], [[3, -1]], [[1, -1], [3, -1]], [[1, -2], [3, -1]], [[1, -1], [3, -2]]]
cost_lst = [1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 2]
solved_cp = [[0, 1, 2, 3, 4, 5, 6, 7], [2, 3, 4, 5, 6, 7, 0, 1], [4, 5, 6, 7, 0, 1, 2, 3], [6, 7, 0, 1, 2, 3, 4, 5], [1, 7, 3, 5, 2, 4, 0, 6], [3, 5, 2, 4, 0, 6, 1, 7], [2, 4, 0, 6, 1, 7, 3, 5], [0, 6, 1, 7, 3, 5, 2, 4], [7, 6, 5, 4, 3, 2, 1, 0], [5, 4, 3, 2, 1, 0, 7, 6], [3, 2, 1, 0, 7, 6, 5, 4], [1, 0, 7, 6, 5, 4, 3, 2], [6, 0, 4, 2, 5, 3, 7, 1], [4, 2, 5, 3, 7, 1, 6, 0], [5, 3, 7, 1, 6, 0, 4, 2], [7, 1, 6, 0, 4, 2, 5, 3], [2, 0, 3, 1, 5, 7, 4, 6], [3, 1, 5, 7, 4, 6, 2, 0], [5, 7, 4, 6, 2, 0, 3, 1], [4, 6, 2, 0, 3, 1, 5, 7], [6, 4, 7, 5, 1, 3, 0, 2], [7, 5, 1, 3, 0, 2, 6, 4], [1, 3, 0, 2, 6, 4, 7, 5], [0, 2, 6, 4, 7, 5, 1, 3]]
solved_co = [[0, 0, 0, 0, 0, 0, 0, 0], [2, 1, 1, 2, 2, 1, 1, 2], [0, 0, 0, 0, 0, 0, 0, 0], [2, 1, 1, 2, 2, 1, 1, 2], [1, 2, 2, 1, 1, 2, 2, 1], [1, 2, 2, 1, 1, 2, 2, 1], [1, 2, 2, 1, 1, 2, 2, 1], [1, 2, 2, 1, 1, 2, 2, 1], [0, 0, 0, 0, 0, 0, 0, 0], [2, 1, 1, 2, 2, 1, 1, 2], [0, 0, 0, 0, 0, 0, 0, 0], [2, 1, 1, 2, 2, 1, 1, 2], [1, 2, 2, 1, 1, 2, 2, 1], [1, 2, 2, 1, 1, 2, 2, 1], [1, 2, 2, 1, 1, 2, 2, 1], [1, 2, 2, 1, 1, 2, 2, 1], [0, 0, 0, 0, 0, 0, 0, 0], [2, 1, 1, 2, 2, 1, 1, 2], [0, 0, 0, 0, 0, 0, 0, 0], [2, 1, 1, 2, 2, 1, 1, 2], [0, 0, 0, 0, 0, 0, 0, 0], [2, 1, 1, 2, 2, 1, 1, 2], [0, 0, 0, 0, 0, 0, 0, 0], [2, 1, 1, 2, 2, 1, 1, 2]]
neary_solved_depth = 15

I will explain the meaning of each constant and array when actually using it.

Summary

I explained the basic functions of the Rubik's Cube robot. All other programs use this function and constants.

[PYTHON] Rubik's Cube Robot Software Updated 1. Basic Functions

What is this article?

Related articles

Function to rotate the puzzle

State indexing

Frequently used constants

Summary