我正在编写一个算法来解决 8 难题。 https://en.wikipedia.org/wiki/15_puzzle
状态由元组 (1,2,3,4,5,6,7,8,0) 表示，其中 0 是自由框(这相当于 3*3 矩阵)。
给定拼图 p = (1,3,2,5,4,6,0,7,8) 的状态，我编写了一个函数来计算邻居。
def neighbours(p):
p = np.array(p).reshape(3,3)
ind0 = np.argwhere(p == 0).squeeze()
x0, y0 = ind0
ind_neig = [[ind0[0] - 1, ind0[1]],
[ind0[0] + 1, ind0[1]],
[ind0[0], ind0[1] - 1],
[ind0[0], ind0[1] + 1]]
ind_neig = [ind for ind in ind_neig if min(ind) >= 0 and max(ind) < 3]
neig = [ p.copy() for i in range(len(ind_neig))]
for i in range(len(ind_neig)):
x, y = ind_neig[i]
neig[i][x0, y0] = p[x, y]
neig[i][x, y] = 0
neig = [tuple(np.ravel(i)) for i in neig]
return neig
我想要一个更快版本的邻居函数，并且可能不需要 numpy 库。特别是我想要一个函数，当拼图具有更大的尺寸时也可以使用，例如 15-拼图
最佳答案
我认为您会发现以下实现非常简单，而且它不使用 numpy:
def neighbours(p):
res = []
ind = p.index(0)
if not top(ind):
res.append(up_neig(p, ind))
if not bottom(ind):
res.append(down_neig(p, ind))
if not left(ind):
res.append(left_neig(p, ind))
if not right(ind):
res.append(right_neig(p, ind))
return res
def top(ind):
return ind < 3
def bottom(ind):
return ind > 5
def left(ind):
return ind in [0, 3, 6]
def right(ind):
return ind in [2, 5, 8]
def up_neig(p, ind):
_p = list(p)
_p[ind], _p[ind-3] = _p[ind-3], _p[ind]
return tuple(_p)
def down_neig(p, ind):
_p = list(p)
_p[ind], _p[ind+3] = _p[ind+3], _p[ind]
return tuple(_p)
def left_neig(p, ind):
_p = list(p)
_p[ind], _p[ind-1] = _p[ind-1], _p[ind]
return tuple(_p)
def right_neig(p, ind):
_p = list(p)
_p[ind], _p[ind+1] = _p[ind+1], _p[ind]
return tuple(_p)
p = (1,3,2,5,4,6,0,7,8)
print neighbours(p) # [(1, 3, 2, 0, 4, 6, 5, 7, 8), (1, 3, 2, 5, 4, 6, 7, 0, 8)]
关于python - 8个拼图计算邻居python，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25955254/