用python还原二阶魔方（Rubik‘s Cube）

矫情吗；* 2023-07-17 06:19 42阅读 0赞

# 用python还原二阶魔方（Rubik’s Cube） #

本文使用numpy实现多维数组对魔方建模，并用前序遍历进行搜索，适合编程基础和数学基础较差的编程初学者

## 前言 ##

**智能控制课程第一周作业：要求建立搜索算法完成二阶魔方(Rubik’s Cube)从起始状态向指定状态的转换**。二阶魔方结构较为简单，对魔方基础要求不高，从来没有接触过的笔者也可以运用简单的递归搜索算法解决问题。

参考过的类似的博文：[二阶魔方（仿真问题）作者：璐璐丫头][Link 1]

## 解题思路 ##

### 魔方相关 ###

了解最少量的魔方知识

1.  二阶魔方(Rubik’s Cube)是最简单的魔方，由**8**个小块组成，且每个小块都有**3**个带有颜色的面，相比于具有3个状态（涂了一个面、两个面、三个面）的标准的3阶魔方而言相对来说构成形式较为简单。但是需要注意的是，魔方的每个小块涂色状态都各不相同。  
    ![在这里插入图片描述][format_png]
2.  二阶魔方的[上帝之数][Link 2]=11，即在任意状态下的魔方最多只需要11次操作就可以得到完美魔方，这是解题的**关键信息**
3.  规定对魔方的操作一共只有三种，即分别绕x、y、z轴旋转。且只选定距离我们最近的一组进行变换。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pleWlSVGFuZ2VudA_size_16_color_FFFFFF_t_70]  
    带有颜色的魔方旋转见参考博文：[二阶魔方（仿真问题）作者：璐璐丫头][Link 1]

### 算法相关 ###

本科前两年所学的内容，理解难度简单

1.  由且刚接触智能控制，对启发式(Heuristic)搜索算法尚不了解，暂时使用深度优先算法中的**前序遍历**（盲目式搜索算法）
2.  魔方每次可以沿着x、y、z三轴中的任意一轴旋转，假设每一次对魔方进行单步操作，每一次操作有三种可能(x、y、z)，于是我们可以构建一颗关于魔方操作的三叉树。这颗三叉树的深度就是11层（上帝之数），全部节点使用等比数列计算可以得到11步内对魔方的操作最多有88572种
3.  不管是将魔方还原，还是搜索我们想要任意的魔方状态(本质上两者没区别)，我们要做的工作就是在按照三叉树不断操作魔方，然后计算魔方的状态，并且检测是否与目标状态一致

### 建模相关 ###

数学不佳，一切以易于理解的方式建模，建模思路如下：

1.  使用numpy中的**3维数组**来表示8个小魔方在空间中的位置，魔方块索引如下：  
    ![我这字符画还是很好看得懂吧][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pleWlSVGFuZ2VudA_size_16_color_FFFFFF_t_70 1]
2.  对于每一个小魔方块，我们依次按照x-y-z的顺序表示其3个面上的颜色，没有颜色的部分我们不管  
    ![小魔方][20200320002748925.jpg]  
    所以，对于下面这个魔方，我们可以得到最靠近我们的那块魔方的坐标为\[0\]\[1\]\[1\]，其颜色为\[ ‘g’ ‘r’ ‘w’ \]  
    ![在这里插入图片描述][format_png]
