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

本页面需要浏览器支持(启用)JavaScript


了解详情 >

一、游戏介绍

我们的机器人小萝卜头(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

评论