非常有趣的问题！我有一些建议。
首先，在我看来，如果没有明确的想法，搜索这样一个庞大的配置树最多只能算是低效。为什么不优先选择“方向”，以便在同一颜色中更多地填充或更高地填充更多瓶子。请参见下面的
__iter__。
我认为，如果瓶子的顺序不同，但颜色相同，则将谜题的两个状态视为相同可能会很有价值。您可以通过使用整数元组表示瓶子中的颜色并保存这些元组的集合（因为集合不保存顺序）来实现这一点。请参见下面的
set_rep。
我忍不住要编写代码了。作为基础，我使用了 Raymond Hettinger 的通用谜题解决器。特别是我的
solve 方法受到了他的影响。
实际代码：
import numpy as np
from collections import deque
class ColoredWater:
def __init__(self, pos):
self.pos = pos
@staticmethod
def get_first_non_zero(arr):
try:
return arr[arr != 0][0]
except IndexError:
return 0
@staticmethod
def get_first_non_zero_index(arr):
try:
return np.where(arr != 0)[0][0]
except IndexError:
return 3
@staticmethod
def get_last_zero_index(arr):
try:
return np.where(arr == 0)[0][-1]
except IndexError:
return 3
def get_legal_moves_to(self, moveable_to):
first_non_zero = self.first_non_zero
n = first_non_zero.shape[0]
if first_non_zero[moveable_to] == 0:
return np.where((first_non_zero != 0) & (np.arange(n) != moveable_to))[0], moveable_to
else:
return np.where((first_non_zero == first_non_zero[moveable_to]) & (np.arange(n) != moveable_to))[0], moveable_to
def swap(self, i, j):
out = self.pos.copy()
idx_from = (self.get_first_non_zero_index(self.pos[:, i]), i)
idx_to = (self.get_last_zero_index(self.pos[:, j]), j)
out[idx_from], out[idx_to] = out[idx_to], out[idx_from]
return ColoredWater(out)
def isgoal(self):
return np.array_equiv(self.pos, self.pos[0])
def __iter__(self):
self.first_non_zero = np.apply_along_axis(self.get_first_non_zero, 0, self.pos)
moveable_to = np.where(self.pos[0] == 0)[0]
legal_moves = tuple(map(self.get_legal_moves_to, moveable_to))
out = [self.swap(origin, target)
for origins, target in legal_moves
for origin in origins]
def number_of_full_stacks(pos):
return np.sum(np.all((pos == [pos[0]]), axis=0))
def fillings_of_stacks(game):
pos = game.pos
return number_of_full_stacks(pos), number_of_full_stacks(pos[1:]), number_of_full_stacks(pos[2:])
return iter(sorted(out, key=fillings_of_stacks, reverse=True))
def set_rep(self):
return frozenset(map(tuple, self.pos.T))
def __repr__(self):
return repr(self.pos)
def solve(pos, depthFirst=False):
queue = deque([pos])
trail = {pos.set_rep(): None}
solution = deque()
load = queue.append if depthFirst else queue.appendleft
while not pos.isgoal():
for m in pos:
if m.set_rep() in trail:
continue
trail[m.set_rep()] = pos
load(m)
pos = queue.pop()
while pos:
solution.appendleft(pos)
pos = trail[pos.set_rep()]
return list(solution)
如何运行
首先在您的示例上运行。使用 depthFirst=True 运行，它在 376 毫秒内给出了 117 步的解决方案。当我使用 depthFirst=False 运行时，它在 9.42 秒内给出了最优解的 55 步。
from ColoredWater import ColoredWater
import numpy as np
ColoredWater(np.array([[ 0, 1, 0, 5, 8, 9, 7, 4, 2, 8, 2, 5, 5, 10, 12],
[ 0, 2, 0, 6, 3, 10, 9, 7, 11, 3, 11, 12, 3, 6, 13],
[ 0, 3, 0, 7, 4, 2, 11, 11, 6, 12, 12, 13, 1, 13, 1],
[ 0, 4, 0, 5, 9, 9, 7, 6, 8, 8, 13, 1, 4, 10, 10]]))\
.solve(depthFirst=True)
我还在一个“随机”的示例上进行了测试：
def sort_zeros(x):
return sorted(x, key=lambda x:x != 0)
n = 15
arr = np.broadcast_to(np.array([0,0,*range(n)]),(4,n+2)).copy()
np.random.shuffle(arr.reshape(-1))
arr = np.apply_along_axis(sort_zeros,0,arr)
print(ColoredWater(arr).solve(depthFirst=True))