3.  **在旋转魔方的时候，不仅小魔方的位置在变，魔方的颜色也在变**，举例说明变化规律：假设\[0\]\[1\]\[0\]处的魔方块经过一次绕x轴旋转的操作到了\[0\]\[1\]\[1\]，那么这一个移动的小块的颜色也会从\[ ‘g’ ‘o’ 'w ’ \]变成\[ ‘g’ ‘w’ ‘o’\]，即，**沿着x轴转，那么除了x轴的其他两个方向上的两个颜色位置会发生交换，这一规律也适用于其他轴**。

综上，我们可以建立一个三维数组，对于每一个数据单元，我们又可以在其中放列表(长度为3)存储其颜色。**所以我们实际上创建的是一个大小为2\*2\*2\*3的四维数组**来表示二阶魔方的状态，对于这样一个魔方，使用前序遍历算法，按照深度优先算法在三叉树内对魔方的状态进行不断的变换和匹配检测，就可以实现对魔方的复原和向特定状态的转化。

## Code ##

# -*- coding = utf-8 -*- #
    """
    """
    import numpy as np
    
    
    cube_color = ['b', 'g', 'r', 'o', 'y', 'w']
    
    # Generate a perfect cube, for testing
    def generate_test_cube():
        cube = np.zeros((2, 2, 2, 3), dtype='string_')
        cube[0][0][0] = ['b', 'o', 'w']
        cube[0][0][1] = ['b', 'r', 'w']
        cube[0][1][0] = ['g', 'o', 'w']
        cube[0][1][1] = ['g', 'r', 'w']
        cube[1][0][0] = ['b', 'o', 'y']
        cube[1][0][1] = ['b', 'r', 'y']
        cube[1][1][0] = ['g', 'o', 'y']
        cube[1][1][1] = ['g', 'r', 'y']
        return cube
    
    
    def input_cube():
        cube = np.zeros((2, 2, 2, 3), dtype='string_')
    
        def hint():
            print('-------Please input the value of 8 cube zone.-------\n')
            print('Rubik Cube are indexed as below:')
            print('      ______________________\n'
                  '    /           /           / |\n'
                  '   / [0][0][0] / [0][0][1] /  |\n'
                  '  ------------------------    |\n'
                  ' /          /            / |  |\n'
                  '/ [0][1][0]/ [0][1][1]  /  |  |\n'
                  ' ______________________    | /|\n'
                  '|          |           |   |/ |\n'
                  '|[0][1][0] | [0][1][1] |   |  |\n'
                  '|          |           |  /   |\n'
                  '|          |           | / | <---[1][0][1]\n'
                  '----------------------- /  |  |\n'
                  '|          |           |   |  |\n'
                  '|[1][1][0] | [1][1][1] |   |  |\n'
                  '|          |           |   |/\n'
                  '|          |           |  /\n'
                  '----------------------- /\n')
            print('For each cube, colors are arranged by [x, y, z] order.\n'
                  '    ------------\n'
                  '  /     z      /|\n'
                  ' /           /  |\n'
                  ' -----------    |\n'
                  '|           | y |\n'
                  '|     x     |   |\n'
                  '|           |  / \n'
                  '|           | / \n'
                  ' -----------/ \n')
            print('now please input your cube state.')
    
        def show_cube(cube):
            print(cube[0, 0, 0, 2])
            print('This is your cube:')
            print('      ______________________\n'
                  '    /           /           / |\n'
                  '   /     %s   /     %s     /  |\n'
                  '  ------------------------    |\n'
                  ' /          /            / |%s|\n'
                  '/    %s    /     %s     /  |  |\n'
                  ' ______________________    | /|\n'
                  '|          |           |%s |/ |\n'
                  '|    %s    |     %s    |   |  |\n'
                  '|          |           |  /   |\n'
                  '|          |           | / |%s|\n'
                  '----------------------- /  |  |\n'
                  '|          |           |%s |  |\n'
                  '|    %s    |     %s    |   |  |\n'
                  '|          |           |   |/\n'
                  '|          |           |  /\n'
                  '----------------------- /\n'
                  % (str(cube[0, 0, 0, 2]), str(cube[0, 0, 1, 2]), str(cube[0, 0, 1, 1]), str(cube[0, 1, 0, 2]),
                     str(cube[0, 1, 1, 2]), str(cube[0, 1, 1, 1]), str(cube[0, 1, 0, 0]), str(cube[0, 1, 1, 0]),
                     str(cube[1, 0, 1, 1]), str(cube[1, 1, 1, 1]), str(cube[1, 1, 0, 0]), str(cube[1, 1, 1, 0])))
    
        hint()
        # input state from keyboard, divided with Space, press Enter to change different small cube
        for i in range(2):
            for j in range(2):
                for k in range(2):
                    print('The value of cube[%d][%d][%d]:' % (i, j, k))
                    value = [temp for temp in input().split()]
                    while input_is_error(value):
                        print('current state in not correct, please check your input and try again.')
                        value = [temp for temp in input().split()]
                    cube[i, j, k] = value
        show_cube(cube)
    
        return cube
    
    # Detect whether the color of input is correct
    def input_is_error(items):
        if len(items) < 3:
            return True
        for item in items:
            if item in cube_color:
                return False
            else:
                return True
    
    
    def swap(item, axis):
        if axis == 'x':
            temp = item[2]
            item[2] = item[1]
            item[1] = temp
        elif axis == 'y':
            temp = item[2]
            item[2] = item[0]
            item[0] = temp
        elif axis == 'z':
            temp = item[1]
            item[1] = item[0]
            item[0] = temp
        else:
            print('ERROR: SWAP')
            exit(-1)
    
        return item
    
    
    def rotate(cube, axis):
        if axis == 'x':
            temp = cube[0, 1, 1].copy()
            cube[0, 1, 1] = swap(cube[0, 1, 0], 'x')
            cube[0, 1, 0] = swap(cube[1, 1, 0], 'x')
            cube[1, 1, 0] = swap(cube[1, 1, 1], 'x')
            cube[1, 1, 1] = swap(temp, 'x')
        elif axis == 'y':
            temp = cube[0, 1, 1].copy()
            cube[0, 1, 1] = swap(cube[1, 1, 1], 'y')
            cube[1, 1, 1] = swap(cube[1, 0, 1], 'y')
            cube[1, 0, 1] = swap(cube[0, 0, 1], 'y')
            cube[0, 0, 1] = swap(temp, 'y')
        elif axis == 'z':
            temp = cube[0, 1, 1].copy()
            cube[0, 1, 1] = swap(cube[0, 0, 1], 'z')
            cube[0, 0, 1] = swap(cube[0, 0, 0], 'z')
            cube[0, 0, 0] = swap(cube[0, 1, 0], 'z')
            cube[0, 1, 0] = swap(temp, 'z')
        elif axis == ' ':
            pass
        else:
            print('ERROR:ROTATE')
            exit(-1)
    
        return cube
    
    
    def cube_is_perfect(cube):
        complete_facets = 0
        # check the top side
        if cube[0, 0, 0, 2] == cube[0, 0, 1, 2] == cube[0, 1, 0, 2] == cube[0, 1, 1, 2]:
            complete_facets += 1
        # check the front side
        if cube[0, 1, 0, 0] == cube[0, 1, 1, 0] == cube[1, 1, 0, 0] == cube[1, 1, 1, 0]:
            complete_facets += 1
        # check the right side
        if cube[0, 1, 1, 1] == cube[0, 0, 1, 1] == cube[1, 1, 1, 1] == cube[1, 0, 1, 1]:
            complete_facets += 1
        # check the down side
        if cube[1, 0, 0, 2] == cube[1, 0, 1, 2] == cube[1, 1, 0, 2] == cube[1, 1, 1, 2]:
            complete_facets += 1
        # check the back side
        if cube[0, 0, 0, 0] == cube[0, 0, 1, 0] == cube[1, 0, 0, 0] == cube[0, 0, 1, 0]:
            complete_facets += 1
        # check the left side
        if cube[0, 0, 0, 1] == cube[0, 1, 0, 1] == cube[1, 0, 0, 1] == cube[1, 1, 0, 1]:
            complete_facets += 1
    
        if complete_facets == 6:
            return True
        else:
            return False
    
    
    def cube_is_the_same(cube, target_cube):
        for i in range(2):
            for j in range(2):
                for k in range(2):
                    if cube[i][j][k] == target_cube[i][j][k]:
                        continue
                    else:
                        return False
        return True
    
    
    def restore_convert(cube, target_cube):
        steps_records = []
        number_of_god = 11
        depth = 0
    
        def reverse(cube, operation):
            return rotate(rotate(rotate(cube, operation), operation), operation)
    
        def pre_traverse(cube, operation, depth):
            global steps
            global mode
    
            depth += 1
    
            if operation == ' ':
                pass
            else:
                cube = rotate(cube, operation)
    
            if depth <= number_of_god:
                steps_records.append(operation)
            # print(depth)
            # print(steps_records)
    
            if mode == '0':
                if cube_is_perfect(cube):
                    print('The cube is in perfect state with in ' + str(steps) + ' steps,')
                    print('The step is:' + str(steps_records[1:]))
                    exit(0)
            elif mode == '1':
                if cube_is_the_same(cube, target_cube):
                    print('The cube is in target state with in ' + str(steps) + ' steps,')
                    print('The step is:' + str(steps_records[1:]))
                    exit(0)
            else:
                print('ERROR:MODE')
                exit(0)
    
            if depth >= number_of_god:
                depth -= 1
                cube = reverse(cube, operation)
                steps_records.pop()
                return
    
            steps += 1
    
            if steps > 88572:
                print('The cube can not be restored, please check your input')
    
            pre_traverse(cube, 'x', depth)
            pre_traverse(cube, 'y', depth)
            pre_traverse(cube, 'z', depth)
            cube = reverse(cube, operation)
            steps_records.pop()
    
        pre_traverse(cube, ' ', depth)
        print(steps)
    
    
    steps = 0
    
    mode = '0'
    mode = input('Select mode: [0]Restore   [1]Convert to target state')
    if mode == '0':
        cube = input_cube()
        restore_convert(cube.copy(), None)
    elif mode == '1':
        current_cube = input_cube()
        print('Now Please input your target cube.\n')
        target_cube = input_cube()
        restore_convert(current_cube.copy(), target_cube.copy())
    else:
        print('ERROR:MODE SELECT')
        exit(-1)

运行示例：

Select mode: [0]Restore   [1]Convert to target state 0
    -------Please input the value of 8 cube zone.-------
    
    Rubik Cube are indexed as below:
          ______________________
        /                /               /   |
       / [0][0][0] / [0][0][1] /     |
      ------------------------    |
      /              /                /  |   |
    / [0][1][0]/ [0][1][1]  /    |   |
     ______________________     | /|
    |              |               |       |/  |
    |[0][1][0] | [0][1][1] |       |   |
    |              |               |     /   |
    |              |               |       / | <---[1][0][1]
    ----------------------- /  |  |
    |              |               |       |  |
    |[1][1][0] | [1][1][1]   |       |  |
    |              |               |        |/
    |              |               |      /
    ----------------------- /
    
    For each cube, colors are arranged by [x, y, z] order.
        ------------
      /         z      /|
     /               /   |
     -----------    |
    |                | y |
    |         x     |    |
    |                |  / 
    |                | / 
     -----------/ 
    
    now please input your cube state.
    The value of cube[0][0][0]:
    b o w
    The value of cube[0][0][1]:
    b r w
    The value of cube[0][1][0]:
    g y o
    The value of cube[0][1][1]:
    g w o
    The value of cube[1][0][0]:
    b o y
    The value of cube[1][0][1]:
    b r y
    The value of cube[1][1][0]:
    g y r
    The value of cube[1][1][1]:
    g w r
    b'w'
    This is your cube:
          ______________________
        /            /           /  |
       /     b'w'   /     b'w'     /  |
      ------------------------    |
     /          /            / |b'r'|
    /    b'o'    /     b'o'     /  |  |
     ______________________    | /|
    |          |           |b'w' |/ |
    |    b'g'    |     b'g'    |   |  |
    |          |           |  /   |
    |          |           | / |b'r'|
    ----------------------- /  |  |
    |          |           |b'w' |  |
    |    b'g'    |     b'g'    |   |  |
    |          |           |   |/
    |          |           |  /
    ----------------------- /
    
    The cube is in perfect state with in 3 steps,
    The step is:['x', 'x', 'x']

这个乱码就很魔性  
总而言之，算法基于盲目搜索，无用步骤很多。思想也十分简单，日后使用启发式算法再试一下

[Link 1]: https://blog.csdn.net/li1500742101/article/details/8853860
[format_png]: /images/20230528/10bd628b68c3456f9dc0f7b7ece9c7de.png
[Link 2]: https://baike.baidu.com/item/%E4%B8%8A%E5%B8%9D%E4%B9%8B%E6%95%B0/10098625?fr=aladdin
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pleWlSVGFuZ2VudA_size_16_color_FFFFFF_t_70]: /images/20230528/c826af4e3bb147b1bf356e4db534960a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pleWlSVGFuZ2VudA_size_16_color_FFFFFF_t_70 1]: /images/20230528/c0dc16ff70904d38a262e856dd1d3469.png
[20200320002748925.jpg]: /images/20230528/a03f933d22834350b9790a83627881d5.png