我知道有几个类似的线程，但即使在 SO 之外我也没有找到解决方案。这是我的问题：我为骑士之旅问题实现了 Warnsdorff 的算法http://en.wikipedia.org/wiki/Knight%27s_tour，但在某些情况下它没有给出解决方案。在我读到的某些地方，它可以通过一些更改更好地工作，但没有人指定哪些更改是那些。有人知道解决方案吗？我知道其他算法，但它们要复杂得多。
即使对于 8x8 棋盘，它有时也不能提供好的解决方案。我认为阅读我的代码没有意义，因为它是经典的 Warnsdorff 的：检查可能的移动，并在下一步中选择移动最少的一个。
W+的链接不再存在，使得接受的答案不可用。
Warnsdorff 算法的改进包括：
Arnd Roth 的命题：Roth 认为 Warnsdorff 启发式中的问题在于随机抢七规则。提议是通过选择距棋盘中心欧几里德距离最大的继任者来打破平局。
这里的问题是当多个后继者共享相同距离时会发生什么。
Arnd Roth 声称，这种改进首先在 428 行的板上失败，在所有少于 2000 行的板上失败率不到 1%。
Ira Pohl 的提议：为了打破关系，Pohl 决定再次应用 Warnsdorff 的规则。为了实现这一点，我们必须取所有未访问邻居的度数之和，以及并列的后继者的度数之和，并选择总和最小的平方。
这里的问题之一是，无论我们应用 Warnsdorff 规则多少次，如果我们从角落方格开始，我们将导致平局（在两个相邻方格之间）。此外，如果我们多次应用 Warnsdorff 的启发式算法，那么渐近地这等于穷举搜索。
Pohl 还建议，如果我们在第二次应用 Warnsdorff 后未能产生继任者，则通过使用固定的任意正方形排序来打破平局。他声称这成功地在 8*8 板上产生了解决方案。
通过使用这些增强功能之一，我们有更好的机会通过防止可能的锁定来系统地创建解决方案。
这是我发现的：
请注意，这仍然不是一个明确的答案，我也不是图论专家，所以这些只是观察。
我将把经典的 Warnsdorff 启发式称为“W”。来自http://mirran.web.surftown.se/knight/bWarnsd.htm的改进（缓存：http ://web.archive.org/web/20120213164632/http://mirran.web.surftown.se/knight /bWarnsd.htm ) 将被称为“W+”。https://github.com/douglassquirrel/warnsdorff/blob/master/5_Squirrel96.pdf?raw=true的改进将是“W2”。水平场的数量为“x”，垂直场的数量为“y”。
所以，这是我的观察。
简短版本：
W 很简单，但在很多情况下它无法提供解决方案。这首先引发了这个问题。W+ 也很简单，并且有很大的改进，尤其是在大型电路板上。W2 实现起来要复杂得多，与 W+ 相比，它似乎并没有给出更好的结果。所以我投票给W+。无论如何，这就是我将使用的变体。
长版：
W
优点： 与其他 Knights Tour 算法相比，简单。与W+相比，它并没有真正的优势。与 W2 相比，它更容易实现。
缺点： 有很多情况下有解决方案，但 W 无法提供它往往会弄乱更大的电路板 (50+)
W+
优点： 与其他 Knights Tour 算法相比，简单。与W相比：它可以在更多的情况下提供解决方案，并且几乎不比W复杂。与W2相比，它更容易实现，并且W+也适用于非方板。例如 10x20。
缺点： 与W相比，它没有缺点。与其他骑士游览算法相比，这个算法在某些情况下可能会卡住。W+ 最困难的是小板，如 5x5、6x6、7x7、9x9 等。正如 Wiki 中所述，当 x 和 y 都是偶数时，它会出现问题。另一方面，当 x 和 y 是偶数，但大于 9 时，W+ 似乎设法找到了解决方案。与W2相比，我没有遇到缺点。
W2
优点： 与W相比，它在更多的情况下提供了解决方案，特别是对于大板。与W+相比，我没有注意到优势。
缺点： 与 W 和 W+ 相比的实现。
结论：
我的观点是 W+ 实际上是最容易接受的。不要忘记它并不完美。我不得不说，我的实现不允许真正的大板。我测试了高达 90x90（8100 个节点）的 W+，它仍然提供了解决方案。虽然，由于时间有限，我没有进行广泛的测试。我希望这对以前遇到过这个问题的人有所帮助。因为这不是一个确定的答案，所以我暂时不会接受它，希望有人出现可以给出完整的答案。抱歉读了很久。
这是 Python 2 中的一个工作示例，它使用计时器来遍历电路板并说明解决方案。我找到了最接近板边缘的节点以用于决胜局，如果两者相同，我只返回第一个。这似乎是一个自然的选择，因为如果棋盘是空的，靠近边缘的单元格应该有更少的可能移动。似乎运作良好，但正如帕诺斯所说，Arnd Roth 的提议有 1% 的失败率。可以轻松修改此代码以使用Ira Pohl 的 Proposition。可以修改访问节点以针对都具有最小移动的节点再次运行 possible_unvisited_moves。在关系的情况下，使用第一个应该工作。
class GNode(object):
""" Used to represent a node in the graph """
def __init__(self, value, row=None, col=None):
self.row = row # allows node to know its loc. in array
self.col = col
self.value = value
def setup_graph(n):
""" Create x by x grid (graph inside an array). """
graph = []
for row in range(n):
graph.append([])
for col in range(n):
graph[row].append(GNode(None,row=row, col=col))
return graph
def possible_moves(graph_node, total):
""" Find out all possible moves for the current node position. """
moves = []
move_patterns = [[-1,-2], [-1, 2], [-2, 1], [-2, -1], [1, -2], [1, 2], [2, 1], [2, -1]]
for row, col in move_patterns:
move_row = graph_node.row + row; move_col = graph_node.col + col
if move_row >= 0 and move_col >= 0 and move_row < total and move_col < total:
moves.append([move_row, move_col])
return moves
def possible_unvisited_moves(graph_node, grid):
"""Get all possible moves and weed out the ones that are already visited.
visited means they have a value.
"""
moves = possible_moves(graph_node, len(grid))
unvisited = []
for move in moves:
if grid[move[0]][move[1]].value is None:
unvisited.append(move)
return unvisited
def closest_to_edge(pos1, pos2, total):
""" Find out which position is closest to the edge of board, and return it.
pos are 2 arrays [x,y], total is the board size (length)
"""
total -= 1
pos1_min = min(total - pos1[0], pos1[0], pos1[1], total-pos1[1])
pos2_min = min(total - pos2[0], pos2[0], pos2[1], total-pos2[1])
if pos2_min < pos1_min: return pos2
return pos1 # default
def visit_node(graph_node, graph):
""" Check possible unvisited moves from the pos & find next move to make """
graph_node.value = "{}{}".format(graph_node.row, graph_node.col) # visited
p_moves = possible_unvisited_moves(graph_node, graph)
next_move = None
min_no_moves = 9 # highest can be 8 for knights move pattern
for move in p_moves:
next_moves = possible_unvisited_moves(graph[move[0]][move[1]], graph)
if len(next_moves) < min_no_moves:
next_move = move
min_no_moves = len(next_moves)
elif len(next_moves) == min_no_moves:
min_move = closest_to_edge(next_move, move, len(graph))
if min_move != next_move:
next_move = min_move
min_no_moves = len(next_moves)
if next_move:
os.system(clear_screen)
print "This Move: [",graph_node.row, ",", graph_node.col, "]. Next Move: ", next_move, "Min Moves from next: ", min_no_moves
display_graph(graph)
import time
time.sleep(.5)
return visit_node(graph[next_move[0]][next_move[1]], graph)
else:
os.system(clear_screen)
display_graph(graph)
return "Done"
def display_graph(graph):
print ""
for row in graph:
row_vals = []
for cell in row:
row_vals.append(cell.value)
print row_vals
import os
clear_screen = 'cls' if os.name == 'nt' else 'clear'
graph = setup_graph(8)
print visit_node(graph[4][4], graph)
玩得开心。:)
我认为在应用 Warnsdorff 规则时最容易被忽视的是正在构建的路径有两端。将两级平局规则应用于路径的两端时，可以获得相当好的结果。而且，作为额外的奖励，产生的可重入旅游的数量大大增加。