最近在同学的 QQ 空间上，发现了这样一道智力题：
有一条河，河边有一个猎人牵着一头狼，一个男人带着两个小男孩，还有一个女人带着两个小女孩。
如果猎人离开，狼就会把所有人吃掉。
如果男人离开，女人会把两个小男孩掐死。
如果女人离开，男人会把两个小女孩掐死。
河里有一条船，船上只能乘坐两人（狼算一人），只有猎人、男人、女人会划船。
如何使他们全部过河？
看到这道题，首先想到的是农夫过河问题。既然这两个问题十分相似，那我就尝试按照农夫过河问题的思路，通过程序来找出该题的解。
程序代码如下：
#!/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!")
留言