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.

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

Updated software for Rubik's Cube Robot

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

This time, I will introduce `` `create_array.py``` as a pre-calculation edition.

Import of libraries etc.

Import the library and the Basic Functions (https://qiita.com/Nyanyan_Cube/items/e225e8e31897d81a1401)

from collections import deque
import csv

from basic_functions import *

Create a state transition table

The state transition function created in the previous article is a bit slow. It will take time to use this function one by one to transition the state hundreds of thousands or millions of times in the future. Therefore, in order to finish the state transition immediately (complexity $ O (1) $), create a state transition array.

Transition array[State number before rotation][Rotation number] =Status number after rotation

Create a transition array that becomes.

'''Create a state transition table'''
''' Create state transition tables '''

def create_cp_trans():
    #CP transition array
    # 8!Describe how to transition with 12 types of rotation for each of the individual states
    cp_trans = [[-1 for _ in range(12)] for _ in range(fac[8])]
    #Turn the number idx that represents the state before the transition
    for idx in range(fac[8]):
        if idx % 1000 == 0:
            print(idx / fac[8])
        #Create a CP array from idx and actually turn it
        cp = idx2cp(idx)
        for i, twist in enumerate(twist_lst):
            twisted_cp = [j for j in cp]
            for each_twist in twist:
                twisted_cp = move_cp(twisted_cp, each_twist)
            #Convert CP array to unique number
            twisted_idx = cp2idx(twisted_cp)
            cp_trans[idx][i] = twisted_idx
    #Save to CSV file
    with open('cp_trans.csv', mode='w') as f:
        writer = csv.writer(f, lineterminator='\n')
        for line in cp_trans:
            writer.writerow(line)
    print('cp trans done')

def create_co_trans():
    #The content of the process is create_cp_Only trans CP became CO
    co_trans = [[-1 for _ in range(12)] for _ in range(3 ** 7)]
    for idx in range(3 ** 7):
        if idx % 1000 == 0:
            print(idx / 3 ** 7)
        co = idx2co(idx)
        for i, twist in enumerate(twist_lst):
            twisted_co = [j for j in co]
            for each_twist in twist:
                twisted_co = move_co(twisted_co, each_twist)
            twisted_idx = co2idx(twisted_co)
            co_trans[idx][i] = twisted_idx
    with open('co_trans.csv', mode='w') as f:
        writer = csv.writer(f, lineterminator='\n')
        for line in co_trans:
            writer.writerow(line)
    print('co trans done')

Fill the array efficiently using the function that goes back and forth between the state array and the state number in the basic function, and save the last array in a CSV file.

The twist_lst used for rotation is the array that appeared in the previous Basic Functions, and is the original rotation symbol of the puzzle. It is a summary of.

Make a pruning array

When actually searching for a solution to a puzzle, the search is stopped when it is known that "the solution can never be found even if you search further". This is called pruning.

It is this pruning array that is used to check if "no solution can be found by further search". In this array, CP and CO are recorded separately, and the cost for each state is recorded. By the way, CP and CO are separate because the number of states explodes and the memory usage becomes enormous when both are taken into consideration.

'''Make a pruning array'''
''' Create prunning tables '''

def create_cp_cost():
    #Read the state transition array
    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(',')])
    # 8!Calculate the cost for each state
    cp_cost = [1000 for _ in range(fac[8])]
    #Breadth-first search is done, so the first in the queue(Aligned)Put the state
    solved_cp_idx = [cp2idx(i) for i in solved_cp]
    que = deque([[i, 0] for i in solved_cp_idx])
    for i in solved_cp_idx:
        cp_cost[i] = 0
    cnt = 0
    #Breadth-first search
    while que:
        cnt += 1
        if cnt % 1000 == 0:
            print(cnt, len(que))
        #Get state from queue
        cp, cost = que.popleft()
        twists = range(12)
        #Rotate and calculate cost
        for twist, cost_pls in zip(twists, cost_lst):
            twisted_idx = cp_trans[cp][twist]
            n_cost = cost + grip_cost + cost_pls
            #Update the array when there is a cost update and add it to the queue
            if cp_cost[twisted_idx] > n_cost:
                cp_cost[twisted_idx] = n_cost
                que.append([twisted_idx, n_cost])
    #Save to CSV file
    with open('cp_cost.csv', mode='w') as f:
        writer = csv.writer(f, lineterminator='\n')
        writer.writerow(cp_cost)
    print('cp cost done')

