算法解《机械迷城》游戏二：箭头换位置

才怪

发布于：2020年5月23日

一、游戏介绍

原文再续，书接上回。
机器人小萝卜头从牢房出来后，遇到了一个丢失了小狗的阿姨。
阿姨附近有一个起重电磁铁，小萝卜头打算使用起重电磁铁把铁箱子吸上去，不过需要先打开开关才能使用起重电磁铁。
电磁铁的开关有6个箭头，左边3个，右边3个，中间隔了一个空格。（注：游戏里使用的是上下箭头，而本文章使用左右箭头，讲解比较方便）

箭头移动的规则和玻璃珠跳棋的规则类似。
箭头只能移动到空格里，而且只能往箭头朝向的方向移动，不能够后退。
箭头移动的方式有两种，一种是把箭头移动到相邻的空格（例如上图第3个位置的箭头往前走一步）：

另一种是跳过相邻的箭头后进入后面的空格，但是最多只能跳过一个箭头（例如上图倒数第3个位置的箭头往前走两步）：

将左右两边的箭头互换位置，就能打开开关，如图所示：

那么新的问题来了，你能帮小萝卜头找出打开开关的最少移动步骤吗？

二、游戏分析

如果用1来表示方向朝右的箭头，用-1表示方向朝左的箭头，0表示空格，那么游戏可以用一个数组来表示：

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

用1和-1来表示箭头是有原因的，因为方向朝右的箭头要往数组右边移动，所以下标要+1。而方向朝左的箭头往数组左边移动，下标要-1。箭头的值即为箭头移动时下标的偏移量，这会给代码增加一点便利性。

当箭头移动时，只需要交换数组里元素的值就行了。

三、游戏编写

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

#coding:utf-8

class Game:
    def __init__(self, values):
        self.values = values
        self.length = len(self.values)

    def show(self):
        print(self.values)

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

代码执行结果为：

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

再给游戏类添加一个移动箭头的方法，参数为要移动的箭头的下标。
先把箭头当前所在的下标加上箭头的值，就得到箭头移动的新下标，如果这个下标所在的格子是空格，就说明可以移动。如果这个格子不是空格，就把新下标再加上该箭头的值得到新的下标，再继续判断。
因为箭头最多只能移动两个格子的位置，所以只需要判断两次。

#coding:utf-8

class Game:

    # ...

    def move(self, index):
        """移动箭头
        Args:
            index: 箭头所在的下标
        Returns: 是否移动成功
        """
        new_index = index
        value = self.values[index]
        # 箭头最多移动两格
        for _ in range(2):
            # 按箭头的方向移动下标
            new_index += value
            if new_index < 0 or new_index >= self.length:
                return False
            new_value = self.values[new_index]
            if new_value == 0:
                # 如果遇到空格，就交换两个位置的值
                self.values[index], self.values[new_index] = \
                    self.values[new_index], self.values[index]
                return True
        return False

values = [1, 1, 1, 0, -1, -1, -1]
game = Game(values)
game.show()
# 先移动第3个格子的箭头
game.move(2)
game.show()
# 再移动第5个格子的箭头
game.move(4)
game.show()

执行结果为：

1
2
3

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

可见箭头的移动结果是正确的。

四、游戏解法

首先实现一下判断游戏是否完成的方法，如果游戏完成的话，中间的格子肯定是空格，左半部分全部都是方向朝左的箭头，那么可以写出下面的方法：

#coding:utf-8

class Game:
    def is_done(self):
        """判断是否完成游戏
        Returns: 是否完成
        """
        # 如果中间不是空格，肯定未完成
        middle = self.length / 2
        if self.values[middle] != 0:
            return False
        # 判断左半部分是否全部是方向朝左的箭头
        for i in range(0, middle):
            if self.values[i] != -1:
                return False
        return True

沿用上一个游戏的套路，这个游戏也继续使用广度优先搜索算法来求解答案。

那么怎么获取该游戏的操作步骤呢？
因为只有距离空格左右两边两个格子以内的箭头才能够移动，所以只要判断空格周围的4个箭头就行了。
获取空格左边两格内方向朝右的箭头，加上空格右边两格内方向朝左的箭头作为操作步骤。
可以写一个方法来获取空格周围的箭头下标：

#coding:utf-8

class Game:
    def get_space_neighbors(self):
        """获取空格左右两边可移动的箭头下标
        Returns: 下标数组
        """
        index = self.values.index(0)
        # 获取空格左边方向朝右的箭头
        for i in range(max(0, index-2), index):
            if self.values[i] == 1:
                neighbors.append(i)
        # 获取空格右边方向朝左的箭头
        for i in range(index+1, min(index+3, self.length)):
            if self.values[i] == -1:
                neighbors.append(i)
        return neighbors

广度优先搜索算法算法如下所示：

#coding:utf-8

class Game:

    # ...

    def copy(self):
        """拷贝对象
        Returns: 新的游戏对象
        """
        game = Game(self.values[:])
        game.ops = self.ops[:]
        return game
    
    def solve(self):
        """使用BFS求解答案"""
        queue = [self]
        while queue:
            pre_game = queue.pop(0)
            # 获取空格左右两边的箭头下标
            neighbors = pre_game.get_space_neighbors()
            for index in neighbors:
                cur_game = pre_game.copy()
                if not cur_game.move(index):
                    continue
                cur_game.ops += [index]
                if cur_game.is_done():
                    # 如果游戏完成，则打印操作步骤
                    print(cur_game.ops)
                    return
                # 将当前游戏加入队列
                queue.append(cur_game)

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

执行结果为：

1	[2, 4, 5, 3, 1, 0, 2, 4, 6, 5, 3, 1, 2, 4, 3]

数字代表每次移动的箭头下标，如2表示移动第三个格子的箭头，其它类推。

需要移动15步才能打开开关，移动步骤如下：

五、扩展思考

题目中空格左右两边只有3个箭头，人脑也能比较容易思考出游戏解法。
那么如果每边的箭头不止3个，而是有4个、5个或更多个，怎样才能算出最少的移动步数呢？

先使用下面的代码打印出当每边有i个箭头时，最少的移动次数：

#coding:utf-8

class Game:
    # ...
    def solve(self):
        # ...
        if cur_game.is_done():
            # 如果游戏完成，则打印操作次数
            print(len(cur_game.ops))
            return
        # ...

for i in range(11):
    print i, "=>",
    values = [1] * i + [0] + [-1] * i
    game = Game(values)
    game.solve()

执行结果为：

0 => 0
1 => 3
2 => 8
3 => 15
4 => 24
5 => 35
6 => 48
7 => 63
8 => 80
9 => 99
10 => 120

从结果可以看出：
如果每边有0个箭头，这时不用移动箭头就完成游戏，移动次数为0。
如果每边有1个箭头，最少需要移动3次。
如果每边有2个箭头，最少需要移动8次。
如果每边有3个箭头，最少需要移动15次，跟当前游戏相同。

观察结果，可以推出以下式子：

f(0) = 0
f(1) = f(0) + 3
f(2) = f(1) + 5
f(3) = f(2) + 7
f(4) = f(3) + 9
...
f(n) = f(n-1) + 2n + 1

求一下数列的通项式：

由于：
f(n)   - f(n-1) = 2(n) + 1
f(n-1) - f(n-2) = 2(n-1) + 1
f(n-2) - f(n-3) = 2(n-2) + 1
...
f(2) - f(1) = 2(2) + 1
f(1) - f(0) = 2(1) + 1

将等号两边分别相加得：
f(n) - f(0) = 2(1 + 2 + ... + n) + (1 + 1 + ... + 1)
            = 2((1 + n) * n / 2) + n
            = (1 + n) * n + n
            = n * (n + 2)

由于 f(0) = 0，
因此 f(n) = n * (n + 2)

可以很方便地算出，当每边有3个箭头时，所需移动次数为3 * (3 + 2) = 15。

六、完整代码

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

更新于：2021年8月24日

Python

算法

谜题

算法解《机械迷城》游戏三：扳手关水管

一、游戏介绍小萝卜头来到了下水道，下水道里面有一些错综复杂的水管，如图所示（红色箭头表示进水口和出水口）：其中出水口的水流进了蓄水池，而小萝卜头打算进入蓄水池里，所以只能想办法关闭这个出水口...

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

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