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

时间:2020-05-17 | 分类:个人日志,学习园地 | 浏览:151 | 评论:0 | 发表评论

一、游戏介绍

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

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

image

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

image

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


二、游戏分析

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

   1   0   1

 0   1   0   1

   0   1   0

     1   0

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

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

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

先看一下所有点在列表里的下标:

   0   1   2

 3   4   5   6

   7   8   9

    10   11

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

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

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


三、游戏编写

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

新建一个游戏类,使用dots列表来初始化游戏:

#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   0   1

 0   1   0   1

   0   1   0

     1   0

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

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

#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

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

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

执行结果为:

   0   1   1

 0   1   0   1

   1   0   0

     1   0

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


四、游戏解法

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

   0   1   0

 0   1   1   0

   1   1   1

     0   0

将上图转换成列表,结果为:

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

所以只要判断游戏状态是否等于上面的列表就行了:

#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个子结果,这样不断转下去,子子孙孙无穷匮也。当某个子结果完成的时候,这个子结果所转动的次数就是最少的。

算法如下所示:

#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()

执行结果为:

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

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

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

image


五、其它解法

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

image

修改一下初始化列表的值,如下所示:

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

执行结果为:

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

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

image


六、完整代码

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

标签: , ,
本文链接: 算法解《机械迷城》游戏一:红绿点转盘
版权所有: 破博客, 转载请注明本文出处。

发表评论

您的昵称: *

您的邮箱: * (显示gravatar头像)

联系方式: