抱歉，您的浏览器无法访问本站

本页面需要浏览器支持（启用）JavaScript


了解详情 >
This is a picture without description

算法解《机械迷城》游戏一：红绿点转盘

This is a picture without description

才怪
学习园地算法之美

发布于：2020年5月17日

一、游戏介绍

我们的机器人小萝卜头(robot)经历了千辛万苦，终于进入了监狱的第三个牢房。
牢房的柜子里可能藏着好东西，但是柜子的门上安装了一个密码锁，需要先打开密码锁才能开柜子。

密码锁由12个点组成，其中有6个绿点和6个红点。
密码锁上面还有3个转盘，每个转盘边上都有6个点。
转盘可以按顺时针或逆时针的方向旋转，当转盘旋转时，转盘上的6个点会跟着转盘一起转动。

image

如果将6个绿色的点转到中央的三角形区域，密码锁就能打开，如下图所示：

image

那么问题来了：你能帮小萝卜头找出打开密码锁的最少旋转步骤吗？

二、游戏分析

如果用数字1来表示绿点，数字0表示红点，那么游戏可以表示为：

1
2
3
4
5
6
7
  1   0   1

0   1   0   1

  0   1   0

    1   0

若将这12个数字按从左到右、从上到下的顺序保存到一个数组里，则当前游戏状态可以表示为：

1
[1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0]

那么当转盘转动时，怎么改变这个数组的值呢？
可以考虑先记录下每个转盘上的点在数组里的下标，然后根据下标来移动元素的值。

先看一下所有点在数组里的下标：

1
2
3
4
5
6
7
  0   1   2

3   4   5   6

  7   8   9

   10   11

由上图可知，3个转盘边上的点的下标分别为：

1
2
3
第1个转盘：[0, 1, 5, 8, 7, 3]
第2个转盘：[1, 2, 6, 9, 8, 4]
第3个转盘：[4, 5, 9, 11, 10, 7]

注意，上面转盘的点坐标是按顺时针方向获取的，以便进行旋转的操作。
只要能够模拟转盘的转动，就能编写自动求解答案的算法了。

三、游戏编写

要找出游戏的解法，首先要模拟游戏的玩法，下面就用python来实现一下这个游戏。

新建一个游戏类，使用dots数组来初始化游戏：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#coding:utf-8

class Game:
    def __init__(self, dots):
        self.dots = dots

    def show(self):
        text = '''
   %d   %d   %d

 %d   %d   %d   %d

   %d   %d   %d

     %d   %d
        '''%tuple(self.dots)
        print(text)

dots = [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0]
game = Game(dots)
game.show()

代码执行结果为：

1
2
3
4
5
6
7
  1   0   1

0   1   0   1

  0   1   0

    1   0

由结果可见，游戏类能够正常打印出点的位置。

再给游戏类添加一个转动转盘的方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#coding:utf-8

class Game:
    def __init__(self, dots):
        self.dots = dots
        self.wheel_poses = [
            [0, 1, 5, 8, 7, 3],
            [1, 2, 6, 9, 8, 4],
            [4, 5, 9, 11, 10, 7],
        ]

    def turn(self, index, clockwise):
        """转动轮盘
        Args:
            index: 转盘下标
            clockwise: 是否顺时针旋转
        """
        poses = self.wheel_poses[index]
        if clockwise:
            # 顺时针旋转
            temp = self.dots[poses[-1]]
            for i in range(len(poses)-1, -1, -1):
                self.dots[poses[i]] = self.dots[poses[i-1]]
            self.dots[poses[0]] = temp
        else:
            # 逆时针旋转
            temp = self.dots[poses[0]]
            for i in range(1, len(poses)):
                self.dots[poses[i-1]] = self.dots[poses[i]]
            self.dots[poses[-1]] = temp

如果将第一个转盘按顺时针方向转动一下，将会成为下面的样子：

转动前：
image

转动后：
image

测试一下旋转的方法，以下代码将第一个转盘按顺时针方向转动：

1
2
3
4
dots = [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0]
game = Game(dots)
game.turn(0, True)
game.show()

执行结果为：

1
2
3
4
5
6
7
  0   1   1

0   1   0   1

  1   0   0

    1   0

可见结果的数值和图片是相对应的，至此游戏的代码就编写完成了。

四、游戏解法

我们想写算法自动求解游戏，最终肯定要判断游戏是否完成的，所以可以先考虑一下游戏的完成条件。
当结果如下图所示时，就说明游戏完成了：

1
2
3
4
5
6
7
  0   1   0

0   1   1   0

  1   1   1

    0   0

将上图转换成数组，结果为：

1
[0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0]

所以只要判断游戏状态是否等于上面的数组就行了：

1
2
3
4
5
6
#coding:utf-8

class Game:
    def is_done(self):
        """判断是否完成游戏"""
        return self.dots == [0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0]

要找出最少的旋转步骤，可以使用广度优先搜索算法来求解答案。

广度优先搜索就像孙悟空走迷宫一样，比如孙悟空走到迷宫的三岔口，就会拔出猴毛变成三个分身，每个分身进入一个分叉口。每个分身分别到达下一个分叉口后，又变出和分叉口一样多的分身进入每个分叉口。这样当其中某个分身最先到达迷宫终点的时候，这个分身所走过的路径就是最短的。

这个转盘游戏也是一样，游戏有3个转盘，每个转盘有两个旋转方向，所以总共有6种转法。每种转法相当于一个分叉口，把初始游戏按每种转法旋转后得到6个结果，每个结果也分别转6次得到6个子结果，这样不断转下去，子子孙孙无穷匮也。当某个子结果完成的时候，这个子结果所转动的次数就是最少的。

算法如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#coding:utf-8

class Game:

    # ...

    def copy(self):
        """拷贝对象"""
        game = Game(self.dots[:])
        game.ops = self.ops[:]
        return game

    def solve(self):
        """使用BFS求解答案"""
        # 将当前游戏加入队列
        queue = [self]
        while queue:
            pre_game = queue.pop(0)
            # 遍历3个转盘的下标
            for index in [0, 1, 2]:
                # 遍历两种旋转方向
                for clockwise in [True, False]:
                    # 拷贝上一个游戏状态来模拟游戏旋转
                    cur_game = pre_game.copy()
                    cur_game.turn(index, clockwise)
                    cur_game.ops += [(index, clockwise)]
                    if cur_game.is_done():
                        # 如果游戏完成，则打印操作步骤
                        print(cur_game.ops)
                        return
                    # 将当前游戏加入队列
                    queue.append(cur_game)

dots = [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0]
game = Game(dots)
game.solve()

执行结果为：

1
[(0, True), (1, False), (2, True), (1, False)]

其中(0, True)表示将第1个转盘进行顺时针旋转，(1, False)表示将第2个转盘进行逆时针旋转，其它的同理。

也就是说，最少需要转动4次才能解开密码锁，旋转过程为：

image

五、其它解法

多次打开密码锁可以发现，密码锁的初始状态不是固定的，还可能出现另一种状态：

image

修改一下初始化数组的值，如下所示：

1
2
3
dots = [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
game = Game(dots)
game.solve()

执行结果为：

1
[(0, True), (1, True), (2, False), (0, False), (0, False)]

在这种初始状态下，需要旋转5次才能完成游戏，旋转过程为：

image

六、完整代码

完整的代码见：https://github.com/poboke/Machinarium

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://www.poboke.com/machinarium-puzzle-game-wheel.html

更新于：2021年8月24日

Python

算法

谜题

评论