ルービックキューブロボットのソフトウェアをアップデートした 1. 基本関数

この記事はなに？

私は現在2x2x2ルービックキューブを解くロボットを開発中です。これはそのロボットのプログラムの解説記事集です。

かつてこちらの記事に代表される記事集を書きましたが、この時からソフトウェアが大幅にアップデートされたので新しいプログラムについて紹介しようと思います。

該当するコードはこちらで公開しています。

関連する記事集

「ルービックキューブを解くロボットを作ろう！」

1. 概要編
2. アルゴリズム編
3. ソフトウェア編
4. ハードウェア編

「ルービックキューブロボットのソフトウェアをアップデートした」

1. 基本関数(本記事)
2. 事前計算
3. 解法探索
4. 状態認識
5. 機械操作(Python)
6. 機械操作(Arduino)
7. 主要処理

今回は基本関数編として、basic_functions.pyを紹介します。

パズルを回転させる関数

パズルを配列として保持するやり方、およびパズルを回転させる処理の実装について説明します。

''' キューブを回転させる関数 '''
''' Functions for twisting cube '''

# 回転処理 CP
# Rotate CP
def move_cp(cp, arr):
    # surfaceとreplace配列を使ってパーツを置換
    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

# 回転処理 CO
# Rotate CO
def move_co(co, arr):
    # surfaceとreplace配列を使ってパーツを置換した後pls配列を使って90度回転時のCOの変化を再現
    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

2x2x2ルービックキューブ(の色がついているパーズ)には図のように1種類のパーツが8つあります。

このパズルの状態を、例えば色の配置で持っていたらとてもではありませんがメモリ使用量が多く、何より扱いにくいです。そこで、パズルの状態を2つの配列に保持することにします。

• 各パーツの並び順を表すCP(Corner Permutation)配列
• 各パーツの向きを表すCO(Corner Orientation)配列

の2種類です。それぞれ要素数8の配列で表します。なお、パーツは8つあるため、CP配列の要素は0, 1, 2, 3, 4, 5, 6, 7、各パーツの向きには3種類あるため、CO配列の要素は0, 1, 2です。

紹介した関数は基本的にパズルを回す行為を配列の置換で表します。CO配列に関してはパズルの回し方によってはパーツの向きが変化するため、追加の処理があります。

状態のインデックス化

パズルをいつでも配列として保持しておくのはあまり良くはありません。処理に時間がかかる上にメモリも食います。そこで、次回の記事(事前計算)では、パズルの状態1つ1つに固有の値を紐付けます。この時に大活躍する配列と値をつなぐ関数を解説します。

''' 配列のインデックス化 '''
''' Indexing'''

# cp配列から固有の番号を作成
# Return the number of CP
def cp2idx(cp):
    # 階乗進数でインデックス化
    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

# co配列から固有の番号を作成
# Return the number of CO
def co2idx(co):
    # 3進数でインデックス化。7つのパーツを見れば状態が一意に定まる
    res = 0
    for i in co[:7]:
        res *= 3
        res += i
    return res

# 固有の番号からcp配列を作成
# Return the array of CP
def idx2cp(cp_idx):
    # 階乗進数から配列への変換
    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

# 固有の番号からco配列を作成
# Return the array of CO
def idx2co(co_idx):
    # 3進数から配列への変換
    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

インデックス化には、CP配列は要するに順列の番号づけをすれば良いので階乗進数を使います。CO配列は配列自体を7桁の3進数と見なしてそれを10進数に変換します。

階乗進数の計算についてはこちらのサイトに書いてあることを実装しただけです。

CO配列のインデックス化について、「なぜ要素数は8なのに7桁の3進数とみなすんだ？」と思った方がいらっしゃると思います。パズルのCOは揃えられる状態である限り、7つのパーツを見れば残り1つのパーツの状態がわかってしまうのです。だから7桁の3進数で事足りるのです。

よく使う定数

複数のプログラムで使ったりとよく使う定数、配列をまとめて書いています。

''' 定数 '''
''' Constants '''

# 階乗の値
fac = [1]
for i in range(1, 9):
    fac.append(fac[-1] * i)

# よく使う値と配列
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

それぞれの定数と配列の意味するところは実際にそれを使うときに解説します。

まとめ

ルービックキューブロボットの基本関数を解説しました。全ての他のプログラムでこの関数や定数を使っています。