def create_co_cost():
    #The content of the process is create_cp_Only trans CP became CO
    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(',')])
    co_cost = [1000 for _ in range(3 ** 7)]
    solved_co_idx = list(set([co2idx(i) for i in solved_co]))
    que = deque([[i, 0] for i in solved_co_idx])
    for i in solved_co_idx:
        co_cost[i] = 0
    cnt = 0
    while que:
        cnt += 1
        if cnt % 1000 == 0:
            print(cnt, len(que))
        co, cost = que.popleft()
        twists = range(12)
        for twist, cost_pls in zip(twists, cost_lst):
            twisted_idx = co_trans[co][twist]
            n_cost = cost + grip_cost + cost_pls
            if co_cost[twisted_idx] > n_cost:
                co_cost[twisted_idx] = n_cost
                que.append([twisted_idx, n_cost])
    with open('co_cost.csv', mode='w') as f:
        writer = csv.writer(f, lineterminator='\n')
        writer.writerow(co_cost)
    print('co cost done')

Basic processing is performed by breadth-first search. Queue the 24 types of states that are initially aligned (there are 24 states depending on the viewing direction even for the same puzzle), and get the status from the queue in the `` `while``` statement. Will be processed sequentially.

For the rotation process, use the transition array in the state created earlier. Of course you can do it without using it, but it takes an order of magnitude longer.

List the states that will be ready in a little while

In the solution search, I use IDA *, which is the most suitable algorithm for the Rubik's cube solution search. See / items / 60f3699db96dba4a4bf5)), in this program we will search for a solution to minimize the cost: ** a value close to the time it takes to solve the puzzle **. Using this makes the search heavier than using other indicators such as effort. Therefore, when the puzzle was solved by a certain cost or more, the search was ended there, and the pre-calculated solutions were combined to make the whole solution. It is necessary to decide how many "states that can be solved in a little while" are listed depending on the memory and calculation time.

This state enumeration needs to be created using reverse rotation from the state where the puzzles are complete. Therefore, first, create a state transition array for reverse rotation. After that is the main story.

Part 1 Create a state transition array by reverse rotation

As mentioned above, create a state transition array for the reverse rotation of the puzzle procedure. At this point, you may be wondering, "Isn't it possible to reuse the transition array created earlier?" However, due to the structure of the robot, reverse rotation is not included in the array created earlier. This is because the robot has a structure that can always rotate the puzzle only counterclockwise. For more details, please see Hardware edition of "Let's make a robot that solves the Rubik's cube!".

'''Create a state transition array when the reverse procedure is turned'''
''' Create state transition tables for reverse twists'''

def create_cp_trans_rev():
    #The basic process is create_cp_Same as trans
    cp_trans_rev = [[-1 for _ in range(12)] for _ in range(fac[8])]
    for idx in range(fac[8]):
        if idx % 1000 == 0:
            print(idx / fac[8])
        cp = idx2cp(idx)
        for i, twist in enumerate(twist_lst):
            twisted_cp = [j for j in cp]
            for each_twist in twist:
                twisted_cp = move_cp(twisted_cp, each_twist)
            twisted_idx = cp2idx(twisted_cp)
            # create_cp_Unlike trans, cp_trans_rev[twisted_idx][i]To update
            cp_trans_rev[twisted_idx][i] = idx
    with open('cp_trans_rev.csv', mode='w') as f:
        writer = csv.writer(f, lineterminator='\n')
        for line in cp_trans_rev:
            writer.writerow(line)
    print('cp trans rev done')

def create_co_trans_rev():
    #The basic process is create_co_Same as trans
    co_trans_rev = [[-1 for _ in range(12)] for _ in range(3 ** 7)]
    for idx in range(3 ** 7):
        if idx % 1000 == 0:
            print(idx / 3 ** 7)
        co = idx2co(idx)
        for i, twist in enumerate(twist_lst):
            twisted_co = [j for j in co]
            for each_twist in twist:
                twisted_co = move_co(twisted_co, each_twist)
            twisted_idx = co2idx(twisted_co)
            # create_co_Unlike trans, co_trans_rev[twisted_idx][i]To update
            co_trans_rev[twisted_idx][i] = idx
    with open('co_trans_rev.csv', mode='w') as f:
        writer = csv.writer(f, lineterminator='\n')
        for line in co_trans_rev:
            writer.writerow(line)
    print('co trans rev done')

It is very similar to the program when the previous state fiber arrangement was made, but there is one difference.

Reverse rotation state transition array[Number after rotation][Rotation number] =Number before rotation

This is where you have to.

Part 2 List the states that will be ready soon

