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

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

一、游戏介绍

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

image

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

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

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

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


二、游戏分析

如果用1来表示方向朝右的箭头,用-1表示方向朝左的箭头,0表示空格,那么游戏可以用一个列表来表示:

[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, 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, 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()

执行结果为:

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

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

需要移动15步才能打开开关,移动步骤如下:

image


五、扩展思考

题目中空格左右两边只有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

标签: , ,
本文链接: 算法解《机械迷城》游戏二:箭头换位置
版权所有: 破博客, 转载请注明本文出处。

发表评论

您的昵称: *

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

联系方式: