一道智力题

最近在同学的 QQ 空间上,发现了这样一道智力题:

有一条河,河边有一个猎人牵着一头狼,一个男人带着两个小男孩,还有一个女人带着两个小女孩。
如果猎人离开,狼就会把所有人吃掉。
如果男人离开,女人会把两个小男孩掐死。
如果女人离开,男人会把两个小女孩掐死。
河里有一条船,船上只能乘坐两人(狼算一人),只有猎人、男人、女人会划船。
如何使他们全部过河?

看到这道题,首先想到的是农夫过河问题。既然这两个问题十分相似,那我就尝试按照农夫过河问题的思路,通过程序来找出该题的解。

程序代码如下:

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#!/usr/local/bin/python3
##########################################
# 问题:
# 有一条河,河边有一个猎人牵着一头狼,一个男人带着两个小男孩,还有一个女人带着两个小女孩
# 如果猎人离开,狼就会把所有人吃掉
# 如果男人离开,女人会把两个小男孩掐死
# 如果女人离开,男人会把两个小女孩掐死
# 河里有一条船,船上只能乘坐两人(狼算一人),只有猎人、男人、女人会划船
# 如何使他们全部过河?
##########################################
# 思路:
# 与农夫过河问题类似,参考 https://www.zhihu.com/question/29968331
# 一共有 8 个人(包含狼),每个人有两个状态:分别为在河的一侧,以及在河的另一侧
# 这两种状态可用一个二进制位表示,0 代表在河的一侧,1 代表在河的另一侧
# 则可用一个 8 位二进制数表示这 8 个人的状态,进行组合,一共有 256 个状态
# 通过坐船,可以使一种状态转变为另一种状态
# 如果状态从 00000000 转换到 11111111, 则说明所有人均到达河的另一侧
# 将两种可以相互转变的状态相互连接,可以构建出一个用于表示状态转移情况的图
# 在图中找到一条从 00000000 到 11111111 的路径,即可解决该问题
##########################################
# 数据存储格式:
# 使用 8 位二进制数进行表示,从高位到低位分别表示男人,男孩,男孩,女人,女孩,女孩,狼的状态
# 船允许的所有状态,1 代表在船上
# 将两个状态进行异或操作,发生变化的位就会置一,则说明置一的位所对应的人是在船上
# 但是,船的行驶是有方向的,例如从 10000000 到 01000000 的状态是无法通过一次乘船达到的
# 所以需要进行进一步判断,具体方法见下面的代码
boatAllowedStates = [
0b11000000, 0b10100000, 0b00011000, 0b00010100, 0b10000010,
0b01000010, 0b00100010, 0b00010010, 0b00001010, 0b00000110,
0b00000011, 0b10010000, 0b10000000, 0b00010000, 0b00000010
]
# 以邻接矩阵的形式存储可能的状态转移情况
# 矩阵的索引就是用于表示状态的 8 位二进制数(0~255)
statesGraph = [([0] * 256) for i in range(256)] # 创建 256x256 二维数组
# 判断是否为危险的状态
def is_dangerous(x):
# 第一种不安全的情况:男人不在,女人在,男孩在
if ( x & 0b10000000) == 0 and ( x & 0b00010000) != 0 and ( x & 0b01100000) != 0:
return True
if (~x & 0b10000000) == 0 and (~x & 0b00010000) != 0 and (~x & 0b01100000) != 0:
return True
# 第二种不安全的情况:女人不在,男人在,女孩在
if ( x & 0b00010000) == 0 and ( x & 0b10000000) != 0 and ( x & 0b00001100) != 0:
return True
if (~x & 0b00010000) == 0 and (~x & 0b10000000) != 0 and (~x & 0b00001100) != 0:
return True
# 第三种不安全的情况:猎人不在,狼在,其他人在
if ( x & 0b00000010) == 0 and ( x & 0b00000001) != 0 and ( x & 0b11111100) != 0:
return True
if (~x & 0b00000010) == 0 and (~x & 0b00000001) != 0 and (~x & 0b11111100) != 0:
return True
return False
# 构建该邻接矩阵
for x in range(0, 256):
if is_dangerous(x): # 判断 x 的状态是否危险
continue
for y in range(0, 256):
if is_dangerous(y): # 判断 y 的状态是否危险
continue
# 如果通过坐船,可以使状态 x 转变为状态 y, 则使矩阵对应位置为 1
tmp = x ^ y
if tmp in boatAllowedStates:
# 进一步判断,排除类似 10000000 到 01000000 的情况
if tmp & x ^ tmp == 0 or tmp & x ^ tmp == tmp:
statesGraph[x][y] = 1 # 连接图中能够能够转换的状态
# 通过图的深度优先搜索算法,找出一条从 0b00000000 到 0b11111111 的路径
# ⚠️TODO:
# 此时仅仅是找到了一条能够到达的路径,不一定是最佳的结果
# 可考虑直接找出所有可行的结果
# 或使用最短路径算法,找出乘船次数最少的结果
visited = [0] * 256 # 用在图的深度优先搜索中,已访问的状态
path = [257] * 256 # 用于存储路径,数组内元素为下一个状态, 257 代表尚未初始化
def dfs_with_path(src):
visited[src] = 1
for i in range(0, 256):
if statesGraph[src][i] == 1 and visited[i] == 0 and visited[0b11111111] == 0:
path[src] = i
dfs_with_path(i)
dfs_with_path(0b00000000)
# 将路径显示在屏幕上
tmp_path = 0
while tmp_path != 0b11111111:
print('{0:08b}'.format(tmp_path))
tmp_path = path[tmp_path]
if(tmp_path == 257):
# 257 在本程序中代表未初始化的值,如果遇到 257,说明没找到这样的路径
print("Not found!")
exit()
print('{0:08b}'.format(0b11111111))
print("Found!")