Use breadth-first search to enumerate the states. But,

State number
Cost from that state to completion
Procedure from that state to completion

It is a little troublesome because it is necessary to hold a lot of parameters.

Also, even if you have already visited, you may be able to complete it at a lower cost than when you visited before. To reduce the amount of computation in that case (although this method is a bit verbose and I think there is a better way), use `` `neary_solved_idx, neary_solved_cost_dic, neary_solved_idx_dic```.

The actual solution search uses a combination of CP and CO numbers to get the elements in this array using a binary search. Therefore, sort the resulting array before saving.

'''List the states that will be ready in a little while'''
''' Create array of states that can be solved soon '''

def create_neary_solved():
    #Read the reverse procedure transition array
    cp_trans_rev = []
    with open('cp_trans_rev.csv', mode='r') as f:
        for line in map(str.strip, f):
            cp_trans_rev.append([int(i) for i in line.replace('\n', '').split(',')])
    co_trans_rev = []
    with open('co_trans_rev.csv', mode='r') as f:
        for line in map(str.strip, f):
            co_trans_rev.append([int(i) for i in line.replace('\n', '').split(',')])
    # neary_We will update the solved array, but prepare other arrays to speed up the calculation.
    neary_solved = []
    neary_solved_idx = set()
    neary_solved_cost_dic = {}
    neary_solved_idx_dic = {}
    #Create a breadth-first search queue
    solved_cp_idx = [cp2idx(i) for i in solved_cp]
    solved_co_idx = [co2idx(i) for i in solved_co]
    que = deque([])
    for i in range(24):
        twisted_idx = solved_cp_idx[i] * 2187 + solved_co_idx[i]
        neary_solved_idx.add(twisted_idx)
        neary_solved_cost_dic[twisted_idx] = 0
        neary_solved_idx_dic[twisted_idx] = len(neary_solved)
        neary_solved.append([twisted_idx, 0, []])
        que.append([solved_cp_idx[i], solved_co_idx[i], 0, [], 2])
    twists = [range(6, 12), range(6), range(12)]
    cnt = 0
    while que:
        cnt += 1
        if cnt % 1000 == 0:
            print(cnt, len(que))
        #Get state from queue
        cp_idx, co_idx, cost, move, mode = que.popleft()
        for twist in twists[mode]:
            #Get state and cost after rotation, update procedure list
            cost_pls = cost_lst[twist]
            twisted_cp_idx = cp_trans_rev[cp_idx][twist]
            twisted_co_idx = co_trans_rev[co_idx][twist]
            twisted_idx = twisted_cp_idx * 2187 + twisted_co_idx
            n_cost = cost + grip_cost + cost_pls
            n_mode = twist // 6
            n_move = [i for i in move]
            n_move.append(twist)
            if neary_solved_depth >= n_cost and not twisted_idx in neary_solved_idx:
                #If you see it anew
                neary_solved_idx.add(twisted_idx)
                neary_solved_cost_dic[twisted_idx] = n_cost
                neary_solved_idx_dic[twisted_idx] = len(neary_solved)
                neary_solved.append([twisted_idx, n_cost, list(reversed(n_move))])
                que.append([twisted_cp_idx, twisted_co_idx, n_cost, n_move, n_mode])
            elif neary_solved_depth >= n_cost and neary_solved_cost_dic[twisted_idx] > n_cost:
                #If you have already seen it, but you can reach it at a lower cost than that time
                neary_solved_cost_dic[twisted_idx] = n_cost
                neary_solved[neary_solved_idx_dic[twisted_idx]] = [twisted_idx, n_cost, list(reversed(n_move))]
                que.append([twisted_cp_idx, twisted_co_idx, n_cost, n_move, n_mode])
    #Since the solver part uses a 2-minute search, sort by index in advance.
    neary_solved.sort()
    #Save the index and cost as an array in CSV
    with open('neary_solved_idx.csv', mode='w') as f:
        writer = csv.writer(f, lineterminator='\n')
        for line in [i[:2] for i in neary_solved]:
            writer.writerow(line)
    #Save the procedure to a CSV array
    with open('neary_solved_solution.csv', mode='w') as f:
        writer = csv.writer(f, lineterminator='\n')
        for line in [i[2] for i in neary_solved]:
            writer.writerow(line)
    print('neary solved done')

Summary

This time, we pre-calculated various arrays used to search for the solution of the Rubik's cube. Actually, the target array is created by executing all the introduced functions. The solver reads these arrays and uses them in the solution search.

Updated software for Rubik's Cube Robot 2. Pre-calculation