骑士之旅只能解决一个尺寸的板

Question

我正试图在python中实现一个骑士之旅查找器。假设骑士必须从左上角开始(这里称为(0,0((，它会为4x3字段找到一个解决方案，但不会为任何其他字段找到解决方案。

def maneuvrability(position, path, width, height):
if position[0] < width and position[1] < height and position not in path and position[0] >= 0 and position[1] >= 0:
return True
else:
return False

def completedness(path,width,height):
if len(path) == (width*height):
return True
else:
return False

def possible_jumps(pos):
return_list = []
return_list.extend([
(pos[0]-1,pos[1]-2),
(pos[0]+1,pos[1]-2),
(pos[0]+2,pos[1]-1),
(pos[0]+2,pos[1]+1),
(pos[0]-1,pos[1]+2),
(pos[0]+1,pos[1]+2),
(pos[0]-2,pos[1]-1),
(pos[0]-2,pos[1]+1)])
return return_list

def knights_tour(width,height,path=[(0,0)]):
if completedness(path,width,height):
return path
else:
elem = path[len(path)-1]
succs = []
succs.extend(possible_jumps(elem))
for x in succs:
if maneuvrability(x,path,width,height):
return knights_tour(width,height,[y for y in path + [x]])

print(knights_tour(4,3))
print(knights_tour(5,5))

Answer 1

您的回溯不正确。在每一步中，您只检查下一步是否有效，然后返回该移动是否会导致骑士之旅。相反，您需要调整代码以检查所有有效的移动，然后查看是否有任何移动导致了完整的骑士之旅。